常见算法笔试或面试题 - zhenjing的技术博客 - 博客园

Problem 1 : Is it a loop ? （判断链表是否有环？）

Assume that wehave a head pointer to a link-list. Also assumethat we know the list is single-linked. Can you come up an algorithm to checkwhether this link list includes a loop by using O(n) time and O(1) space wheren is the length of the list? Furthermore, can you do so with O(n) time and onlyone register?

方法：使用两个指针，从头开始，一个一次前进一个节点，一个前进2个节点，则最多2N，后两个指针可以重合；如果无环，则正常停止。

同样的，可以找到链表的中间节点。同上。

Problem 2：设计一个复杂度为n的算法找到链表倒数第m个元素。最后一个元素假定是倒数第0个。

提示：双指针查找

Problem 3：用最简单的方法判断一个LONG整形的数A是2^n（2的n次方）

提示：x&(x-1)

Problem 4：两个烧杯，一个放糖一个放盐，用勺子舀一勺糖到盐，搅拌均匀，然后舀一勺混合物会放糖的烧杯，问你两个烧杯哪个杂质多？

提示：相同。假设杂质不等，那么将杂质放回原杯中，则杯中物体重量必变化，不合理。

Problem 5：给你a、b两个文件，各存放50亿条url，每条url各占用64字节，内存限制是4G，让你找出a、b文件共同的url。

法1：使用hash表。使用a中元素创建hash表，hash控制在适当规模。在hash中查找b的元素，找不到的url先存在新文件中，下次查找。如果找到，则将相应的hash表项删除，当hash表项少于某个阈值时，将a中新元素重新hash。再次循环。

法2：对于hash表项增加一项记录属于的文件a，b。只要不存在的表项即放入hash表中，一致的项则删除。注意：可能存在很多重复项，引起插入，删除频繁。 

Problem 6：给你一个单词a，如果通过交换单词中字母的顺序可以得到另外的单词b，那么定义b是a的兄弟单词。现在给你一个字典，用户输入一个单词，让你根据字典找出这个单词有多少个兄弟单词。

提示：将每个的单词按照字母排序，则兄弟单词拥有一致的字母排序（作为单词签名）。使用单词签名来查找兄弟单词。

Problem 7：五桶球，一桶不正常，不知道球的重量和轻重关系，用天平称一次找出那桶不正常的球。

Problem 8：给两个烧杯，容积分别是m和n升（m!=n），还有用不完的水，用这两个烧杯能量出什么容积的水？

m, n, m+n, m-n以及线性叠加的组合

Problem 9：写出一个算法，对给定的n个数的序列，返回序列中的最大和最小的数。

Problem 10：你能设计出一个算法，只需要执行1.5n次比较就能找到序列中最大和最小的数吗？能否再少？

提示：先通过两两比较，区分大小放入“大”，“小”两个数组中。从而最大数在“大”数组中，最小数在“小”数组中。

Problem 11：给你一个由n-1个整数组成的未排序的序列，其元素都是1到n中的不同的整数。请写出一个寻找序列中缺失整数的线性-时间算法。

提示：累加求和

Problem 12：void strton(const char* src, const char*token) 假设src是一长串字符，token存有若干分隔符，只要src的字符是token中的任何一个，就进行分割，最终将src按照token分割成若干单词。找出一种O(n)算法？

提示：查表的方法，将所有的字符串存储在长度为128的数组中，并将作为分隔符的字符位置1，这样即可用常数时间判断字符是否为分隔符，通过n次扫描，将src分割成单词。

