微軟筆試題目分享

微軟筆試題目分享

1、1000!有幾位數(shù)，為什么

2、F(n)=1n8n12

F(n)=2n2

F(n)=3n=6

F(n)=4n=other

使用+-*/和sign(n)函數(shù)組合出F(n)函數(shù)

sign(n)=0n=0

sign(n)=-1n

sign(n)=1n0

3、編一個程序求質數(shù)的和例如F(7)=1+3+5+7+11+13+17=58

輯考題此題源于1981年柏林的德國規(guī)律思索學院，98%的測驗者無法解題。

前提：

有五間房屋排成一列;全部房屋的外表顏色都不一樣;全部的屋主來自不同的國家

;全部的屋主都養(yǎng)不同的寵物;喝不同的飲料;抽不同的香煙。

提示：

英國人住在紅色房屋里;瑞典人養(yǎng)了一只狗;丹麥人喝茶;綠色的房子在白色的房

子的左邊;綠色房屋的屋主喝咖啡;抽PallMall香煙的屋主養(yǎng)鳥;黃色屋主抽Dunhill;

位于最中間的屋主喝牛奶;挪威人住在第一間房屋里;抽Blend的人住在養(yǎng)貓人家的隔壁;

養(yǎng)馬的屋主在抽Dunhill的人家的隔壁。抽BlueMaster的屋主喝啤酒;德國人抽Prince;

挪威人住在藍色房子隔壁;只喝開水的人家住在抽Blend的隔壁。

問：誰養(yǎng)魚?

五個人來自不同地方，住不同房子，養(yǎng)不同動物，吸不同牌子香煙，喝不同飲料，

喜愛不同食物。依據(jù)以下線索確定誰是養(yǎng)貓的人?

1.紅房子在藍房子的右邊，白房子的左邊(不肯定緊鄰)

2.黃房子的仆人來自香港，而且他的房子不在最左邊。

3.?員熱??娜俗詘?瓤筧??娜說母舯凇?

4.來自北京的人愛喝茅臺，住在來自上海的人的隔壁。

5.吸希爾頓香煙的人住在養(yǎng)馬的人?右邊隔壁。

6.愛喝啤酒的人也愛吃雞。

7.綠房子的人養(yǎng)狗。

8.愛吃面條的人住在養(yǎng)蛇的人的隔壁。

9.來自天津的人的鄰居(緊鄰)一個愛吃牛肉，另一個來自成都。

微軟筆試題目共享(二)

寫程序找出二叉樹的深度

一個樹的深度等于max(左子樹深度，右子樹深度)+1?？梢允褂眠f歸實現(xiàn)。

假設節(jié)點為定義為

structNode{

Node*left;Node*right;

};

intGetDepth(Node*root){

if(NULL==root){

return0;

}

intleft_depth=GetDepth(root-left);

intright_depth=GetDepth(root-right);

returnleft_depthright_depth?left_depth+1:right_depth+1;

}

利用天平砝碼，三次將140克的鹽分成50、90克兩份?

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

第一種方法：

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

其次次:稱2+7+9=18克鹽(相當于有2,7,9,18四個法碼)

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

剩下就是90克了.

其次種方法：

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

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

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

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

70+20=90

35+15=50

地球上有多少個滿意這樣條件的點

站在地球上的某一點，向南走一公里，然后向東走一公里，最終向北走一公里，回到了原點。地球上有多少個滿意這樣條件的點?

北極點滿意這個條件。

距離南極點很近的一個圈上也滿意這個條件。在這個圓圈上，向南走一公里，然后向東走一公里恰好繞南極點一圈，向北走一公里回到原點。

所以地球上總共有很多點滿意這個條件。

或者

首先，在地球表面上，南北走向是沿著經度方向，東西是沿著緯度方向。假如你始終往北走就會達到北極點，往南走就到了南極點。因此，向南走一公里，然后向東走一公里，最終向北走一公里，回到了原點，一種狀況就是，動身點是在北極點，這樣向南走一公里，然后向東走任意幾公里，最終向北走一公里，最終都會回到北極點;

其次，可以這么認為假如從A點向南走一公里到達B點，那么若向東走一公里能回到B，那么最終向北走一公里，就能回到了原點A。這樣就可以先找出在南北極點四周找出繞一周只有1公里的圈，那么這個圈落在南極四周時，只要往北推1公里，此時該圈上的點都能滿意;若這個圈落在北極四周時，能不能往北推1公里我就不分析了。反正在南極四周能找到任意多個點就能回到這個問題了

正確標注水果籃

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

從標注成既有蘋果也有橘子的水果籃中選取一個進行檢查。

假如是橘子，則此籃中只有橘子;標有橘子的水果籃中只有蘋果;標有蘋果的水果籃中既有蘋果也有橘子。

假如是蘋果，則此籃中只有蘋果;標有蘋果的水果籃中只有橘子;標有橘子的水果籃中既有蘋果也有橘子。

不利用浮點運算，畫一個圓

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

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

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

我們可以從點(0，r)開頭，搜尋右(1，r)，下(0，r-1)，右下(1，r-1)三個點到圓心的距離，選擇距圓心距離最接近r的點作為下一個點。反復進行這種運算，直至到達點(r，0)。

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

將一個句子按單詞反序

將一個句子按單詞反序。比如"hibaiducommianshiti'，反序后變?yōu)?mianshiticombaiduhi'。

可以分兩步走：

第一步按找字母反序，"hibaiducommianshiti'變?yōu)?itihsnaimmocudiabih'。

其次部將每個單詞中的字母反序，"itihsnaimmocudiabih'變成"mianshiticombaiduhi'。

這個方法可以在原字符串上進行，只需要幾個整數(shù)變量來保持指針即可，空間簡單度低。

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

設此整數(shù)為x。

方法1：

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

將除得的結果進行上面運算，直到結果為0。

方法2：

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

將x和1進行按位與操作(x1)，假如結果為1，說明最終一位是1，統(tǒng)計值加1。

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

方法3：

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

快速求取一個整數(shù)的7倍

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

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

推斷一個數(shù)是不是2的n次冪

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

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

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

證明：

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

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

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

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

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

推斷數(shù)組中是否包含重復數(shù)字

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

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

如何將蛋糕切成相等的兩份

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

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

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

建立一個hash_map，key為鏈表中已經遍歷的節(jié)點內容，開頭時為空。

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

-假如節(jié)點內容已經在hash_map中存在，則刪除此節(jié)點，連續(xù)向后遍歷;

-假如節(jié)點內容不在hash_map中，則保留此節(jié)點，將節(jié)點內容添加到hash_map中，連續(xù)向后遍歷。

小明一家5口如何過橋?

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

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

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

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

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

總共用29s。

題目的關鍵是讓速度差不多的一起走，免得過于拖累較快的一個人。

編一個程序求質數(shù)的和

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

方法1：

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

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

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

方法2：

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

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

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

空間簡單度為O(m)，時間簡單度為O(mn)，其中m為質數(shù)的