微軟面試100題系列

1、微軟面試 100 題系列作者：July-結構之法算法之道 blog 之博主。時間：2010 年 12 月 - 2012 年 9 月出處：本文檔。學習之用，嚴禁用于任何商業(yè)用途。前言本微軟面試 100 題系列，共計 11 篇文章，300 多道面試題，截取本 blog 索引性文章：程序員面試、算法研究、編程藝術、紅黑樹、數據挖掘 5而成，如下圖所示：大系列集錦，中的第一部分編輯本微軟面試 100 題系列涵蓋了數據結構、算法、海量數據處理等 3 大，相比軟面試 100 題系列專欄，去掉了那 3 篇關于永久勘誤的文章（因為，自覺那些不少問題，當然，讀者盡可以讀讀這 100 題一題一題寫的程序員編程藝術

2、系列）。閑不多說，眼下九月正是校招，各種筆試，面試進行火熱的時節(jié)，希望此份微軟面試100 題系列的 PDF 文檔能給正在找工作的朋友助！如果讀者發(fā)現了本系列任何一題的有問題，錯誤，bug，懇請隨時不吝指正，你可以直接評論在原文之下，也可以通過郵件或私信我，方式如下：郵箱：zhoulei0907：1祝諸君均能找到令滿意的 offer 或工作，。July、二零年 9 月。OK，以下是本 blog 內的微軟面試 100 題系列文章的集錦（點擊鏈接，即可跳轉到相應頁面）：橫空出世，席卷互聯網-評微軟等公司數據結構+算法面試 100 題3微軟等公司數據結構+算法面試 100 題(第 1-100 題)首次

3、完整亮相9微軟等數據結構+算法面試 100 題全部集錦36全新整理：微軟、谷歌、等公司經典面試 100 題第 101-160 題111全新整理：微軟、谷歌等公司非常面試題及解答第 161-170 題120海量數據處理：十道面試題與十個海量數據處理總結145海量數據處理面試題與 Bit-map 詳解157教你如何迅速秒殺掉：99%的海量數據處理面試題167九月騰訊，創(chuàng)新工場，淘寶等公司最新面試三十題（第 171-200 題）183十月，阿里巴巴，迅雷搜狗最新面試七十題（第 201-270 題）192十月下旬騰訊，網易游戲，最新校園招聘筆試題集錦(第 271-330 題)212最新九月人搜，阿里巴

4、巴，騰訊京東筆試面試二十題225結語2312橫空出世，席卷互聯網-評微軟等公司數據結構+算法面試 100 題橫空出世，席卷互聯網-評微軟數據結構+算法面試 100 題作者：July。時間：2010 年 10 月-11 月。出處：，。說明：本文原題為：“橫空出世，席卷 Csdn 評微軟等公司數據結構+算法面試 100 題”，但后來此微軟 100 題（加上后續(xù)的 80 道，共計 180 道面試題）已成一系列，被網絡上大量瘋狂，因此特改為上述題目。- - -入編程這一行之初，便些什 列？c 語言程序設計 100 例，太過基礎，入門之后，大量的時間與精力、且得有一定能力之后。說，要多動手寫代碼?？梢?/p>

5、 寫列？寫些什 列？做性不夠。直接做項目，初學者則需花費于是，這份精選微軟等公司數據結構+算法面試 100 題的資料橫空出世了：推薦 整理算法面試：精選微軟經典的算法面試 100 題前 60 題（帖子已結） 10.23。上述帖子已結貼。如果，各位，對 100 題中任何一題、有任何問題，或想法，請把你的思路、或想法回復到這更新帖子上：推薦橫空出世，席卷 Csdn ：記微軟等 100 題系列數次被薦100 題永久維護地址11.26 日。=僅僅一，此帖子 4 次上 csdn bbs 首頁，3 次上 csdn 首頁?？傸c擊率已超過 10000（直至現在已被網絡上大量瘋狂，估計已被上十萬人看過或見識到）

6、。在這份資料里，作者不僅大膽的羅列了微軟等公司極具代表性的精彩 100 題，更為重要的是，作者在展示思考成果的同時，與一群志同道合的同志，一起思考每一道題，想辦法怎樣一步步去編寫代碼，并及時的整理的思路、和方案。3這 100 道題，不僅解決了大量初學者找不到編程素材、練習資料的尷尬，而且更是給你最直接的誘惑：作者隨后直接親自參與做這 100 題，或自個做，或步帶你思考，一步步挖代碼給你看。他人方案，一步作者在展示和他人思考成果的同時，給他人帶來了無比重要的，此舉頗有開源精神。不但授之以魚，而且授之以漁。不但提供給你大量經典的編程素材，而且?guī)Ыo你思考的力量。此等幸運，非有心人。在參與做這 100

