- 相關推薦
Google面試筆試題及答案
谷歌筆試題：判斷一個自然數(shù)是否是某個數(shù)的平方。當然不能使用開方運算。
假設待判斷的數(shù)字是 N。
方法1：
遍歷從1到N的數(shù)字，求取平方并和N進行比較。
如果平方小于N，則繼續(xù)遍歷;如果等于N，則成功退出;如果大于N，則失敗退出。
復雜度為O(n^0.5)。
方法2：
使用二分查找法，對1到N之間的數(shù)字進行判斷。
復雜度為O(log n)。
方法3：
由于
(n+1)^2
=n^2 + 2n + 1，
= ...
= 1 + (2*1 + 1) + (2*2 + 1) + ... + (2*n + 1)
注意到這些項構成了等差數(shù)列(每項之間相差2)。
所以我們可以比較 N-1， N - 1 - 3， N - 1 - 3 - 5 ... 和0的關系。
如果大于0，則繼續(xù)減;如果等于0，則成功退出;如果小于 0，則失敗退出。
復雜度為O(n^0.5)。不過方法3中利用加減法替換掉了方法1中的乘法，所以速度會更快些。
谷歌筆試題：如何隨機選取1000個關鍵字
給定一個數(shù)據(jù)流，其中包含無窮盡的搜索關鍵字(比如，人們在谷歌搜索時不斷輸入的關鍵字)。如何才能從這個無窮盡的流中隨機的選取1000個關鍵字?
定義長度為1000的數(shù)組。
對于數(shù)據(jù)流中的前1000個關鍵字，顯然都要放到數(shù)組中。
對于數(shù)據(jù)流中的的第n(n>1000)個關鍵字，我們知道這個關鍵字被隨機選中的概率為 1000/n。所以我們以 1000/n 的概率用這個關鍵字去替換數(shù)組中的隨機一個。這樣就可以保證所有關鍵字都以 1000/n的概率被選中。
對于后面的關鍵字都進行這樣的處理，這樣我們就可以保證數(shù)組中總是保存著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)中隨機選一個角度，對應于圓中的一條半徑，然后在此半徑上選一個點。但半徑上的點不能均勻選取，選取的概率應該和距圓心的長度成正比，這樣才能保證隨機點在圓內是均勻分布的。
谷歌筆試題：給定一個未知長度的整數(shù)流，如何隨機選取一個數(shù)
方法1.
將整個整數(shù)流保存到一個數(shù)組中，然后再隨機選取。
如果整數(shù)流很長，無法保存下來，則此方法不能使用。
方法2.
如果整數(shù)流在第一個數(shù)后結束，則我們必定會選第一個數(shù)作為隨機數(shù)。
如果整數(shù)流在第二個數(shù)后結束，我們選第二個數(shù)的概率為1/2。我們以1/2的概率用第2個數(shù)替換前面選的隨機數(shù)，得到滿足條件的新隨機數(shù)。
....
如果整數(shù)流在第n個數(shù)后結束，我們選第n個數(shù)的概率為1/n。我們以1/n的概率用第n個數(shù)替換前面選的隨機數(shù)，得到滿足條件的新隨機數(shù)。
....
利用這種方法，我們只需保存一個隨機數(shù)，和迄今整數(shù)流的長度即可。所以可以處理任意長的整數(shù)流。
谷歌筆試題：設計一個數(shù)據(jù)結構，其中包含兩個函數(shù)，1.插入一個數(shù)字，2.獲得中數(shù)。并估計時間復雜度。
1. 使用數(shù)組存儲。
插入數(shù)字時，在O(1)時間內將該數(shù)字插入到數(shù)組最后。
獲取中數(shù)時，在O(n)時間內找到中數(shù)。(選數(shù)組的第一個數(shù)和其它數(shù)比較，并根據(jù)比較結果的大小分成兩組，那么我們可以確定中數(shù)在哪組中。然后對那一組按照同樣的方法進一步細分，直到找到中數(shù)。)
2. 使用排序數(shù)組存儲。
插入數(shù)字時，在O(logn)時間內找到要插入的位置，在O(n)時間里移動元素并將新數(shù)字插入到合適的位置。
獲得中數(shù)時，在O(1)復雜度內找到中數(shù)。
3. 使用大根堆和小根堆存儲。
使用大根堆存儲較小的一半數(shù)字，使用小根堆存儲較大的一半數(shù)字。
插入數(shù)字時，在O(logn)時間內將該數(shù)字插入到對應的堆當中，并適當移動根節(jié)點以保持兩個堆數(shù)字相等(或相差1)。
獲取中數(shù)時，在O(1)時間內找到中數(shù)。
給定一個固定長度的數(shù)組，將遞增整數(shù)序列寫入這個數(shù)組。當寫到數(shù)組尾部時，返回數(shù)組開始重新寫，并覆蓋先前寫過的數(shù)。
請在這個特殊數(shù)組中找出給定的整數(shù)。
假設數(shù)組為a[0, 1, ..., N-1]。
我們可以采用類似二分查找的策略。
首先比較a[0]和a[N/2]，如果a[0] < a[N/2]，則說明a[0,1,...,N/2]為遞增子序列，否則另一部分是遞增子序列。
然后判斷要找的整數(shù)是否在遞增子序列范圍內。如果在，則使用普通的二分查找方法繼續(xù)查找;如果不在，則重復上面的查找過程，直到找到或者失敗為止。
給定兩個已排序序列，找出共同的元素。
不妨假設序列是從小到大排序的。定義兩個指針分別指向序列的開始。
如果指向的兩個元素相等，則找到一個相同的元素;如果不等，則將指向較小元素的指針向前移動。
重復執(zhí)行上面的步驟，直到有一個指針指向序列尾端。
谷歌筆試題：找到鏈表的倒數(shù)第m個節(jié)點。
方法1：
首先遍歷鏈表，統(tǒng)計鏈表的長度N。
然后再次遍歷鏈表，找到第N-m個節(jié)點，即為倒數(shù)第m個節(jié)點。
方法2：
使用兩個指針，并使它們指向的節(jié)點相距m-1個。
然后同時向前移動兩個指針，當一個指針指最后一個節(jié)點時，第二個指針指向倒數(shù)第m個節(jié)點。
兩個方法的復雜度都是O(n)。
但是當N較大而m較小時，方法2可能會更快一些。因為方法2能更好利用CPU的緩存。
更多閱讀：
http://baike.baidu.com/view/2089.htm CPU -> 緩存
谷歌筆試題：給定一個排序數(shù)組，如何構造一個二叉排序樹?
采用遞歸算法。
選取數(shù)組中間的一個元素作為根節(jié)點，左邊的元素構造左子樹，右邊的節(jié)點構造有子樹。
谷歌筆試題：數(shù)組中是否有兩個數(shù)的和為10
1.比較任意兩個數(shù)的和是否為10。如
for (int i = 0; i < n; ++i) { for (int j = i+1; j < n; ++j) { .... }}
復雜度為O(n*n)。
2.將數(shù)組排序后，對每個數(shù)m，使用二分查找在數(shù)組中尋找10-m。
復雜度為O(nlogn)。
3.將數(shù)組存儲到hash_set中去，對每個數(shù)m，在hash_set中尋找10-m。
復雜度為O(n)。
4.如果數(shù)組很大，超過內存的容量，可以按照hash(max(m, 10-m))%g，將數(shù)據(jù)分到g個小的group中。然后對每個小的group進行單獨處理。
復雜度為O(n)。
谷歌筆試題：找到兩個字符串的公共字符，并按照其中一個的排序
寫一函數(shù)f(a,b)，它帶有兩個字符串參數(shù)并返回一串字符，該字符串只包含在兩個串中都有的并按照在a中的順序。寫一個版本算法復雜度O(N^2)和一個O(N)
O(N^2)：
對于a中的每個字符，遍歷b中的每個字符，如果相同，則拷貝到新字符串中。
O(N)：
首先使用b中的字符建立一個hash_map，對于a中的每個字符，檢測hash_map中是否存在，如果存在則拷貝到新字符串中。
給定一個整數(shù)序列，其中有些是負數(shù)，有些是正數(shù)，從該序列中找出最大和的子序列。比如：-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面試筆試題及答案】相關文章：
園林綠化面試題及答案03-03
護士面試筆試�？荚囶}及答案11-17
報社筆試題目及答案03-18
財務會計面試題目及答案03-10
現(xiàn)代教育技術試題及答案03-02
軟件工程師面試題小練帶參考答案12-21
史上最全軟件筆試題目及答案08-21
職業(yè)心理在線測試題及答案06-05
面試題：對跳槽的看法11-04