Problem 13：一个排好序的数组A，长度为n，现在将数组A从位置m(m

提示：同样采用二分查找。核心思想就是确定所查找数所在的范围。通过比较3个数（头，尾，中间）和所查找数之间的关系，可以确定下次查找的范围。

Problem 14：一个排好序的数组A，长度为n，现在将数组A从位置m(m

提示：(A’B’)’ =BA

Problem 15：给出Vector的一个更好实现。（STL的vector内存的倍增的，但是每次倍增需要拷贝已存元素，平均每个元素需要拷贝一次，效率不高）

提示：可使用2^n的固定长度作为每次分配的最小单位，并有序的记录每个块的首地址。这中结构同样可以实现线性查找，并且拷贝代价很低（仅有指针）

Problem 16：给出已排序数组A，B，长度分别为n，m，请找出一个时间复杂度为（lgn）的算法，找到排在第k位置的数。

提示：二分查找。

Problem 17：给出任意数组A，B，长度分别为n，m，请找出一个时间复杂度为（lgn）的算法，找到排在第k位置的数。

提示：通过最小堆记录k个数，不断更新，扫描一次完毕。

这个提示有问题，求最优算法！

Problem 18：假设数组A有n个元素，元素取值范围是1~n，判定数组是否存在重复元素？要求复杂度为O(n)。

法1：使用n的数组，记录元素，存在记为1，两次出现1，即重复。

法2：使用m的数组，分别记录大小：n/m, 2n/m …..的元素个数。桶方法

法3：累加求和。可用于求仅有一个元素重复的方法。

Problem 19：给定排好序的数组A，大小为n，现给定数X，判断A中是否存在两数之和等于X。给出一个O(n)的算法。

提示：从中间向两边查找。利用有序的条件

Problem 20：给定排好序的数组A，大小为n，请给出一个O(n)的算法，删除重复元素，且不能使用额外空间。

提示，既然有重复，必有冗余空间。将元素放入数组的前面，并记录下次可放位置，不断向后扫描即可。

Problem 21：给定两个排好序的数组A，B，大小分别为n，m。给出一个高效算法查找A中的哪些元素存在B数组中。

注意：一般在大数组中执行二分查找，将小数组的元素作为需查找的对象。

更优算法（轩辕刃提供）：可以使用两个指针遍历AB，比较当前大小就可以了...时间复杂度o(n+m)

Problem 22：问：有1000桶酒，其中1桶有毒。而一旦吃了，毒性会在1周后发作。现在我们用小老鼠做实验，要在1周内找出那桶毒酒，问最少需要多少老鼠。

答案：10只。将酒编号为1~1000 将老鼠分别编号为1 2 4 8 16 32 64 128 256 512 喂酒时 让酒的编号等于老鼠编号的加和如：17号酒喂给1号和16号老鼠  76号酒喂给4号、8号和64号老鼠 七天后将死掉的老鼠编号加起来 得到的编号就是有毒的那桶酒 因为2的10次方等于1024 所以10只老鼠最多可以测1024桶酒

证明如下：使用二进制表示：01, 10, 100, 1000, … , 1,000,000,000。对于任何一个小于1024的数，均可以采用前面的唯一一组二进制数来表示。故成立。

Problem 23：设计一组最少个数砝码，使得天平能够称量1~1000的重量。

如果砝码只能放单边，1，2 ，4 ，  512最好。（只能单加）

如果允许砝码双边放，1, 3, 9, 27….  最好。（可加可减）已知1,3，如何计算下一个数。现可称重量1,2,3,4。设下个数为x,可称重量为, x-4, x-3, x-2, x-1, x, x+1, x+2, x+3, x+4。为使砝码最好，所称重量应该不重复（浪费）。故x=9。同理，可得后面。

图形算法题

Problem 24：如何判断一个点是否在一个多边形内？

提示：对多边形进行分割，成为一个个三角形，判断点是否在三角形内。

一个非常有用的解析几何结论：如果P2(x1,y1),P2(x2,y2), P3(x3,y3)是平面上的3个点，那么三角形P1P2P3的面积等于下面绝对值的二分之一：

| x1  y1  1 |

| x2 y2  1 | = x1y2 + x3y1 + x2y3 –x3y2 – x2y1 – x1y3

| x3 y3  1 |

       当且仅当点P3位于直线P1P2(有向直线P1->P2)的右侧时，该表达式的符号为正。这个公式可以在固定的时间内，检查一个点位于两点确定直线的哪侧，以及点到直线的距离(面积=底*高/2)。

       这个结论：可以用来判断点是否在点是否在三角形内。法1：判断点和三角形三边所行程的3个三角形的面积之和是否等于原来三角形的面积。（用了三次上面的公式）。

法2：判断是否都在三条边的同一边，相同则满足，否则不在三角形内。

Problem 25：给出两个n为向量与0点形成角的角平分线。

提示：对两条边进行归一化，得到长度为1的两点，取两个的中点即可。

作者：zhenjing.chen
出处：http://www.cnblogs.com/zhenjing/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。

• Categories: 笔试面试, 综合
• Tags: 面试, 笔试, 算法, 经典

26 条回复

1. #1楼 feng wang      2010-10-18 10:40

   引用

   
   Problem 11：给你一个由n-1个整数组成的未排序的序列，其元素都是1到n中的不同的整数。请写出一个寻找序列中缺失整数的线性-时间算法。
   
   提示：累加求和
   
   
   将 1-n 连续 xor一下，然后继续 xor 这个序列中的所有元素，最后结果就是缺失的整数，累加可能溢出 　回复　引用　查看　  

2. #2楼 菩提树下的杨过      2010-10-18 10:40

   最近正在看数据结构+算法，先收藏着，有空慢慢解 　回复　引用　查看　  

3. #3楼 feng wang      2010-10-18 10:45

   引用

   
   Problem 18：假设数组A有n个元素，元素取值范围是1~n，判定数组是否存在重复元素？要求复杂度为O(n)。
   
   
   依旧是xor 1-n，最后结果为0则表示无重复
   ---------------------------------
   方法不对，见楼下JiangLian评论 　回复　引用　查看　  

4. #4楼 丐帮大侠      2010-10-18 10:53

   这个要支持,我也正在研究,向你学习. 　回复　引用　查看　  

5. #5楼 JiangLian      2010-10-18 13:16

   引用

   feng wang：
   

   引用

   
   Problem 18：假设数组A有n个元素，元素取值范围是1~n，判定数组是否存在重复元素？要求复杂度为O(n)。
   

   
   依旧是xor 1-n，最后结果为0则表示无重复
   
   求详解
   －－－－－－－－－－－
   
   
   －－－－－－－－－－－
   
   引用

   Problem 1 : Is it a loop ? （判断链表是否有环？）
   ...
   ...
   同样的，可以找到链表的中间节点。同上。
   
   快慢指针貌似不能找到中间节点 　回复　引用　查看　  

6. #6楼 hoodlum1980      2010-10-18 13:54

   现在是今年的校园招聘的高峰期，我觉得可以从各大高校BBS上收集添加一些新的面试题目了。 　回复　引用　查看　  

7. #7楼 feng wang      2010-10-18 14:01

   引用

   JiangLian：
   

   引用

   feng wang：
   

   引用

   
   Problem 18：假设数组A有n个元素，元素取值范围是1~n，判定数组是否存在重复元素？要求复杂度为O(n)。
   

   
   依旧是xor 1-n，最后结果为0则表示无重复

   
   求详解
   －－－－－－－－－－－
   
   
   －－－－－－－－－－－
   

   引用

   Problem 1 : Is it a loop ? （判断链表是否有环？）
   ...
   ...
   同样的，可以找到链表的中间节点。同上。

   
   快慢指针貌似不能找到中间节点
   
   1. 因为：
   1) X^X = 0
   2) X^Y = Y^X
   3) X^(Y^Z)=X^Y^Z
   4) X^0 = X
   2. 快指针到尾节点的时候，慢指针到中间节点
   
   
   
   　回复　引用　查看　  

