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)

　　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表中，一致的項則刪除。注意：可能存在很多重復項，引起插入，刪除頻繁。 

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

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

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

　　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的兩點，取兩個的中點即可。