谷歌(Google)算法面試題

1、谷歌(Google算法面試題1.谷歌面試題:給定能隨機(jī)生成整數(shù)1到5的函數(shù),寫出能隨機(jī)生成整數(shù)1到7的函數(shù)?；卮?此題的關(guān)鍵是讓生成的1到7的數(shù)出現(xiàn)概率相同。只要我們可以從n個(gè)數(shù)中隨機(jī)選出1到n個(gè)數(shù),反復(fù)進(jìn)行這種運(yùn)算,直到剩下最后一個(gè)數(shù)即可。我們可以調(diào)用n次給定函數(shù),生成n個(gè)1到5之間的隨機(jī)數(shù),選取最大數(shù)所在位置即可滿足以上要求。例如初始的7個(gè)數(shù)1,2,3,4,5,6,7.7個(gè)1到5的隨機(jī)數(shù)5,3,1,4,2,5,5那么我們保留下1,6,7,3個(gè)1到5的隨機(jī)數(shù)2,4,1那么我們保留下66就是我們這次生成的隨機(jī)數(shù)。2. 谷歌面試題:判斷一個(gè)自然數(shù)是否是某個(gè)數(shù)的平方。當(dāng)然不能使用開方運(yùn)算?；卮?假

2、設(shè)待判斷的數(shù)字是N。方法1:遍歷從1到N的數(shù)字,求取平方并和N進(jìn)行比較。如果平方小于N,則繼續(xù)遍歷;如果等于N,則成功退出;如果大于N,則失敗退出。復(fù)雜度為O(n0.5。方法2:使用二分查找法,對(duì)1到N之間的數(shù)字進(jìn)行判斷。復(fù)雜度為O(logn。方法3:由于(n+12=n2+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(n0.5。不過方法3中利用加減法替換掉了方法1中的乘法,所以速度會(huì)更快些

3、。3. 谷歌面試題:給定一個(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(n1000個(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)鍵字。4. 谷歌面試題:將下列表達(dá)式按照復(fù)雜度排序2nnGoo

4、gol(其中Googol=10100n!nn回答:按照復(fù)雜度從低到高為nGoogol2nn!nn5.谷歌面試題:在半徑為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)

5、在圓內(nèi)是均勻分布的。6. 谷歌面試題:給定一個(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ù)流的長度即可。所以可以處理任

6、意長的整數(shù)流。6.谷歌面試題:給定一個(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ù)流的長度即可。所以可以處理任意長的整

7、數(shù)流。7.谷歌面試題:設(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ǔ)較大的

8、一半數(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ù)。8. 谷歌面試題:在一個(gè)特殊數(shù)組中進(jìn)行查找,給定一個(gè)固定長度的數(shù)組,將遞增整數(shù)序列寫入這個(gè)數(shù)組。當(dāng)寫到數(shù)組尾部時(shí),返回?cái)?shù)組開始重新寫,并覆蓋先前寫過的數(shù)。請(qǐng)?jiān)谶@個(gè)特殊數(shù)組中找出給定的整數(shù)?；卮?假設(shè)數(shù)組為a0,1,.,N-1。我們可以采用類似二分查找的策略。首先比較a0和aN/2,如果a0然后判斷要找的整數(shù)是否在遞增子序列范圍內(nèi)。如果在,則使用普通的二分查找方法繼續(xù)查找;如果不在,則重復(fù)上面的查找過程,直到找到或者失敗為止。9. 谷歌面試題:1024!末尾有多少個(gè)0?答案:末尾0的個(gè)數(shù)取決于乘法中因子2和5的個(gè)數(shù)。顯然乘法中因子2的個(gè)數(shù)大于5的個(gè)數(shù),所以我們只需統(tǒng)計(jì)因子5的個(gè)數(shù)。是5的