微軟筆試題目分享

微軟筆試題目分享

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、編一個(gè)程序求質(zhì)數(shù)的和例如F(7)=1+3+5+7+11+13+17=58

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

前提：

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

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

提示：

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

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

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

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

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

問：誰養(yǎng)魚?

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

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

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

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

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

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

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

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

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

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

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

微軟筆試題目共享(二)

寫程序找出二叉樹的深度

一個(gè)樹的深度等于max(左子樹深度，右子樹深度)+1。可以使用遞歸實(shí)現(xiàn)。

假設(shè)節(jié)點(diǎn)為定義為

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克兩份?

有一個(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

地球上有多少個(gè)滿意這樣條件的點(diǎn)

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

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

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

所以地球上總共有很多點(diǎn)滿意這個(gè)條件。

或者

首先，在地球表面上，南北走向是沿著經(jīng)度方向，東西是沿著緯度方向。假如你始終往北走就會(huì)達(dá)到北極點(diǎn)，往南走就到了南極點(diǎn)。因此，向南走一公里，然后向東走一公里，最終向北走一公里，回到了原點(diǎn)，一種狀況就是，動(dòng)身點(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è)問題了

正確標(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ù))。

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

等價(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è)句子按單詞反序。比如"hibaiducommianshiti'，反序后變?yōu)?mianshiticombaiduhi'。

可以分兩步走：

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

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

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

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

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

方法1：

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

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

方法2：

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

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

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

方法3：

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

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

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

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

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

設(shè)要推斷的數(shù)是無符號(hào)整數(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}，請(qǐng)去掉重復(fù)項(xiàng)，并保留原挨次，以上鏈表去掉重復(fù)項(xiàng)后為newlist={a,l,x,b,e,f,g,h,m}，請(qǐng)寫出一個(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í)是黑夜，所以必需有燈?，F(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：

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

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

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

方法2：

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

對(duì)于從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ù)序列，并對(duì)其進(jìn)行加和。

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