常見算法筆試或面試題

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?方法：使用兩個(gè)指針，從頭開始，一個(gè)一次前進(jìn)一個(gè)節(jié)點(diǎn)，一個(gè)前進(jìn)2個(gè)節(jié)點(diǎn)，則最多2N，后兩個(gè)指針可以重合；如果無(wú)環(huán)，則正常停止。同樣的，可以找到鏈表的中間節(jié)點(diǎn)。同上。Problem 2：設(shè)計(jì)一個(gè)復(fù)雜度為n的算法找到鏈表倒數(shù)第m個(gè)元素。最后一個(gè)元素假定是倒數(shù)第0個(gè)。提示：雙指針查找Problem 3：用最簡(jiǎn)單的方法判斷一個(gè)LONG整形的數(shù)A是2n（2的n次方）提示：x&(x-1)Problem 4：兩個(gè)燒杯，一個(gè)放糖一個(gè)放鹽，用勺子舀一勺糖到鹽，攪拌均勻，然后舀一勺混合物會(huì)放糖的燒杯，問你兩個(gè)燒杯哪個(gè)雜質(zhì)多？

3、提示：相同。假設(shè)雜質(zhì)不等，那么將雜質(zhì)放回原杯中，則杯中物體重量必變化，不合理。Problem 5：給你a、b兩個(gè)文件，各存放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表項(xiàng)刪除，當(dāng)hash表項(xiàng)少于某個(gè)閾值時(shí)，將a中新元素重新hash。再次循環(huán)。法2：對(duì)于hash表項(xiàng)增加一項(xiàng)記錄屬于的文件a，b。只要不存在的表項(xiàng)即放入hash表中，一致的項(xiàng)則刪除。注意：可能存在很多重復(fù)項(xiàng)，引起插入，刪

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

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

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