Google面試筆試題

時(shí)間：2024-05-18 21:12:22 面試筆試我要投稿

相關(guān)推薦

Google面試筆試題

　　谷歌筆試題：將無(wú)向無(wú)環(huán)連通圖轉(zhuǎn)換成深度最小的樹

Google面試筆試題

　　已知一個(gè)無(wú)向無(wú)環(huán)連通圖T的所有頂點(diǎn)和邊的信息，現(xiàn)需要將其轉(zhuǎn)換為一棵樹，要求樹的深度最小，請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法找到所有滿足要求的樹的根結(jié)點(diǎn)，并分析時(shí)空復(fù)雜度。

　　最簡(jiǎn)單直接的方法就是把每個(gè)節(jié)點(diǎn)都試一遍：

　　假設(shè)某個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)，計(jì)算樹的深度。當(dāng)遍歷完所有節(jié)點(diǎn)后，也就找到了使樹的深度最小的根節(jié)點(diǎn)。

　　但這個(gè)方法的復(fù)雜度很高。如果有n個(gè)節(jié)點(diǎn)，則時(shí)間復(fù)雜度為O(n^2)。

　　樹的深度取決于根節(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)。

　　谷歌筆試題：將字符串中的小寫字母排在大寫字母的前面

　　有一個(gè)由大小寫組成的字符串，現(xiàn)在需要對(duì)它進(jìn)行修改，將其中的所有小寫字母排在大寫字母的前面(大寫或小寫字母之間不要求保持原來(lái)次序)。

　　初始化兩個(gè)int變量A和B，代表字符串中的兩個(gè)位置。開始時(shí)A指向字符串的第一個(gè)字符，B指向字符串的最后一個(gè)字符。

　　逐漸增加A的值使其指向一個(gè)大寫字母，逐漸減小B使其指向一個(gè)小寫字母，交換A，B所指向的字符，然后繼續(xù)增加A，減小B....。

　　當(dāng)A>=B時(shí)，就完成了重新排序。

　　i指向最后一個(gè)小寫字符，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]); } } }

　　谷歌筆試題：在重男輕女的國(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指針非常容易，所以題目的難點(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的拷貝。依次類推。

　　當(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)看到一輛車開過的幾率是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個(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。也就是說第2名和第3名一定在a1，a2，b0，b1和c0當(dāng)中，所以在第7場(chǎng)比賽中包括這5匹馬就可以得到第2名和第3名。

　　所以7次比賽就可以獲得前3名的馬。

　　谷歌筆試題：將無(wú)向無(wú)環(huán)連通圖轉(zhuǎn)換成深度最小的樹

　　最簡(jiǎn)單直接的方法就是把每個(gè)節(jié)點(diǎn)都試一遍：

　　但這個(gè)方法的復(fù)雜度很高。如果有n個(gè)節(jié)點(diǎn)，則時(shí)間復(fù)雜度為O(n^2)。

　　樹的深度取決于根節(jié)點(diǎn)到最深葉節(jié)點(diǎn)的距離，所以我們可以從葉節(jié)點(diǎn)入手。

　　谷歌筆試題：將字符串中的小寫字母排在大寫字母的前面

　　初始化兩個(gè)int變量A和B，代表字符串中的兩個(gè)位置。開始時(shí)A指向字符串的第一個(gè)字符，B指向字符串的最后一個(gè)字符。

　　逐漸增加A的值使其指向一個(gè)大寫字母，逐漸減小B使其指向一個(gè)小寫字母，交換A，B所指向的字符，然后繼續(xù)增加A，減小B....。

　　當(dāng)A>=B時(shí)，就完成了重新排序。

　　i指向最后一個(gè)小寫字符，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]); } } }

　　谷歌筆試題：在重男輕女的國(guó)家里，男女的比例是多少?