7、 道題的浩蕩隊伍中，有，有學生，有正在工作的上班族，有經驗豐富的老者，前微軟 SDET.等等。如此無私奉獻，享受幫助他人的樂趣，思考、追根究底每一道題，此等境界，亦非每一人所有也。編程就是享受思考。一句話，盛宴已擺在桌前，敬請享用。- - -updated：-關于此一百道+后續(xù) 185 道（參見文末），近 300 道面試題的所有一切如下：參見，原題珍藏版微軟等數據結構+算法面試全部 100 題全部出爐100 題首次完整亮相1206/至此，第 1-100 題整理完成，如上所示。微軟等 100 題系列 V0.1 版完成。2010 年12 月 6 日。匯總 II微軟等公司數據結構+算法面試第 1-8

8、0 題前 80 題首次集體亮相 11.27帖子1、2010 年 10 月 11 日，發(fā)表第一篇帖子：算法面試：精選微軟經典的算法面試 100 題每周更新 （已結帖）；2、2010 年 10 月 23 日，發(fā)表第二篇帖子：推薦 整理算法面試：精選微軟經典的算法面試 100 題前 40 題 （4 次被推薦，已結帖）；3、2010 年 11 月 26 日，發(fā)表第三篇帖子，此微軟等 100 題系列永久維護地址：4推薦 橫空出世，席卷 Csdn：記微軟等 100 題系列數次被薦100 題維護地址 （帖子未結）。資源題目系列：1.珍藏版微軟等數據結構+算法面試 100 題全部出爐 完整 100 題地址：2

9、. 最新整理公布 匯總 II 微軟等數據結構+ 算法面試 100 題 第 1-80 題 ：系列：1.最新04：2.V0.4 版微軟等數據結構+算法面試 100 題第 41-60 題2011、01、V0.3 版 微軟等數據結構+ 算法面試 100 題 第 21-40 題 ：3.V0.2 版 精選微軟數據結構+ 算法面試 100 題 前 20 題-：/注：，僅僅只作為思路參考。資源，地址：。本微軟公司面試 100 題的全部日前已經上傳資源，所有讀者可到此處：。2011.10.15。維護1.關微軟等公司數據結構+ 算法面試 100 題系列的鄭重1202 ：52.3.各位，若關于這 100 題，有任何

10、問題，可各位，若對這 100 題中任何一題，有我，My：zhoulei0907思路、或想法，歡迎回復到下面的帖子上：本微軟等 100 題系列的永久維護，帖子地址，推薦橫空出世，席卷 Csdn：記微軟等 100 題系列數 次被薦100 題永久維 護地址11.26 日： 9.html為了更廣泛的與讀者就這微軟等面試 100 題交流，也為了更獲取讀者的反饋，現在，除了可以在帖子上，發(fā)表思路回復，和資源外，我把此微軟 100 題的全部直接放到了本博客上，歡迎，所有的廣大讀者批評指正。V0.2 版第 1 題-20 題博文 IV0.3 版第 21-40 題博文 IIV0.4 版第 41-60 題博文 II

11、I有部分或參考或借鑒自此博客：。特此，十分感謝。現今，這 100 題的錦：已經全部整理出來了，微軟面試 100 題 2010 年版全部。2011.10.13。集勘誤1.化：微軟技術面試 100 題第 1-10 題與優(yōu)化，。2.化：微軟技術面試 100 題第 11-20 題與優(yōu)化，。后續(xù)6微軟面試 100 題 2010 年版全部集錦（含地址）全新整理：微軟、谷歌、等公司經典面試 100 題第 101-160 題全新整理：微軟、Google 等公司的面試題及解答第 161-170 題十道海量數據處理面試題與十個大總結海量數據處理面試題集錦與 Bit-map 詳解教你如何迅速秒殺掉：99%的海量數據

12、處理面試題（解決海量數據處理問題之六把密匙）九月騰訊，創(chuàng)新工場，淘寶等公司最新面試三十題（第 171-200 題）十月，阿里巴巴，迅雷搜狗最新面試七十題（第 201-270 題）十月下旬騰訊，網易游戲，最新校園招聘筆試題集錦(第 271-330 題)藝術根據本 blog 里面的 180 道面試題為題材之一，我專門每一道編程題而創(chuàng)作了程序員編程藝術系列，力爭將編程過程中所有能體現的到的有關選擇合適的數據結構、尋找更高效的算法、編碼規(guī)范等等內容無私，造福天下。參見：程序員編程藝術系列。目前已經寫到了第十章，且將長期寫下去。本編程藝術系列分為三個部分，第一部分、程序設計，主要面試題目，ACM 題目等

