- 相關(guān)推薦
Google面試筆試題及答案
谷歌筆試題：判斷一個(gè)自然數是否是某個(gè)數的平方。當然不能使用開(kāi)方運算。
假設待判斷的數字是 N。
方法1：
遍歷從1到N的數字，求取平方并和N進(jìn)行比較。
如果平方小于N，則繼續遍歷;如果等于N，則成功退出;如果大于N，則失敗退出。
復雜度為O(n^0.5)。
方法2：
使用二分查找法，對1到N之間的數字進(jì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的關(guān)系。
如果大于0，則繼續減;如果等于0，則成功退出;如果小于 0，則失敗退出。
復雜度為O(n^0.5)。不過(guò)方法3中利用加減法替換掉了方法1中的乘法，所以速度會(huì )更快些。
谷歌筆試題：如何隨機選取1000個(gè)關(guān)鍵字
給定一個(gè)數據流，其中包含無(wú)窮盡的搜索關(guān)鍵字(比如，人們在谷歌搜索時(shí)不斷輸入的關(guān)鍵字)。如何才能從這個(gè)無(wú)窮盡的流中隨機的選取1000個(gè)關(guān)鍵字?
定義長(cháng)度為1000的數組。
對于數據流中的前1000個(gè)關(guān)鍵字，顯然都要放到數組中。
對于數據流中的的第n(n>1000)個(gè)關(guān)鍵字，我們知道這個(gè)關(guān)鍵字被隨機選中的概率為 1000/n。所以我們以 1000/n 的概率用這個(gè)關(guān)鍵字去替換數組中的隨機一個(gè)。這樣就可以保證所有關(guān)鍵字都以 1000/n的概率被選中。
對于后面的關(guān)鍵字都進(jìn)行這樣的處理，這樣我們就可以保證數組中總是保存著(zhù)1000個(gè)隨機關(guān)鍵字。
谷歌筆試題：將下列表達式按照復雜度排序
將下列表達式按照復雜度排序
2^n
n^Googol (其中 Googol = 10^100)
n!
n^n
按照復雜度從低到高為
n^Googol
2^n
n!
n^n
谷歌筆試題：在半徑為1的圓中隨機選取一點(diǎn)
假設圓心所在位置為坐標元點(diǎn)(0, 0)。
方法1.
在x軸[-1, 1]，y軸[-1, 1]的正方形內隨機選取一點(diǎn)。然后判斷此點(diǎn)是否在圓內(通過(guò)計算此點(diǎn)到圓心的距離)。如果在圓內，則此點(diǎn)即為所求;如果不在，則重新選取直到找到為止。
正方形的面積為4，圓的面積為pi，所以正方形內的隨機點(diǎn)在圓內的概率是 pi / 4。
方法2.
從[0, 2*pi)中隨機選一個(gè)角度，對應于圓中的一條半徑，然后在此半徑上選一個(gè)點(diǎn)。但半徑上的點(diǎn)不能均勻選取，選取的概率應該和距圓心的長(cháng)度成正比，這樣才能保證隨機點(diǎn)在圓內是均勻分布的。
谷歌筆試題：給定一個(gè)未知長(cháng)度的整數流，如何隨機選取一個(gè)數
方法1.
將整個(gè)整數流保存到一個(gè)數組中，然后再隨機選取。
如果整數流很長(cháng)，無(wú)法保存下來(lái)，則此方法不能使用。
方法2.
如果整數流在第一個(gè)數后結束，則我們必定會(huì )選第一個(gè)數作為隨機數。
如果整數流在第二個(gè)數后結束，我們選第二個(gè)數的概率為1/2。我們以1/2的概率用第2個(gè)數替換前面選的隨機數，得到滿(mǎn)足條件的新隨機數。
....
如果整數流在第n個(gè)數后結束，我們選第n個(gè)數的概率為1/n。我們以1/n的概率用第n個(gè)數替換前面選的隨機數，得到滿(mǎn)足條件的新隨機數。
....
利用這種方法，我們只需保存一個(gè)隨機數，和迄今整數流的長(cháng)度即可。所以可以處理任意長(cháng)的整數流。
谷歌筆試題：設計一個(gè)數據結構，其中包含兩個(gè)函數，1.插入一個(gè)數字，2.獲得中數。并估計時(shí)間復雜度。
1. 使用數組存儲。
插入數字時(shí)，在O(1)時(shí)間內將該數字插入到數組最后。
獲取中數時(shí)，在O(n)時(shí)間內找到中數。(選數組的第一個(gè)數和其它數比較，并根據比較結果的大小分成兩組，那么我們可以確定中數在哪組中。然后對那一組按照同樣的方法進(jìn)一步細分，直到找到中數。)
2. 使用排序數組存儲。
插入數字時(shí)，在O(logn)時(shí)間內找到要插入的位置，在O(n)時(shí)間里移動(dòng)元素并將新數字插入到合適的位置。
獲得中數時(shí)，在O(1)復雜度內找到中數。
3. 使用大根堆和小根堆存儲。
使用大根堆存儲較小的一半數字，使用小根堆存儲較大的一半數字。
插入數字時(shí)，在O(logn)時(shí)間內將該數字插入到對應的堆當中，并適當移動(dòng)根節點(diǎn)以保持兩個(gè)堆數字相等(或相差1)。
獲取中數時(shí)，在O(1)時(shí)間內找到中數。
給定一個(gè)固定長(cháng)度的數組，將遞增整數序列寫(xiě)入這個(gè)數組。當寫(xiě)到數組尾部時(shí)，返回數組開(kāi)始重新寫(xiě)，并覆蓋先前寫(xiě)過(guò)的數。
請在這個(gè)特殊數組中找出給定的整數。
假設數組為a[0, 1, ..., N-1]。
我們可以采用類(lèi)似二分查找的策略。
首先比較a[0]和a[N/2]，如果a[0] < a[N/2]，則說(shuō)明a[0,1,...,N/2]為遞增子序列，否則另一部分是遞增子序列。
然后判斷要找的整數是否在遞增子序列范圍內。如果在，則使用普通的二分查找方法繼續查找;如果不在，則重復上面的查找過(guò)程，直到找到或者失敗為止。
給定兩個(gè)已排序序列，找出共同的元素。
不妨假設序列是從小到大排序的。定義兩個(gè)指針?lè )謩e指向序列的開(kāi)始。
如果指向的兩個(gè)元素相等，則找到一個(gè)相同的元素;如果不等，則將指向較小元素的指針向前移動(dòng)。
重復執行上面的步驟，直到有一個(gè)指針指向序列尾端。
谷歌筆試題：找到鏈表的倒數第m個(gè)節點(diǎn)。
方法1：
首先遍歷鏈表，統計鏈表的長(cháng)度N。
然后再次遍歷鏈表，找到第N-m個(gè)節點(diǎn)，即為倒數第m個(gè)節點(diǎn)。
方法2：
使用兩個(gè)指針，并使它們指向的節點(diǎn)相距m-1個(gè)。
然后同時(shí)向前移動(dòng)兩個(gè)指針，當一個(gè)指針指最后一個(gè)節點(diǎn)時(shí)，第二個(gè)指針指向倒數第m個(gè)節點(diǎn)。
兩個(gè)方法的復雜度都是O(n)。
但是當N較大而m較小時(shí)，方法2可能會(huì )更快一些。因為方法2能更好利用CPU的緩存。
更多閱讀：
http://baike.baidu.com/view/2089.htm CPU -> 緩存
谷歌筆試題：給定一個(gè)排序數組，如何構造一個(gè)二叉排序樹(shù)?
采用遞歸算法。
選取數組中間的一個(gè)元素作為根節點(diǎn)，左邊的元素構造左子樹(shù)，右邊的節點(diǎn)構造有子樹(shù)。
谷歌筆試題：數組中是否有兩個(gè)數的和為10
1.比較任意兩個(gè)數的和是否為10。如
for (int i = 0; i < n; ++i) { for (int j = i+1; j < n; ++j) { .... }}
復雜度為O(n*n)。
2.將數組排序后，對每個(gè)數m，使用二分查找在數組中尋找10-m。
復雜度為O(nlogn)。
3.將數組存儲到hash_set中去，對每個(gè)數m，在hash_set中尋找10-m。
復雜度為O(n)。
4.如果數組很大，超過(guò)內存的容量，可以按照hash(max(m, 10-m))%g，將數據分到g個(gè)小的group中。然后對每個(gè)小的group進(jìn)行單獨處理。
復雜度為O(n)。
谷歌筆試題：找到兩個(gè)字符串的公共字符，并按照其中一個(gè)的排序
寫(xiě)一函數f(a,b)，它帶有兩個(gè)字符串參數并返回一串字符，該字符串只包含在兩個(gè)串中都有的并按照在a中的順序。寫(xiě)一個(gè)版本算法復雜度O(N^2)和一個(gè)O(N)
O(N^2)：
對于a中的每個(gè)字符，遍歷b中的每個(gè)字符，如果相同，則拷貝到新字符串中。
O(N)：
首先使用b中的字符建立一個(gè)hash_map，對于a中的每個(gè)字符，檢測hash_map中是否存在，如果存在則拷貝到新字符串中。
給定一個(gè)整數序列，其中有些是負數，有些是正數，從該序列中找出最大和的子序列。比如：-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面試筆試題及答案】相關(guān)文章：
名企面試試題 面試題目 Google02-24
google招聘筆試題02-18
Google筆試題目分享11-21
醫院面試試題及答案02-18
經(jīng)典面試題 及答案分析11-20
英語(yǔ)面試試題及答案02-18
外企面試的經(jīng)典試題及答案02-18
Google令人抓狂的面試題，看看你能承受幾個(gè)11-19
Google公司預選筆試試題02-18
電工面試題目及答案？02-23