微軟筆試題目分享(一)
1、1000!有幾位數，為什麼
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)函式組合出F(n)函式
sign(n)=0 n=0
sign(n)=-1 n<
sign(n)=1 n>0
3、編一個程式求質數的和例如F(7)=1+3+5+7+11+13+17=58
輯考題 此題源於1981年柏林的德國邏輯思考學院，98%的測驗者無法解題。
前提：
有五間房屋排成一列;所有房屋的外表顏色都不一樣;所有的屋主來自不同的國家
;所有的屋主都養不同的寵物;喝不同的飲料;抽不同的香菸。
提示：
英國人住在紅色房屋裡;瑞典人養了一隻狗;丹麥人喝茶;綠色的房子在白色的房
子的左邊;綠色房屋的屋主喝咖啡;抽Pall Mall香菸的屋主養鳥;黃色屋主抽Dunhill;
位於最中間的屋主喝牛奶;挪威人住在第一間房屋裡;抽Blend的人住在養貓人家的隔壁;
養馬的屋主在抽Dunhill的人家的隔壁。抽Blue Master的屋主喝啤酒;德國人抽Prince;
挪威人住在藍色房子隔壁;只喝開水的人家住在抽Blend的隔壁。
問：誰養魚?
五個人來自不同地方，住不同房子，養不同動物，吸不同牌子香菸，喝不同飲料，
喜歡不同食物。根據以下線索確定誰是養貓的人?
1.紅房子在藍房子的右邊，白房子的左邊(不一定緊鄰)
2.黃房子的主人來自香港，而且他的房子不在最左邊。
3.?員熱??娜俗≡詘?瓤筧??娜說母舯凇?
4.來自北京的人愛喝茅臺，住在來自上海的人的隔壁。
5.吸希爾頓香菸的人住在養馬的人?右邊隔壁。
6.愛喝啤酒的人也愛吃雞。
7.綠房子的人養狗。
8.愛吃麵條的人住在養蛇的人的隔壁。
9.來自天津的人的鄰居(緊鄰)一個愛吃牛肉，另一個來自成都。
微軟筆試題目分享(二)
寫程式找出二元樹的深度
一個樹的深度等於max(左子樹深度，右子樹深度)+1。可以使用遞迴實現。
假設節點為定義為
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口如何過橋?
小明一家過一座橋，過橋時是黑夜，所以必須有燈。現在小明過橋要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)。