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