常見算法筆試或面試題

Problem 1 : Is it a loop ? （判斷連結清單是否有環？）

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 you do so with O(n) time and onlyone register?

方法：使用兩個指針，從頭開始，一個一次前進一個節點，一個前進2個節點，則最多2N，後兩個指針可以重合；如果無環，則正常停止。

同樣的，可以找到連結清單的中間節點。同上。

Problem 2：設計一個複雜度為n的算法找到連結清單倒數第m個元素。最後一個元素假定是倒數第0個。

提示：雙指針查找

Problem 3：用最簡單的方法判斷一個LONG整形的數A是2^n（2的n次方）

提示：x&(x-1)，

(下面分析出自：WilsonPeng3，并非來自文章原文。

如果A是2^n，則A的二進制肯定隻有一個1，且後面全是零。則A-1的二進制則全是1組成。那麼A&(A-1)肯定等于零。

如果A不是2^n，則A的二進制中，至少有兩個1，那麼A減去1後，借位時頂多借到第一個1的位置（從右往左數），也就是說再往左走，肯定存在一個位置，使得A的二進制在這個位置上是1，同時A-1的二進制在這個位置上也是1，那麼A&(A-1)就肯定不等于零。

綜上：

A=2^n  能推出 A&(A-1)=零。  根據逆否命題知：A&(A-1)!=零  能推出 A!=2^n;

A!=2^n 能推出 A&(A-1)!=零。 同上知：A&(A-1)=零   能退出  A=2^n;

） 

Problem 4：兩個燒杯，一個放糖一個放鹽，用勺子舀一勺糖到鹽，攪拌均勻，然後舀一勺混合物會放糖的燒杯，問你兩個燒杯哪個雜質多？

提示：相同。假設雜質不等，那麼将雜質放回原杯中，則杯中物體重量必變化，不合理。

Problem 5：給你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表中，一緻的項則删除。注意：可能存在很多重複項，引起插入，删除頻繁。 

可以将兩個打檔案，hash成1024個小檔案。一般情況下，初步計算，可以知道每個小檔案不會超過400M。不會超出記憶體。這樣可分别得到a-1.....a-1024和b-1.....b-1024個小檔案。如果a、b中存在相同的url，那麼hash後，必定分别存在a-x和b-x檔案中，是以剩下的事就是可以分别對比這(a-1,b-1).....(a-1024,b-1024)

1024組檔案，如果有，則存在相同url,如果沒有，就不存在相同url。可根據實際情況，将大檔案hash成更少的檔案。這樣可以提高效率

）

Problem 6：給你一個單詞a，如果通過交換單詞中字母的順序可以得到另外的單詞b，那麼定義b是a的兄弟單詞。現在給你一個字典，使用者輸入一個單詞，讓你根據字典找出這個單詞有多少個兄弟單詞。

提示：将每個的單詞按照字母排序，則兄弟單詞擁有一緻的字母排序（作為單詞簽名）。使用單詞簽名來查找兄弟單詞。

Problem 7：五桶球，一桶不正常，不知道球的重量和輕重關系，用天平稱一次找出那桶不正常的球。

（以下方法摘抄自另一出處。

5個桶依次編号1，2，3，4，5

方法一：

依次從編号好的前4個桶拿出5，7，11，13個球

      5+13=7+11 放天平左右

     if(天平平衡)

         第五個壞的

     if(不平衡)

         用遊标+砝碼把天平弄平

         看遊标+砝碼的總和（以最小刻度為标準）是5，7，11，13誰的倍數，哪個桶的球就是壞的

確定實驗的正确性 可以找4個更大且滿足條件的質數

原文連結：http://zylishiyu.blog.163.com/blog/static/130146674201091865144712/

方法二：

首先假定隻要不把球從天平拿下來就還算一次，另外每個桶内的球是一樣的：

從1 号和2 号桶各拿一個，放上天平（1 号左，2 号右），如果平衡，說明這兩桶球都是正常的，可以做為砝碼。如果不平衡，那麼1 号和2 号桶必有一個不正常，而其他3 ，4 ，5 桶是正常的，可以作為砝碼。

首先考慮1 号2 号桶不平衡的情況，這時從1 号和3 号桶再各拿一個球，放上天平（1 号右，3 号左），如果這時平衡了，說明1 号桶是不正常的，如果還是不平衡，那麼2 号桶是不正常的。

如果第一步1 号2 号桶是平衡的，那麼也好辦，把3 ，4 号桶各拿一個放上天平（3 号左，4 号右），這時如果還是平衡的，那麼5 号桶必然是不正常的。如果不平衡，說明不正常的就在3 ，4 号桶之中。我們再用2 ）的方法找出來即可。

原文連結：http://blog.csdn.net/knightliao/article/details/5831576

Problem 8：給兩個燒杯，容積分别是m和n升（m!=n），還有用不完的水，用這兩個燒杯能量出什麼容積的水？

m, n, m+n, m-n以及線性疊加的組合

Problem 9：寫出一個算法，對給定的n個數的序列，傳回序列中的最大和最小的數。

Problem 10：你能設計出一個算法，隻需要執行1.5n次比較就能找到序列中最大和最小的數嗎？能否再少？

提示：先通過兩兩比較，區分大小放入“大”，“小”兩個數組中。進而最大數在“大”數組中，最小數在“小”數組中。

Problem 11：給你一個由n-1個整數組成的未排序的序列，其元素都是1到n中的不同的整數。請寫出一個尋找序列中缺失整數的線性-時間算法。

提示：累加求和

Problem 12：void strton(const char* src, const char*token) 假設src是一長串字元，token存有若幹分隔符，隻要src的字元是token中的任何一個，就進行分割，最終将src按照token分割成若幹單詞。找出一種O(n)算法？

提示：查表的方法，将所有的字元串存儲在長度為128的數組中，并将作為分隔符的字元位置1，這樣即可用常數時間判斷字元是否為分隔符，通過n次掃描，将src分割成單詞。

Problem 13：一個排好序的數組A，長度為n，現在将數組A從位置m(m<n，m未知)分開，并将兩部分互換位置，假設新數組記為B，找到時間複雜度為O(lgn)的算法查找給定的數x是否存在數組B中？

提示：同樣采用二分查找。核心思想就是确定所查找數所在的範圍。通過比較3個數（頭，尾，中間）和所查找數之間的關系，可以确定下次查找的範圍。

Problem 14：一個排好序的數組A，長度為n，現在将數組A從位置m(m<n，m已知)分開，并将兩部分互換位置，設計一個O(n)的算法實作這樣的倒置，隻允許使用一個額外空間。（循環移位的效率不高）

提示：(A’B’)’ =BA

Problem 15：給出Vector的一個更好實作。（STL的vector記憶體的倍增的，但是每次倍增需要拷貝已存元素，平均每個元素需要拷貝一次，效率不高）

提示：可使用2^n的固定長度作為每次配置設定的最小機關，并有序的記錄每個塊的首位址。這中結構同樣可以實作線性查找，并且拷貝代價很低（僅有指針）

Problem 16：給出已排序數組A，B，長度分别為n，m，請找出一個時間複雜度為（lgn）的算法，找到排在第k位置的數。

提示：二分查找。

Problem 17：給出任意數組A，B，長度分别為n，m，請找出一個時間複雜度為（lgn）的算法，找到排在第k位置的數。

提示：通過最小堆記錄k個數，不斷更新，掃描一次完畢。

這個提示有問題，求最優算法！

Problem 18：假設數組A有n個元素，元素取值範圍是1~n，判定數組是否存在重複元素？要求複雜度為O(n)。

法1：使用n的數組，記錄元素，存在記為1，兩次出現1，即重複。

法2：使用m的數組，分别記錄大小：n/m, 2n/m …..的元素個數。桶方法

法3：累加求和。可用于求僅有一個元素重複的方法。

Problem 19：給定排好序的數組A，大小為n，現給定數X，判斷A中是否存在兩數之和等于X。給出一個O(n)的算法。

提示：從中間向兩邊查找。利用有序的條件

Problem 20：給定排好序的數組A，大小為n，請給出一個O(n)的算法，删除重複元素，且不能使用額外空間。

提示，既然有重複，必有備援空間。将元素放入數組的前面，并記錄下次可放位置，不斷向後掃描即可。

Problem 21：給定兩個排好序的數組A，B，大小分别為n，m。給出一個高效算法查找A中的哪些元素存在B數組中。

注意：一般在大數組中執行二分查找，将小數組的元素作為需查找的對象。

更優算法（軒轅刃提供）：可以使用兩個指針周遊AB，比較目前大小就可以了...時間複雜度o(n+m)

Problem 22：問：有1000桶酒，其中1桶有毒。而一旦吃了，毒性會在1周後發作。現在我們用小老鼠做實驗，要在1周内找出那桶毒酒，問最少需要多少老鼠。

答案：10隻。将酒編号為1~1000 将老鼠分别編号為1 2 4 8 16 32 64 128 256 512 喂酒時 讓酒的編号等于老鼠編号的加和如：17号酒喂給1号和16号老鼠  76号酒喂給4号、8号和64号老鼠 七天後将死掉的老鼠編号加起來 得到的編号就是有毒的那桶酒 因為2的10次方等于1024 是以10隻老鼠最多可以測1024桶酒

證明如下：使用二進制表示：01, 10, 100, 1000, … , 1,000,000,000。對于任何一個小于1024的數，均可以采用前面的唯一一組二進制數來表示。故成立。

Problem 23：設計一組最少個數砝碼，使得天平能夠稱量1~1000的重量。

如果砝碼隻能放單邊，1，2 ，4 ，  512最好。（隻能單加）

如果允許砝碼雙邊放，1, 3, 9, 27….  最好。（可加可減）已知1,3，如何計算下一個數。現可稱重量1,2,3,4。設下個數為x,可稱重量為, x-4, x-3, x-2, x-1, x, x+1, x+2, x+3, x+4。為使砝碼最好，所稱重量應該不重複（浪費）。故x=9。同理，可得後面。

圖形算法題

Problem 24：如何判斷一個點是否在一個多邊形内？

提示：對多邊形進行分割，成為一個個三角形，判斷點是否在三角形内。

一個非常有用的解析幾何結論：如果P2(x1,y1),P2(x2,y2), P3(x3,y3)是平面上的3個點，那麼三角形P1P2P3的面積等于下面絕對值的二分之一：

| x1  y1  1 |

| x2 y2  1 | = x1y2 + x3y1 + x2y3 –x3y2 – x2y1 – x1y3

| x3 y3  1 |

       當且僅當點P3位于直線P1P2(有向直線P1->P2)的右側時，該表達式的符号為正。這個公式可以在固定的時間内，檢查一個點位于兩點确定直線的哪側，以及點到直線的距離(面積=底*高/2)。

       這個結論：可以用來判斷點是否在點是否在三角形内。法1：判斷點和三角形三邊所行程的3個三角形的面積之和是否等于原來三角形的面積。（用了三次上面的公式）。

法2：判斷是否都在三條邊的同一邊，相同則滿足，否則不在三角形内。

Problem 25：給出兩個n為向量與0點形成角的角平分線。

提示：對兩條邊進行歸一化，得到長度為1的兩點，取兩個的中點即可。

原文連結：http://www.cnblogs.com/zhenjing/archive/2010/10/18/1854020.html