微軟公司的面試問題

★鏈接表和數組之間的區別是什麼？

★做一個鏈接表，你為什麼要選擇這樣的方法？

★選擇一種算法來整理出一個鏈接表。你為什麼要選擇這種方法？現在用O(n)時間來做。

★説説各種股票分類算法的優點和缺點。

★用一種算法來顛倒一個鏈接表的順序。現在在不用遞歸式的情況下做一遍。

★用一種算法在一個循環的鏈接表裏插入一個節點，但不得穿越鏈接表。

★用一種算法整理一個數組。你為什麼選擇這種方法？

★用一種算法使通用字符串相匹配。

★顛倒一個字符串。優化速度。優化空間。

★顛倒一個句子中的詞的順序，比如將“我叫克麗絲”轉換為“克麗絲叫我”，實現速度最快，移動最少。

★找到一個子字符串。優化速度。優化空間。

★比較兩個字符串，用O(n)時間和恆量空間。

★假設你有一個用1001個整數組成的數組，這些整數是任意排列的，但是你知道所有的整數都在1到1000(包括1000)之間。此外，除一個數字出現兩次外，其他所有數字只出現一次。假設你只能對這個數組做一次處理，用一種算法找出重複的那個數字。如果你在運算中使用了輔助的存儲方式，那麼你能找到不用這種方式的算法嗎？

★不用乘法或加法增加8倍。現在用同樣的方法增加7倍。

★鏈接表和數組之間的區別是什麼？

★做一個鏈接表，你為什麼要選擇這樣的方法？

★選擇一種算法來整理出一個鏈接表。你為什麼要選擇這種方法？現在用O(n)時間來做。

★説説各種股票分類算法的優點和缺點。

★用一種算法來顛倒一個鏈接表的順序。現在在不用遞歸式的情況下做一遍。

★用一種算法在一個循環的鏈接表裏插入一個節點，但不得穿越鏈接表。

★用一種算法整理一個數組。你為什麼選擇這種方法？

★用一種算法使通用字符串相匹配。

★顛倒一個字符串。優化速度。優化空間。

★顛倒一個句子中的詞的順序，比如將“我叫克麗絲”轉換為“克麗絲叫我”，實現速度最快，移動最少。

★找到一個子字符串。優化速度。優化空間。

★比較兩個字符串，用O(n)時間和恆量空間。

★假設你有一個用1001個整數組成的數組，這些整數是任意排列的，但是你知道所有的整數都在1到1000(包括1000)之間。此外，除一個數字出現兩次外，其他所有數字只出現一次。假設你只能對這個數組做一次處理，用一種算法找出重複的那個數字。如果你在運算中使用了輔助的存儲方式，那麼你能找到不用這種方式的算法嗎？

★不用乘法或加法增加8倍。現在用同樣的方法增加7倍。

★如果你有一個許多部件可以拆卸的時鐘，你將它一塊塊拆開，但是沒有記住是怎樣拆的。然後你將各個零件重新組裝起來，最後發現有三個重要零件沒有放進去。這時你如何重新組裝這個時鐘？

★如果你需要學習一門新的計算機語言，你會怎樣做？

★假設由你負責設計比爾·蓋茨的衞生間。當然，錢不成問題，但是你不可以和比爾談。你會怎樣做？

★到目前為止，你遇到的最難回答的問題是什麼？

★如果微軟公司説，我們願意投資500萬美元用來開發你提出的方案。那麼你會做什麼？為什麼？

★如果你將世界上所有的計算機制造商召集起來，告訴他們必須要做一件事，你會讓他們做什麼事？

★如果你在五年內會得到一筆獎金，你認為會是因為什麼？關注你的成績的人會是誰？

★你如何教自己的奶奶使用微軟Excel表格系統？

★為什麼當我們在任何一家賓館打開熱水龍頭時，熱水會馬上流出來？

★你為什麼想在微軟工作？

★假設你回到家，進入自己的房間，打開電燈開關，可是一點反應都沒有——燈沒有亮。這時，你在判斷問題出在哪裏時，會依次採取怎樣的做法？

★如果你有一個許多部件可以拆卸的時鐘，你將它一塊塊拆開，但是沒有記住是怎樣拆的。然後你將各個零件重新組裝起來，最後發現有三個重要零件沒有放進去。這時你如何重新組裝這個時鐘？

★如果你需要學習一門新的計算機語言，你會怎樣做？

★假設由你負責設計比爾·蓋茨的衞生間。當然，錢不成問題，但是你不可以和比爾談。你會怎樣做？

