微軟筆試題目

　　微軟在IT界依然是數一數二的企業(yè)了，不少人的夢(mèng)想都是進(jìn)入微軟公司。那么在這之前的面試以及筆試就需要進(jìn)行一下準備了。那么這里就來(lái)看看小編為大家總結的微軟筆試題吧。

　　微軟筆試題：

　　寫(xiě)程序找出二叉樹(shù)的深度

　　一個(gè)樹(shù)的深度等于max(左子樹(shù)深度，右子樹(shù)深度)+1�？梢允褂眠f歸實(shí)現。

　　假設節點(diǎn)為定義為

　　struct Node {

　　Node* left; Node* right;

　　};

　　int GetDepth(Node* root) {

　　if (NULL == root) {

　　return 0;

　　}

　　int left_depth = GetDepth(root->left);

　　int right_depth = GetDepth(root->right);

　　return left_depth > right_depth ? left_depth + 1 :right_depth + 1;

　　}

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

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

　　第一種方法：

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

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

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

　　剩下就是90克了.

　　第二種方法：

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

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

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

　　現在有四堆面粉70，35，15，20，分別組合得到

　　70+20=90

　　35+15=50

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

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

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

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

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

　　或者

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

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

　　微軟筆試題：正確標注水果籃

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

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

　　如果是橘子，則此籃中只有橘子;標有橘子的水果籃中只有蘋(píng)果;標有蘋(píng)果的水果籃中既有蘋(píng)果也有橘子。

　　如果是蘋(píng)果，則此籃中只有蘋(píng)果;標有蘋(píng)果的水果籃中只有橘子;標有橘子的水果籃中既有蘋(píng)果也有橘子。

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

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

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

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

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

　　由于不能利用浮點(diǎn)運算，所以距離的比較只能在距離平方的基礎上進(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è)整數變量來(lái)保持指針即可，空間復雜度低。

　　微軟筆試題：計算n bit的整數中有多少bit 為1

　　設此整數為x。

　　方法1：

　　讓此整數除以2，如果余數為1，說(shuō)明最后一位是1，統計值加1。

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

　　方法2：

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

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

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

　　方法3：

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

　　微軟筆試題：快速求取一個(gè)整數的7倍

　　乘法相對比較慢，所以快速的方法就是將這個(gè)乘法轉換成加減法和移位操作。

　　可以將此整數先左移三位(×8)然后再減去原值：X << 3 - X。

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

　　設要判斷的數是無(wú)符號整數X。

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

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

　　證明：

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

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

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

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

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

　　微軟筆試題：判斷數組中是否包含重復數字

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

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

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

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

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

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

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

　　從頭開(kāi)始遍歷鏈表中的節點(diǎn)：

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

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

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

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

　　小明與弟弟過(guò)去，小明回來(lái)，用4s;

　　媽媽與爺爺過(guò)去，弟弟回來(lái)，用15s;

　　小明與弟弟過(guò)去，小明回來(lái)，用4s;

　　小明與爸爸過(guò)去，用6s;

　　總共用29s。

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

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

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

　　方法1：

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

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

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

　　方法2：

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

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

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

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

　　方法3：

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

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

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

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

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

　　微軟筆試的題目

　　一般來(lái)說(shuō)，微軟的面試問(wèn)題分為４類(lèi)：謎語(yǔ)類(lèi)試題、數學(xué)型試題、智力性試題、應用程序類(lèi)試題。先舉兩個(gè)謎語(yǔ)類(lèi)試題：

　　1美國有多少輛汽車(chē)？

　　2、將汽車(chē)鑰匙插入車(chē)門(mén)，向哪個(gè)方向旋轉就可以打開(kāi)車(chē)鎖？

　　小張（復旦大學(xué)管理學(xué)院９９級學(xué)生）：這兩道試題并不難，我想他可能只是想考察一下應聘者的應變能力，亦即在短時(shí)間內快速應對不規范問(wèn)題的能力。

