常見算法筆試或面試題

1、.Problem 1: Is it a loop ? （判斷鏈表是否有環(huán)？）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

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：用最簡單的方法判斷一個LONG整形的數(shù)A是2n（2的n次方）提示：x&(x-1)Problem 4：兩個燒杯，一個放糖一個放鹽，用勺子舀一勺糖到鹽，攪拌均勻，然后舀一勺混合物會放糖的燒杯，問你兩個燒杯哪個雜質(zhì)多？

3、提示：相同。假設(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控制在適當(dāng)規(guī)模。在hash中查找b的元素，找不到的url先存在新文件中，下次查找。如果找到，則將相應(yīng)的hash表項刪除，當(dāng)hash表項少于某個閾值時，將a中新元素重新hash。再次循環(huán)。法2：對于hash表項增加一項記錄屬于的文件a，b。只要不存在的表項即放入hash表中，一致的項則刪除。注意：可能存在很多重復(fù)項，引起插入，刪

4、除頻繁。 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以及線性疊加的組合Problem 9：寫出一個算法，對給

5、定的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è)src是一長串字符，token存有若干分隔符，只要src的字符

6、是token中的任何一個，就進行分割，最終將src按照token分割成若干單詞。找出一種O(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個三角形的面積之和是否等于原來三角形的面積。（用了三次