微軟面試100題系列

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19、小的 k 個(gè)。例如輸入 1，2，3，4，5，6，7 和 8 這 8 個(gè)數(shù)字，則最小的 4 個(gè)數(shù)字為 1，2，3 和 4。第 6 題（數(shù)組） 騰訊面試題：給你 10 分鐘時(shí)間，根據(jù)上排給出十個(gè)數(shù)，在其下排填出對應(yīng)的十個(gè)數(shù)要求下排每個(gè)數(shù)都是先前上排那十個(gè)數(shù)在下排出現(xiàn)的次數(shù)。上排的十個(gè)數(shù)如下：【0，1，2，3，4，5，6，7，8，9】舉一個(gè)例子，數(shù)值: 0,1,2,3,4,5,6,7,8,9分配: 6,2,1,0,0,0,1,0,0,00 在下排出現(xiàn)了 6 次，1 在下排出現(xiàn)了 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 在下排出現(xiàn)了 1 次，3 在下排出現(xiàn)了 0 次.以此類推.第 7 題（鏈表）微軟亞院之編程倆個(gè)鏈表是否相交給出倆個(gè)單向鏈表的頭指針，比如 h1，h2， 為了簡化問題，我們假設(shè)倆個(gè)鏈表均不帶環(huán)。問題擴(kuò)展：1. 如果鏈表可能有環(huán)列?2. 如果需要求出倆個(gè)鏈表相交的第一個(gè)節(jié)點(diǎn)列?這倆個(gè)鏈表是否相交。第 8 題（算法）此貼選一些 比較怪的題，由于其中題目本身與算法1.

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

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

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

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

25、)。如果有多對數(shù)字的和等于輸入的數(shù)字，輸出任意一對即可。例如輸入數(shù)組 1、2、4、7、11、15 和數(shù)字 15。由于 4+11=15，因此輸出 4 和 11。第 15 題（樹）：題目：輸入一顆二元查找樹，將該樹轉(zhuǎn)換為它的鏡像，即在轉(zhuǎn)換后的二元查找，左子樹的結(jié)點(diǎn)都大于右子樹的結(jié)點(diǎn)。用遞歸和循環(huán)兩種例如輸入：8/ 6 10/ / 5 7 9 11輸出：8完成樹的鏡像轉(zhuǎn)換。/ 10/ 6/ 11 9 7 5定義二元查找樹的結(jié)點(diǎn)為：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 題（樹）：題目（微軟）：輸入一顆二，從上往下按層打印樹的每個(gè)結(jié)點(diǎn)，同一層中按照從左往右的順序打印。例如輸入8/610/ / 5 7 9 11輸出 8 6 10 5 7 9 11。第 17 題（字）：題目：在一個(gè)字中找到第一個(gè)只出現(xiàn)一次的字符。如輸入 abaccdeff，則輸出 b。分析：這道題是 2006 年 google 的一道筆試題。第 18 題

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

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

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

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

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

32、了簡單起見，我們假設(shè) push 序列的任意兩個(gè)整數(shù)都是不相等的。比如輸入的 push 序列是 1、2、3、4、5，那因?yàn)榭梢杂腥缦碌?push 和 pop 序列：4、5、3、2、1 就有可能是一個(gè) 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 的正數(shù)中 1 出現(xiàn)的次數(shù)（數(shù)組）題目：輸入一個(gè)整數(shù) n，求從 1 到 n 這n 個(gè)整數(shù)的十進(jìn)制表示中 1 出

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

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

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

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

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

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

39、有重復(fù)，以文本文件的形式保存，一行一條，有重復(fù)。請用 5 分鐘時(shí)間，找出重復(fù)出現(xiàn)最多的前 10 條。3.收藏了 1 萬條 url，現(xiàn)在給你一條 url，如何找出相似的url。（面試官不解釋何為相似）45.雅虎（運(yùn)算、矩陣）：1.對于一個(gè)整數(shù)矩陣，一種運(yùn)算，對矩陣中任意元素加一時(shí)，需要其相鄰（上下左右）某一個(gè)元素也加一，現(xiàn)給出一正數(shù)矩陣其是否能夠由一個(gè)矩陣經(jīng)過上述運(yùn)算得到。2.一個(gè)整數(shù)數(shù)組，長度為 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、（運(yùn)算）：四對括號可以有多少種匹配排列方式？比如兩對括號可以有兩種：（）（）和（）47.創(chuàng)新工場（算法）：求一個(gè)數(shù)組的最長遞減子序列 比如9，4，3，2，5，4，3，2的最長遞減子序列為9，5，4，3，248.微軟（運(yùn)算）：一個(gè)數(shù)組是由一個(gè)遞減數(shù)列左移若干位形成的，比如4，3，2，1，6，5 是由6，5，4，3，2，1左移兩位形成的，在這種數(shù)組中查找某一個(gè)數(shù)。49.一道看上去很嚇人的算法面試題（排序、算法）：如何對 n 個(gè)數(shù)進(jìn)行排序，要求時(shí)間復(fù)雜度 O(n)，空間復(fù)雜度 O(1)50.網(wǎng)易有道筆試（sorry，與第 39 題重復(fù)）：1.求一個(gè)二的個(gè)數(shù)，中任意兩個(gè)節(jié)點(diǎn)間的最大距離，兩個(gè)節(jié)點(diǎn)的距離

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

