- 相關(guān)推薦
Google面試筆試題
谷歌筆試題：將無(wú)向無(wú)環(huán)連通圖轉(zhuǎn)換成深度最小的樹(shù)
已知一個(gè)無(wú)向無(wú)環(huán)連通圖T的所有頂點(diǎn)和邊的信息，現(xiàn)需要將其轉(zhuǎn)換為一棵樹(shù)，要求樹(shù)的深度最小，請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法找到所有滿(mǎn)足要求的樹(shù)的根結(jié)點(diǎn)，并分析時(shí)空復(fù)雜度。
最簡(jiǎn)單直接的方法就是把每個(gè)節(jié)點(diǎn)都試一遍：
假設(shè)某個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)，計(jì)算樹(shù)的深度。當(dāng)遍歷完所有節(jié)點(diǎn)后，也就找到了使樹(shù)的深度最小的根節(jié)點(diǎn)。
但這個(gè)方法的復(fù)雜度很高。如果有n個(gè)節(jié)點(diǎn)，則時(shí)間復(fù)雜度為O(n^2)。
樹(shù)的深度取決于根節(jié)點(diǎn)到最深葉節(jié)點(diǎn)的距離，所以我們可以從葉節(jié)點(diǎn)入手。
葉節(jié)點(diǎn)會(huì)且只會(huì)和某一個(gè)節(jié)點(diǎn)連通(反之不成立，因?yàn)楦?jié)點(diǎn)也可能只和一個(gè)節(jié)點(diǎn)連通)，所以我們很容易找到所有可能的葉節(jié)點(diǎn)。
題目可以等價(jià)于找到了兩個(gè)葉節(jié)點(diǎn)，使得兩個(gè)葉節(jié)點(diǎn)之間的距離最遠(yuǎn)。根節(jié)點(diǎn)就是這兩個(gè)葉節(jié)點(diǎn)路徑的中間點(diǎn)(或者中間兩個(gè)點(diǎn)的任意一個(gè))。
我們可以每次都將連接度為1的節(jié)點(diǎn)刪掉，直到最后只剩下1個(gè)或2個(gè)節(jié)點(diǎn)，則這一個(gè)節(jié)點(diǎn)，或者兩個(gè)節(jié)點(diǎn)中的任意一個(gè)，就是我們要找的根節(jié)點(diǎn)。
谷歌筆試題：將字符串中的小寫(xiě)字母排在大寫(xiě)字母的前面
有一個(gè)由大小寫(xiě)組成的字符串，現(xiàn)在需要對(duì)它進(jìn)行修改，將其中的所有小寫(xiě)字母排在大寫(xiě)字母的前面(大寫(xiě)或小寫(xiě)字母之間不要求保持原來(lái)次序)。
初始化兩個(gè)int變量A和B，代表字符串中的兩個(gè)位置。開(kāi)始時(shí)A指向字符串的第一個(gè)字符，B指向字符串的最后一個(gè)字符。
逐漸增加A的值使其指向一個(gè)大寫(xiě)字母，逐漸減小B使其指向一個(gè)小寫(xiě)字母，交換A，B所指向的字符，然后繼續(xù)增加A，減小B....。
當(dāng)A>=B時(shí)，就完成了重新排序。
i指向最后一個(gè)小寫(xiě)字符，j尋找小寫(xiě)字符。
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]); } } }
谷歌筆試題：在重男輕女的國(guó)家里，男女的比例是多少?
在一個(gè)重男輕女的國(guó)家里，每個(gè)家庭都想生男孩，如果他們生的孩子是女孩，就再生一個(gè)，直到生下的是男孩為止。這樣的國(guó)家，男女比例會(huì)是多少?
還是1：1。
在所有出生的第一個(gè)小孩中，男女比例是1：1;在所有出生的第二個(gè)小孩中，男女比例是1：1;.... 在所有出生的第n個(gè)小孩中，男女比例還是1：1。
所以總的男女比例是1：1。
谷歌筆試題：如何拷貝特殊鏈表
有一個(gè)特殊的鏈表，其中每個(gè)節(jié)點(diǎn)不但有指向下一個(gè)節(jié)點(diǎn)的指針pNext，還有一個(gè)指向鏈表中任意節(jié)點(diǎn)的指針pRand，如何拷貝這個(gè)特殊鏈表?
拷貝pNext指針?lè)浅Ｈ菀�，所以題目的難點(diǎn)是如何拷貝pRand指針。
假設(shè)原來(lái)鏈表為A1 -> A2 ->... -> An，新拷貝鏈表是B1 -> B2 ->...-> Bn。
為了能夠快速的找到pRand指向的節(jié)點(diǎn)，并把對(duì)應(yīng)的關(guān)系拷貝到B中。我們可以將兩個(gè)鏈表合并成
A1 -> B1 -> A2 -> B2 -> ... -> An -> Bn。
從A1節(jié)點(diǎn)出發(fā)，很容易找到A1的pRand指向的節(jié)點(diǎn)Ax,然后也就找到了Bx，將B1的pRand指向Bx也就完成了B1節(jié)點(diǎn)pRand的拷貝。依次類(lèi)推。
當(dāng)所有節(jié)點(diǎn)的pRand都拷貝完成后，再將合并鏈表分成兩個(gè)鏈表就可以了。
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)看到一輛車(chē)開(kāi)過(guò)的幾率是0.95，那么在10分鐘內(nèi)看到一輛車(chē)開(kāi)過(guò)的幾率是多少?(假設(shè)為常概率條件下)
假設(shè)10分鐘內(nèi)看到一輛車(chē)開(kāi)過(guò)的概率是x，那么沒(méi)有看到車(chē)開(kāi)過(guò)的概率就是1-x，30分鐘沒(méi)有看到車(chē)開(kāi)過(guò)的概率是(1-x)^3，也就是0.05。所以得到方程(1-x)^3 = 0.05
解方程得到x大約是0.63。
谷歌筆試題：從25匹馬中找出最快的3匹
最少需要7次。
首先將馬分成a,b,c,d,e 5個(gè)組，每組5匹，每組單獨(dú)比賽。然后將每組的第一名放在一起比賽。假設(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，所以在接下來(lái)的比賽中要包含這兩匹馬。如果a1快，那么第3名是a2或者b0，如果b0快，那么第3名是a1，b1或者c0。也就是說(shuō)第2名和第3名一定在a1，a2，b0，b1和c0當(dāng)中，所以在第7場(chǎng)比賽中包括這5匹馬就可以得到第2名和第3名。
所以7次比賽就可以獲得前3名的馬。
谷歌筆試題：將無(wú)向無(wú)環(huán)連通圖轉(zhuǎn)換成深度最小的樹(shù)
已知一個(gè)無(wú)向無(wú)環(huán)連通圖T的所有頂點(diǎn)和邊的信息，現(xiàn)需要將其轉(zhuǎn)換為一棵樹(shù)，要求樹(shù)的深度最小，請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法找到所有滿(mǎn)足要求的樹(shù)的根結(jié)點(diǎn)，并分析時(shí)空復(fù)雜度。
最簡(jiǎn)單直接的方法就是把每個(gè)節(jié)點(diǎn)都試一遍：
假設(shè)某個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)，計(jì)算樹(shù)的深度。當(dāng)遍歷完所有節(jié)點(diǎn)后，也就找到了使樹(shù)的深度最小的根節(jié)點(diǎn)。
但這個(gè)方法的復(fù)雜度很高。如果有n個(gè)節(jié)點(diǎn)，則時(shí)間復(fù)雜度為O(n^2)。
樹(shù)的深度取決于根節(jié)點(diǎn)到最深葉節(jié)點(diǎn)的距離，所以我們可以從葉節(jié)點(diǎn)入手。
葉節(jié)點(diǎn)會(huì)且只會(huì)和某一個(gè)節(jié)點(diǎn)連通(反之不成立，因?yàn)楦?jié)點(diǎn)也可能只和一個(gè)節(jié)點(diǎn)連通)，所以我們很容易找到所有可能的葉節(jié)點(diǎn)。
題目可以等價(jià)于找到了兩個(gè)葉節(jié)點(diǎn)，使得兩個(gè)葉節(jié)點(diǎn)之間的距離最遠(yuǎn)。根節(jié)點(diǎn)就是這兩個(gè)葉節(jié)點(diǎn)路徑的中間點(diǎn)(或者中間兩個(gè)點(diǎn)的任意一個(gè))。
我們可以每次都將連接度為1的節(jié)點(diǎn)刪掉，直到最后只剩下1個(gè)或2個(gè)節(jié)點(diǎn)，則這一個(gè)節(jié)點(diǎn)，或者兩個(gè)節(jié)點(diǎn)中的任意一個(gè)，就是我們要找的根節(jié)點(diǎn)。
谷歌筆試題：將字符串中的小寫(xiě)字母排在大寫(xiě)字母的前面
有一個(gè)由大小寫(xiě)組成的字符串，現(xiàn)在需要對(duì)它進(jìn)行修改，將其中的所有小寫(xiě)字母排在大寫(xiě)字母的前面(大寫(xiě)或小寫(xiě)字母之間不要求保持原來(lái)次序)。
初始化兩個(gè)int變量A和B，代表字符串中的兩個(gè)位置。開(kāi)始時(shí)A指向字符串的第一個(gè)字符，B指向字符串的最后一個(gè)字符。
逐漸增加A的值使其指向一個(gè)大寫(xiě)字母，逐漸減小B使其指向一個(gè)小寫(xiě)字母，交換A，B所指向的字符，然后繼續(xù)增加A，減小B....。
當(dāng)A>=B時(shí)，就完成了重新排序。
i指向最后一個(gè)小寫(xiě)字符，j尋找小寫(xiě)字符。
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]); } } }
谷歌筆試題：在重男輕女的國(guó)家里，男女的比例是多少?
在一個(gè)重男輕女的國(guó)家里，每個(gè)家庭都想生男孩，如果他們生的孩子是女孩，就再生一個(gè)，直到生下的是男孩為止。這樣的國(guó)家，男女比例會(huì)是多少?
還是1：1。
在所有出生的第一個(gè)小孩中，男女比例是1：1;在所有出生的第二個(gè)小孩中，男女比例是1：1;.... 在所有出生的第n個(gè)小孩中，男女比例還是1：1。
所以總的男女比例是1：1。
谷歌筆試題：如何拷貝特殊鏈表
有一個(gè)特殊的鏈表，其中每個(gè)節(jié)點(diǎn)不但有指向下一個(gè)節(jié)點(diǎn)的指針pNext，還有一個(gè)指向鏈表中任意節(jié)點(diǎn)的指針pRand，如何拷貝這個(gè)特殊鏈表?
拷貝pNext指針?lè)浅Ｈ菀�，所以題目的難點(diǎn)是如何拷貝pRand指針。
假設(shè)原來(lái)鏈表為A1 -> A2 ->... -> An，新拷貝鏈表是B1 -> B2 ->...-> Bn。
為了能夠快速的找到pRand指向的節(jié)點(diǎn)，并把對(duì)應(yīng)的關(guān)系拷貝到B中。我們可以將兩個(gè)鏈表合并成
A1 -> B1 -> A2 -> B2 -> ... -> An -> Bn。
從A1節(jié)點(diǎn)出發(fā)，很容易找到A1的pRand指向的節(jié)點(diǎn)Ax,然后也就找到了Bx，將B1的pRand指向Bx也就完成了B1節(jié)點(diǎn)pRand的拷貝。依次類(lèi)推。
當(dāng)所有節(jié)點(diǎn)的pRand都拷貝完成后，再將合并鏈表分成兩個(gè)鏈表就可以了。
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)看到一輛車(chē)開(kāi)過(guò)的幾率是0.95，那么在10分鐘內(nèi)看到一輛車(chē)開(kāi)過(guò)的幾率是多少?(假設(shè)為常概率條件下)
假設(shè)10分鐘內(nèi)看到一輛車(chē)開(kāi)過(guò)的概率是x，那么沒(méi)有看到車(chē)開(kāi)過(guò)的概率就是1-x，30分鐘沒(méi)有看到車(chē)開(kāi)過(guò)的概率是(1-x)^3，也就是0.05。所以得到方程(1-x)^3 = 0.05
解方程得到x大約是0.63。
谷歌筆試題：從25匹馬中找出最快的3匹
最少需要7次。
首先將馬分成a,b,c,d,e 5個(gè)組，每組5匹，每組單獨(dú)比賽。然后將每組的第一名放在一起比賽。假設(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，所以在接下來(lái)的比賽中要包含這兩匹馬。如果a1快，那么第3名是a2或者b0，如果b0快，那么第3名是a1，b1或者c0。也就是說(shuō)第2名和第3名一定在a1，a2，b0，b1和c0當(dāng)中，所以在第7場(chǎng)比賽中包括這5匹馬就可以得到第2名和第3名。
所以7次比賽就可以獲得前3名的馬。
【Google面試筆試題】相關(guān)文章：
名企面試試題 面試題目 Google02-24
google招聘筆試題02-18
Google筆試題目分享11-21
Google令人抓狂的面試題，看看你能承受幾個(gè)11-19
Google公司預(yù)選筆試試題02-18
Google面試官談面試技巧02-18
求教筆面試的時(shí)間02-23
面試題精選02-18