13、各類編程題目的設計與實現，第二部分、算法研究，主要以我之前寫的經典算法研究系列為題材擴展深入，第三部分、編碼規(guī)范，主要闡述有關編程中要注意的規(guī)范等問題。ok，一切的參見：程序員編程藝術系列。加入能在網上找到有意義的事情并不多，而如此能幫助到千千萬萬的初學者，和即將要找工作而參加面試的人的事情更是罕見。希望，你也能參與進我們之中來，一起來做這微軟面試187 題，一起享受無私，開源，思考，共同努力，彼此交流，探討的諸多無限樂趣：無限-誠邀你加入微軟面試 187 題的解題中重啟開源，有很多朋友跟我說，已畢業(yè)工作了的都不喜歡做面試編程題了。我覺不然，看你接受的是什式，如果拋開面試這個負擔，純粹為編程而

14、編程，享受思考鍛煉思維的樂趣，則也可以凝聚成一股開源軍，且將聲勢浩大。如我去年 11 月發(fā)的微軟面試貼，如今早已超過 1000 條回復：。7-：1、本人對此微軟面試 100 題系列，原題整理，上傳資源，帖子，勘誤，與優(yōu)化等系列的全部文章或內容，享有全部的超鏈接形式注明出處。任何人或以上任何資料，一律必2、本人，嚴禁任何本 BLOG 內任何內容。否則，永久法律責任，永不懈?。↗uly、二零一零年十月）。8微軟等公司數據結構+算法面試 100 題(第 1-100 題)首次完整亮相作者:July、2010 年 12 月 6 日。1.更新：現今，這 100 題的集錦：已經全部整理出來了，微軟面試 10

15、0 題 2010 年版全部。2.關于此 100 道面試題的所有一切詳情，資源，帖子維護，更新，都請參考此文：橫空出世，席卷 Csdn 評微軟等數據結構+算法面試 100 題。3.以下 100 題中有部分題目整理自何海濤的博客（ 感謝。-）。十分微軟等 100 題系列 V0.1 版終于結束了。從 2010 年 10 月 11 日當天最初發(fā)表前 40 題以來，直至此刻，整理這 100 題，已有近 2 個月。2，因為要整理這 100 題，很多很多其它的事都被我強迫性的擱置一旁，如今，要好好專心去做因這 100 題而被耽誤的、其它的事了。這微軟等數據結構+算法面試 100 題系列(是的，系列)，到底現

16、在、或此刻、或未來，對初學者有多大的意義，在此，我就不給予評說了。由他們來認定。所謂，公道自在人心，我相信這句話。任何人，對以下任何資料、題目、或作者郵箱： zhoulei0907786165179，有任何問題，歡迎我。作者：或以下任何資料、或題目，請注明作者本人 July 及出處。向您的厚道致敬，。9好了，請享受這完完整整的 100 題吧，這-1.把二元查找樹轉變成排序的雙向鏈表（樹） 題目：首次完整亮相哦。:D。輸入一棵二元查找樹，將該二元查找樹轉換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的結點，只調整指針的指向。10/ 6/ 14/48 12 16轉換成雙向鏈表4=6=8=10=12=1

17、4=16。首先我們定義的二元查找樹 節(jié)點的數據結構如下：2.設計包含 min 函數的棧（棧）定義棧的數據結構，要求添加一個 min 函數，能夠得到棧的最小元素。要求函數 min、push 以及 pop 的時間復雜度都是 O(1)。3.求子數組的最大和（數組）題目：輸入一個整形數組，數組里有正數也有負數。數組中連續(xù)的一個或多個整數組成一個子數組，每個子數組求所有子數組的和的最大值。要求時間復雜度為 O(n)。一個和。例如輸入的數組為 1, -2, 3, 10, -4, 7, 2, -5，和最大的子數組為 3, 10, -4, 7, 2，因此輸出為該子數組的和 18。10struct BSTree

18、Nodeint m_nValue; / value of nodeBSTreeNode *m_pLeft; / left child of node BSTreeNode *m_pRight; / right child of node;4.在二中找出和為某一值的所有路徑（樹）題目：輸入一個整數和一棵二。從樹的根結點開始往下一直到葉結點所經過的所有結點形成一條路徑。打印出和與輸入整數相等的所有路徑。例如 輸入整數 22 和如下二10/ 5/4 127則打印出兩條路徑：10, 12 和 10, 5, 7。二節(jié)點的數據結構定義為：5.查找最小的 k 個元素（數組）題目：輸入 n 個整數，輸出其中最

19、小的 k 個。例如輸入 1，2，3，4，5，6，7 和 8 這 8 個數字，則最小的 4 個數字為 1，2，3 和 4。第 6 題（數組） 騰訊面試題：給你 10 分鐘時間，根據上排給出十個數，在其下排填出對應的十個數要求下排每個數都是先前上排那十個數在下排出現的次數。上排的十個數如下：【0，1，2，3，4，5，6，7，8，9】舉一個例子，數值: 0,1,2,3,4,5,6,7,8,9分配: 6,2,1,0,0,0,1,0,0,00 在下排出現了 6 次，1 在下排出現了 2 次，11struct BinaryTreeNode / a node in the binary treeint m_