42、深度。例如：輸入二：2110/614/12164輸出該樹的深度 3。二的結(jié)點(diǎn)定義如下：分析：這道題本質(zhì)上還是考查二的遍歷。53.字的排列（字）。題目：輸入一個(gè)字，打印出該字中字符的所有排列。例如輸入字abc，則輸出由字符 a、b、c 所能排列出來的所有字abc、acb、bac、bca、cab 和 cba。分析：這是一道很考查對遞歸理解的編程題，因此在過去一年中頻繁出現(xiàn)在各大公司的面試、筆試題中。54.調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面（數(shù)組）。題目：輸入一個(gè)整數(shù)數(shù)組，調(diào)整數(shù)組中數(shù)字的順序，使得所有奇數(shù)位于數(shù)組的前半部分， 所有偶數(shù)位于數(shù)組的后半部分。要求時(shí)間復(fù)雜度為 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;請實(shí)現(xiàn)其賦值運(yùn)算符的重載函數(shù)，要求異常安全，即當(dāng)對一個(gè)對象進(jìn)行賦值時(shí)發(fā)生異常，對象的狀態(tài)不能改變。56.最長公題目：如果字串（算法、字）。一的所有字符按其在字中的順序出現(xiàn)在另外一個(gè)字二中，則字一稱之為字二的子串。一）的字符必須連續(xù)出現(xiàn)在字注意，并不要求子串（字二中。請編寫一個(gè)函數(shù)，輸入兩個(gè)字，求它們的最長公共子串，并打印出最長公共子串。例如：輸入兩個(gè)字BDCABA 和 ABCBDAB，字BCBA 和 BDAB 都是是它們的最長公共子串，則輸出它們的長度 4，并打印任意一個(gè)子串。分析：求最長公共

45、子串（Longest Common Subsequence, LCS）是一道非常經(jīng)典的動(dòng)態(tài)規(guī)劃題，因此一些重視算法的公司像 MicroStrategy 都把它當(dāng)作面試題。57.用倆個(gè)棧實(shí)現(xiàn)隊(duì)列（棧、隊(duì)列）。題目：某隊(duì)列的如下：分析：從上面的類的中，我們發(fā)現(xiàn)在隊(duì)列中有兩個(gè)棧。因此這道題實(shí)質(zhì)上是要求我們用兩個(gè)棧來實(shí)現(xiàn)一個(gè)隊(duì)列。相信大家對棧和隊(duì)列的基本性質(zhì)都非常了解了：棧是一種先出的數(shù)據(jù)容器，因此對隊(duì)列進(jìn)行的我們總是把新元素和刪除操作都是在棧頂上進(jìn)行；隊(duì)列是一種先入先出的數(shù)據(jù)容器，到隊(duì)列的尾部，而從隊(duì)列的頭部刪除元素。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.從尾到頭輸出鏈表（鏈表）。題目：輸入一個(gè)鏈表的頭結(jié)點(diǎn)，從尾到頭反過來輸出每個(gè)結(jié)點(diǎn)的值。鏈表結(jié)點(diǎn)定義如下：分析：這是一道很有意思的面試題。該題以及它的變體經(jīng)常出現(xiàn)在各大公司

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

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

49、相因此在微軟的面試題中，鏈表出現(xiàn)的概率相當(dāng)高。題目，63.在字中刪除特定的字符（字）。中刪除第二個(gè)字題目：輸入兩個(gè)字例如，輸入”They are則刪除之后的第一個(gè)字，從第一字中所有的字符。s.”和”aeiou”，變成”Thy r stdnts.”。分析：這是一道微軟面試題。在微軟的常見面試題中，與字相題目占了很大的一部分，因?yàn)閷懗绦虿僮髯帜芎芊从澄覀兊木幊袒竟Α?4. 尋找（運(yùn)算）。題目：我們把只包含因子 2、3 和 5 的數(shù)稱作（Ugly Number）。例如 6、8 都是，但 14 不是，因?yàn)樗蜃?7。習(xí)慣上我們把 1 當(dāng)做是第一個(gè)。求按從小到大的順序的第 1500 個(gè)。分析：這是

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

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