待解决的面试题

以你之姓@ 2022-05-27 04:50 156阅读 0赞

hulu：

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