20、nValue; / value of nodeBinaryTreeNode *m_pLeft; / left child of node BinaryTreeNode *m_pRight; / right child of node;2 在下排出現了 1 次，3 在下排出現了 0 次.以此類推.第 7 題（鏈表）微軟亞院之編程倆個鏈表是否相交給出倆個單向鏈表的頭指針，比如 h1，h2， 為了簡化問題，我們假設倆個鏈表均不帶環(huán)。問題擴展：1. 如果鏈表可能有環(huán)列?2. 如果需要求出倆個鏈表相交的第一個節(jié)點列?這倆個鏈表是否相交。第 8 題（算法）此貼選一些 比較怪的題，由于其中題目本身與算法1.

21、有兩個房間，一間房里有三盞燈，另一間房有不大，僅考考思維。特此并作一題。著三盞燈的三個開關，這兩個房間是 分割開的，從一間里不能看到另一間的情況。現在要求受訓者分別進這兩房間一次，然后出這三盞燈分別是由哪個開關的。有什 辦法呢？2.你讓一些人為你工作了七天，你要用一根金條作為塊。如果你只能將金條切割兩次，你怎樣分給這些工人?。金條被分成七小塊，每天給出一3.用一種算法來顛倒一個鏈接表的順序?，F在在不用遞歸式的情況下做一遍。用一種算法在一個循環(huán)的鏈接表里一個節(jié)點，但不得穿越鏈接表。?用一種算法整理一個數組。你為什 選擇這種用一種算法使通用字相匹配。顛倒一個字。優(yōu)化速度。優(yōu)化空間。顛倒一個句子中的

22、詞的順序，比如將“我叫”轉換為“叫我”，實現速度最快，移動最少。找到一個子字。優(yōu)化速度。優(yōu)化空間。比較兩個字，用 O(n)時間和恒量空間。假設你有一個用 1001 個整數組成的數組，這些整數是任意排列的，但是你知道所有的整數都在 1 到 1000(1000)之間。此外，除一個數字出現兩次外，其他所有數字只出現一次。假設你只能對這個數組做一次處理，用一種算法找出重復的那個數字。如果你在運方式，那 你能找到不用這種方式的算法嗎?算中使用了輔助的不用乘法或加法增加 8 倍?，F在用同樣的增加 7 倍。12第 9 題（樹）整數序列是不是二元查找樹的后序遍歷結果題目：輸入一個整數數組，該數組是不是某二元查

23、找樹的后序遍歷的結果。如果是返回 true，否則返回 false。例如輸入 5、7、6、9、11、10、8，由于這一整數序列是如下樹的后序遍歷結果： 8/ 6/10/579 11因此返回 true。如果輸入 7、4、6、5，沒有哪棵樹的后序遍歷的結果是這個序列，因此返回 false。第 10 題（字）翻轉句子中單詞的順序。題目：輸入一個英文句子，翻轉句子中單詞的順序，但單詞內字符的順序不變。句子中單詞以空格符隔開。為簡單起見，標點符號和普通字母一樣處理。例如輸入“I am a.”，則輸出“. a am I”。第 11 題（樹）求二中節(jié)點的最大距離.如果我們把二看成一個圖，父子節(jié)點之間的連線看成

24、是雙向的，我們姑且定義"距離"為兩節(jié)點之間邊的個數。寫一個程序，求一棵二中相距最遠的兩個節(jié)點之間的距離。第 12 題（語法）題目：求 1+2+n，要求不能使用乘除法、for、while、if、else、switch、case 等關鍵字以及條件語句（A?B:C）。第 13 題（鏈表）：題目：輸入一個單向鏈表，輸出該鏈表中倒數第 k 個結點。鏈表的倒數第 0 個結點為鏈表的尾指針。鏈表結點定義如下：13struct ListNode第 14 題（數組）：題目：輸入一個已經按升序排序過的數組和一個數字，在數組中查找兩個數，使得它們的和正好是輸入的那個數字。要求時間復雜度是 O(n

25、)。如果有多對數字的和等于輸入的數字，輸出任意一對即可。例如輸入數組 1、2、4、7、11、15 和數字 15。由于 4+11=15，因此輸出 4 和 11。第 15 題（樹）：題目：輸入一顆二元查找樹，將該樹轉換為它的鏡像，即在轉換后的二元查找，左子樹的結點都大于右子樹的結點。用遞歸和循環(huán)兩種例如輸入：8/ 6 10/ / 5 7 9 11輸出：8完成樹的鏡像轉換。/ 10/ 6/ 11 9 7 5定義二元查找樹的結點為：14struct BSTreeNode / a node in the binary search tree (BST)int m_nValue; / value of n

