- 相關(guān)推薦
Google面試筆試題
谷歌筆試題：將無向無環(huán)連通圖轉(zhuǎn)換成深度最小的樹
已知一個無向無環(huán)連通圖T的所有頂點和邊的信息，現(xiàn)需要將其轉(zhuǎn)換為一棵樹，要求樹的深度最小，請設(shè)計一個算法找到所有滿足要求的樹的根結(jié)點，并分析時空復(fù)雜度。
最簡單直接的方法就是把每個節(jié)點都試一遍：
假設(shè)某個節(jié)點為根節(jié)點，計算樹的深度。當(dāng)遍歷完所有節(jié)點后，也就找到了使樹的深度最小的根節(jié)點。
但這個方法的復(fù)雜度很高。如果有n個節(jié)點，則時間復(fù)雜度為O(n^2)。
樹的深度取決于根節(jié)點到最深葉節(jié)點的距離，所以我們可以從葉節(jié)點入手。
葉節(jié)點會且只會和某一個節(jié)點連通(反之不成立，因為根節(jié)點也可能只和一個節(jié)點連通)，所以我們很容易找到所有可能的葉節(jié)點。
題目可以等價于找到了兩個葉節(jié)點，使得兩個葉節(jié)點之間的距離最遠(yuǎn)。根節(jié)點就是這兩個葉節(jié)點路徑的中間點(或者中間兩個點的任意一個)。
我們可以每次都將連接度為1的節(jié)點刪掉，直到最后只剩下1個或2個節(jié)點，則這一個節(jié)點，或者兩個節(jié)點中的任意一個，就是我們要找的根節(jié)點。
谷歌筆試題：將字符串中的小寫字母排在大寫字母的前面
有一個由大小寫組成的字符串，現(xiàn)在需要對它進(jìn)行修改，將其中的所有小寫字母排在大寫字母的前面(大寫或小寫字母之間不要求保持原來次序)。
初始化兩個int變量A和B，代表字符串中的兩個位置。開始時A指向字符串的第一個字符，B指向字符串的最后一個字符。
逐漸增加A的值使其指向一個大寫字母，逐漸減小B使其指向一個小寫字母，交換A，B所指向的字符，然后繼續(xù)增加A，減小B....。
當(dāng)A>=B時，就完成了重新排序。
i指向最后一個小寫字符，j尋找小寫字符。
void swapString(char* str, int len) { int i=-1; int j=0; for(j=0; j<len; str[j]="" &&="" if(str[j]<="z">='a') { i++; swap(str[i], str[j]); } } }
谷歌筆試題：在重男輕女的國家里，男女的比例是多少?
在一個重男輕女的國家里，每個家庭都想生男孩，如果他們生的孩子是女孩，就再生一個，直到生下的是男孩為止。這樣的國家，男女比例會是多少?
還是1：1。
在所有出生的第一個小孩中，男女比例是1：1;在所有出生的第二個小孩中，男女比例是1：1;.... 在所有出生的第n個小孩中，男女比例還是1：1。
所以總的男女比例是1：1。
谷歌筆試題：如何拷貝特殊鏈表
有一個特殊的鏈表，其中每個節(jié)點不但有指向下一個節(jié)點的指針pNext，還有一個指向鏈表中任意節(jié)點的指針pRand，如何拷貝這個特殊鏈表?
拷貝pNext指針非常容易，所以題目的難點是如何拷貝pRand指針。
假設(shè)原來鏈表為A1 -> A2 ->... -> An，新拷貝鏈表是B1 -> B2 ->...-> Bn。
為了能夠快速的找到pRand指向的節(jié)點，并把對應(yīng)的關(guān)系拷貝到B中。我們可以將兩個鏈表合并成
A1 -> B1 -> A2 -> B2 -> ... -> An -> Bn。
從A1節(jié)點出發(fā)，很容易找到A1的pRand指向的節(jié)點Ax,然后也就找到了Bx，將B1的pRand指向Bx也就完成了B1節(jié)點pRand的拷貝。依次類推。
當(dāng)所有節(jié)點的pRand都拷貝完成后，再將合并鏈表分成兩個鏈表就可以了。
class ListNode { int value; ListNode* p_next; ListNOde* p_rand; public ListNode(int v, ListNode* next, ListNode* rand): value(v), p_next(next), p_rand(rand) { } }; ListNode*copyList(ListNode*p) { if(p!=null) { /*構(gòu)建交叉數(shù)組 p0->q0->p1->q1->p2->q2...*/ ListNOde*ppre=p; ListNode*post=->next; while(pre!=null) { pre->next=newListNode(pre->value,post,pre->p_rand->p_next); pre=last; lastlast=last->p_next; } /*拆分成被拷貝數(shù)組和拷貝數(shù)組 p0->p1->p2....;q0->q1->q2....*/ ppre=p; ListNode*res=p->p_next; while(res->p_next!=null) { p->p_next=res->p_next; res->p_next=res->p_next->p_next; } returnres; }else { returnp; } }
如果在高速公路上30分鐘內(nèi)看到一輛車開過的幾率是0.95，那么在10分鐘內(nèi)看到一輛車開過的幾率是多少?(假設(shè)為常概率條件下)
假設(shè)10分鐘內(nèi)看到一輛車開過的概率是x，那么沒有看到車開過的概率就是1-x，30分鐘沒有看到車開過的概率是(1-x)^3，也就是0.05。所以得到方程(1-x)^3 = 0.05
解方程得到x大約是0.63。
谷歌筆試題：從25匹馬中找出最快的3匹
最少需要7次。
首先將馬分成a,b,c,d,e 5個組，每組5匹，每組單獨比賽。然后將每組的第一名放在一起比賽。假設(shè)結(jié)果如下
a0,a1,a2,a3,a4
b0,b1,b2,b3,b4
c0,c1,c2,c3,c4
d0,d1,d2,d3,d4
e0,e1,e2,e3,e4
其中a, b,c,d,e小組都是按照名次排列(速度a0>a1>a2>a3>a4, b0>b1....)。并第6次比賽的結(jié)果為a0>b0>c0>d0>e0。
那么第6次比賽結(jié)束后，我們知道最快的一匹為a0。
我們知道第2名的馬一定是a1或者b0，所以在接下來的比賽中要包含這兩匹馬。如果a1快，那么第3名是a2或者b0，如果b0快，那么第3名是a1，b1或者c0。也就是說第2名和第3名一定在a1，a2，b0，b1和c0當(dāng)中，所以在第7場比賽中包括這5匹馬就可以得到第2名和第3名。
所以7次比賽就可以獲得前3名的馬。
谷歌筆試題：將無向無環(huán)連通圖轉(zhuǎn)換成深度最小的樹
已知一個無向無環(huán)連通圖T的所有頂點和邊的信息，現(xiàn)需要將其轉(zhuǎn)換為一棵樹，要求樹的深度最小，請設(shè)計一個算法找到所有滿足要求的樹的根結(jié)點，并分析時空復(fù)雜度。
最簡單直接的方法就是把每個節(jié)點都試一遍：
假設(shè)某個節(jié)點為根節(jié)點，計算樹的深度。當(dāng)遍歷完所有節(jié)點后，也就找到了使樹的深度最小的根節(jié)點。
但這個方法的復(fù)雜度很高。如果有n個節(jié)點，則時間復(fù)雜度為O(n^2)。
樹的深度取決于根節(jié)點到最深葉節(jié)點的距離，所以我們可以從葉節(jié)點入手。
葉節(jié)點會且只會和某一個節(jié)點連通(反之不成立，因為根節(jié)點也可能只和一個節(jié)點連通)，所以我們很容易找到所有可能的葉節(jié)點。
題目可以等價于找到了兩個葉節(jié)點，使得兩個葉節(jié)點之間的距離最遠(yuǎn)。根節(jié)點就是這兩個葉節(jié)點路徑的中間點(或者中間兩個點的任意一個)。
我們可以每次都將連接度為1的節(jié)點刪掉，直到最后只剩下1個或2個節(jié)點，則這一個節(jié)點，或者兩個節(jié)點中的任意一個，就是我們要找的根節(jié)點。
谷歌筆試題：將字符串中的小寫字母排在大寫字母的前面
有一個由大小寫組成的字符串，現(xiàn)在需要對它進(jìn)行修改，將其中的所有小寫字母排在大寫字母的前面(大寫或小寫字母之間不要求保持原來次序)。
初始化兩個int變量A和B，代表字符串中的兩個位置。開始時A指向字符串的第一個字符，B指向字符串的最后一個字符。
逐漸增加A的值使其指向一個大寫字母，逐漸減小B使其指向一個小寫字母，交換A，B所指向的字符，然后繼續(xù)增加A，減小B....。
當(dāng)A>=B時，就完成了重新排序。
i指向最后一個小寫字符，j尋找小寫字符。
void swapString(char* str, int len) { int i=-1; int j=0; for(j=0; j<len; str[j]="" &&="" if(str[j]<="z">='a') { i++; swap(str[i], str[j]); } } }
谷歌筆試題：在重男輕女的國家里，男女的比例是多少?
在一個重男輕女的國家里，每個家庭都想生男孩，如果他們生的孩子是女孩，就再生一個，直到生下的是男孩為止。這樣的國家，男女比例會是多少?
還是1：1。
在所有出生的第一個小孩中，男女比例是1：1;在所有出生的第二個小孩中，男女比例是1：1;.... 在所有出生的第n個小孩中，男女比例還是1：1。
所以總的男女比例是1：1。
谷歌筆試題：如何拷貝特殊鏈表
有一個特殊的鏈表，其中每個節(jié)點不但有指向下一個節(jié)點的指針pNext，還有一個指向鏈表中任意節(jié)點的指針pRand，如何拷貝這個特殊鏈表?
拷貝pNext指針非常容易，所以題目的難點是如何拷貝pRand指針。
假設(shè)原來鏈表為A1 -> A2 ->... -> An，新拷貝鏈表是B1 -> B2 ->...-> Bn。
為了能夠快速的找到pRand指向的節(jié)點，并把對應(yīng)的關(guān)系拷貝到B中。我們可以將兩個鏈表合并成
A1 -> B1 -> A2 -> B2 -> ... -> An -> Bn。
從A1節(jié)點出發(fā)，很容易找到A1的pRand指向的節(jié)點Ax,然后也就找到了Bx，將B1的pRand指向Bx也就完成了B1節(jié)點pRand的拷貝。依次類推。
當(dāng)所有節(jié)點的pRand都拷貝完成后，再將合并鏈表分成兩個鏈表就可以了。
class ListNode { int value; ListNode* p_next; ListNOde* p_rand; public ListNode(int v, ListNode* next, ListNode* rand): value(v), p_next(next), p_rand(rand) { } }; ListNode*copyList(ListNode*p) { if(p!=null) { /*構(gòu)建交叉數(shù)組 p0->q0->p1->q1->p2->q2...*/ ListNOde*ppre=p; ListNode*post=->next; while(pre!=null) { pre->next=newListNode(pre->value,post,pre->p_rand->p_next); pre=last; lastlast=last->p_next; } /*拆分成被拷貝數(shù)組和拷貝數(shù)組 p0->p1->p2....;q0->q1->q2....*/ ppre=p; ListNode*res=p->p_next; while(res->p_next!=null) { p->p_next=res->p_next; res->p_next=res->p_next->p_next; } returnres; }else { returnp; } }
如果在高速公路上30分鐘內(nèi)看到一輛車開過的幾率是0.95，那么在10分鐘內(nèi)看到一輛車開過的幾率是多少?(假設(shè)為常概率條件下)
假設(shè)10分鐘內(nèi)看到一輛車開過的概率是x，那么沒有看到車開過的概率就是1-x，30分鐘沒有看到車開過的概率是(1-x)^3，也就是0.05。所以得到方程(1-x)^3 = 0.05
解方程得到x大約是0.63。
谷歌筆試題：從25匹馬中找出最快的3匹
最少需要7次。
首先將馬分成a,b,c,d,e 5個組，每組5匹，每組單獨比賽。然后將每組的第一名放在一起比賽。假設(shè)結(jié)果如下
a0,a1,a2,a3,a4
b0,b1,b2,b3,b4
c0,c1,c2,c3,c4
d0,d1,d2,d3,d4
e0,e1,e2,e3,e4
其中a, b,c,d,e小組都是按照名次排列(速度a0>a1>a2>a3>a4, b0>b1....)。并第6次比賽的結(jié)果為a0>b0>c0>d0>e0。
那么第6次比賽結(jié)束后，我們知道最快的一匹為a0。
我們知道第2名的馬一定是a1或者b0，所以在接下來的比賽中要包含這兩匹馬。如果a1快，那么第3名是a2或者b0，如果b0快，那么第3名是a1，b1或者c0。也就是說第2名和第3名一定在a1，a2，b0，b1和c0當(dāng)中，所以在第7場比賽中包括這5匹馬就可以得到第2名和第3名。
所以7次比賽就可以獲得前3名的馬。
【Google面試筆試題】相關(guān)文章：
名企面試試題 面試題目 Google02-24
google招聘筆試題02-18
Google筆試題目分享11-21
Google公司預(yù)選筆試試題02-18
Google面試官談面試技巧02-18
剛剛完成了Google的電話面試11-19
求教筆面試的時間02-23
面試題精選02-18