文档介绍：精品文档
精品文档
1
精品文档
精品文档
Problem1 :Isitaloop? （判断链表是否有环？）
Assumethatwehaveaheadpointertoalink-
knowthelistissingle-
checkwhetherthislinklistincludesaloopbyusingO(n)timeandO(1)
spacewherenisthelengthofthelist?Furthermore,canyoudosowith
O(n)timeandonlyoneregister?
方法：使用两个指针，从头开始，一个一次前进一个节点，一个前进 2个节点，
则最多2N，后两个指针可以重合；如果无环，则正常停止。
同样的，可以找到链表的中间节点。同上。
Problem2 ：设计一个复杂度为 n的算法找到链表倒数第 m个元素。最后一个
元素假定是倒数第 0个。
提示：双指针查找
Problem3 ：用最简单的方法判断一个 LONG整形的数A是2^n（2的n次方）
提示：x&(x-1)
Problem4 ：两个烧杯，一个放糖一个放盐，用勺子舀一勺糖到盐，搅拌均匀，
然后舀一勺混合物会放糖的烧杯，问你两个烧杯哪个杂质多？
提示：相同。假设杂质不等，那么将杂质放回原杯中，则杯中物体重量必变化，
不合理。
.
精品文档
精品文档
2
精品文档
精品文档
Problem5 ：给你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表中，一致的项则删除。注意：可能存在很多重复项，引起插入，删除频
繁。
Problem6 ：给你一个单词a，如果通过交换单词中字母的顺序可以得到另外的
单词b，那么定义b是a的兄弟单词。现在给你一个字典，用户输入一个单词，
让你根据字典找出这个单词有多少个兄弟单词。
提示：将每个的单词按照字母排序， 则兄弟单词拥有一致的字母排序 （作为单词
签名）。使用单词签名来查找兄弟单词。
Problem7 ：五桶球，一桶不正常，不知道球的重量和轻重关系，用天平称一
次找出那桶不正常的球。
精品文档
精品文档
3
精品文档
精品文档
精品文档
13
精品文档
.
精品文档
精品文档
5
精品文档
精品文档
Problem8 ：给两个烧杯，容积分别是 m和n升（m!=n），还有用不完的水，
用这两个烧杯能量出什么容积的水？
m,n,m+n,m-n 以及线性叠加的组合
Problem9 ：写出一个算法，对给定的 n个数的序列，返回序列中的最大和最
小的数。
Problem10 ：你能设计出一个算法，只需要执行
最大和最小的数吗？能否再少？
提示：先通过两两比较，区分大小放入“大”，“小”两个数组中。从而最大数
在“大”数组中，最小数在“小”数组中。
Problem11 ：给你一个由n-1个整数组成的未排序的序列，其元素都是 1到n
中的不同的整数。请写出一个寻找序列中缺失整数的线性 -时间算法。
提示：累加求和
Problem12 ：voidstrton(constchar*src,constchar*token) 假设src是一
长串字符，token 存有若干分隔符，只要src的字符是token 中的任何一个，就
进行分割，最终将 src按照token 分割成若干单词。找出一种 O(n)算法？
精品文档
精品文档
6
精品文档
精品文档
精品文档
13
精品文档
.
精品文档
精品文档
8
精品文档
精品文档
提示：查表的方法，将所有的字符串存储在长度为 128的数组中，并将作为分
隔符的字符位置 1，这样