微軟谷歌筆試題目

　　微軟和谷歌公司是我國的著名公司，微軟和谷歌公司的筆試題目有哪些呢?

　　微軟筆試題：地球上有多少個(gè)滿足這樣條件的點(diǎn)

　　站在地球上的某一點(diǎn)，向南走一公里，然后向東走一公里，最后向北走一公里，回到了原點(diǎn)。地球上有多少個(gè)滿足這樣條件的點(diǎn)?

　　北極點(diǎn)滿足這個(gè)條件。

　　距離南極點(diǎn)很近的一個(gè)圈上也滿足這個(gè)條件。在這個(gè)圓圈上，向南走一公里，然后向東走一公里恰好繞南極點(diǎn)一圈，向北走一公里回到原點(diǎn)。

　　所以地球上總共有無數(shù)點(diǎn)滿足這個(gè)條件。

　　或者

　　首先，在地球表面上，南北走向是沿著經(jīng)度方向，東西是沿著緯度方向。如果你一直往北走就會(huì)達(dá)到北極點(diǎn)，往南走就到了南極點(diǎn)。因此，向南走一公里，然后向東走一公里，最后向北走一公里，回到了原點(diǎn)，一種情況就是，出發(fā)點(diǎn)是在北極點(diǎn)，這樣向南走一公里，然后向東走任意幾公里，最后向北走一公里，最后都會(huì)回到北極點(diǎn);

　　其次，可以這么認(rèn)為如果從A點(diǎn)向南走一公里到達(dá)B點(diǎn)，那么若向東走一公里能回到B，那么最后向北走一公里，就能回到了原點(diǎn)A。這樣就可以先找出在南北極點(diǎn)附近找出繞一周只有1公里的圈，那么這個(gè)圈落在南極附近時(shí)，只要往北推1公里，此時(shí)該圈上的點(diǎn)都能滿足;若這個(gè)圈落在北極附近時(shí)，能不能往北推1公里我就不分析了。反正在南極附近能找到任意多個(gè)點(diǎn)就能回到這個(gè)問題了

　　微軟筆試題：利用天平砝碼，三次將140克的鹽 分成50、90克兩份?

　　有一個(gè)天平，2克和7克砝碼各一個(gè)。如何利用天平砝碼在三次內(nèi)將140克鹽分成50，90克兩份。

　　第一種方法：

　　第一次:先稱 7+2克鹽 (相當(dāng)于有三個(gè)法碼2,7,9)

　　第二次:稱2+7+9=18克鹽 (相當(dāng)于有2,7,9,18四個(gè)法碼)

　　第三次:稱7+18=x+2,得出x是23，23+9+18=50克鹽.

　　剩下就是90克了.

　　第二種方法：

　　1.先把140克鹽分為兩份，每份70克

　　2.在把70克分為兩份，每份35克

　　3.然后把兩個(gè)砝碼放在天平兩邊，把35克面粉分成兩份也放在兩邊(15+7=20+2)

　　現(xiàn)在有四堆面粉70，35，15，20，分別組合得到

　　70+20=90

　　35+15=50

　　微軟筆試題：正確標(biāo)注水果籃

　　有三個(gè)水果籃。其中一個(gè)里面只有蘋果，一個(gè)里面只有橘子，另外一個(gè)既有蘋果又有橘子。每個(gè)水果籃上都有標(biāo)簽，但標(biāo)簽都是錯(cuò)的。如何檢查某個(gè)水果籃中的一個(gè)水果，然后正確標(biāo)注每個(gè)水果籃?

　　從標(biāo)注成既有蘋果也有橘子的水果籃中選取一個(gè)進(jìn)行檢查。

　　如果是橘子，則此籃中只有橘子;標(biāo)有橘子的水果籃中只有蘋果;標(biāo)有蘋果的水果籃中既有蘋果也有橘子。

　　如果是蘋果，則此籃中只有蘋果;標(biāo)有蘋果的水果籃中只有橘子;標(biāo)有橘子的水果籃中既有蘋果也有橘子。

　　微軟筆試題：不利用浮點(diǎn)運(yùn)算，畫一個(gè)圓

　　不利用浮點(diǎn)運(yùn)算，在屏幕上畫一個(gè)圓 (x**2 + y**2 = r**2，其中 r 為正整數(shù))。

　　考慮到圓的對稱性，我們只需考慮第一象限即可。

　　等價(jià)于找到一條連接點(diǎn)(0，r)到點(diǎn)(r，0)的一條曲線，曲線上的點(diǎn)距圓心(0，0)的距離最接近 r。

　　我們可以從點(diǎn)(0，r)開始，搜索右(1，r)，下(0，r-1)，右下(1，r-1)三個(gè)點(diǎn)到圓心的距離，選擇距圓心距離最接近 r 的點(diǎn)作為下一個(gè)點(diǎn)。反復(fù)進(jìn)行這種運(yùn)算，直至到達(dá)點(diǎn)(r，0)。