8. #8楼 JiangLian      2010-10-18 14:19

   引用

   feng wang：
   

   引用

   JiangLian：
   

   引用

   feng wang：
   

   引用

   
   Problem 18：假设数组A有n个元素，元素取值范围是1~n，判定数组是否存在重复元素？要求复杂度为O(n)。
   

   
   依旧是xor 1-n，最后结果为0则表示无重复

   
   求详解
   －－－－－－－－－－－
   
   
   －－－－－－－－－－－
   

   引用

   Problem 1 : Is it a loop ? （判断链表是否有环？）
   ...
   ...
   同样的，可以找到链表的中间节点。同上。

   
   快慢指针貌似不能找到中间节点

   
   1. 因为：
   1) X^X = 0
   2) X^Y = Y^X
   3) X^(Y^Z)=X^Y^Z
   2. 快指针到尾节点的时候，慢指针到中间节点
   
   
   
   
   
   
   
   1.N=5,A[0..4]={1,1,1,1,1},XOR(1,2,3,4,5)=1
   
   2.噢，原来这个说的是不带环的链表。
   　回复　引用　查看　  

9. #9楼 feng wang      2010-10-18 14:21

   引用

   JiangLian：
   1.N=5,A[0..4]={1,1,1,1,1},XOR(1,2,3,4,5)=1
   
   
   结果不是0，表明有重复，有问题么？
   　回复　引用　查看　  

10. #10楼 JiangLian      2010-10-18 14:25

    引用

    feng wang：
    

    引用

    JiangLian：
    1.N=5,A[0..4]={1,1,1,1,1},XOR(1,2,3,4,5)=1
    

    
    结果不是0，表明有重复，有问题么？
    
    
    
    莫非你的算法的意思不是XOR(1..N,A[0..N-1])? 　回复　引用　查看　  

