文档介绍：Problem1 :Isitaloop? (判断链表是否有环?)Assumethatwehaveaheadpointertoalink--(n)timeandO(1)spacewherenisthelengthofthelist?Furthermore,canyoudosowithO(n)timeandonlyoneregister?方法:使用两个指针,从头开始,一个一次前进一个节点,一个前进 2个节点,则最多2N,后两个指针可以重合;如果无环,则正常停止。同样的,可以找到链表的中间节点。同上。Problem2 :设计一个复杂度为 n的算法找到链表倒数第 m个元素。最后一个元素假定是倒数第 0个。提示:双指针查找Problem3 :用最简单的方法判断一个 LONG整形的数A是2^n(2的n次方)提示:x&(x-1)Problem4 :两个烧杯,一个放糖一个放盐,用勺子舀一勺糖到盐,搅拌均匀,然后舀一勺混合物会放糖的烧杯,问你两个烧杯哪个杂质多?提示:相同。假设杂质不等,那么将杂质放回原杯中,则杯中物体重量必变化,不合理。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 :五桶球,一桶不正常,不知道球的重量和轻重关系,用天平称一次找出那桶不正常的球。Problem8 :给两个烧杯,容积分别是m和n升(m!=n),还有用不完的水,用这两个烧杯能量出什么容积的水?m,n,m+n,m-n 以及线性叠加的组合Problem9 :写出一个算法,对给定的 n个数的序列,返回序列中的最大和最小的数。Problem10 :你能设计出一个算法,只需要执行 ?能否再少?提示:先通过两两比较,区分大小放入“大”,“小”两个数组中。从而最大数在“大”数组中,最小数在“小”数组中。Problem11 :给你一个由n-1个整数组成的未排序的序列,其元素都是1到n中的不同的整数。请写出一个寻找序列中缺失整数的线性 -时间算法。提示:累加求和Problem12 :voidstrton(constchar*src,constchar