26、odeBSTreeNode *m_pLeft; / left child of node BSTreeNode *m_pRight; / right child of node;int m_nKey; ListNode* m_pNext;第 16 題（樹）：題目（微軟）：輸入一顆二，從上往下按層打印樹的每個結點，同一層中按照從左往右的順序打印。例如輸入8/610/ / 5 7 9 11輸出 8 6 10 5 7 9 11。第 17 題（字）：題目：在一個字中找到第一個只出現一次的字符。如輸入 abaccdeff，則輸出 b。分析：這道題是 2006 年 google 的一道筆試題。第 18 題

27、（數組）：題目：n 個數字（0,1,n-1）形成一個圓圈，從數字 0 開始，每次從這個圓圈中刪除第 m 個數一個為當前數字本身，第二個為當前數字的下一個數字）。當一個數字刪除后，從被刪除數字的下一個繼續(xù)刪除第 m 個數字。求出在這個圓圈中剩下的最后一個數字。July：，這個題目，不少人已經見識過了。第 19 題（數組、遞歸）：題目：定義 Fibonacci 數列如下：/ 0 n=0f(n)= 1 n=1/ f(n-1)+f(n-2) n=2輸入 n，用最快的求該數列的第 n 項。分析：在很多 C 語言教科書中講到遞歸函數的時候，都會用 Fibonacci 作為例子。因此很多程序員對這道題的遞歸

28、解法非常熟悉，但呵呵，你知道的。第 20 題（字）：題目：輸入一個表示整數的字，把該字轉換成整數并輸出。例如輸入字"345"，則輸出整數 345。15第 21 題（數組）2010 年中興面試題編程求解：輸入兩個整數 n 和 m，從數列 1，2，3.n 中 隨意取幾個數,使其和等于 m ,要求將其中所有的可能組合列出來.第 22 題（推理）：有 4 張紅色的牌和 4 張藍色的牌，先拿任意兩張，再分別在 A、B、C 三人額頭上貼任意兩張牌，A、B、C 三人都可以看見其余兩人額頭上的牌，看讓他們猜額頭上是什 顏色的牌，A 說不知道，B 說不知道，C 說不知道，然后 A 說知道了。

29、請教如何推理，A 是怎 知道的。如果用程序，又怎 實現呢？第 23 題（算法）：用最簡單，最快速的計算出下面這個圓形是否和正方形相交。" 3D 坐標系 原點(0.0,0.0,0.0)圓形:半徑 r = 3.0圓心 o = (*.*, 0.0, *.*)正方形:4 個角坐標;1:(*.*, 0.0, *.*)2:(*.*, 0.0, *.*)3:(*.*, 0.0, *.*)4:(*.*, 0.0, *.*)第 24 題（鏈表）：鏈表操作，單鏈表就地逆置，第 25 題（字寫一個函數,它的功能：）：是 int continumax(char *outputstr,char *intput

30、str)在字中找出連續(xù)最長的數字串，并把這個串的長度返回，并把這個最長數字串付給其中一個函數參數 outputstr 所指內存。例如："abcd12345ed125ss123456789"的首地址傳給 intputstr 后，函數將返回 9，16outputstr 所指的值為 12345678926.左旋轉字題目：（字）定義字的左旋轉操作：把字前面的若干個字符移動到字的尾部。abcdef 左旋轉 2 位得到字cdefab。請實現字如把字左旋轉的函數。要求時間對長度為 n 的字操作的復雜度為 O(n)，輔助內存為 O(1)。27.跳臺階問題（遞歸）題目：一個臺階總共有 n 級

31、，如果一次可以跳 1 級，也可以跳 2 級。求總共有多少總跳法，并分析算法的時間復雜度。這道題最近經常出現，MicroStrategy 等比較重視算法的公司都曾先后選用過個這道題作為面試題或者筆試題。28.整數的二進制表示中 1 的個數（運算）題目：輸入一個整數，求該整數的二進制表達中有多少個 1。例如輸入 10，由于其二進制表示為 1010，有兩個 1，因此輸出 2。分析：這是一道很基本的考查位運算的面試題。微軟在內的很多公司都曾采用過這道題。29.棧的 push、pop 序列（棧）題目：輸入兩個整數序列。其中一個序列表示棧的 push 順序， 另一個序列有沒有可能是對應的 pop 順序。為

32、了簡單起見，我們假設 push 序列的任意兩個整數都是不相等的。比如輸入的 push 序列是 1、2、3、4、5，那因為可以有如下的 push 和 pop 序列：4、5、3、2、1 就有可能是一個 pop 系列。push 1，push 2，push 3，push 4，pop，push 5，pop，pop，pop，pop， 這樣得到的 pop 序列就是 4、5、3、2、1。但序列 4、3、5、1、2 就不可能是 push 序列 1、2、3、4、5 的 pop 序列。30.在從 1 到 n 的正數中 1 出現的次數（數組）題目：輸入一個整數 n，求從 1 到 n 這n 個整數的十進制表示中 1 出