11. #11楼 feng wang      2010-10-18 14:30

    @JiangLian
    看不明白你要表达的意思，我说的是，对于
    A[0..4]={1,1,1,1,2}
    应该这样算：
    1^2^3^4^5^1^1^1^1^2
    前边5个是1-n，后边5个是A里边的元素
    　回复　引用　查看　  

12. #12楼 JiangLian      2010-10-18 14:32

    引用

    feng wang：
    @JiangLian
    看不明白你要表达的意思，我说的是，对于
    A[0..4]={1,1,1,1,2}
    应该这样算：
    1^2^3^4^5^1^1^1^1^2
    前边5个是1-n，后边5个是A里边的元素
    
    
    
    对啊，就是这意思，所以那个例子XOR 1-n等于1，然后再XOR A的所有元素，结果是0 　回复　引用　查看　  

13. #13楼 feng wang      2010-10-18 14:46

    引用

    JiangLian：
    

    引用

    feng wang：
    @JiangLian
    看不明白你要表达的意思，我说的是，对于
    A[0..4]={1,1,1,1,2}
    应该这样算：
    1^2^3^4^5^1^1^1^1^2
    前边5个是1-n，后边5个是A里边的元素
    

    
    
    对啊，就是这意思，所以那个例子XOR 1-n等于1，然后再XOR A的所有元素，结果是0
    
    是我弄错了，不好意思，我上边提出的那种方法不对。
    　回复　引用　查看　  

14. #14楼 chenkai      2010-10-18 18:40

    光罗列 出来 没有加以自己理解和思考 我觉得意义不带.
    这样的题 微软已经有了一个HR Tech库. 　回复　引用　查看　  

15. #15楼 广广      2010-10-18 22:35

    Problem 7 先加两桶球上去看是否平衡，平衡再加两桶球上去称。假如平衡就是那个没有称的桶了。是这样不？ 　回复　引用　查看　  

16. #16楼[楼主] zhenjing      2010-10-19 09:16

    @chenkai
    
    偶的思考不能代替您的思考，不是吗 　回复　引用　查看　  

17. #17楼[楼主] zhenjing      2010-10-19 09:17

    @广广
    
    提示是自己加的。这题没有，我没有正解，不好意思 　回复　引用　查看　  

18. #18楼 luojiesi      2010-10-21 01:43

    19题能不能详细说说？ 　回复　引用　查看　  

19. #19楼[楼主] zhenjing      2010-10-21 10:31

    @luojiesi
    
    假设数组从小到大排（从左到右）
    算法：取头尾两个，假定位置l、r，若和大于X，则r右移；反之l左移。如此反复。
    
    疑惑：是否会遗漏可能的组合？可能吗？
    证明：任意取两个位置，截取数组片段，证明之 　回复　引用　查看　  

20. #20楼 轩脉刃      2010-10-22 13:41

    Problem 19：给定排好序的数组A，大小为n，现给定数X，判断A中是否存在两数之和等于X。给出一个O(n)的算法。
    提示：从中间向两边查找。利用有序的条件
    
    从两边向中间找也行~~也是o(n) 　回复　引用　查看　  

21. #21楼 轩脉刃      2010-10-22 13:48

    Problem 17：给出任意数组A，B，长度分别为n，m，请找出一个时间复杂度为（lgn）的算法，找到排在第k位置的数。
    提示：通过最小堆记录k个数，不断更新，扫描一次完毕。
    
    用最小堆能使得时间复杂度为lgn??还是nlgn？？求详细说明 　回复　引用　查看　  

22. #22楼 轩脉刃      2010-10-22 13:52

    Problem 21：给定两个排好序的数组A，B，大小分别为n，m。给出一个高效算法查找A中的哪些元素存在B数组中。
    注意：一般在大数组中执行二分查找，将小数组的元素作为需查找的对象。
    
    .....没有使用排好序的AB这个条件....可以使用两个指针遍历AB，比较当前大小就可以了...时间复杂度o(n+m) 　回复　引用　查看　  

23. #23楼[楼主] zhenjing      2010-10-22 17:13

    @轩脉刃
    
    一样的，关键在于有序 　回复　引用　查看　  

24. #24楼[楼主] zhenjing      2010-10-22 17:16

    @轩脉刃
    
    谢谢。你是对的。文中给出的并非最优算法 　回复　引用　查看　  

25. #25楼[楼主] zhenjing      2010-10-22 17:26

    @轩脉刃
    
    得说抱歉。也看不懂这个说明
    现在只能给出(n+m)的算法 　回复　引用　查看　  

26. #26楼 MicroCoder      2010-11-09 09:05

    mark