　　由于不能利用浮點(diǎn)運(yùn)算，所以距離的比較只能在距離平方的基礎(chǔ)上進(jìn)行。也就是比較 x**2 + y**2 和 r**2之間的差值。

　　微軟筆試題：將一個(gè)句子按單詞反序

　　將一個(gè)句子按單詞反序。比如 “hi baidu com mianshiti”，反序后變?yōu)?“mianshiti com baidu hi”。

　　可以分兩步走：

　　第一步按找字母反序，“hi baidu com mianshiti” 變?yōu)?“itihsnaim moc udiab ih”。

　　第二部將每個(gè)單詞中的字母反序，“itihsnaim moc udiab ih” 變成 “mianshiti com baidu hi”。

　　這個(gè)方法可以在原字符串上進(jìn)行，只需要幾個(gè)整數(shù)變量來保持指針即可，空間復(fù)雜度低。

　　微軟筆試題：計(jì)算n bit的整數(shù)中有多少bit 為1

　　設(shè)此整數(shù)為x。

　　方法1：

　　讓此整數(shù)除以2，如果余數(shù)為1，說明最后一位是1，統(tǒng)計(jì)值加1。

　　將除得的結(jié)果進(jìn)行上面運(yùn)算，直到結(jié)果為0。

　　方法2：

　　考慮除法復(fù)雜度有些高，可以使用移位操作代替除法。

　　將 x 和 1 進(jìn)行按位與操作(x&1)，如果結(jié)果為1，說明最后一位是1，統(tǒng)計(jì)值加1。

　　將x 向右一位(x >> 1)，重復(fù)上面過程，直到移位后結(jié)果為0。

　　方法3：

　　如果需要統(tǒng)計(jì)很多數(shù)字，并且內(nèi)存足夠大，可以考慮將每個(gè)數(shù)對應(yīng)的bit為1的數(shù)量記錄下來，這樣每次計(jì)算只是一次查找操作。

　　微軟筆試題：判斷一個(gè)數(shù)是不是2的n次冪

　　設(shè)要判斷的數(shù)是無符號整數(shù)X。

　　首先判斷X是否為0，如果為0則不是2的n次冪，返回。

　　X和X-1進(jìn)行按位與操作，如果結(jié)果是0，則說明這個(gè)數(shù)是2的n次冪;如果結(jié)果非0，則說明這個(gè)數(shù)不是2 的n次冪。

　　證明：

　　如果是2的n次冪，則此數(shù)用二進(jìn)制表示時(shí)只有一位是1，其它都是0。減1后，此位變成0，后面的位變成1，所以按位與后結(jié)果是0。

　　如果不是2的n次冪，則此數(shù)用二進(jìn)制表示時(shí)有多位是1。減1后，只有最后一個(gè)1變成0，前面的 1還是1，所以按位與后結(jié)果不是0。

　　微軟筆試題：三只螞蟻不相撞的概率是多少

　　在三角形的三個(gè)頂點(diǎn)上各有一只螞蟻，它們向另一個(gè)頂點(diǎn)運(yùn)動(dòng)，目標(biāo)隨機(jī)(可能為另外兩個(gè)頂點(diǎn)的任意一個(gè))。問三只螞蟻不相撞的概率是多少?

　　如果螞蟻順時(shí)針爬行記為0，逆時(shí)針爬行記為1。那么三只螞蟻的狀態(tài)可能為000，001，...，110，111中的任意一個(gè)，且為每種狀態(tài)的概率相等。在這8種狀態(tài)中，只有000和111可以避免相撞，所以螞蟻不相撞的概率是1/4。

　　微軟筆試題：判斷數(shù)組中是否包含重復(fù)數(shù)字

　　給定一個(gè)長度為N的數(shù)組，其中每個(gè)元素的取值范圍都是1到N。判斷數(shù)組中是否有重復(fù)的數(shù)字。(原數(shù)組不必保留)

　　給定一個(gè)長度為N的數(shù)組，其中每個(gè)元素的取值范圍都是1到N。判斷數(shù)組中是否有重復(fù)的數(shù)字。(原數(shù)組不必保留)

　　微軟筆試題：如何將蛋糕切成相等的兩份

　　一塊長方形的蛋糕，其中有一個(gè)小長方形的空洞(角度任意)。使用一把直刀，如何一刀將蛋糕切成相等的兩份?

　　通過長方形中心的的任意直線都能將長方形等分，所以連接兩個(gè)長方形的中心點(diǎn)的直線可以等分這個(gè)蛋糕。

　　一個(gè)沒有排序的鏈表，比如list={a,l,x,b,e,f,f,e,a,g,h,b,m}，請去掉重復(fù)項(xiàng)，并保留原順序，以上鏈表去掉重復(fù)項(xiàng)后為newlist={a,l,x,b,e,f,g,h,m}，請寫出一個(gè)高效算法(時(shí)間比空間更重要)。

