25道常見算法面試題

1、Problem 1: Is it a loop ?(判斷鏈表是否有環(huán)？)Assumethat wehave a head pointer to a link-list. Also assumethat we know the list is sin gle-l in ked. Can you come up an algorithm to checkwhether this link list includes a loop by using O(n) time and 0(1) space wheren is the length of the list? Furthermore, can

2、you do so with O(n) time and onlyone register?方法：使用兩個指針，從頭開始，一個一次前進一個節(jié)點，一個前進2個節(jié)點，則最多2N,后兩個指針可以重合；如果無環(huán)，則正常停止。同樣的，可以找到鏈表的中間節(jié)點。同上。Problem 2 :設(shè)計一個復(fù)雜度為n的算法找到鏈表倒數(shù)第m個元素。最后一個元 素假定是倒數(shù)第0個。提示：雙指針查找Problem 3 :用最簡單的方法判斷一個LON(整形的數(shù)A是25 (2的n次方) 提示：x&(x-1)Problem 4 :兩個燒杯，一個放糖一個放鹽，用勺子舀一勺糖到鹽，攪拌均勻, 然后舀一勺混合物會放糖的燒杯，問你兩個燒

3、杯哪個雜質(zhì)多？提示：相同。假設(shè)雜質(zhì)不等，那么將雜質(zhì)放回原杯中，則杯中物體重量必變化, 不合理。Problem 5：給你a、b兩個文件，各存放50億條url，每條url各占用64字節(jié)， 內(nèi)存限制是4G讓你找出a、b文件共同的url。法1:使用hash表。使用a中元素創(chuàng)建hash表，hash控制在適當規(guī)模。在hash 中查找b的元素，找不到的url先存在新文件中，下次查找。如果找到，則將相 應(yīng)的hash表項刪除，當hash表項少于某個閾值時，將a中新元素重新hash。 再次循環(huán)。法2：對于hash表項增加一項記錄屬于的文件 a，b。只要不存在的表項即放入 hash表中，一致的項則刪除。注意：可能存

4、在很多重復(fù)項，引起插入，刪除頻 繁。Problem 6 :給你一個單詞a，如果通過交換單詞中字母的順序可以得到另外的 單詞b,那么定義b是a的兄弟單詞?，F(xiàn)在給你一個字典，用戶輸入一個單詞， 讓你根據(jù)字典找出這個單詞有多少個兄弟單詞。提示：將每個的單詞按照字母排序，則兄弟單詞擁有一致的字母排序(作為單詞 簽名)。使用單詞簽名來查找兄弟單詞。Problem 7 :五桶球，一桶不正常，不知道球的重量和輕重關(guān)系，用天平稱一次 找出那桶不正常的球。Problem 8 :給兩個燒杯，容積分別是 m和n升（m!=n），還有用不完的水，用 這兩個燒杯能量出什么容積的水？m, n, m+n, m-n以及線性疊加

5、的組合Problem 9 :寫出一個算法，對給定的n個數(shù)的序列，返回序列中的最大和最小 的數(shù)。Problem 10 :你能設(shè)計出一個算法，只需要執(zhí)行 1.5n次比較就能找到序列中最 大和最小的數(shù)嗎？能否再少？提示：先通過兩兩比較，區(qū)分大小放入“大”，“小”兩個數(shù)組中。從而最大數(shù) 在“大”數(shù)組中，最小數(shù)在“小”數(shù)組中。Problem 11 :給你一個由n-1個整數(shù)組成的未排序的序列，其元素都是1到n中的不同的整數(shù)。請寫出一個尋找序列中缺失整數(shù)的線性-時間算法。提示：累加求和Problem 12 : void strton（const char* src, const char*token）假設(shè)

6、src 是一長串字符，token存有若干分隔符，只要src的字符是token中的任何一個， 就進行分割，最終將src按照token分割成若干單詞。找出一種 0（n）算法？ 提示：查表的方法，將所有的字符串存儲在長度為128的數(shù)組中，并將作為分隔 符的字符位置1,這樣即可用常數(shù)時間判斷字符是否為分隔符，通過n次掃描，將src分割成單詞。Problem 13 : 一個排好序的數(shù)組 A，長度為n，現(xiàn)在將數(shù)組A從位置m（mn m 未知）分開，并將兩部分互換位置，假設(shè)新數(shù)組記為B,找到時間復(fù)雜度為O（lgn） 的算法查找給定的數(shù)x是否存在數(shù)組B中？提示：同樣采用二分查找。核心思想就是確定所查找數(shù)所在的范圍。通過比較3個數(shù)（頭，尾，中間）和所查找數(shù)之間的關(guān)系，可以確定下次查找的范圍。Problem 14 : 一個排好序的數(shù)組 A，長度為n，現(xiàn)在將數(shù)組A從位置m（mP2）的右側(cè)時，該表達 式的符號為正。這個公式可以在固定的時間內(nèi)，檢查一個點位于兩點確定直線的 哪側(cè)，以及點到直線的距離（面積=底*高/2）。這個結(jié)論：可以用來判斷點是否在點是否在三角形內(nèi)。法1:判斷點和三角形三邊所行程的3個三角形的面積之和是否等于原來三角形的面積。（