33、現的次數。例如輸入 12，從 1 到 12 這些整數中包含 1 的數字有 1，10，11 和 12，1 一共出現了 5 次。分析：這是一道廣為流傳的 google 面試題。1731.面試題（搜索）：一類似于蜂窩的結構的圖，進行搜索最短路徑（要求 5 分鐘）32.（數組、規(guī)劃）有兩個序列 a,b，大小n,序列元素的值任意整數，無序；要求：通過交換 a,b 中的元素，使序列 a 元素的和與序列 b 元素的和之間的差最小。例如:33.（字）實現一個挺高級的字符匹配算法：給一串很長字，要求找到符合要求的字，例如目的串：1231*3*2 ,12*3 這些都要找出來其實就是類似一些和諧系統。34.（隊列）

34、實現一個隊列。隊列的應用場景為：一個生產者線程將 int 類型的數入列，一個消費者線程將 int 類型的數出列35.（矩陣）求一個矩陣中最大的二維矩陣(元素和最大).如: 1 2 0 3 42 3 4 5 11 1 5 3 0中最大的是:4 55 3要求:(1)寫出算法;(2)分析時間復雜度;(3)用 C 寫出關鍵代碼第 36 題-40 題（有些題目搜集于 CSDN 上的網友，已標明）：36.自網友：longzuo（運算）谷歌筆試：18var a=100,99,98,1,2,3;var b=1,2,3,4,5,40;n 支隊伍比賽，分別編號為 0，1，2。n-1，已知它們之間的實力對比，在一個

35、二維數組 wnn中，wij 的值代表編號為 i，j 的隊伍中更強的一支。所以 wij=i 或者 j，現在給出它們的出場順序，并在數組 ordern中，比如 ordern = 4,3,5,8,1.，那 第一輪比賽就是 4 對 3， 5 對 8。.勝者晉級，敗者淘汰，同一輪淘汰的所有隊伍排名不再細分，即可以隨便排，下一輪由上一輪的勝者按照順序，再依次兩兩比，比如可能是 4 對 5,直至出現第一名編程實現，給出二維數組 w，一維數組 order 和 用于輸出比賽名次的數組 resultn，求出 result。37.（字）有 n 個長為 m+1 的字，如果某個字問這 n 個字的最后m 個字符與某個字的

36、前 m 個字符匹配，則兩個字可以聯接，最多可以連成一個多長的字，如果出現循環(huán)，則返回錯誤。38.（算法）面試：1.用天平（只能比較，不能稱重）從一堆小球中找出其中唯一一個較輕的，使用 x 次天平，最多可以從 y 個小球中找出較輕的那個，求 y 與 x 的式。2.有一個很大很大的輸入流，大到沒有器可以將其下來，。而且只輸入一次，如何從這個輸入流中隨機取得 m 個3.大量的 URL 字，如何從中去除重復的，優(yōu)化時間空間復雜度39.（樹、圖、算法） 網易有道筆試：(1).求一個二中任意兩個節(jié)點間的最大距離，兩個節(jié)點的距離的定義是 這兩個節(jié)點間邊的個數，比如某個孩子節(jié)點和父節(jié)點間的距離是 1，和相鄰兄

37、弟節(jié)點間的距離是 2，優(yōu)化時間空間復雜度。(2).求一個有向連通圖的割點，割點的定義是，如果除去此節(jié)點和與其相有向圖不再連通，描述算法。邊，40.研發(fā)筆試題（棧、算法）自：zp155334877191) 設計一個棧結構，滿足一下條件：min，push，pop 操作的時間復雜度為 O(1)。2) 一串首尾相連的珠子(m 個)，有 N 種顏色(N<=10)，設計一個算法，取出其中一段，要求包含所有 N 中顏色，并使長度最短。并分析時間復雜度與空間復雜度。3)設計一個系統處理詞語搭配問題，比如說和人民可以搭配，則人民效。要求：數量可能上千次；*系統每秒的*詞語的數量級為 10W；*每個詞至多可

38、以與 1W 個詞搭配當用戶輸入的時候，要求返回與這個搭配詞組相。41.求機的查找程序（匹配、算法）盤由數目不詳的大小一樣的組成，并不一定全布滿盤，照相機每次這能匹配一個，如匹配過，則拾取該，若匹配不過，照相機則按測間距移到下一個位置。求遍歷盤的算法 求思路。42.請修改 append 函數，利用這個函數實現（鏈表）：兩個非降序鏈表的并集，1->2->3 和 2->3->5 并為 1->2->3->5另外只能輸出結果，不能修改兩個鏈表的數據。43.遞歸和非遞歸倆種實現二的前序遍歷。44.騰訊面試題（算法）：1.設計一個魔方（六面）的程序。2.有一千萬條，

