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(" "); } 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）宽度优先算面积 然后解释了下，说可行
更多详见：http://tianwei.sinaapp.com/2012/09/%E9%9D%A2%E8%AF%95%E9%A2%98%E6%94%B6%E9%9B%86/