微軟筆試題目
微軟在IT界依然是數(shù)一數(shù)二的企業(yè)了,不少人的夢想都是進入微軟公司。那么在這之前的面試以及筆試就需要進行一下準(zhǔn)備了。那么這里就來看看小編為大家總結(jié)的微軟筆試題吧。
微軟筆試題:
寫程序找出二叉樹的深度
一個樹的深度等于max(左子樹深度,右子樹深度)+1?梢允褂眠f歸實現(xiàn)。
假設(shè)節(jié)點為定義為
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克兩份?
有一個天平,2克和7克砝碼各一個。如何利用天平砝碼在三次內(nèi)將140克鹽分成50,90克兩份。
第一種方法:
第一次:先稱 7+2克鹽 (相當(dāng)于有三個法碼2,7,9)
第二次:稱2+7+9=18克鹽 (相當(dāng)于有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
微軟筆試題:地球上有多少個滿足這樣條件的點
站在地球上的某一點,向南走一公里,然后向東走一公里,最后向北走一公里,回到了原點。地球上有多少個滿足這樣條件的點?
北極點滿足這個條件。
距離南極點很近的一個圈上也滿足這個條件。在這個圓圈上,向南走一公里,然后向東走一公里恰好繞南極點一圈,向北走一公里回到原點。
所以地球上總共有無數(shù)點滿足這個條件。
或者
首先,在地球表面上,南北走向是沿著經(jīng)度方向,東西是沿著緯度方向。如果你一直往北走就會達(dá)到北極點,往南走就到了南極點。因此,向南走一公里,然后向東走一公里,最后向北走一公里,回到了原點,一種情況就是,出發(fā)點是在北極點,這樣向南走一公里,然后向東走任意幾公里,最后向北走一公里,最后都會回到北極點;
其次,可以這么認(rèn)為如果從A點向南走一公里到達(dá)B點,那么若向東走一公里能回到B,那么最后向北走一公里,就能回到了原點A。這樣就可以先找出在南北極點附近找出繞一周只有1公里的圈,那么這個圈落在南極附近時,只要往北推1公里,此時該圈上的點都能滿足;若這個圈落在北極附近時,能不能往北推1公里我就不分析了。反正在南極附近能找到任意多個點就能回到這個問題了
微軟筆試題:正確標(biāo)注水果籃
有三個水果籃。其中一個里面只有蘋果,一個里面只有橘子,另外一個既有蘋果又有橘子。每個水果籃上都有標(biāo)簽,但標(biāo)簽都是錯的。如何檢查某個水果籃中的一個水果,然后正確標(biāo)注每個水果籃?
從標(biāo)注成既有蘋果也有橘子的水果籃中選取一個進行檢查。
如果是橘子,則此籃中只有橘子;標(biāo)有橘子的水果籃中只有蘋果;標(biāo)有蘋果的水果籃中既有蘋果也有橘子。
如果是蘋果,則此籃中只有蘋果;標(biāo)有蘋果的水果籃中只有橘子;標(biāo)有橘子的水果籃中既有蘋果也有橘子。
微軟筆試題:不利用浮點運算,畫一個圓
不利用浮點運算,在屏幕上畫一個圓 (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 的點作為下一個點。反復(fù)進行這種運算,直至到達(dá)點(r,0)。
由于不能利用浮點運算,所以距離的比較只能在距離平方的基礎(chǔ)上進行。也就是比較 x**2 + y**2 和 r**2之間的差值。
微軟筆試題:將一個句子按單詞反序
將一個句子按單詞反序。比如 “hi baidu com mianshiti”,反序后變?yōu)?“mianshiti com baidu hi”。
可以分兩步走:
第一步按找字母反序,“hi baidu com mianshiti” 變?yōu)?“itihsnaim moc udiab ih”。
第二部將每個單詞中的字母反序,“itihsnaim moc udiab ih” 變成 “mianshiti com baidu hi”。
這個方法可以在原字符串上進行,只需要幾個整數(shù)變量來保持指針即可,空間復(fù)雜度低。
微軟筆試題:計算n bit的整數(shù)中有多少bit 為1
設(shè)此整數(shù)為x。
方法1:
讓此整數(shù)除以2,如果余數(shù)為1,說明最后一位是1,統(tǒng)計值加1。
將除得的結(jié)果進行上面運算,直到結(jié)果為0。
方法2:
考慮除法復(fù)雜度有些高,可以使用移位操作代替除法。
將 x 和 1 進行按位與操作(x&1),如果結(jié)果為1,說明最后一位是1,統(tǒng)計值加1。
將x 向右一位(x >> 1),重復(fù)上面過程,直到移位后結(jié)果為0。
方法3:
如果需要統(tǒng)計很多數(shù)字,并且內(nèi)存足夠大,可以考慮將每個數(shù)對應(yīng)的bit為1的數(shù)量記錄下來,這樣每次計算只是一次查找操作。
微軟筆試題:快速求取一個整數(shù)的7倍
乘法相對比較慢,所以快速的方法就是將這個乘法轉(zhuǎn)換成加減法和移位操作。
可以將此整數(shù)先左移三位(×8)然后再減去原值:X << 3 - X。
微軟筆試題:判斷一個數(shù)是不是2的n次冪
設(shè)要判斷的數(shù)是無符號整數(shù)X。
首先判斷X是否為0,如果為0則不是2的n次冪,返回。
X和X-1進行按位與操作,如果結(jié)果是0,則說明這個數(shù)是2的n次冪;如果結(jié)果非0,則說明這個數(shù)不是2 的n次冪。
證明:
如果是2的n次冪,則此數(shù)用二進制表示時只有一位是1,其它都是0。減1后,此位變成0,后面的位變成1,所以按位與后結(jié)果是0。
如果不是2的n次冪,則此數(shù)用二進制表示時有多位是1。減1后,只有最后一個1變成0,前面的 1還是1,所以按位與后結(jié)果不是0。
微軟筆試題:三只螞蟻不相撞的概率是多少
在三角形的三個頂點上各有一只螞蟻,它們向另一個頂點運動,目標(biāo)隨機(可能為另外兩個頂點的任意一個)。問三只螞蟻不相撞的概率是多少?
如果螞蟻順時針爬行記為0,逆時針爬行記為1。那么三只螞蟻的狀態(tài)可能為000,001,...,110,111中的任意一個,且為每種狀態(tài)的概率相等。在這8種狀態(tài)中,只有000和111可以避免相撞,所以螞蟻不相撞的概率是1/4。
微軟筆試題:判斷數(shù)組中是否包含重復(fù)數(shù)字
給定一個長度為N的數(shù)組,其中每個元素的取值范圍都是1到N。判斷數(shù)組中是否有重復(fù)的數(shù)字。(原數(shù)組不必保留)
給定一個長度為N的數(shù)組,其中每個元素的取值范圍都是1到N。判斷數(shù)組中是否有重復(fù)的數(shù)字。(原數(shù)組不必保留)
微軟筆試題:如何將蛋糕切成相等的兩份
一塊長方形的蛋糕,其中有一個小長方形的空洞(角度任意)。使用一把直刀,如何一刀將蛋糕切成相等的兩份?
通過長方形中心的的任意直線都能將長方形等分,所以連接兩個長方形的中心點的直線可以等分這個蛋糕。
一個沒有排序的鏈表,比如list={a,l,x,b,e,f,f,e,a,g,h,b,m},請去掉重復(fù)項,并保留原順序,以上鏈表去掉重復(fù)項后為newlist={a,l,x,b,e,f,g,h,m},請寫出一個高效算法(時間比空間更重要)。
建立一個hash_map,key為鏈表中已經(jīng)遍歷的節(jié)點內(nèi)容,開始時為空。
從頭開始遍歷鏈表中的節(jié)點:
- 如果節(jié)點內(nèi)容已經(jīng)在hash_map中存在,則刪除此節(jié)點,繼續(xù)向后遍歷;
- 如果節(jié)點內(nèi)容不在hash_map中,則保留此節(jié)點,將節(jié)點內(nèi)容添加到hash_map中,繼續(xù)向后遍歷。
微軟筆試題:小明一家5口如何過橋?
小明一家過一座橋,過橋時是黑夜,所以必須有燈。現(xiàn)在小明過橋要1秒,小明的弟弟要3秒,小明的爸爸要6秒,小明的媽媽要8秒,小明的爺爺要12秒。每次此橋最多可過兩人,而過橋的速度依過橋最慢者而定,而且燈在點燃后30秒就會熄滅。問:小明一家如何過橋?
小明與弟弟過去,小明回來,用4s;
媽媽與爺爺過去,弟弟回來,用15s;
小明與弟弟過去,小明回來,用4s;
小明與爸爸過去,用6s;
總共用29s。
題目的關(guān)鍵是讓速度差不多的一起走,免得過于拖累較快的一個人。
微軟筆試題:編一個程序求質(zhì)數(shù)的和
編一個程序求質(zhì)數(shù)的和,例如F(7) = 2+3+5+7+11+13+17=58。
方法1:
對于從2開始的遞增整數(shù)n進行如下操作:
用 [2,n-1] 中的數(shù)依次去除n,如果余數(shù)為0,則說明n不是質(zhì)數(shù);如果所有余數(shù)都不是0,則說明n是質(zhì)數(shù),對其進行加和。
空間復(fù)雜度為O(1),時間復(fù)雜度為O(n^2),其中n為需要找到的最大質(zhì)數(shù)值(例子對應(yīng)的值為17)。
方法2:
可以維護一個質(zhì)數(shù)序列,這樣當(dāng)需要判斷一個數(shù)是否是質(zhì)數(shù)時,只需判斷是否能被比自己小的質(zhì)數(shù)整除即可。
對于從2開始的遞增整數(shù)n進行如下操作:
用 [2,n-1] 中的質(zhì)數(shù)(2,3,5,7,開始時此序列為空)依次去除n,如果余數(shù)為0,則說明n不是質(zhì)數(shù);如果所有余數(shù)都不是0,則說明n是質(zhì)數(shù),將此質(zhì)數(shù)加入質(zhì)數(shù)序列,并對其進行加和。
空間復(fù)雜度為O(m),時間復(fù)雜度為O(mn),其中m為質(zhì)數(shù)的個數(shù)(例子對應(yīng)的值為7),n為需要找到的最大質(zhì)數(shù)值(例子對應(yīng)的值為17)。
方法3:
也可以不用除法,而用加法。
申請一個足夠大的空間,每個bit對應(yīng)一個整數(shù),開始將所有的bit都初始化為0。
對于已知的質(zhì)數(shù)(開始時只有2),將此質(zhì)數(shù)所有的倍數(shù)對應(yīng)的bit都改為1,那么最小的值為0的bit對應(yīng)的數(shù)就是一個質(zhì)數(shù)。對新獲得的質(zhì)數(shù)的倍數(shù)也進行標(biāo)注。
對這樣獲得的質(zhì)數(shù)序列累加就可以獲得質(zhì)數(shù)和。
空間復(fù)雜度為O(n),時間負(fù)責(zé)度為O(n),其中n為需要找到的最大質(zhì)數(shù)值(例子對應(yīng)的值為17)。
微軟筆試的題目
一般來說,微軟的面試問題分為4類:謎語類試題、數(shù)學(xué)型試題、智力性試題、應(yīng)用程序類試題。先舉兩個謎語類試題:
1美國有多少輛汽車?
2、將汽車鑰匙插入車門,向哪個方向旋轉(zhuǎn)就可以打開車鎖?
小張(復(fù)旦大學(xué)管理學(xué)院99級學(xué)生):這兩道試題并不難,我想他可能只是想考察一下應(yīng)聘者的應(yīng)變能力,亦即在短時間內(nèi)快速應(yīng)對不規(guī)范問題的能力。
孫先生(某大型跨國企業(yè)員工):很明顯,這是兩道答案開放的試題。我想它是為了考察應(yīng)聘者能否對一個問題進行符合邏輯的創(chuàng)造性的思考,并迅速通過這種思考尋求到解決問題的辦法。至于答案,發(fā)問者顯然并不關(guān)心。
裘副教授(復(fù)旦大學(xué)):問題是開放性的,但指向性也很明顯。應(yīng)聘者是否能在很短的時間對出其不意的問題作出反應(yīng),并能夠有邏輯地回答這樣的問題,發(fā)問者同樣希望能夠得到出其不意的答案。有不少人通過在網(wǎng)上搜集這種試題來準(zhǔn)備答案,顯然大違發(fā)問者的本意。重復(fù)的答案都不是好答案。
下面是兩道數(shù)學(xué)型的試題:
1、1000 有幾位數(shù),為什么?
2、編一個程序求質(zhì)數(shù)的和,例如F 7 =1+3+5+7+11+13+17=58。
小陸(復(fù)旦大學(xué)物理系99級學(xué)生):數(shù)學(xué)試題與應(yīng)用程序試題是微軟面試中指向性最明顯的一類試題。這些試題就是考察應(yīng)聘者的數(shù)學(xué)能力與計算機能力。
師女士(某咨詢公司高級顧問):微軟是一家電腦軟件公司,當(dāng)然要求其員工有一定的計算機和數(shù)學(xué)能力,面試中自然就會考察這類能力。微軟的上述面試題目就考察了應(yīng)聘人員對基礎(chǔ)知識的掌握程度、對基礎(chǔ)知識的應(yīng)用能力,甚至暗含了對計算機基本原理的考察。所以,這樣的面試題目的確很“毒辣”,足以篩選到合適的人。
下面是智力題:
。、燒一根不均勻的繩需用一個小時,如何用它來判斷半個小時?
小何(復(fù)旦大學(xué)計算機系00級碩士研究生):我覺得我很難理解微軟這一部分的試題,我大多數(shù)時候并不知道他考察我什么,有時候我甚至覺得它僅僅是腦筋急轉(zhuǎn)彎。不過,我記得李開復(fù)在央視的節(jié)目里說過,他們的考察內(nèi)容是應(yīng)聘者的可塑性。
石先生(某大型國企職工):我認(rèn)為這一部分的問題有很大的隨意性,主要是考察應(yīng)聘者的智商,但是因為問題的不同又有不同的考察方向,比如第一個問題就考察了應(yīng)聘者的逆向思維能力,第二個就考察了應(yīng)聘者的觀察能力與細(xì)致程度。
于先生(某外資公司人事主管):我不知道微軟出這些題目的用意,但在我看來,智力題是微軟面試中最好的考察方式。不僅考察的指向不同,就連問題的答案有時候也能給人以啟發(fā)。比如上述第二個問題,如果你能找到答案,它就會幫你理解企業(yè)的資源使用組合方式,經(jīng)過優(yōu)化以后可以發(fā)揮不同的作用。不同的管理者就會使用不同的組合方式,當(dāng)然結(jié)果就會不一樣!
【微軟筆試題目】相關(guān)文章:
微軟的筆試題目10-26
微軟筆試題目精選01-15
微軟筆試題目03-17
微軟筆試題目 110-13
有趣的微軟筆試題目12-19
微軟筆試題目分享12-03
微軟筆試題目(附答案)10-28
微軟求職筆試中考察的題目11-23
微軟筆試面試題目03-12