39、有重復，以文本文件的形式保存，一行一條，有重復。請用 5 分鐘時間，找出重復出現最多的前 10 條。3.收藏了 1 萬條 url，現在給你一條 url，如何找出相似的url。（面試官不解釋何為相似）45.雅虎（運算、矩陣）：1.對于一個整數矩陣，一種運算，對矩陣中任意元素加一時，需要其相鄰（上下左右）某一個元素也加一，現給出一正數矩陣其是否能夠由一個矩陣經過上述運算得到。2.一個整數數組，長度為 n，將其分為 m 份，使各份的和相等，求 m 的最大值比如3，2，4，3，6 可以分成3，2，4，3，6 m=1;3,62,4,3 m=2203,32,46 m=3 所以 m 的最大值為 346.搜狐

40、（運算）：四對括號可以有多少種匹配排列方式？比如兩對括號可以有兩種：（）（）和（）47.創(chuàng)新工場（算法）：求一個數組的最長遞減子序列 比如9，4，3，2，5，4，3，2的最長遞減子序列為9，5，4，3，248.微軟（運算）：一個數組是由一個遞減數列左移若干位形成的，比如4，3，2，1，6，5 是由6，5，4，3，2，1左移兩位形成的，在這種數組中查找某一個數。49.一道看上去很嚇人的算法面試題（排序、算法）：如何對 n 個數進行排序，要求時間復雜度 O(n)，空間復雜度 O(1)50.網易有道筆試（sorry，與第 39 題重復）：1.求一個二的個數，中任意兩個節(jié)點間的最大距離，兩個節(jié)點的距離

41、的定義是 這兩個節(jié)點間邊比如某個孩子節(jié)點和父節(jié)點間的距離是 1，和相鄰兄弟節(jié)點間的距離是 2，優(yōu)化時間空間復雜度。2.求一個有向連通圖的割點，割點的定義是，如果除去此節(jié)點和與其相邊，有向圖不再連通，描述算法。-51.和為 n 連續(xù)正數序列（數組）。題目：輸入一個正數 n，輸出所有和為 n 連續(xù)正數序列。例如輸入 15，由于 1+2+3+4+5=4+5+6=7+8=15，所以輸出 3 個連續(xù)序列 1-5、4-6 和 7-8。分析：這是網易的一道面試題。52.二的深度（樹）。題目：輸入一棵二的根結點，求該樹的深度。從根結點到葉結點依次經過的結點（含根、葉結點）形成樹的一條路徑，最長路徑的長度為樹的

42、深度。例如：輸入二：2110/614/12164輸出該樹的深度 3。二的結點定義如下：分析：這道題本質上還是考查二的遍歷。53.字的排列（字）。題目：輸入一個字，打印出該字中字符的所有排列。例如輸入字abc，則輸出由字符 a、b、c 所能排列出來的所有字abc、acb、bac、bca、cab 和 cba。分析：這是一道很考查對遞歸理解的編程題，因此在過去一年中頻繁出現在各大公司的面試、筆試題中。54.調整數組順序使奇數位于偶數前面（數組）。題目：輸入一個整數數組，調整數組中數字的順序，使得所有奇數位于數組的前半部分， 所有偶數位于數組的后半部分。要求時間復雜度為 O(n)。55.（語法）題目：

43、類 CMyString 的如下：22class CMyStringpublic:CMyString(char* pData = NULL); CMyString(const CMyString& str);CMyString(void);CMyString& operator = (const CMyString& str);struct SBinaryTreeNode / a node of the binary treeint m_nValue; / value of nodeSBinaryTreeNode *m_pLeft; / left child of nod

44、e SBinaryTreeNode *m_pRight; / right child of node;請實現其賦值運算符的重載函數，要求異常安全，即當對一個對象進行賦值時發(fā)生異常，對象的狀態(tài)不能改變。56.最長公題目：如果字串（算法、字）。一的所有字符按其在字中的順序出現在另外一個字二中，則字一稱之為字二的子串。一）的字符必須連續(xù)出現在字注意，并不要求子串（字二中。請編寫一個函數，輸入兩個字，求它們的最長公共子串，并打印出最長公共子串。例如：輸入兩個字BDCABA 和 ABCBDAB，字BCBA 和 BDAB 都是是它們的最長公共子串，則輸出它們的長度 4，并打印任意一個子串。分析：求最長公共

