【正文】 [珍藏版]微軟等數(shù)據(jù)結(jié)構(gòu)+算法面試100題全部出爐[] 微軟等數(shù)據(jù)結(jié)構(gòu)+算法面試100題首次完整亮相 ================作者:July 2010年12月6日。從2010年10月11日當(dāng)天最初發(fā)表前40題以來，直至此刻，整理這100題，已有近2個月。2個月，因為要整理這100題，很多很多其它的事都被我強迫性的擱置一旁，如今，要好好專心去做因這100題而被耽誤的、其它的事了。這微軟等數(shù)據(jù)結(jié)構(gòu)+算法面試100題系列(是的，系列)，到底現(xiàn)在、或此刻、或未來，對初學(xué)者有多大的意義，在此，我就不給予評說了。由他們自己來認(rèn)定。所謂，公道自在人心，我相信這句話。 題目：輸入一棵二元查找樹，將該二元查找樹轉(zhuǎn)換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點，只調(diào)整指針的指向。 10 / \ 6 14 / \ / \4 8 12 16 轉(zhuǎn)換成雙向鏈表4=6=8=10=12=14=16。 首先我們定義的二元查找樹 節(jié)點的數(shù)據(jù)結(jié)構(gòu)如下： struct BSTreeNode{ int m_nValue。 // value of node BSTreeNode *m_pLeft。 // left child of node BSTreeNode *m_pRight。 // right child of node}。 。定義棧的數(shù)據(jù)結(jié)構(gòu)，要求添加一個min函數(shù)，能夠得到棧的最小元素。要求函數(shù)min、push以及pop的時間復(fù)雜度都是O(1)。 題目：輸入一個整形數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。數(shù)組中連續(xù)的一個或多個整數(shù)組成一個子數(shù)組，每個子數(shù)組都有一個和。求所有子數(shù)組的和的最大值。要求時間復(fù)雜度為O(n)。例如輸入的數(shù)組為1, 2, 3, 10, 4, 7, 2, 5，和最大的子數(shù)組為3, 10, 4, 7, 2，因此輸出為該子數(shù)組的和18。 題目：輸入一個整數(shù)和一棵二元樹。從樹的根結(jié)點開始往下訪問一直到葉結(jié)點所經(jīng)過的所有結(jié)點形成一條路徑。打印出和與輸入整數(shù)相等的所有路徑。例如 輸入整數(shù)22和如下二元樹 10 / \ 5 12 / \ 4 7則打印出兩條路徑：10, 12和10, 5, 7。二元樹節(jié)點的數(shù)據(jù)結(jié)構(gòu)定義為：struct BinaryTreeNode // a node in the binary tree{int m_nValue。 // value of nodeBinaryTreeNode *m_pLeft。 // left child of nodeBinaryTreeNode *m_pRight。 // right child of node}。 題目：輸入n個整數(shù)，輸出其中最小的k個。例如輸入1，2，3，4，5，6，7和8這8個數(shù)字，則最小的4個數(shù)字為1，2，3和4。 第6題騰訊面試題： 給你10分鐘時間，根據(jù)上排給出十個數(shù)，在其下排填出對應(yīng)的十個數(shù) 要求下排每個數(shù)都是先前上排那十個數(shù)在下排出現(xiàn)的次數(shù)。 上排的十個數(shù)如下： 【0，1，2，3，4，5，6，7，8，9】舉一個例子， 數(shù)值: 0,1,2,3,4,5,6,7,8,9 分配: 6,2,1,0,0,0,1,0,0,0 0在下排出現(xiàn)了6次，1在下排出現(xiàn)了2次， 2在下排出現(xiàn)了1次，3在下排出現(xiàn)了0次.... 以此類推.. 第7題微軟亞院之編程判斷倆個鏈表是否相交給出倆個單向鏈表的頭指針，比如h1，h2，判斷這倆個鏈表是否相交。為了簡化問題，我們假設(shè)倆個鏈表均不帶環(huán)。問題擴展：??第8題此貼選一些 比較怪的題，由于其中題目本身與算法關(guān)系不大，僅考考思維。特此并作一題。，一間房里有三盞燈，另一間房有控制著三盞燈的三個開關(guān)，這兩個房間是 分割開的，從一間里不能看到另一間的情況。現(xiàn)在要求受訓(xùn)者分別進(jìn)這兩房間一次，然后判斷出這三盞燈分別是由哪個開關(guān)控制的。有什么辦法呢？，你要用一根金條作為報酬。金條被分成七小塊，每天給出一塊。如果你只能將金條切割兩次，你怎樣分給這些工人?3.　★用一種算法來顛倒一個鏈接表的順序?，F(xiàn)在在不用遞歸式的情況下做一遍?！　　镉靡环N算法在一個循環(huán)的鏈接表里插入一個節(jié)點，但不得穿越鏈接表。　　★用一種算法整理一個數(shù)組。你為什么選擇這種方法?　　★用一種算法使通用字符串相匹配?！　　镱嵉挂粋€字符串。優(yōu)化速度。優(yōu)化空間?！　　镱嵉挂粋€句子中的詞的順序，比如將“我叫克麗絲”轉(zhuǎn)換為“克麗絲叫我”，實現(xiàn)速度最快，移動最少?！　　镎业揭粋€子字符串。優(yōu)化速度。優(yōu)化空間。　　★比較兩個字符串，用O(n)時間和恒量空間?！　　锛僭O(shè)你有一個用1001個整數(shù)組成的數(shù)組，這些整數(shù)是任意排列的，但是你知道所有的整數(shù)都在1到1000(包括1000)之間。此外，除一個數(shù)字出現(xiàn)兩次外，其他所有數(shù)字只出現(xiàn)一次。假設(shè)你只能對這個數(shù)組做一次處理，用一種算法找出重復(fù)的那個數(shù)字。如果你在運算中使用了輔助的存儲方式，那么你能找到不用這種方式的算法嗎?　　★不用乘法或加法增加8倍?，F(xiàn)在用同樣的方法增加7倍。第9題判斷整數(shù)序列是不是二元查找樹的后序遍歷結(jié)果題目：輸入一個整數(shù)數(shù)組，判斷該數(shù)組是不是某二元查找樹的后序遍歷的結(jié)果。如果是返回true，否則返回false。例如輸入18，由于這一整數(shù)序列是如下樹的后序遍歷結(jié)果： 8 / \ 6 10 / \ / \ 5 7 9 11因此返回true。如果輸入5，沒有哪棵樹的后序遍歷的結(jié)果是這個序列，因此返回false。第10題翻轉(zhuǎn)句子中單詞的順序。題目：輸入一個英文句子，翻轉(zhuǎn)句子中單詞的順序，但單詞內(nèi)字符的順序不變。句子中單詞以空格符隔開。為簡單起見，標(biāo)點符號和普通字母一樣處理。例如輸入“I am a student.”，則輸出“student. a am I”。第11題求二叉樹中節(jié)點的最大距離...如果我們把二叉樹看成一個圖，父子節(jié)點之間的連線看成是雙向的，我們姑且定義距離為兩節(jié)點之間邊的個數(shù)。寫一個程序，求一棵二叉樹中相距最遠(yuǎn)的兩個節(jié)點之間的距離。第12題題目：求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case等關(guān)鍵字以及條件判斷語句（A?B:C）。第13題：題目：輸入一個單向鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點。鏈表的倒數(shù)第0個結(jié)點為鏈表的尾指針。鏈表結(jié)點定義如下： struct ListNode{ int m_nKey。 ListNode* m_pNext。}。第14題：題目：輸入一個已經(jīng)按升序排序過的數(shù)組和一個數(shù)字，在數(shù)組中查找兩個數(shù)，使得它們的和正好是輸入的那個數(shù)字。要求時間復(fù)雜度是O(n)。如果有多對數(shù)字的和等于輸入的數(shù)字，輸出任意一對即可。例如輸入數(shù)組115和數(shù)字15。由于4+11=15，因此輸出4和11。第15題：題目：輸入一顆二元查找樹，將該樹轉(zhuǎn)換為它的鏡像，即在轉(zhuǎn)換后的二元查找樹中，左子樹的結(jié)點都大于右子樹的結(jié)點。用遞歸和循環(huán)兩種方法完成樹的鏡像轉(zhuǎn)換。 例如輸入： 8 / \ 6 10/\ /\5 7 9 11輸出： 8 / \10 6/\ /\11 9 7 5定義二元查找樹的結(jié)點為：struct BSTreeNode // a node in the binary search tree (BST){ int m_nValue。 // value of node BSTreeNode *m_pLeft。 // left child of node BSTreeNode *m_pRight。 // right child of node}。第16題：題目（微軟）：輸入一顆二元樹，從上往下按層打印樹的每個結(jié)點，同一層中按照從左往右的順序打印。 例如輸入 8 / \6 10/ \ / \5 7 9 11輸出8 6 10 5 7 9 11。第17題：題目：在一個字符串中找到第一個只出現(xiàn)一次的字符。如輸入abaccdeff，則輸出b。 分析：這道題是2006年google的一道筆試題。第18題：題目：n個數(shù)字（0,1,…,n1）形成一個圓圈，從數(shù)字0開始，每次從這個圓圈中刪除第m個數(shù)字（第一個為當(dāng)前數(shù)字本身，第二個為當(dāng)前數(shù)字的下一個數(shù)字）。當(dāng)一個數(shù)字刪除后，從被刪除數(shù)字的下一個繼續(xù)刪除第m個數(shù)字。求出在這個圓圈中剩下的最后一個數(shù)字。July：我想，這個題目，不少人已經(jīng) 見識過了。第19題：題目：定義Fibonacci數(shù)列如下： / 0 n=0f(n)= 1 n=1 \ f(n1)+f(n2) n=2輸入n，用最快的方法求該數(shù)列的第n項。分析：在很多C語言教科書中講到遞歸函數(shù)的時候，都會用Fibonacci作為例子。因此很多程序員對這道題的遞歸解法非常熟悉，但....呵呵，你知道的。第20題：題目：輸入一個表示整數(shù)的字符串，把該字符串轉(zhuǎn)換成整數(shù)并輸出。例如輸入字符串345，則輸出整數(shù)345。第21題2010年中興面試題編程求解：輸入兩個整數(shù) n 和 m，從數(shù)列1，2，3.......n 中 隨意取幾個數(shù),使其和等于 m ,要求將其中所有的可能組合列出來.第22題：有4張紅色的牌和4張藍(lán)色的牌，主持人先拿任意兩張，再分別在A、B、C三人額頭上貼任意兩張牌，A、B、C三人都可以看見其余兩人額頭上的牌，看完后讓他們猜自己額頭上是什么顏色的牌，A說不知道，B說不知道，C說不知道，然后A說知道了。請教如何推理，A是怎么知道的。如果用程序，又怎么實現(xiàn)呢？第23題：用最簡單，最快速的方法計算出下面這個圓形是否和正方形相交。 3D坐標(biāo)系 原點(,)圓形:半徑r = 圓心o = (*.*, , *.*)正方形:4個角坐標(biāo)。 1:(*.*, , *.*)2:(*.*, , *.*)3:(*.*, , *.*)4:(*.*, , *.*)第24題：鏈表操作，（1）.單鏈表就地逆置，（2）合并鏈表第25題：寫一個函數(shù),它的原形是int continumax(char *outputstr,char *intputstr)功能：在字符串中找出連續(xù)最長的數(shù)字串，并把這個串的長度返回，并把這個最長數(shù)字串付給其中一個函數(shù)參數(shù)outputstr所指內(nèi)存。例如：abcd12345ed125ss123456789的首地址傳給intputstr后，函數(shù)將返回9，outputstr所指的值為123456789題目：定義字符串的左旋轉(zhuǎn)操作：把字符串前面的若干個字符移動到字符串的尾部。如把字符串a(chǎn)bcdef左旋轉(zhuǎn)2位得到字符串cdefab。請實現(xiàn)字符串左旋轉(zhuǎn)的函數(shù)。要求時間對長度為n的字符串操作的復(fù)雜度為O(n)，輔助內(nèi)存為O(1)。題目：一個臺階總共有n級，如果一次可以跳1級，也可以跳2級。求總共有多少總跳法，并分析算法的時間復(fù)雜度。這道題最近經(jīng)常出現(xiàn)，包括MicroStrategy等比較重視算法的公司都曾先后選用過個這道題作為面試題或者筆試題。題目：輸入一個整數(shù)，求該整數(shù)的二進(jìn)制表達(dá)中有多少個1。例如輸入10，由于其二進(jìn)制表示為1010，有兩個1，因此輸出2。分析：這是一道很基本的考查位運算的面試題。包括微軟在內(nèi)的很多公司都曾采用過這道題。、pop序列題目：輸入兩個整數(shù)序列。其中一個序列表示棧的push順序，判斷另一個序列有沒有可能是對應(yīng)的pop順序。為了簡單起見，我們假設(shè)push序列的任意兩個整數(shù)都是不相等的。 比如輸入的push序列是5，那么1就有可能是一個pop系列。因為可以有如下的push和pop序列：push 1，push 2，push 3，push 4，pop，push 5，pop，pop，pop，pop，這樣得到的pop序列就是1。但序列2就不可能是push序列5的pop序列。題目：輸入一個整數(shù)n，求從1到