Hulu棉镜系列（一）

1、给定一个N位数，例如12345，从里面去掉k个数字，得到一个N-k位的数，例如去掉2，4，得到135，去掉1，5，得到234。设计算法，求出所有得到的N-k位数里面最小的那一个?

解决方案一：
（1）第一步要确定剩余N-K位的数的最高位：
从个位开始算起，从第N-K位开始向高位比较，求出最小数字，作为高位。
例如，3 1 1 2 3 3 1，K=3时，从7-3=4开始（为2），向上比较发现，1更小，所以高位设置为1，记录此时位置P1（等于也可以替换，从而取最高位的1）.
（2）再确定次高位：
从N-K-1开始向上到P1-1，此时最小数字为1.
依此类推，最后就可以得到最小数1121.

解决方案二：
例如，1 2 3 4 5 6 7， K=3
剩余N-K位，则定义一个N-K的数组R，用来存放所选数字。
（1）初始化R，存最低N-K位 4567
（2）向上遇到1，则3<R最高位4：
此时需要对R进行调整，调整规则如下，如果高位数字小于相邻低位数字，则用高位数字替换之。
最高位再用当前数字替换。
于是，得到3456.
不断执行以上过程，就得到了最终结果1234.
对方案一中举例进行验证，正确。

解决方案三：

求每位数字元素，依据元素建立最小堆进行处理，若头为0，设为次高位，以此类推。。。时间复杂度O(nlog(n))。。

2、“找明星”，N个人中，只有一个明星：明星不认识其他所有的人，而其他人都认识明星，这些人中也可能相互认识。你每次只可以问一个人是否认识另一个人这样的问题，问最少问多少次可以找出明星。