45、子串（Longest Common Subsequence, LCS）是一道非常經典的動態(tài)規(guī)劃題，因此一些重視算法的公司像 MicroStrategy 都把它當作面試題。57.用倆個棧實現隊列（棧、隊列）。題目：某隊列的如下：分析：從上面的類的中，我們發(fā)現在隊列中有兩個棧。因此這道題實質上是要求我們用兩個棧來實現一個隊列。相信大家對棧和隊列的基本性質都非常了解了：棧是一種先出的數據容器，因此對隊列進行的我們總是把新元素和刪除操作都是在棧頂上進行；隊列是一種先入先出的數據容器，到隊列的尾部，而從隊列的頭部刪除元素。23template<typename T> class CQueue

46、public:CQueue() CQueue() void appendTail(const T& node); / append a element to tailvoid deleteHead();/ remove a element from headprivate:Stack<T> m_stack1; Stack<T> m_stack2;private:char* m_pData;58.從尾到頭輸出鏈表（鏈表）。題目：輸入一個鏈表的頭結點，從尾到頭反過來輸出每個結點的值。鏈表結點定義如下：分析：這是一道很有意思的面試題。該題以及它的變體經常出現在各大公司

47、的面試、筆試題中。59.不能被繼承的類（語法）。題目：用 C+設計一個不能被繼承的類。分析：這是 Adobe 公司 2007 年校園招聘的最新筆試題。這道題除了考察應聘者的 C+基本功底外，還能考察反應能力，是一道很題目。60.在 O（1）時間內刪除鏈表結點（鏈表、算法）。題目：給定鏈表的頭指針和一個結點指針，在 O(1)時間刪除該結點。鏈表結點的定義如下：函數的如下：分析：這是一道廣為流傳的 Google 面試題，能有效考察我們的編程基本功，還能考察我們的反應速度，更重要的是，還能考察我們對時間復雜度的理解。-61.找出數組中兩個只出現一次的數字（數組）題目：一個整型數組里除了兩個數字之外，

48、其他的數字都出現了兩次。請寫程序找出這兩個只出現一次的數字。要求時間復雜度是 O(n)，空間復雜度是 O(1)。分析：這是一道很新穎的關于位運算的面試題。62.找出鏈表的第一個公共結點（鏈表）。題目：兩個單向鏈表，找出它們的第一個公共結點。24void DeleteNistNode* pListHead, ListNode* pToBeDeleted);struct ListNodeint m_nKey; ListNode* m_pNext;struct ListNodeint m_nKey; ListNode* m_pNext;鏈表的結點定義為：分析：這是一道微軟的面試題。微軟非常喜歡與鏈表

49、相因此在微軟的面試題中，鏈表出現的概率相當高。題目，63.在字中刪除特定的字符（字）。中刪除第二個字題目：輸入兩個字例如，輸入”They are則刪除之后的第一個字，從第一字中所有的字符。s.”和”aeiou”，變成”Thy r stdnts.”。分析：這是一道微軟面試題。在微軟的常見面試題中，與字相題目占了很大的一部分，因為寫程序操作字能很反映我們的編程基本功。64. 尋找（運算）。題目：我們把只包含因子 2、3 和 5 的數稱作（Ugly Number）。例如 6、8 都是，但 14 不是，因為它包含因子 7。習慣上我們把 1 當做是第一個。求按從小到大的順序的第 1500 個。分析：這是

50、一道在網絡上廣為流傳的面試題，據說 google 曾經采用過這道題。65.輸出 1 到最大的 N 位數（運算）題目：輸入數字 n，按順序輸出從 1 最大的 n 位 10 進制數。比如輸入 3， 則輸出 1、2、3 一直到最大的 3 位數即 999。分析：這是一道很有意思的題目?？雌饋砗芎唵?，其實里面卻有不少的。66.顛倒棧（棧）。題目：用遞歸顛倒一個棧。例如輸入棧1, 2, 3, 4, 5，1 在棧頂。顛倒之后的棧為5, 4, 3, 2, 1，5 處在棧頂。67.倆個閑玩娛樂（運算）。1.從牌的順子牌中隨機抽 5 張牌，是不是一個順子，即這 5 張牌是不是連續(xù)的。2-10 為數字本身，A 為

51、1，J 為 11，Q 為 12，K 為 13，而大小王可以看成任意數字。25struct ListNodeint m_nKey; ListNode*m_pNext;2.n 個把 n 個的點數。朝上一面的點數之和為 S。輸入 n，扔在地上，所有打印出 S 的所有可能的值出現的概率。68.把數組排小的數（數組、算法）。題目：輸入一個正整數數組，將它們連接起來排成一個數，輸出能排出的所有數字中最小的一個。例如輸入數組32, 321，則輸出這兩個能排成的最小數字 32132。請給出解決問題的算法，并證明該算法。分析：這是 09 年 6 月份從這道題我們可以看出的一道面試題，對應聘者在算法方面有很高的要求。69.