微軟筆試題目精選
微軟在IT界依然是數一數二的企業了,不少人的夢想都是進入微軟公司。那么在這之前的面試以及筆試就需要進行一下準備了。那么這里就來看看小編為大家總結的微軟筆試題吧。
微軟筆試題:寫程序找出二叉樹的深度
一個樹的深度等于max(左子樹深度,右子樹深度)+1?梢允褂眠f歸實現。
假設節點為定義為
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克砝碼各一個。如何利用天平砝碼在三次內將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)
現在有四堆面粉70,35,15,20,分別組合得到
70+20=90
35+15=50
微軟筆試題:地球上有多少個滿足這樣條件的點
站在地球上的某一點,向南走一公里,然后向東走一公里,最后向北走一公里,回到了原點。地球上有多少個滿足這樣條件的點?
北極點滿足這個條件。
距離南極點很近的一個圈上也滿足這個條件。在這個圓圈上,向南走一公里,然后向東走一公里恰好繞南極點一圈,向北走一公里回到原點。
所以地球上總共有無數點滿足這個條件。
或者
首先,在地球表面上,南北走向是沿著經度方向,東西是沿著緯度方向。如果你一直往北走就會達到北極點,往南走就到了南極點。因此,向南走一公里,然后向東走一公里,最后向北走一公里,回到了原點,一種情況就是,出發點是在北極點,這樣向南走一公里,然后向東走任意幾公里,最后向北走一公里,最后都會回到北極點;
其次,可以這么認為如果從A點向南走一公里到達B點,那么若向東走一公里能回到B,那么最后向北走一公里,就能回到了原點A。這樣就可以先找出在南北極點附近找出繞一周只有1公里的圈,那么這個圈落在南極附近時,只要往北推1公里,此時該圈上的點都能滿足;若這個圈落在北極附近時,能不能往北推 1公里我就不分析了。反正在南極附近能找到任意多個點就能回到這個問題了
微軟筆試題:正確標注水果籃
有三個水果籃。其中一個里面只有蘋果,一個里面只有橘子,另外一個既有蘋果又有橘子。每個水果籃上都有標簽,但標簽都是錯的。如何檢查某個水果籃中的一個水果,然后正確標注每個水果籃?
從標注成既有蘋果也有橘子的水果籃中選取一個進行檢查。
如果是橘子,則此籃中只有橘子;標有橘子的水果籃中只有蘋果;標有蘋果的水果籃中既有蘋果也有橘子。
如果是蘋果,則此籃中只有蘋果;標有蘋果的水果籃中只有橘子;標有橘子的水果籃中既有蘋果也有橘子。
微軟筆試題:不利用浮點運算,畫一個圓
不利用浮點運算,在屏幕上畫一個圓 (x**2 + y**2 = r**2,其中 r 為正整數)。
考慮到圓的對稱性,我們只需考慮第一象限即可。
等價于找到一條連接點(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之間的差值。
微軟筆試題:將一個句子按單詞反序
將一個句子按單詞反序。比如 “hi baidu com mianshiti”,反序后變為 “mianshiti com baidu hi”。
可以分兩步走:
第一步按找字母反序,“hi baidu com mianshiti” 變為 “itihsnaim moc udiab ih”。
第二部將每個單詞中的字母反序,“itihsnaim moc udiab ih” 變成 “mianshiti com baidu hi”。
這個方法可以在原字符串上進行,只需要幾個整數變量來保持指針即可,空間復雜度低。
微軟筆試題:計算n bit的整數中有多少bit 為1
設此整數為x。
方法1:
讓此整數除以2,如果余數為1,說明最后一位是1,統計值加1。
將除得的結果進行上面運算,直到結果為0。
方法2:
考慮除法復雜度有些高,可以使用移位操作代替除法。
將 x 和 1 進行按位與操作(x&1),如果結果為1,說明最后一位是1,統計值加1。
將x 向右一位(x >> 1),重復上面過程,直到移位后結果為0。
方法3:
如果需要統計很多數字,并且內存足夠大,可以考慮將每個數對應的bit為1的數量記錄下來,這樣每次計算只是一次查找操作。
微軟筆試題:快速求取一個整數的7倍
乘法相對比較慢,所以快速的方法就是將這個乘法轉換成加減法和移位操作。
可以將此整數先左移三位(×8)然后再減去原值:X << 3 - X。
微軟筆試題:判斷一個數是不是2的n次冪
設要判斷的數是無符號整數X。
首先判斷X是否為0,如果為0則不是2的n次冪,返回。
X和X-1進行按位與操作,如果結果是0,則說明這個數是2的n次冪;如果結果非0,則說明這個數不是2 的n次冪。
證明:
如果是2的n次冪,則此數用二進制表示時只有一位是1,其它都是0。減1后,此位變成0,后面的位變成1,所以按位與后結果是0。
如果不是2的n次冪,則此數用二進制表示時有多位是1。減1后,只有最后一個1變成0,前面的 1還是1,所以按位與后結果不是0。
微軟筆試題:三只螞蟻不相撞的概率是多少
在三角形的三個頂點上各有一只螞蟻,它們向另一個頂點運動,目標隨機(可能為另外兩個頂點的任意一個)。問三只螞蟻不相撞的概率是多少?
如果螞蟻順時針爬行記為0,逆時針爬行記為1。那么三只螞蟻的'狀態可能為000,001,...,110,111中的任意一個,且為每種狀態的概率相等。在這8種狀態中,只有000和111可以避免相撞,所以螞蟻不相撞的概率是1/4。
微軟筆試題:判斷數組中是否包含重復數字
給定一個長度為N的數組,其中每個元素的取值范圍都是1到N。判斷數組中是否有重復的數字。(原數組不必保留)
給定一個長度為N的數組,其中每個元素的取值范圍都是1到N。判斷數組中是否有重復的數字。(原數組不必保留)
微軟筆試題:如何將蛋糕切成相等的兩份
一塊長方形的蛋糕,其中有一個小長方形的空洞(角度任意)。使用一把直刀,如何一刀將蛋糕切成相等的兩份?
通過長方形中心的的任意直線都能將長方形等分,所以連接兩個長方形的中心點的直線可以等分這個蛋糕。
一個沒有排序的鏈表,比如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為鏈表中已經遍歷的節點內容,開始時為空。
從頭開始遍歷鏈表中的節點:
- 如果節點內容已經在hash_map中存在,則刪除此節點,繼續向后遍歷;
- 如果節點內容不在hash_map中,則保留此節點,將節點內容添加到hash_map中,繼續向后遍歷。
微軟筆試題:小明一家5口如何過橋?
小明一家過一座橋,過橋時是黑夜,所以必須有燈,F在小明過橋要1秒,小明的弟弟要3秒,小明的爸爸要6秒,小明的媽媽要8秒,小明的爺爺要12秒。每次此橋最多可過兩人,而過橋的速度依過橋最慢者而定,而且燈在點燃后30秒就會熄滅。問:小明一家如何過橋?
小明與弟弟過去,小明回來,用4s;
媽媽與爺爺過去,弟弟回來,用15s;
小明與弟弟過去,小明回來,用4s;
小明與爸爸過去,用6s;
總共用29s。
題目的關鍵是讓速度差不多的一起走,免得過于拖累較快的一個人。
微軟筆試題:編一個程序求質數的和
編一個程序求質數的和,例如F(7) = 2+3+5+7+11+13+17=58。
方法1:
對于從2開始的遞增整數n進行如下操作:
用 [2,n-1] 中的數依次去除n,如果余數為0,則說明n不是質數;如果所有余數都不是0,則說明n是質數,對其進行加和。
空間復雜度為O(1),時間復雜度為O(n^2),其中n為需要找到的最大質數值(例子對應的值為17)。
方法2:
可以維護一個質數序列,這樣當需要判斷一個數是否是質數時,只需判斷是否能被比自己小的質數整除即可。
對于從2開始的遞增整數n進行如下操作:
用 [2,n-1] 中的質數(2,3,5,7,開始時此序列為空)依次去除n,如果余數為0,則說明n不是質數;如果所有余數都不是0,則說明n是質數,將此質數加入質數序列,并對其進行加和。
空間復雜度為O(m),時間復雜度為O(mn),其中m為質數的個數(例子對應的值為7),n為需要找到的最大質數值(例子對應的值為17)。
方法3:
也可以不用除法,而用加法。
申請一個足夠大的空間,每個bit對應一個整數,開始將所有的bit都初始化為0。
對于已知的質數(開始時只有2),將此質數所有的倍數對應的bit都改為1,那么最小的值為0的bit對應的數就是一個質數。對新獲得的質數的倍數也進行標注。
對這樣獲得的質數序列累加就可以獲得質數和。
空間復雜度為O(n),時間負責度為O(n),其中n為需要找到的最大質數值(例子對應的值為17)。
【微軟筆試題目精選】相關文章:
微軟10道筆試面試題目08-19
微軟中英文筆試題目11-05
微軟筆試經驗03-01
微軟office認證筆試經驗07-15
EMC筆試題目精選08-15
美的筆試題目04-09
惠普筆試題目08-10
伊利筆試題目07-09
夏普筆試題目07-03