　　建立一個(gè)hash_map，key為鏈表中已經(jīng)遍歷的節(jié)點(diǎn)內(nèi)容，開始時(shí)為空。

　　從頭開始遍歷鏈表中的節(jié)點(diǎn)：

　　- 如果節(jié)點(diǎn)內(nèi)容已經(jīng)在hash_map中存在，則刪除此節(jié)點(diǎn)，繼續(xù)向后遍歷;

　　- 如果節(jié)點(diǎn)內(nèi)容不在hash_map中，則保留此節(jié)點(diǎn)，將節(jié)點(diǎn)內(nèi)容添加到hash_map中，繼續(xù)向后遍歷。

　　微軟筆試題：小明一家5口如何過橋?

　　小明一家過一座橋，過橋時(shí)是黑夜，所以必須有燈。現(xiàn)在小明過橋要1秒，小明的弟弟要3秒，小明的爸爸要6秒，小明的媽媽要8秒，小明的爺爺要12秒。每次此橋最多可過兩人，而過橋的速度依過橋最慢者而定，而且燈在點(diǎn)燃后30秒就會(huì)熄滅。問：小明一家如何過橋?

　　小明與弟弟過去，小明回來，用4s;

　　媽媽與爺爺過去，弟弟回來，用15s;

　　小明與弟弟過去，小明回來，用4s;

　　小明與爸爸過去，用6s;

　　總共用29s。

　　題目的關(guān)鍵是讓速度差不多的一起走，免得過于拖累較快的一個(gè)人。

　　微軟筆試題：編一個(gè)程序求質(zhì)數(shù)的和

　　編一個(gè)程序求質(zhì)數(shù)的和，例如F(7) = 2+3+5+7+11+13+17=58。

　　方法1：

　　對于從2開始的遞增整數(shù)n進(jìn)行如下操作：

　　用 [2，n-1] 中的數(shù)依次去除n，如果余數(shù)為0，則說明n不是質(zhì)數(shù);如果所有余數(shù)都不是0，則說明n是質(zhì)數(shù)，對其進(jìn)行加和。

　　空間復(fù)雜度為O(1)，時(shí)間復(fù)雜度為O(n^2)，其中n為需要找到的最大質(zhì)數(shù)值(例子對應(yīng)的值為17)。

　　方法2：

　　可以維護(hù)一個(gè)質(zhì)數(shù)序列，這樣當(dāng)需要判斷一個(gè)數(shù)是否是質(zhì)數(shù)時(shí)，只需判斷是否能被比自己小的質(zhì)數(shù)整除即可。

　　對于從2開始的遞增整數(shù)n進(jìn)行如下操作：

　　用 [2，n-1] 中的質(zhì)數(shù)(2，3，5，7，開始時(shí)此序列為空)依次去除n，如果余數(shù)為0，則說明n不是質(zhì)數(shù);如果所有余數(shù)都不是0，則說明n是質(zhì)數(shù)，將此質(zhì)數(shù)加入質(zhì)數(shù)序列，并對其進(jìn)行加和。

　　空間復(fù)雜度為O(m)，時(shí)間復(fù)雜度為O(mn)，其中m為質(zhì)數(shù)的個(gè)數(shù)(例子對應(yīng)的值為7)，n為需要找到的最大質(zhì)數(shù)值(例子對應(yīng)的值為17)。

　　方法3：

　　也可以不用除法，而用加法。

　　申請一個(gè)足夠大的空間，每個(gè)bit對應(yīng)一個(gè)整數(shù)，開始將所有的bit都初始化為0。

　　對于已知的質(zhì)數(shù)(開始時(shí)只有2)，將此質(zhì)數(shù)所有的倍數(shù)對應(yīng)的bit都改為1，那么最小的值為0的bit對應(yīng)的數(shù)就是一個(gè)質(zhì)數(shù)。對新獲得的質(zhì)數(shù)的倍數(shù)也進(jìn)行標(biāo)注。

　　對這樣獲得的質(zhì)數(shù)序列累加就可以獲得質(zhì)數(shù)和。

　　空間復(fù)雜度為O(n)，時(shí)間負(fù)責(zé)度為O(n)，其中n為需要找到的最大質(zhì)數(shù)值(例子對應(yīng)的值為17)。

　　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：

　　使用二分查找法，對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)鍵字(比如，人們在谷歌搜索時(shí)不斷輸入的關(guān)鍵字)。如何才能從這個(gè)無窮盡的流中隨機(jī)的選取1000個(gè)關(guān)鍵字?

　　定義長度為1000的數(shù)組。

　　對于數(shù)據(jù)流中的前1000個(gè)關(guān)鍵字，顯然都要放到數(shù)組中。

　　對于數(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的概率被選中。

　　對于后面的關(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è)角度，對應(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ù)在哪組中。然后對那一組按照同樣的方法進(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ù)字插入到對應(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ù)。

　　請?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è)指針指向序列尾端。