- 相關推薦
Google面試筆試題及答案
谷歌筆試題：判斷一個自然數是否是某個數的平方。當然不能使用開方運算。
假設待判斷的數字是 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的緩存。
更多閱讀：
http://baike.baidu.com/view/2089.htm 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
【Google面試筆試題及答案】相關文章：
名企面試試題 面試題目 Google02-24
google招聘筆試題02-18
Google筆試題目分享11-21
醫院面試試題及答案02-18
經典面試題 及答案分析11-20
英語面試試題及答案02-18
外企面試的經典試題及答案02-18
Google公司預選筆試試題02-18
電工面試題目及答案？02-23