★到目前為止，你遇到的最難回答的問題是什麼？

★如果微軟公司説，我們願意投資500萬美元用來開發你提出的方案。那麼你會做什麼？為什麼？

★如果你將世界上所有的計算機制造商召集起來，告訴他們必須要做一件事，你會讓他們做什麼事？

★如果你在五年內會得到一筆獎金，你認為會是因為什麼？關注你的成績的人會是誰？

★你如何教自己的奶奶使用微軟Excel表格系統？

★為什麼當我們在任何一家賓館打開熱水龍頭時，熱水會馬上流出來？

★你為什麼想在微軟工作？

★假設你回到家，進入自己的房間，打開電燈開關，可是一點反應都沒有——燈沒有亮。這時，你在判斷問題出在哪裏時，會依次採取怎樣的做法？

以下是微軟公司的員工在面試時所遇到的問題。這些問題往往遵循以下一些基本主題：難題、運算、應用、頭腦。

難題

1.為什麼下水道的井蓋是圓的？

2.美國有多少輛車？（類似問題是：美國有多少家加油站？）

3.美國有多少個下水道井蓋？

4.你讓某些人為你工作了七天，你要用一根金條作為報酬。這根金條要被分成七塊。你必須在每天的活幹完後交給他們一塊。如果你只能將這根金條切割兩次，你怎樣給這些工人分？

5.一列火車以每小時15英里的速度離開洛杉磯，朝紐約進發。另外一列火車以每小時20英里的速度離開紐約，朝洛杉磯進發。如果一隻每小時飛行25英里的鳥同時離開洛杉磯，在兩列火車之間往返飛行，請問當兩列火車相遇時，鳥飛了多遠？

6.假設一張圓盤像唱機上的唱盤那樣轉動。這張盤一半是黑色，一半是白色。假設你有數量不限的一些顏色傳感器。要想確定圓盤轉動的方向，你需要在它周圍擺多少個顏色傳感器？它們應該被擺放在什麼位置？

7.假設時鐘到了12點。注意時針和分針重疊在一起。在一天之中，時針和分針共重疊多少次？你知道它們重疊時的具體時間嗎？

8.你有兩個罐子，分別裝着50個紅色的玻璃球和50個藍色的玻璃球。隨意拿起一個罐子，然後從裏面拿出一個玻璃球。怎樣最大程度地增加讓自己拿到紅球的機會？利用這種方法，拿到紅球的機率有多大？

9.中間只隔一個數字的兩個奇數被稱為奇數對，比如17和19。證明奇數對之間的數字總能被6整除（假設這兩個奇數都大於6）。現在證明沒有由三個奇數組成的奇數對。

10.一個屋子有一個門（門是關閉的）和3盞電燈。屋外有3個開關，分別與這3盞燈相連。你可以隨意操縱這些開關，可一旦你將門打開，就不能變換開關了。確定每個開關具體管哪盞燈。

11.假設你有8個球，其中一個略微重一些，但是找出這個球的惟一方法是將兩個球放在天平上對比。最少要稱多少次才能找出這個較重的球？

12.假設你站在鏡子前，抬起左手，抬起右手，看看鏡中的自己。當你抬起左手時，鏡中的自己抬起的似乎是右手。可是當你仰頭時，鏡中的自己也在仰頭，而不是低頭。為什麼鏡子中的影像似乎顛倒了左右，卻沒有顛倒上下？

13.你有4瓶藥。每粒藥丸的重量是固定的，不過其中有一瓶藥受到了污染，藥丸的重量發生了變化，每個藥丸增加了一點重量。你怎樣一下子測出哪瓶藥是遭到污染的呢？

14.下面玩一個拆字遊戲，所有字母的順序都被打亂。你要判斷這個字是什麼？假設這個被拆開的字由5個字母組成：(1)共有多少種可能的組合方式？(2)如果我們知道是哪5個字母，那會怎麼樣？(3)找出一種解決這個問題的方法。

15.有4個女人要過一座橋。她們都站在橋的某一邊，要讓她們在17分鐘內全部通過這座橋。這時是晚上。她們只有一個手電筒。最多隻能讓兩個人同時過橋。不管是誰過橋，不管是一個人還是兩個人，必須要帶着手電筒。手電筒必須要傳來傳去，不能扔過去。每個女人過橋的速度不同，兩個人的速度必須以較慢的那個人的速度過橋。第一個女人：過橋需要1分鐘；第二個女人：過橋需要2分鐘；第三個女人：過橋需要5分鐘；第四個女人：過橋需要10分鐘。比如，如果第一個女人與第4個女人首先過橋，等她們過去時，已經過去了10分鐘。如果讓第4個女人將手電筒送回去，那麼等她到達橋的另一端時，總共用去了20分鐘，行動也就失敗了。怎樣讓這4個女人在17分鐘內過橋？還有別的什麼方法？