分析：该问题在创新工场(Innovation Works）和葫芦（Hulu）的面试中都被问到：
N个人中只有一个明星：明星不认识其他所有的人，而其他人都认识明星，不是明星的人可能认识也可能不认识。你每次只可以问一个人是否认识另一个人这样的问题，问最少问多少次可以找出明星。

方法：从N个人中找两个人a b，问a是否认识b，若a认识b则a肯定不是明星排除a，若a不认识b则分两种情况讨论，为明星为1，不为明星为0。
1: 0 0
2: 0 1（不可能，a肯定认识b）
3: 1 0
4: 1 1(不可能，只有一个明星)
只有1，3两种情况，这两种情况中b肯定不是明星。因此问一个问题我们便可以排除掉一个人，最多经过n-1次便可以找到明星。

扩展：
如果有两个明星呢？所有的人都认识明星，明星之间互不认识，其它的人可能认识也可能不认识。最少问多少次可以找出明星？
一种显然的方法是：先通过第一种方法找出一个明星，然后在剩下的n-1个人种找出第2个明星。这样总共需要问(n-1 + n - 2)=2n-3次问题。

这个问题等价于找未知序列数中的最小数
我们将reg这个函数等价为以下过程：
如果i认识j，记作i大于等于j,同样j不一定大于等于i,满足要求
i不认识j记作i<j
对明星k,他不认识所有人，则k是其中最小的数，且满足其余的人都认识他，也就是其余的人都大于等于k.
这样问题就被转换了。

就拿N=5来说
首先有数组S[5]={A,B,C,D,E}这5个变量，里边存放着随机数，求是否存在唯一最小数，如果存在位置在S中的哪里。（楼主这里是这个意思，按我的理解题中这个最小数一定是存在且唯一的）

int finds(S,N)
{int flag=0;//用于判定是否有明星，即当前最小数另外出现几次int temp=0;//存放最小数在S中的位置for(i=1;i<N;i++)｛if(!reg(S[i],S[temp])//如果temp标号的数小于i标号的数｛temp=i;flag=0;//更换怀疑对象（最小数）时，标记清零｝elseif(reg(S[temp]，S[i])//如果temp里存放的确实是唯一最小数是不会跑进这里来的{flag++;
`     }｝if(flag>0) return -1;//表示没有明星,例如所有的数都相等return temp;//返回明星在S中的位置
}

遍历 1~n 这n个人；
首先取出 1号 和 2号， 如果 1 认识 2， 那么把 1 去掉；--如果1不认识2，就可以把2去掉了。
如果 2 认识 1， 那么把 2 去掉；
如果 1 和 2 都互相不认识，把他们都去掉； 
如果有剩下，在拿剩下的和3号进行比较；
如果没有剩下的，则拿出3号和4号进行比较；

如此循环；
最后若剩下最后1个人，再遍历一遍看是否剩下的n-1个人都认识它

时间复杂度分析：
每对之间的比较最多比较2次， 每对之间的比较至少淘汰1个人，要淘汰n-1个人最多比较 2*（n-1）次；
所以时间复杂度是 O（n）的。。

3、两个有序链表的合并。看过这个题，考虑下边界问题，可以用O(n)时间,O(1)空间解决。写完后，说我代码有个小bug，然后讨论后改之。问这个算法在哪种条件下不work，想了许久，突然灵光一现，想出可能链表有环或者两个链表有可能有公共节点。他很开心，说很久没有人能同时想出两个case了。

node merge_sorted_list(const node head1,const node head2)
{if((NULL == head1) && (NULL == head1)){return NULL;}else if(NULL == head1){return head2;}else if(NULL == head2){return head1;}else{    node head = NULL,p1 = NULL,p2 = NULL;if(head1->value >= head2->value){head = head1;p1 = head1->next;p2 = head2;}else{        head = head2;p2 = head2->next;p1 = head1;}node p = head;while((NULL != p1) && (NULL != p2)){if(p1->value >= p2->value){p->next = p1;p = p1;p1 = p1->next;}else{p->next = p2;p = p2;p2 = p2->next;}}p->next = p1 ? p1 : p2;//if(NULL != p1->next)//    p->next = p1;//else//    p->next = p2;return head;        }
}

递归实现：

Node * MergeRecursive(Node *head1 , Node *head2)
{if ( head1 == NULL )return head2 ;if ( head2 == NULL)return head1 ;Node *head = NULL ;if ( head1->value > head2->value ){head = head1 ;head->next = MergeRecursive(head1->next,head2);}else{head = head2 ;head->next = MergeRecursive(head1,head2->next);}return head ;
}

//不带头节点的链表
#include <stdio.h>
#include <malloc.h>struct Node
{int value;struct Node *next;
};typedef struct Node * node;node CreateList(int iStart,int num)
{node head = NULL,p = NULL,q = NULL;for(int i = num;i > 0 ;i --){p = (node)malloc(sizeof(struct Node));p->value = iStart + i;if(head == NULL){head = p;}else{q->next = p;}q = p;        }p->next = NULL;return head;
}node merge_sorted_list(node head1,node head2)
{if((NULL == head1) && (NULL == head2)){return NULL;}else if(NULL == head1){return head2;}else if(NULL == head2){return head1;}else{node p = NULL,p1 = NULL,p2 = NULL;if(head1->value >= head2->value){p = head1;p1 = head1->next;p2 = head2;}else{        p = head2;p2 = head2->next;p1 = head1;}while((NULL != p1) && (NULL != p2)){if(p1->value >= p2->value){          p->next = p1;p = p1;p1 = p1->next;}else{          p->next = p2;p = p2;p2 = p2->next;}}    p->next = p1 ? p1 : p2;return head1->value >= head2->value ? head1 : head2;}
}void display(node head)
{node p = head;while(NULL != p){printf("%3d",p->value);p = p->next;}printf("\n");
}int main()
{node head1 = NULL ,head2 = NULL,head = NULL;head1 = CreateList(5,6);head2 = CreateList(5,6);display(head1);display(head2);head = merge_sorted_list(head1,head2);display(head);return 0;}

2、字符串A和字符串B。是否B包含了A所有的字符串，要考虑字符的个数问题，比如A:aabb , B: abccc,就不满足条件了。这个题目跟google当年的笔试题很像，开一个256的int[]数组做hashtable，很容易解决了。由于之前没有考虑上述的情况，他指出来了，稍微改下，就过了

3、一个n*n迷宫，方块里可能是墙，可能是路，问怎么走出出口，求最短路径。先说思路，然后写伪代码。很简单的宽度优先，每个方格里记录走的步数和来自于哪个方块。很快就解决了。

分析：宽度有限搜索问题，采用队列结构。。

1）N个数，选出任意两个数求和，问所有这些可能性的和是多少。我说最简单的方法是模拟，O(N^2)，然后问有没有更简单的，想了想，计算了下所有数出现的个数是 （N-1）/2，所以很简单，就是 sum*（N-1）/2，时间复杂度是O（N）

2）问试卷最后一个题。之前听同学说过，我自己想过。A B两个有序数组，A中选一个，B中选一个，要求和为某个指定值m，问怎么选。感觉是《编程之美》上一维数组中求两个数和的变形，所以只要变换一下：A中的数从头往尾走，B中数从尾往前走就好；但是这么会遗漏，如果没找到，用相同的方式，A中的数从尾往头走，B中的数从头往尾走，看能否找到

3）问知道怎么确定有环链表。说知道。然后问，怎么确定环的起点节点。然后说没见过。他说，浙大的很奇怪，第一个问题都会，而第二个问题都不会。然后我开始想，最简单的用hash表保存已遍历的节点。然后他说需要常数空间。想了很久大概15分钟不会，让他提示下。说如果两个链表有公共节点，问怎么去找这个公共节点，想了几分钟，想出来了。只要都遍历一下得到长度的信息，利用这个信息再遍历一次，就可以找到公共节点。然后想到第有环的只是一个变种，只要把环断开。就成了第一个问题。然后叫我写代码，很顺利的写完。

4）已知两个矩形的四个节点信息，然后给一个API——可以得到某个点在是否在某矩形内，问怎么判断矩形相交。答曰，矩形相交不需要这么复杂，只要判断线段相交就行。可能他之前没想到我会这么回答，仔细解释了下，他说可行。然后问有没有特殊情况，我说有，一个矩形在另一个矩形内，可能线段不相交，矩形也相交了。然后答曰，这个只要判断小矩阵的几点是否在大矩阵内就可以了

5）问一个n*n的方块内，有一条环形路径。路径上的点都是1，其他点都是0.。给路径中的任意一个点，问这个路径所包含的面积。想了一分钟，觉得粉两步走：1）深度优先找路径 2）宽度优先算面积 然后解释了下，说可行