谷歌筆試題：判斷一個自然數是否是某個數的平方。當然不能使用開方運算。
假設待判斷的數字是 N。
方法1：
遍歷從1到N的數字，求取平方並和N進行比較。
如果平方小於N，則繼續遍歷;如果等於N，則成功退出;如果大於N，則失敗退出。
複雜度為O(n^0.5)。
方法2：
使用二分查詢法，對1到N之間的數字進行判斷。
複雜度為O(log n)。
方法3：
由於
(n+1)^2
=n^2 + 2n + 1，
= ...
= 1 + (2*1 + 1) + (2*2 + 1) + ... + (2*n + 1)
注意到這些項構成了等差數列(每項之間相差2)。
所以我們可以比較 N-1， N - 1 - 3， N - 1 - 3 - 5 ... 和0的關係。
如果大於0，則繼續減;如果等於0，則成功退出;如果小於 0，則失敗退出。
複雜度為O(n^0.5)。不過方法3中利用加減法替換掉了方法1中的乘法，所以速度會更快些。
谷歌筆試題：如何隨機選取1000個關鍵字
給定一個數據流，其中包含無窮盡的搜尋關鍵字(比如，人們在谷歌搜尋時不斷輸入的關鍵字)。如何才能從這個無窮盡的流中隨機的選取1000個關鍵字?
定義長度為1000的陣列。
對於資料流中的前1000個關鍵字，顯然都要放到陣列中。
對於資料流中的的第n(n>1000)個關鍵字，我們知道這個關鍵字被隨機選中的概率為 1000/n。所以我們以 1000/n 的概率用這個關鍵字去替換陣列中的隨機一個。這樣就可以保證所有關鍵字都以 1000/n的概率被選中。
對於後面的關鍵字都進行這樣的處理，這樣我們就可以保證陣列中總是儲存著1000個隨機關鍵字。
谷歌筆試題：將下列表達式按照複雜度排序
將下列表達式按照複雜度排序
2^n
n^Googol (其中 Googol = 10^100)
n!
n^n
按照複雜度從低到高為
n^Googol
2^n
n!
n^n
谷歌筆試題：在半徑為1的圓中隨機選取一點
假設圓心所在位置為座標元點(0, 0)。
方法1.
在x軸[-1, 1]，y軸[-1, 1]的正方形內隨機選取一點。然後判斷此點是否在圓內(通過計算此點到圓心的距離)。如果在圓內，則此點即為所求;如果不在，則重新選取直到找到為止。
正方形的面積為4，圓的面積為pi，所以正方形內的隨機點在圓內的概率是 pi / 4。
方法2.
從[0, 2*pi)中隨機選一個角度，對應於圓中的一條半徑，然後在此半徑上選一個點。但半徑上的點不能均勻選取，選取的概率應該和距圓心的長度成正比，這樣才能保證隨機點在圓內是均勻分佈的。
谷歌筆試題：給定一個未知長度的整數流，如何隨機選取一個數
方法1.
將整個整數流儲存到一個數組中，然後再隨機選取。
如果整數流很長，無法儲存下來，則此方法不能使用。
方法2.
如果整數流在第一個數後結束，則我們必定會選第一個數作為隨機數。
如果整數流在第二個數後結束，我們選第二個數的概率為1/2。我們以1/2的概率用第2個數替換前面選的隨機數，得到滿足條件的新隨機數。
....
如果整數流在第n個數後結束，我們選第n個數的`概率為1/n。我們以1/n的概率用第n個數替換前面選的隨機數，得到滿足條件的新隨機數。
....
利用這種方法，我們只需儲存一個隨機數，和迄今整數流的長度即可。所以可以處理任意長的整數流。
谷歌筆試題：設計一個資料結構，其中包含兩個函式，1.插入一個數字，2.獲得中數。並估計時間複雜度。
1. 使用陣列儲存。
插入數字時，在O(1)時間內將該數字插入到陣列最後。
獲取中數時，在O(n)時間內找到中數。(選陣列的第一個數和其它數比較，並根據比較結果的大小分成兩組，那麼我們可以確定中數在哪組中。然後對那一組按照同樣的方法進一步細分，直到找到中數。)
2. 使用排序陣列儲存。
插入數字時，在O(logn)時間內找到要插入的位置，在O(n)時間裡移動元素並將新數字插入到合適的位置。
獲得中數時，在O(1)複雜度內找到中數。
3. 使用大根堆和小根堆儲存。
使用大根堆儲存較小的一半數字，使用小根堆儲存較大的一半數字。
插入數字時，在O(logn)時間內將該數字插入到對應的堆當中，並適當移動根節點以保持兩個堆數字相等(或相差1)。
獲取中數時，在O(1)時間內找到中數。
給定一個固定長度的陣列，將遞增整數序列寫入這個陣列。當寫到陣列尾部時，返回陣列開始重新寫，並覆蓋先前寫過的數。
請在這個特殊陣列中找出給定的整數。
假設陣列為a[0, 1, ..., N-1]。
我們可以採用類似二分查詢的策略。
首先比較a[0]和a[N/2]，如果a[0] < a[N/2]，則說明a[0,1,...,N/2]為遞增子序列，否則另一部分是遞增子序列。
然後判斷要找的整數是否在遞增子序列範圍內。如果在，則使用普通的二分查詢方法繼續查詢;如果不在，則重複上面的查詢過程，直到找到或者失敗為止。
給定兩個已排序序列，找出共同的元素。
不妨假設序列是從小到大排序的。定義兩個指標分別指向序列的開始。
如果指向的兩個元素相等，則找到一個相同的元素;如果不等，則將指向較小元素的指標向前移動。
重複執行上面的步驟，直到有一個指標指向序列尾端。
谷歌筆試題：找到連結串列的倒數第m個節點。
方法1：
首先遍歷連結串列，統計連結串列的長度N。
然後再次遍歷連結串列，找到第N-m個節點，即為倒數第m個節點。
方法2：
使用兩個指標，並使它們指向的節點相距m-1個。
然後同時向前移動兩個指標，當一個指標指最後一個節點時，第二個指標指向倒數第m個節點。
兩個方法的複雜度都是O(n)。
但是當N較大而m較小時，方法2可能會更快一些。因為方法2能更好利用CPU的快取。
更多閱讀：
CPU -> 快取
谷歌筆試題：給定一個排序陣列，如何構造一個二叉排序樹?
採用遞迴演算法。
選取陣列中間的一個元素作為根節點，左邊的元素構造左子樹，右邊的節點構造有子樹。
谷歌筆試題：陣列中是否有兩個數的和為10
1.比較任意兩個數的和是否為10。如
for (int i = 0; i < n; ++i) { for (int j = i+1; j < n; ++j) { .... }}
複雜度為O(n*n)。
2.將陣列排序後，對每個數m，使用二分查詢在陣列中尋找10-m。
複雜度為O(nlogn)。
3.將陣列儲存到hash_set中去，對每個數m，在hash_set中尋找10-m。
複雜度為O(n)。
4.如果陣列很大，超過記憶體的容量，可以按照hash(max(m, 10-m))%g，將資料分到g個小的group中。然後對每個小的group進行單獨處理。
複雜度為O(n)。
谷歌筆試題：找到兩個字串的公共字元，並按照其中一個的排序
寫一函式f(a,b)，它帶有兩個字串引數並返回一串字元，該字串只包含在兩個串中都有的並按照在a中的順序。寫一個版本演算法複雜度O(N^2)和一個O(N)
O(N^2)：
對於a中的每個字元，遍歷b中的每個字元，如果相同，則拷貝到新字串中。
O(N)：
首先使用b中的字元建立一個hash_map，對於a中的每個字元，檢測hash_map中是否存在，如果存在則拷貝到新字串中。
給定一個整數序列，其中有些是負數，有些是正數，從該序列中找出最大和的子序列。比如：-5，20，-4，10，-18，子序列[20，-4，10]具有最大和26。
` int GetMaxSubArraySum(int* array, int array_len) { ` int current_sum = 0; ` int max_sum = 0; ` for (int i = 0; i < array_len; ++i) { ` current_sum += array[i]; ` if (current_sum > max_sum) { ` max_sum = current_sum; ` } else if (current_sum < 0) { ` current_sum = 0; ` } ` } ` return max_sum; ` } 或者 int maxsum(int n,int[] list) { int ret,sum=0; int i; for (ret=list[i=0];i