微軟筆試題目分享
微軟筆試題目分享(一)
1、1000!有幾位數(shù)，為什么
2、F(n)=1 n>8 n<12
F(n)=2 n<2
F(n)=3 n=6
F(n)=4 n=other
使用+ - * /和sign(n)函數(shù)組合出F(n)函數(shù)
sign(n)=0 n=0
sign(n)=-1 n<
sign(n)=1 n>0
3、編一個(gè)程序求質(zhì)數(shù)的和例如F(7)=1+3+5+7+11+13+17=58
輯考題 此題源于1981年柏林的德國(guó)邏輯思考學(xué)院，98%的測(cè)驗(yàn)者無(wú)法解題。
前提：
有五間房屋排成一列;所有房屋的外表顏色都不一樣;所有的屋主來(lái)自不同的國(guó)家
;所有的屋主都養(yǎng)不同的寵物;喝不同的飲料;抽不同的香煙。
提示：
英國(guó)人住在紅色房屋里;瑞典人養(yǎng)了一只狗;丹麥人喝茶;綠色的房子在白色的房
子的左邊;綠色房屋的屋主喝咖啡;抽Pall Mall香煙的屋主養(yǎng)鳥(niǎo);黃色屋主抽Dunhill;
位于最中間的屋主喝牛奶;挪威人住在第一間房屋里;抽Blend的人住在養(yǎng)貓人家的隔壁;
養(yǎng)馬的屋主在抽Dunhill的人家的隔壁。抽Blue Master的屋主喝啤酒;德國(guó)人抽Prince;
挪威人住在藍(lán)色房子隔壁;只喝開(kāi)水的人家住在抽Blend的隔壁。
問(wèn)：誰(shuí)養(yǎng)魚(yú)?
五個(gè)人來(lái)自不同地方，住不同房子，養(yǎng)不同動(dòng)物，吸不同牌子香煙，喝不同飲料，
喜歡不同食物。根據(jù)以下線(xiàn)索確定誰(shuí)是養(yǎng)貓的人?
1.紅房子在藍(lán)房子的右邊，白房子的左邊(不一定緊鄰)
2.黃房子的主人來(lái)自香港，而且他的房子不在最左邊。
3.?員熱??娜俗≡詘?瓤筧??娜說(shuō)母舯凇?
4.來(lái)自北京的人愛(ài)喝茅臺(tái)，住在來(lái)自上海的人的隔壁。
5.吸希爾頓香煙的人住在養(yǎng)馬的人?右邊隔壁。
6.愛(ài)喝啤酒的人也愛(ài)吃雞。
7.綠房子的人養(yǎng)狗。
8.愛(ài)吃面條的人住在養(yǎng)蛇的人的隔壁。
9.來(lái)自天津的人的鄰居(緊鄰)一個(gè)愛(ài)吃牛肉，另一個(gè)來(lái)自成都。
微軟筆試題目分享(二)
寫(xiě)程序找出二叉樹(shù)的深度
一個(gè)樹(shù)的深度等于max(左子樹(shù)深度，右子樹(shù)深度)+1�？梢允褂眠f歸實(shí)現(xiàn)。
假設(shè)節(jié)點(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è)。如何利用天平砝碼在三次內(nèi)將140克鹽分成50，90克兩份。
第一種方法：
第一次:先稱(chēng) 7+2克鹽 (相當(dāng)于有三個(gè)法碼2,7,9)
第二次:稱(chēng)2+7+9=18克鹽 (相當(dāng)于有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)
現(xiàn)在有四堆面粉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ú)數(shù)點(diǎn)滿(mǎ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)都能滿(mǎn)足;若這個(gè)圈落在北極附近時(shí)，能不能往北推1公里我就不分析了。反正在南極附近能找到任意多個(gè)點(diǎn)就能回到這個(gè)問(wèn)題了
正確標(biāo)注水果籃
有三個(gè)水果籃。其中一個(gè)里面只有蘋(píng)果，一個(gè)里面只有橘子，另外一個(gè)既有蘋(píng)果又有橘子。每個(gè)水果籃上都有標(biāo)簽，但標(biāo)簽都是錯(cuò)的。如何檢查某個(gè)水果籃中的一個(gè)水果，然后正確標(biāo)注每個(gè)水果籃?
從標(biāo)注成既有蘋(píng)果也有橘子的水果籃中選取一個(gè)進(jìn)行檢查。
如果是橘子，則此籃中只有橘子;標(biāo)有橘子的水果籃中只有蘋(píng)果;標(biāo)有蘋(píng)果的水果籃中既有蘋(píng)果也有橘子。
如果是蘋(píng)果，則此籃中只有蘋(píng)果;標(biāo)有蘋(píng)果的水果籃中只有橘子;標(biāo)有橘子的水果籃中既有蘋(píng)果也有橘子。
不利用浮點(diǎn)運(yùn)算，畫(huà)一個(gè)圓
不利用浮點(diǎn)運(yùn)算，在屏幕上畫(huà)一個(gè)圓 (x**2 + y**2 = r**2，其中 r 為正整數(shù))。
考慮到圓的對(duì)稱(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)。反復(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ù)變量來(lái)保持指針即可，空間復(fù)雜度低。
微軟筆試題：計(jì)算n bit的整數(shù)中有多少bit 為1
設(shè)此整數(shù)為x。
方法1：
讓此整數(shù)除以2，如果余數(shù)為1，說(shuō)明最后一位是1，統(tǒng)計(jì)值加1。
將除得的結(jié)果進(jìn)行上面運(yùn)算，直到結(jié)果為0。
方法2：
考慮除法復(fù)雜度有些高，可以使用移位操作代替除法。
將 x 和 1 進(jìn)行按位與操作(x&1)，如果結(jié)果為1，說(shuō)明最后一位是1，統(tǒng)計(jì)值加1。
將x 向右一位(x >> 1)，重復(fù)上面過(guò)程，直到移位后結(jié)果為0。
方法3：
如果需要統(tǒng)計(jì)很多數(shù)字，并且內(nèi)存足夠大，可以考慮將每個(gè)數(shù)對(duì)應(yīng)的bit為1的數(shù)量記錄下來(lái)，這樣每次計(jì)算只是一次查找操作。
快速求取一個(gè)整數(shù)的7倍
乘法相對(duì)比較慢，所以快速的方法就是將這個(gè)乘法轉(zhuǎn)換成加減法和移位操作。
可以將此整數(shù)先左移三位(×8)然后再減去原值：X << 3 - X。
判斷一個(gè)數(shù)是不是2的n次冪
設(shè)要判斷的數(shù)是無(wú)符號(hào)整數(shù)X。
首先判斷X是否為0，如果為0則不是2的n次冪，返回。
X和X-1進(jìn)行按位與操作，如果結(jié)果是0，則說(shuō)明這個(gè)數(shù)是2的n次冪;如果結(jié)果非0，則說(shuō)明這個(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è))。問(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。
判斷數(shù)組中是否包含重復(fù)數(shù)字
給定一個(gè)長(zhǎng)度為N的數(shù)組，其中每個(gè)元素的取值范圍都是1到N。判斷數(shù)組中是否有重復(fù)的數(shù)字。(原數(shù)組不必保留)
給定一個(gè)長(zhǎng)度為N的數(shù)組，其中每個(gè)元素的取值范圍都是1到N。判斷數(shù)組中是否有重復(fù)的數(shù)字。(原數(shù)組不必保留)
如何將蛋糕切成相等的兩份
一塊長(zhǎng)方形的蛋糕，其中有一個(gè)小長(zhǎng)方形的空洞(角度任意)。使用一把直刀，如何一刀將蛋糕切成相等的兩份?
通過(guò)長(zhǎng)方形中心的的任意直線(xiàn)都能將長(zhǎng)方形等分，所以連接兩個(gè)長(zhǎng)方形的中心點(diǎn)的直線(xiàn)可以等分這個(gè)蛋糕。
一個(gè)沒(méi)有排序的鏈表，比如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)寫(xiě)出一個(gè)高效算法(時(shí)間比空間更重要)。
建立一個(gè)hash_map，key為鏈表中已經(jīng)遍歷的節(jié)點(diǎn)內(nèi)容，開(kāi)始時(shí)為空。
從頭開(kāi)始遍歷鏈表中的節(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口如何過(guò)橋?
小明一家過(guò)一座橋，過(guò)橋時(shí)是黑夜，所以必須有燈�，F(xiàn)在小明過(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ì)數(shù)的和
編一個(gè)程序求質(zhì)數(shù)的和，例如F(7) = 2+3+5+7+11+13+17=58。
方法1：
對(duì)于從2開(kāi)始的遞增整數(shù)n進(jìn)行如下操作：
用 [2，n-1] 中的數(shù)依次去除n，如果余數(shù)為0，則說(shuō)明n不是質(zhì)數(shù);如果所有余數(shù)都不是0，則說(shuō)明n是質(zhì)數(shù)，對(duì)其進(jìn)行加和。
空間復(fù)雜度為O(1)，時(shí)間復(fù)雜度為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開(kāi)始的遞增整數(shù)n進(jìn)行如下操作：
用 [2，n-1] 中的質(zhì)數(shù)(2，3，5，7，開(kāi)始時(shí)此序列為空)依次去除n，如果余數(shù)為0，則說(shuō)明n不是質(zhì)數(shù);如果所有余數(shù)都不是0，則說(shuō)明n是質(zhì)數(shù)，將此質(zhì)數(shù)加入質(zhì)數(shù)序列，并對(duì)其進(jìn)行加和。
空間復(fù)雜度為O(m)，時(shí)間復(fù)雜度為O(mn)，其中m為質(zhì)數(shù)的個(gè)數(shù)(例子對(duì)應(yīng)的值為7)，n為需要找到的最大質(zhì)數(shù)值(例子對(duì)應(yīng)的值為17)。
方法3：
也可以不用除法，而用加法。
申請(qǐng)一個(gè)足夠大的空間，每個(gè)bit對(duì)應(yīng)一個(gè)整數(shù)，開(kāi)始將所有的bit都初始化為0。
對(duì)于已知的質(zhì)數(shù)(開(kāi)始時(shí)只有2)，將此質(zhì)數(shù)所有的倍數(shù)對(duì)應(yīng)的bit都改為1，那么最小的值為0的bit對(duì)應(yīng)的數(shù)就是一個(gè)質(zhì)數(shù)。對(duì)新獲得的質(zhì)數(shù)的倍數(shù)也進(jìn)行標(biāo)注。
對(duì)這樣獲得的質(zhì)數(shù)序列累加就可以獲得質(zhì)數(shù)和。
空間復(fù)雜度為O(n)，時(shí)間負(fù)責(zé)度為O(n)，其中n為需要找到的最大質(zhì)數(shù)值(例子對(duì)應(yīng)的值為17)。
【微軟筆試題目分享】相關(guān)文章：
微軟筆試題目精選01-15
惠普筆試題目分享08-06
分享Google筆試題目06-20
微軟中英文筆試題目11-05
微軟10道筆試面試題目08-19
C++筆試題目分享12-20
德勤筆試題目分享08-21
微軟筆試經(jīng)驗(yàn)12-07
中興筆試題目分享有答案12-07