16.如果你有一個5夸脱的水桶和一個3夸脱的水桶，如何準確量出4夸脱的水？

17.你有一袋糖，有紅色的，藍色的，綠色的。閉上眼睛，拿出兩塊顏色一樣的糖，你需要拿多少次才能確保有兩塊顏色相同的？

18.如果你有兩個桶，一個裝的是紅色的顏料，另一個裝的是藍色的顏料。你從藍色顏料桶裏舀一杯，倒入紅色顏料桶，再從紅色顏料桶裏舀一杯倒入藍顏料桶。兩個桶中紅藍顏料的比例哪個更高？通過算術的方式來證明這一點。

運算

1.鏈接表和數組之間的區別是什麼？

2.做一個鏈接表，你為什麼要選擇這樣的方法？

3.選擇一種算法來整理出一個鏈接表。你為什麼要選擇這種方法？現在用O(n)時間來做。

4.説説各種股票分類算法的優點和缺點。

5.用一種算法來顛倒一個鏈接表的順序。現在在不用遞歸式的情況下做一遍。

6.用一種算法在一個循環的鏈接表裏插入一個節點，但不得穿越鏈接表。

7.用一種算法整理一個數組。你為什麼選擇這種方法？

8.用一種算法使通用字符串相匹配。

9.顛倒一個字符串。優化速度。優化空間。

10.顛倒一個句子中的詞的順序，比如將“我叫克麗絲”轉換為“克麗絲叫我”，實現速度最快，移動最少。

11.找到一個子字符串。優化速度。優化空間。

12.比較兩個字符串，用O(n)時間和恆量空間。

13.假設你有一個用1001個整數組成的數組，這些整數是任意排列的，但是你知道所有的整數都在1到1000（包括1000）之間。此外，除一個數字出現兩次外，其他所有數字只出現一次。假設你只能對這個數組做一次處理，用一種算法找出重複的那個數字。如果你在運算中使用了輔助的存儲方式，那麼你能找到不用這種方式的算法嗎？

14.不用乘法或加法增加8倍。現在用同樣的方法增加7倍。

應用

1.如何將計算機技術應用於一幢100層高的辦公大樓的電梯系統上？你怎樣優化這種應用？工作日時的交通、樓層或時間等因素會對此產生怎樣的影響？

2.你如何對一種可以隨時存在文件中或從因特網上拷貝下來的操作系統實施保護措施，防止被非法複製？

3.你如何重新設計自動取款機？

4.假設我們想通過電腦來操作一台微波爐，你會開發什麼樣的軟件來完成這個任務？

5.你如何為一輛汽車設計一台咖啡機？

6. 如果你想給微軟的Word系統增加點內容，你會增加什麼樣的內容？

7.你會給失聰的人設計什麼樣的鬧鐘？

頭腦

1.如果你有一個許多部件可以拆卸的時鐘，你將它一塊塊拆開，但是沒有記住是怎樣拆的。然後你將各個零件重新組裝起來，最後發現有三個重要零件沒有放進去。這時你如何重新組裝這個時鐘？

2.如果你需要學習一門新的計算機語言，你會怎樣做？

3.假設由你負責設計比爾·蓋茨的衞生間。當然，錢不成問題，但是你不可以和比爾談。你會怎樣做？

4.到目前為止，你遇到的最難回答的問題是什麼？

5.如果微軟公司説，我們願意投資500萬美元用來開發你提出的方案。那麼你會做什麼？為什麼？

6.如果你將世界上所有的計算機制造商召集起來，告訴他們必須要做一件事，你會讓他們做什麼事？

7.如果你在五年內會得到一筆獎金，你認為會是因為什麼？關注你的.成績的人會是誰？

8.你如何教自己的奶奶使用微軟Excel表格系統？

9.為什麼當我們在任何一家賓館打開熱水龍頭時，熱水會馬上流出來？

10.假設你回到家，進入自己的房間，打開電燈開關，可是一點反應都沒有——燈沒有亮。這時，你在判斷問題出在哪裏時，會依次採取怎樣的做法？

★為什麼下水道的井蓋是圓的？