　　孫先生（某大型跨國企業(yè)員工）：很明顯，這是兩道答案開(kāi)放的試題。我想它是為了考察應聘者能否對一個(gè)問(wèn)題進(jìn)行符合邏輯的創(chuàng )造性的思考，并迅速通過(guò)這種思考尋求到解決問(wèn)題的辦法。至于答案，發(fā)問(wèn)者顯然并不關(guān)心。

　　裘副教授（復旦大學(xué)）：?jiǎn)?wèn)題是開(kāi)放性的，但指向性也很明顯。應聘者是否能在很短的時(shí)間對出其不意的問(wèn)題作出反應，并能夠有邏輯地回答這樣的問(wèn)題，發(fā)問(wèn)者同樣希望能夠得到出其不意的答案。有不少人通過(guò)在網(wǎng)上搜集這種試題來(lái)準備答案，顯然大違發(fā)問(wèn)者的本意。重復的答案都不是好答案。

　　下面是兩道數學(xué)型的試題：

　　1、1000 有幾位數，為什么？

　　2、編一個(gè)程序求質(zhì)數的和，例如Ｆ ７ ＝１＋３＋５＋７＋１１＋１３＋１７＝５８。

　　小陸（復旦大學(xué)物理系99級學(xué)生）：數學(xué)試題與應用程序試題是微軟面試中指向性最明顯的一類(lèi)試題。這些試題就是考察應聘者的數學(xué)能力與計算機能力。

　　師女士（某咨詢(xún)公司高級顧問(wèn)）：微軟是一家電腦軟件公司，當然要求其員工有一定的計算機和數學(xué)能力，面試中自然就會(huì )考察這類(lèi)能力。微軟的上述面試題目就考察了應聘人員對基礎知識的掌握程度、對基礎知識的應用能力，甚至暗含了對計算機基本原理的考察。所以，這樣的面試題目的確很“毒辣”，足以篩選到合適的人。

　　下面是智力題：

　�。�、燒一根不均勻的繩需用一個(gè)小時(shí)，如何用它來(lái)判斷半個(gè)小時(shí)？

　　小何（復旦大學(xué)計算機系00級碩士研究生）：我覺(jué)得我很難理解微軟這一部分的試題，我大多數時(shí)候并不知道他考察我什么，有時(shí)候我甚至覺(jué)得它僅僅是腦筋急轉彎。不過(guò)，我記得李開(kāi)復在央視的節目里說(shuō)過(guò)，他們的考察內容是應聘者的可塑性。

　　石先生（某大型國企職工）：我認為這一部分的問(wèn)題有很大的隨意性，主要是考察應聘者的智商，但是因為問(wèn)題的不同又有不同的考察方向，比如第一個(gè)問(wèn)題就考察了應聘者的逆向思維能力，第二個(gè)就考察了應聘者的觀(guān)察能力與細致程度。

　　于先生（某外資公司人事主管）：我不知道微軟出這些題目的用意，但在我看來(lái)，智力題是微軟面試中最好的考察方式。不僅考察的指向不同，就連問(wèn)題的答案有時(shí)候也能給人以啟發(fā)。比如上述第二個(gè)問(wèn)題，如果你能找到答案，它就會(huì )幫你理解企業(yè)的資源使用組合方式，經(jīng)過(guò)優(yōu)化以后可以發(fā)揮不同的作用。不同的管理者就會(huì )使用不同的組合方式，當然結果就會(huì )不一樣！

【微軟筆試題目】相關(guān)文章：

微軟的筆試題目10-26

微軟筆試題目精選01-15

微軟筆試題目03-17

微軟筆試題目 110-13

有趣的微軟筆試題目12-19

微軟筆試題目分享12-03

微軟筆試題目（附答案）10-28

微軟求職筆試中考察的題目11-23

微軟筆試面試題目03-12