★美國有多少輛車？（一個常見的類似問題是：美國有多少家加油站？）

★美國有多少個下水道井蓋？

★你讓某些人為你工作了七天，你要用一根金條作為報酬。這根金條要被分成七塊。你必須在每天的活幹完後交給他們一塊。如果你只能將這根金條切割兩次，你怎樣給這些工人分？

★一列火車以每小時15英里的速度離開洛杉磯，朝紐約進發。另外一列火車以每小時20英里的速度離開紐約，朝洛杉磯進發。如果一隻每小時飛行25英里的鳥同時離開洛杉磯，在兩列火車之間往返飛行，請問當兩列火車相遇時，鳥飛了多遠？

★假設一張圓盤像唱機上的唱盤那樣轉動。這張盤一半是黑色，一半是白色。假設你有數量不限的一些顏色傳感器。要想確定圓盤轉動的方向，你需要在它周圍擺多少個顏色傳感器？它們應該被擺放在什麼位置？

★假設時鐘到了12點。注意時針和分針重疊在一起。在一天之中，時針和分針共重疊多少次？你知道它們重疊時的具體時間嗎？

★你有兩個罐子，分別裝着50個紅色的玻璃球和50個藍色的玻璃球。隨意拿起一個罐子，然後從裏面拿出一個玻璃球。怎樣最大程度地增加讓自己拿到紅球的機會？利用這種方法，拿到紅球的機率有多大？

★中間只隔一個數字的兩個奇數被稱為奇數對，比如17和19。證明奇數對之間的數字總能被6整除（假設這兩個奇數都大於6）。現在證明沒有由三個奇數組成的奇數對。

★一個屋子有一個門（門是關閉的）和3盞電燈。屋外有3個開關，分別與這3盞燈相連。你可以隨意操縱這些開關，可一旦你將門打開，就不能變換開關了。確定每個開關具體管哪盞燈。

★假設你有8個球，其中一個略微重一些，但是找出這個球的惟一方法是將兩個球放在天平上對比。最少要稱多少次才能找出這個較重的球？

★假設你站在鏡子前，抬起左手，抬起右手，看看鏡中的自己。當你抬起左手時，鏡中的自己抬起的似乎是右手。可是當你仰頭時，鏡中的自己也在仰頭，而不是低頭。為什麼鏡子中的影像似乎顛倒了左右，卻沒有顛倒上下？

★你有4瓶藥。每粒藥丸的重量是固定的，不過其中有一瓶藥受到了污染，藥丸的重量發生了變化，每個藥丸增加了一點重量。你怎樣一下子測出哪瓶藥是遭到污染的呢？

★下面玩一個拆字遊戲，所有字母的順序都被打亂。你要判斷這個字是什麼。假設這個被拆開的字由5個字母組成：

1.共有多少種可能的組合方式？

2.如果我們知道是哪5個字母，那會怎麼樣？

3.找出一種解決這個問題的方法。

★有4個女人要過一座橋。她們都站在橋的某一邊，要讓她們在17分鐘內全部通過這座橋。這時是晚上。她們只有一個手電筒。最多隻能讓兩個人同時過橋。不管是誰過橋，不管是一個人還是兩個人，必須要帶着手電筒。手電筒必須要傳來傳去，不能扔過去。每個女人過橋的速度不同，兩個人的速度必須以較慢的那個人的速度過橋。

第一個女人：過橋需要1分鐘;

第二個女人：過橋需要2分鐘;

第三個女人：過橋需要5分鐘;

第四個女人：過橋需要10分鐘。

比如，如果第一個女人與第4個女人首先過橋，等她們過去時，已經過去了10分鐘。如果讓第4個女人將手電筒送回去，那麼等她到達橋的另一端時，總共用去了20分鐘，行動也就失敗了。怎樣讓這4個女人在17分鐘內過橋？還有別的什麼方法？

★如果你有一個5夸脱的水桶和一個3夸脱的水桶，如何準確量出4夸脱的水？

★你有一袋糖，有紅色的，藍色的，綠色的。閉上眼睛，拿出兩塊顏色一樣的糖，你需要拿多少次才能確保有兩塊顏色相同的？

★如果你有兩個桶，一個裝的是紅色的顏料，另一個裝的是藍色的顏料。你從藍色顏料桶裏舀一杯，倒入紅色顏料桶，再從紅色顏料桶裏舀一杯倒入藍顏料桶。兩個桶中紅藍顏料的比例哪個更高？通過算術的方式來證明這一點。