微软公司等数据结构+算法面试100题2010版全部出炉
微軟等公司數據結構+算法面試100題2010版首次完整亮相??
??????????????????????
作者:July、2010年12月6日。
---------------------------------------------------?
?
微軟等100題系列V0.1版終于結束了。
從2010年10月11日當天最初發表前40題以來，直至此刻，整理這100題，已有近2個月。
2個月，因為要整理這100題，很多很多其它的事都被我強迫性的擱置一旁，
如今，要好好專心去做因這100題而被耽誤的、其它的事了。
?
這微軟等數據結構+算法面試100題系列(是的，系列)，到底現在、或此刻、或未來，對初學者有多大的意義，
在此，我就不給予評說了。
由他們自己來認定。所謂，公道自在人心，我相信這句話。
?
任何人，對以下任何資料、題目、或答案，有任何問題，歡迎聯系我。
作者郵箱：
zhoulei0907@yahoo.cn
786165179@qq.com
?
作者聲明：
轉載或引用以下任何資料、或題目，請注明作者本人July及出處。
向您的厚道致敬，謝謝。
?
好了，請享受這完完整整的100題吧，這可是首次完整亮相哦。:D。
-----------------------------------
1.把二元查找樹轉變成排序的雙向鏈表（樹）
?題目：
輸入一棵二元查找樹，將該二元查找樹轉換成一個排序的雙向鏈表。
要求不能創建任何新的結點，只調整指針的指向。
?? 10
? / /
? 6? 14
?/ / / /
4? 8 12 16
?轉換成雙向鏈表
4=6=8=10=12=14=16。
?
?首先我們定義的二元查找樹 節點的數據結構如下：
?struct BSTreeNode
{
? int m_nValue; // value of node
? BSTreeNode *m_pLeft; // left child of node
? BSTreeNode *m_pRight; // right child of node
};
?
2.設計包含min函數的棧（棧）
定義棧的數據結構，要求添加一個min函數，能夠得到棧的最小元素。
要求函數min、push以及pop的時間復雜度都是O(1)。
?
3.求子數組的最大和（數組）
題目：
輸入一個整形數組，數組里有正數也有負數。
數組中連續的一個或多個整數組成一個子數組，每個子數組都有一個和。
求所有子數組的和的最大值。要求時間復雜度為O(n)。
例如輸入的數組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數組為3, 10, -4, 7, 2，
因此輸出為該子數組的和18。
?
4.在二元樹中找出和為某一值的所有路徑（樹）
題目：輸入一個整數和一棵二元樹。
從樹的根結點開始往下訪問一直到葉結點所經過的所有結點形成一條路徑。
打印出和與輸入整數相等的所有路徑。
例如 輸入整數22和如下二元樹
? 10?
? / /??
?5? 12??
?/?? /??
4???? 7
則打印出兩條路徑：10, 12和10, 5, 7。
二元樹節點的數據結構定義為：
struct BinaryTreeNode // a node in the binary tree
{
int m_nValue; // value of node
BinaryTreeNode *m_pLeft; // left child of node
BinaryTreeNode *m_pRight; // right child of node
};
?
5.查找最小的k個元素（數組）
題目：輸入n個整數，輸出其中最小的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,0
0在下排出現了6次，1在下排出現了2次，
2在下排出現了1次，3在下排出現了0次....
以此類推..
第7題（鏈表）
微軟亞院之編程判斷倆個鏈表是否相交
給出倆個單向鏈表的頭指針，比如h1，h2，判斷這倆個鏈表是否相交。
為了簡化問題，我們假設倆個鏈表均不帶環。
問題擴展：
1.如果鏈表可能有環列?
2.如果需要求出倆個鏈表相交的第一個節點列?
?
第8題（算法）
此貼選一些 比較怪的題，，由于其中題目本身與算法關系不大，僅考考思維。特此并作一題。
1.有兩個房間，一間房里有三盞燈，另一間房有控制著三盞燈的三個開關，
這兩個房間是 分割開的，從一間里不能看到另一間的情況。
現在要求受訓者分別進這兩房間一次，然后判斷出這三盞燈分別是由哪個開關控制的。
有什么辦法呢？
2.你讓一些人為你工作了七天，你要用一根金條作為報酬。金條被分成七小塊，每天給出一塊。
如果你只能將金條切割兩次，你怎樣分給這些工人?
3. ★用一種算法來顛倒一個鏈接表的順序。現在在不用遞歸式的情況下做一遍。
★用一種算法在一個循環的鏈接表里插入一個節點，但不得穿越鏈接表。
★用一種算法整理一個數組。你為什么選擇這種方法?
★用一種算法使通用字符串相匹配。
★顛倒一個字符串。優化速度。優化空間。
★顛倒一個句子中的詞的順序，比如將“我叫克麗絲”轉換為“克麗絲叫我”，
實現速度最快，移動最少。
★找到一個子字符串。優化速度。優化空間。
★比較兩個字符串，用O(n)時間和恒量空間。
★假設你有一個用1001個整數組成的數組，這些整數是任意排列的，但是你知道所有的整數都在1到1000(包括1000)之間。此外，除一個數字出現兩次外，其他所有數字只出現一次。假設你只能對這個數組做一次處理，用一種算法找出重復的那個數字。如果你在運算中使用了輔助的存儲方式，那么你能找到不用這種方式的算法嗎?
★不用乘法或加法增加8倍。現在用同樣的方法增加7倍。
?
第9題（樹）
判斷整數序列是不是二元查找樹的后序遍歷結果
題目：輸入一個整數數組，判斷該數組是不是某二元查找樹的后序遍歷的結果。
如果是返回true，否則返回false。
例如輸入5、7、6、9、11、10、8，由于這一整數序列是如下樹的后序遍歷結果：
???????? 8
????? /? /
???? 6??? 10
??? / /? / /
?? 5? 7 9? 11
因此返回true。
如果輸入7、4、6、5，沒有哪棵樹的后序遍歷的結果是這個序列，因此返回false。
?
第10題（字符串）
翻轉句子中單詞的順序。
題目：輸入一個英文句子，翻轉句子中單詞的順序，但單詞內字符的順序不變。
句子中單詞以空格符隔開。為簡單起見，標點符號和普通字母一樣處理。
例如輸入“I am a student.”，則輸出“student. a am I”。
?
第11題（樹）
求二叉樹中節點的最大距離...
如果我們把二叉樹看成一個圖，父子節點之間的連線看成是雙向的，
我們姑且定義"距離"為兩節點之間邊的個數。
寫一個程序，
求一棵二叉樹中相距最遠的兩個節點之間的距離。
?
第12題（語法）
題目：求1+2+…+n，
要求不能使用乘除法、for、while、if、else、switch、case等關鍵字以及條件判斷語句（A?B:C）。
?
第13題（鏈表）：
題目：輸入一個單向鏈表，輸出該鏈表中倒數第k個結點。鏈表的倒數第0個結點為鏈表的尾指針。
鏈表結點定義如下：?
struct ListNode
{
? int m_nKey;
? ListNode* m_pNext;
};
?
第14題（數組）：
題目：輸入一個已經按升序排序過的數組和一個數字，
在數組中查找兩個數，使得它們的和正好是輸入的那個數字。
要求時間復雜度是O(n)。如果有多對數字的和等于輸入的數字，輸出任意一對即可。
例如輸入數組1、2、4、7、11、15和數字15。由于4+11=15，因此輸出4和11。
?
第15題（樹）：
題目：輸入一顆二元查找樹，將該樹轉換為它的鏡像，
即在轉換后的二元查找樹中，左子樹的結點都大于右子樹的結點。
用遞歸和循環兩種方法完成樹的鏡像轉換。?
例如輸入：
? 8
? / /
? 6 10
?// //
5 7 9 11
輸出：
?? 8
? / /
?10 6
?// //
11 9 7 5
定義二元查找樹的結點為：
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題（樹）：
題目（微軟）：
輸入一顆二元樹，從上往下按層打印樹的每個結點，同一層中按照從左往右的順序打印。?
例如輸入
? ?8
? / /
?6 10
/ / / /
5 7 9 11
輸出8 6 10 5 7 9 11。
?
第17題（字符串）：
題目：在一個字符串中找到第一個只出現一次的字符。如輸入abaccdeff，則輸出b。?
分析：這道題是2006年google的一道筆試題。
?
第18題（數組）：
題目：n個數字（0,1,…,n-1）形成一個圓圈，從數字0開始，
每次從這個圓圈中刪除第m個數字（第一個為當前數字本身，第二個為當前數字的下一個數字）。
當一個數字刪除后，從被刪除數字的下一個繼續刪除第m個數字。
求出在這個圓圈中剩下的最后一個數字。
July：我想，這個題目，不少人已經 見識過了。
?
第19題（數組、遞歸）：
題目：定義Fibonacci數列如下：?
? / 0 n=0
f(n)= 1 n=1
? / f(n-1)+f(n-2) n=2
輸入n，用最快的方法求該數列的第n項。
分析：在很多C語言教科書中講到遞歸函數的時候，都會用Fibonacci作為例子。
因此很多程序員對這道題的遞歸解法非常熟悉，但....呵呵，你知道的。。
?
第20題（字符串）：
題目：輸入一個表示整數的字符串，把該字符串轉換成整數并輸出。
例如輸入字符串"345"，則輸出整數345。
?
第21題（數組）
2010年中興面試題
編程求解：
輸入兩個整數 n 和 m，從數列1，2，3.......n 中 隨意取幾個數,
使其和等于 m ,要求將其中所有的可能組合列出來.
?
第22題（推理）：
有4張紅色的牌和4張藍色的牌，主持人先拿任意兩張，再分別在A、B、C三人額頭上貼任意兩張牌，
A、B、C三人都可以看見其余兩人額頭上的牌，看完后讓他們猜自己額頭上是什么顏色的牌，
A說不知道，B說不知道，C說不知道，然后A說知道了。
請教如何推理，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 *intputstr)
功能：
在字符串中找出連續最長的數字串，并把這個串的長度返回，
并把這個最長數字串付給其中一個函數參數outputstr所指內存。
例如："abcd12345ed125ss123456789"的首地址傳給intputstr后，函數將返回9，
outputstr所指的值為123456789
?
26.左旋轉字符串（字符串）
題目：
定義字符串的左旋轉操作：把字符串前面的若干個字符移動到字符串的尾部。
如把字符串abcdef左旋轉2位得到字符串cdefab。請實現字符串左旋轉的函數。
要求時間對長度為n的字符串操作的復雜度為O(n)，輔助內存為O(1)。
?
27.跳臺階問題（遞歸）
題目：一個臺階總共有n級，如果一次可以跳1級，也可以跳2級。
求總共有多少總跳法，并分析算法的時間復雜度。
這道題最近經常出現，包括MicroStrategy等比較重視算法的公司
都曾先后選用過個這道題作為面試題或者筆試題。
?
28.整數的二進制表示中1的個數（運算）
題目：輸入一個整數，求該整數的二進制表達中有多少個1。
例如輸入10，由于其二進制表示為1010，有兩個1，因此輸出2。
分析：
這是一道很基本的考查位運算的面試題。
包括微軟在內的很多公司都曾采用過這道題。
?
29.棧的push、pop序列（棧）
題目：輸入兩個整數序列。其中一個序列表示棧的push順序，
判斷另一個序列有沒有可能是對應的pop順序。
為了簡單起見，我們假設push序列的任意兩個整數都是不相等的。?
比如輸入的push序列是1、2、3、4、5，那么4、5、3、2、1就有可能是一個pop系列。
因為可以有如下的push和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出現的次數。
例如輸入12，從1到12這些整數中包含1 的數字有1，10，11和12，1一共出現了5次。
分析：這是一道廣為流傳的google面試題。
?
31.華為面試題（搜索）：
一類似于蜂窩的結構的圖，進行搜索最短路徑（要求5分鐘）
?
32.（數組、規劃）
有兩個序列a,b，大小都為n,序列元素的值任意整數，無序；
要求：通過交換a,b中的元素，使[序列a元素的和]與[序列b元素的和]之間的差最小。
例如:?
var a=[100,99,98,1,2, 3];
var b=[1, 2, 3, 4,5,40];
?
33.（字符串）
實現一個挺高級的字符匹配算法：
給一串很長字符串，要求找到符合要求的字符串，例如目的串：123
1******3***2 ,12*****3這些都要找出來
其實就是類似一些和諧系統。。。。。
?
34.（隊列）
實現一個隊列。
隊列的應用場景為：
一個生產者線程將int類型的數入列，一個消費者線程將int類型的數出列
?
35.（矩陣）
求一個矩陣中最大的二維矩陣(元素和最大).如:
1 2 0 3 4
2 3 4 5 1
1 1 5 3 0
中最大的是:
4 5
5 3
要求:(1)寫出算法;(2)分析時間復雜度;(3)用C寫出關鍵代碼
?
第36題-40題（有些題目搜集于CSDN上的網友，已標明）：
36.引用自網友：longzuo（運算）
谷歌筆試：
n支隊伍比賽，分別編號為0，1，2。。。。n-1，已知它們之間的實力對比關系，
存儲在一個二維數組w[n][n]中，w[i][j] 的值代表編號為i，j的隊伍中更強的一支。
所以w[i][j]=i 或者j，現在給出它們的出場順序，并存儲在數組order[n]中，
比如order[n] = {4,3,5,8,1......}，那么第一輪比賽就是 4對3， 5對8。.......
勝者晉級，敗者淘汰，同一輪淘汰的所有隊伍排名不再細分，即可以隨便排，
下一輪由上一輪的勝者按照順序，再依次兩兩比，比如可能是4對5,直至出現第一名
編程實現，給出二維數組w，一維數組order 和 用于輸出比賽名次的數組result[n]，
求出result。
?
37.（字符串）
有n個長為m+1的字符串，
如果某個字符串的最后m個字符與某個字符串的前m個字符匹配，則兩個字符串可以聯接，
問這n個字符串最多可以連成一個多長的字符串，如果出現循環，則返回錯誤。
?
38.（算法）
百度面試：
1.用天平（只能比較，不能稱重）從一堆小球中找出其中唯一一個較輕的，使用x次天平，
最多可以從y個小球中找出較輕的那個，求y與x的關系式。
2.有一個很大很大的輸入流，大到沒有存儲器可以將其存儲下來，
而且只輸入一次，如何從這個輸入流中隨機取得m個記錄。
3.大量的URL字符串，如何從中去除重復的，優化時間空間復雜度
?
39.（樹、圖、算法）
網易有道筆試：
(1).
求一個二叉樹中任意兩個節點間的最大距離，
兩個節點的距離的定義是 這兩個節點間邊的個數，
比如某個孩子節點和父節點間的距離是1，和相鄰兄弟節點間的距離是2，優化時間空間復雜度。
(2).
求一個有向連通圖的割點，割點的定義是，如果除去此節點和與其相關的邊，
有向圖不再連通，描述算法。
?
40.百度研發筆試題（棧、算法）
引用自：zp155334877
1)設計一個棧結構，滿足一下條件：min，push，pop操作的時間復雜度為O(1)。
2)一串首尾相連的珠子(m個)，有N種顏色(N<=10)，
設計一個算法，取出其中一段，要求包含所有N中顏色，并使長度最短。
并分析時間復雜度與空間復雜度。
3)設計一個系統處理詞語搭配問題，比如說 中國 和人民可以搭配，
則中國人民 人民中國都有效。要求：
? *系統每秒的查詢數量可能上千次；
? *詞語的數量級為10W；
? *每個詞至多可以與1W個詞搭配
當用戶輸入中國人民的時候，要求返回與這個搭配詞組相關的信息。
41.求固晶機的晶元查找程序（匹配、算法）
晶元盤由數目不詳的大小一樣的晶元組成，晶元并不一定全布滿晶元盤，
照相機每次這能匹配一個晶元，如匹配過，則拾取該晶元，
若匹配不過，照相機則按測好的晶元間距移到下一個位置。
求遍歷晶元盤的算法 求思路。
?
42.請修改append函數，利用這個函數實現（鏈表）：
兩個非降序鏈表的并集，1->2->3 和 2->3->5 并為 1->2->3->5
另外只能輸出結果，不能修改兩個鏈表的數據。
?
43.遞歸和非遞歸倆種方法實現二叉樹的前序遍歷。
?
44.騰訊面試題（算法）：
1.設計一個魔方（六面）的程序。
2.有一千萬條短信，有重復，以文本文件的形式保存，一行一條，有重復。
請用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,6}{2,4,3} m=2
? {3,3}{2,4}{6} m=3 所以m的最大值為3
?
46.搜狐（運算）：
四對括號可以有多少種匹配排列方式？比如兩對括號可以有兩種：（）（）和（（））
47.創新工場（算法）：
求一個數組的最長遞減子序列 比如{9，4，3，2，5，4，3，2}的最長遞減子序列為{9，5，4，3，2}
?
48.微軟（運算）：
一個數組是由一個遞減數列左移若干位形成的，比如{4，3，2，1，6，5}
是由{6，5，4，3，2，1}左移兩位形成的，在這種數組中查找某一個數。
?
49.一道看上去很嚇人的算法面試題（排序、算法）：
如何對n個數進行排序，要求時間復雜度O(n)，空間復雜度O(1)
?
50.網易有道筆試（sorry，與第39題重復）：
1.求一個二叉樹中任意兩個節點間的最大距離，兩個節點的距離的定義是 這兩個節點間邊的個數，
比如某個孩子節點和父節點間的距離是1，和相鄰兄弟節點間的距離是2，優化時間空間復雜度。
2.求一個有向連通圖的割點，割點的定義是，
如果除去此節點和與其相關的邊，有向圖不再連通，描述算法。
-------------------------------------------------------------------
51.和為n連續正數序列（數組）。
題目：輸入一個正數n，輸出所有和為n連續正數序列。
例如輸入15，由于1+2+3+4+5=4+5+6=7+8=15，所以輸出3個連續序列1-5、4-6和7-8。
分析：這是網易的一道面試題。
?
52.二元樹的深度（樹）。
題目：輸入一棵二元樹的根結點，求該樹的深度。
從根結點到葉結點依次經過的結點（含根、葉結點）形成樹的一條路徑，最長路徑的長度為樹的深度。
例如：輸入二元樹：
??????????????????????????????????????????? 10
????????????????????????????????????????? /???? /
??????????????????????????????????????? 6??????? 14
????????????????????????????????????? /???????? /?? /
??????????????????????????????????? 4???????? 12???? 16
輸出該樹的深度3。
二元樹的結點定義如下：
struct SBinaryTreeNode // a node of the binary tree
{
????? int?????????????? m_nValue; // value of node
????? SBinaryTreeNode? *m_pLeft;? // left child of node
????? SBinaryTreeNode? *m_pRight; // right child of node
};
分析：這道題本質上還是考查二元樹的遍歷。
?
53.字符串的排列（字符串）。
題目：輸入一個字符串，打印出該字符串中字符的所有排列。
例如輸入字符串abc，則輸出由字符a、b、c所能排列出來的所有字符串
abc、acb、bac、bca、cab和cba。
分析：這是一道很好的考查對遞歸理解的編程題，
因此在過去一年中頻繁出現在各大公司的面試、筆試題中。
?
54.調整數組順序使奇數位于偶數前面（數組）。
題目：輸入一個整數數組，調整數組中數字的順序，使得所有奇數位于數組的前半部分，
所有偶數位于數組的后半部分。要求時間復雜度為O(n)。
?
55.（語法）
題目：類CMyString的聲明如下：
class CMyString
{
public:
????? CMyString(char* pData = NULL);
????? CMyString(const CMyString& str);
????? ~CMyString(void);
????? CMyString& operator = (const CMyString& str);
private:
????? char* m_pData;
};
請實現其賦值運算符的重載函數，要求異常安全，即當對一個對象進行賦值時發生異常，對象的狀態不能改變。
?
56.最長公共字串（算法、字符串）。
題目：如果字符串一的所有字符按其在字符串中的順序出現在另外一個字符串二中，
則字符串一稱之為字符串二的子串。
注意，并不要求子串（字符串一）的字符必須連續出現在字符串二中。
請編寫一個函數，輸入兩個字符串，求它們的最長公共子串，并打印出最長公共子串。
例如：輸入兩個字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它們的最長公共子串，
則輸出它們的長度4，并打印任意一個子串。
分析：求最長公共子串（Longest Common Subsequence, LCS）是一道非常經典的動態規劃題，
因此一些重視算法的公司像MicroStrategy都把它當作面試題。
?
57.用倆個棧實現隊列（棧、隊列）。
題目：某隊列的聲明如下：
template<typename T> class CQueue
{
public:
????? CQueue() {}
????? ~CQueue() {}
????? void appendTail(const T& node);? // append a element to tail
????? void deleteHead();?????????????? // remove a element from head
private:
???? T> m_stack1;
???? T> m_stack2;
};
分析：從上面的類的聲明中，我們發現在隊列中有兩個棧。
因此這道題實質上是要求我們用兩個棧來實現一個隊列。
相信大家對棧和隊列的基本性質都非常了解了：棧是一種后入先出的數據容器，
因此對隊列進行的插入和刪除操作都是在棧頂上進行；隊列是一種先入先出的數據容器，
我們總是把新元素插入到隊列的尾部，而從隊列的頭部刪除元素。
?
58.從尾到頭輸出鏈表（鏈表）。
題目：輸入一個鏈表的頭結點，從尾到頭反過來輸出每個結點的值。鏈表結點定義如下：
struct ListNode
{
????? int?????? m_nKey;
????? ListNode* m_pNext;
};
分析：這是一道很有意思的面試題。
該題以及它的變體經常出現在各大公司的面試、筆試題中。
?
59.不能被繼承的類（語法）。
題目：用C++設計一個不能被繼承的類。
分析：這是Adobe公司2007年校園招聘的最新筆試題。
這道題除了考察應聘者的C++基本功底外，還能考察反應能力，是一道很好的題目。
?
?
60.在O（1）時間內刪除鏈表結點（鏈表、算法）。
題目：給定鏈表的頭指針和一個結點指針，在O(1)時間刪除該結點。鏈表結點的定義如下：
struct ListNode
{
????? int??????? m_nKey;
????? ListNode*? m_pNext;
};
函數的聲明如下：
void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);
分析：這是一道廣為流傳的Google面試題，能有效考察我們的編程基本功，還能考察我們的反應速度，
更重要的是，還能考察我們對時間復雜度的理解。
-------------------------------------------------------------------------
?
61.找出數組中兩個只出現一次的數字（數組）
題目：一個整型數組里除了兩個數字之外，其他的數字都出現了兩次。
請寫程序找出這兩個只出現一次的數字。要求時間復雜度是O(n)，空間復雜度是O(1)。
分析：這是一道很新穎的關于位運算的面試題。
?
62.找出鏈表的第一個公共結點（鏈表）。
題目：兩個單向鏈表，找出它們的第一個公共結點。
鏈表的結點定義為：
struct ListNode
{
????? int???????? m_nKey;
????? ListNode*?? m_pNext;
};
分析：這是一道微軟的面試題。微軟非常喜歡與鏈表相關的題目，
因此在微軟的面試題中，鏈表出現的概率相當高。
?
63.在字符串中刪除特定的字符（字符串）。
題目：輸入兩個字符串，從第一字符串中刪除第二個字符串中所有的字符。
例如，輸入”They are students.”和”aeiou”，
則刪除之后的第一個字符串變成”Thy r stdnts.”。
分析：這是一道微軟面試題。在微軟的常見面試題中，與字符串相關的題目占了很大的一部分，
因為寫程序操作字符串能很好的反映我們的編程基本功。
?
64. 尋找丑數（運算）。
題目：我們把只包含因子2、3和5的數稱作丑數（Ugly Number）。例如6、8都是丑數，
但14不是，因為它包含因子7。習慣上我們把1當做是第一個丑數。
求按從小到大的順序的第1500個丑數。
分析：這是一道在網絡上廣為流傳的面試題，據說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張牌是不是連續的。
2-10為數字本身，A為1，J為11，Q為12，K為13，而大小王可以看成任意數字。
2.n個骰子的點數。
把n個骰子扔在地上，所有骰子朝上一面的點數之和為S。輸入n，
打印出S的所有可能的值出現的概率。
?
68.把數組排成最小的數（數組、算法）。
題目：輸入一個正整數數組，將它們連接起來排成一個數，輸出能排出的所有數字中最小的一個。
例如輸入數組{32,? 321}，則輸出這兩個能排成的最小數字32132。
請給出解決問題的算法，并證明該算法。
分析：這是09年6月份百度的一道面試題，
從這道題我們可以看出百度對應聘者在算法方面有很高的要求。
?
69.旋轉數組中的最小元素（數組、算法）。
題目：把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個排好序的數組的一個旋轉，
輸出旋轉數組的最小元素。例如數組{3, 4, 5, 1, 2}為{1, 2, 3, 4, 5}的一個旋轉，該數組的最小值為1。
??? 分析：這道題最直觀的解法并不難。從頭到尾遍歷數組一次，就能找出最小的元素，
時間復雜度顯然是O(N)。但這個思路沒有利用輸入數組的特性，我們應該能找到更好的解法。
?
70.給出一個函數來輸出一個字符串的所有排列（經典字符串問題）。
ANSWER 簡單的回溯就可以實現了。當然排列的產生也有很多種算法，去看看組合數學，
還有逆序生成排列和一些不需要遞歸生成排列的方法。
印象中Knuth的<TAOCP>第一卷里面深入講了排列的生成。這些算法的理解需要一定的數學功底，
也需要一定的靈感，有興趣最好看看。
?
71.數值的整數次方（數字、運算）。
題目：實現函數double Power(double base, int exponent)，求base的exponent次方。
不需要考慮溢出。
分析：這是一道看起來很簡單的問題。可能有不少的人在看到題目后30秒寫出如下的代碼：
double Power(double base, int exponent)
{
????? double result = 1.0;
????? for(int i = 1; i <= exponent; ++i)
??????????? result *= base;
????? return result;
}
?
?
72.（語法）
題目：設計一個類，我們只能生成該類的一個實例。
分析：只能生成一個實例的類是實現了Singleton模式的類型。
?
?
73.對稱字符串的最大長度（字符串）。
題目：輸入一個字符串，輸出該字符串中對稱的子字符串的最大長度。
比如輸入字符串“google”，由于該字符串里最長的對稱子字符串是“goog”，因此輸出4。
分析：可能很多人都寫過判斷一個字符串是不是對稱的函數，這個題目可以看成是該函數的加強版。
?
74.數組中超過出現次數超過一半的數字（數組）
題目：數組中有一個數字出現的次數超過了數組長度的一半，找出這個數字。
分析：這是一道廣為流傳的面試題，包括百度、微軟和Google在內的多家公司都
曾經采用過這個題目。要幾十分鐘的時間里很好地解答這道題，
除了較好的編程能力之外，還需要較快的反應和較強的邏輯思維能力。
?
?
75.二叉樹兩個結點的最低共同父結點（樹）
題目：二叉樹的結點定義如下：
struct TreeNode
{
??? int m_nvalue;
??? TreeNode* m_pLeft;
??? TreeNode* m_pRight;
};
輸入二叉樹中的兩個結點，輸出這兩個結點在數中最低的共同父結點。
分析：求數中兩個結點的最低共同結點是面試中經常出現的一個問題。這個問題至少有兩個變種。
?
76.復雜鏈表的復制（鏈表、算法）
題目：有一個復雜鏈表，其結點除了有一個m_pNext指針指向下一個結點外，
還有一個m_pSibling指向鏈表中的任一結點或者NULL。其結點的C++定義如下：
?struct ComplexNode
{
??? int m_nValue;
??? ComplexNode* m_pNext;
??? ComplexNode* m_pSibling;
};
下圖是一個含有5個結點的該類型復雜鏈表。
圖中實線箭頭表示m_pNext指針，虛線箭頭表示m_pSibling指針。為簡單起見，
指向NULL的指針沒有畫出。
????????????????????????????????
請完成函數ComplexNode* Clone(ComplexNode* pHead)，以復制一個復雜鏈表。
分析：在常見的數據結構上稍加變化，這是一種很新穎的面試題。
要在不到一個小時的時間里解決這種類型的題目，我們需要較快的反應能力，
對數據結構透徹的理解以及扎實的編程功底。
?
?
77.關于鏈表問題的面試題目如下（鏈表）：
1.給定單鏈表，檢測是否有環。
?使用兩個指針p1,p2從鏈表頭開始遍歷，p1每次前進一步，p2每次前進兩步。如果p2到達鏈表尾部，
說明無環，否則p1、p2必然會在某個時刻相遇(p1==p2)，從而檢測到鏈表中有環。
?
2.給定兩個單鏈表(head1, head2)，檢測兩個鏈表是否有交點，如果有返回第一個交點。
??????? 如果head1==head2，那么顯然相交，直接返回head1。
否則，分別從head1,head2開始遍歷兩個鏈表獲得其長度len1與len2，假設len1>=len2，
那么指針p1由head1開始向后移動len1-len2步，指針p2=head2，
下面p1、p2每次向后前進一步并比較p1p2是否相等，如果相等即返回該結點，
否則說明兩個鏈表沒有交點。
3.給定單鏈表(head)，如果有環的話請返回從頭結點進入環的第一個節點。
??????? 運用題一，我們可以檢查鏈表中是否有環。
??????? 如果有環，那么p1p2重合點p必然在環中。從p點斷開環，
方法為：p1=p, p2=p->next, p->next=NULL。此時，原單鏈表可以看作兩條單鏈表，
一條從head開始，另一條從p2開始，于是運用題二的方法，我們找到它們的第一個交點即為所求。
4.只給定單鏈表中某個結點p(并非最后一個結點，即p->next!=NULL)指針，刪除該結點。
?辦法很簡單，首先是放p中數據,然后將p->next的數據copy入p中，接下來刪除p->next即可。
5.只給定單鏈表中某個結點p(非空結點)，在p前面插入一個結點。
? 辦法與前者類似，首先分配一個結點q，將q插入在p后，接下來將p中的數據copy入q中，
然后再將要插入的數據記錄在p中。
?
78.鏈表和數組的區別在哪里（鏈表、數組）？
分析：主要在基本概念上的理解。
但是最好能考慮的全面一點，現在公司招人的競爭可能就在細節上產生，
誰比較仔細，誰獲勝的機會就大。
?
79.（鏈表、字符串）
1.編寫實現鏈表排序的一種算法。說明為什么你會選擇用這樣的方法？
2.編寫實現數組排序的一種算法。說明為什么你會選擇用這樣的方法？
3.請編寫能直接實現strstr()函數功能的代碼。
?
80.阿里巴巴一道筆試題（運算、算法）
問題描述:
12個高矮不同的人,排成兩排,每排必須是從矮到高排列,而且第二排比對應的第一排的人高,問排列方式有多少種?
這個筆試題,很YD,因為把某個遞歸關系隱藏得很深。
?
先來幾組百度的面試題：
===================
81.第1組百度面試題
1.一個int數組，里面數據無任何限制，要求求出所有這樣的數a[i]，
其左邊的數都小于等于它，右邊的數都大于等于它。
能否只用一個額外數組和少量其它空間實現。
2.一個文件，內含一千萬行字符串，每個字符串在1K以內，
要求找出所有相反的串對，如abc和cba。
3.STL的set用什么實現的？為什么不用hash？
?
82.第2組百度面試題
1.給出兩個集合A和B，其中集合A={name}，
集合B={age、sex、scholarship、address、...}，
要求：
問題1、根據集合A中的name查詢出集合B中對應的屬性信息；
問題2、根據集合B中的屬性信息（單個屬性，如age<20等），查詢出集合A中對應的name。
2.給出一個文件，里面包含兩個字段{url、size}，
即url為網址，size為對應網址訪問的次數，
要求：
問題1、利用Linux Shell命令或自己設計算法，
查詢出url字符串中包含“baidu”子字符串對應的size字段值；
問題2、根據問題1的查詢結果，對其按照size由大到小的排列。
（說明：url數據量很大，100億級以上）
?
83.第3組百度面試題
1.今年百度的一道題目
百度筆試：給定一個存放整數的數組，重新排列數組使得數組左邊為奇數，右邊為偶數。
要求：空間復雜度O(1)，時間復雜度為O（n）。
2.百度筆試題
用C語言實現函數void * memmove(void *dest, const void *src, size_t n)。
memmove函數的功能是拷貝src所指的內存內容前n個字節到dest所指的地址上。
分析：
由于可以把任何類型的指針賦給void類型的指針
這個函數主要是實現各種數據類型的拷貝。
?
84.第4組百度面試題
2010年3道百度面試題[相信，你懂其中的含金量]
1.a~z包括大小寫與0~9組成的N個數
用最快的方式把其中重復的元素挑出來。
2.已知一隨機發生器，產生0的概率是p，產生1的概率是1-p，現在要你構造一個發生器，
使得它構造0和1的概率均為1/2；構造一個發生器，使得它構造1、2、3的概率均為1/3；...，
構造一個發生器，使得它構造1、2、3、...n的概率均為1/n，要求復雜度最低。
3.有10個文件，每個文件1G，
每個文件的每一行都存放的是用戶的query，每個文件的query都可能重復。
要求按照query的頻度排序.
?
85.又見字符串的問題
1.給出一個函數來復制兩個字符串A和B。
字符串A的后幾個字節和字符串B的前幾個字節重疊。
分析：記住，這種題目往往就是考你對邊界的考慮情況。
2.已知一個字符串，比如asderwsde,尋找其中的一個子字符串比如sde的個數，
如果沒有返回0，有的話返回子字符串的個數。
?
86.
怎樣編寫一個程序，把一個有序整數數組放到二叉樹中？
分析:本題考察二叉搜索樹的建樹方法，簡單的遞歸結構。
關于樹的算法設計一定要聯想到遞歸，因為樹本身就是遞歸的定義。
而，學會把遞歸改稱非遞歸也是一種必要的技術。
畢竟，遞歸會造成棧溢出，關于系統底層的程序中不到非不得以最好不要用。
但是對某些數學問題，就一定要學會用遞歸去解決。
?
87.
1.大整數數相乘的問題。（這是2002年在一考研班上遇到的算法題）
2.求最大連續遞增數字串（如“ads3sl456789DF3456ld345AA”中的“456789”）
3.實現strstr功能，即在父串中尋找子串首次出現的位置。
（筆試中常讓面試者實現標準庫中的一些函數）
?
88.2005年11月金山筆試題。編碼完成下面的處理函數。
函數將字符串中的字符'*'移到串的前部分，
前面的非'*'字符后移，但不能改變非'*'字符的先后順序，函數返回串中字符'*'的數量。
如原始串為：ab**cd**e*12，
處理后為*****abcde12，函數并返回值為5。（要求使用盡量少的時間和輔助空間）
?
89.神州數碼、華為、東軟筆試題
1.2005年11月15日華為軟件研發筆試題。實現一單鏈表的逆轉。
2.編碼實現字符串轉整型的函數（實現函數atoi的功能），據說是神州數碼筆試題。如將字符
串 ”+123”123, ”-0123”-123, “123CS45”123, “123.45CS”123, “CS123.45”0
3.快速排序（東軟喜歡考類似的算法填空題，又如堆排序的算法等）
4.刪除字符串中的數字并壓縮字符串。
如字符串”abc123de4fg56”處理后變為”abcdefg”。注意空間和效率。
（下面的算法只需要一次遍歷，不需要開辟新空間，時間復雜度為O(N)）
5.求兩個串中的第一個最長子串（神州數碼以前試題）。
如"abractyeyt","dgdsaeactyey"的最大子串為"actyet"。
?
90.
1.不開辟用于交換數據的臨時空間，如何完成字符串的逆序
(在技術一輪面試中，有些面試官會這樣問)。
2.刪除串中指定的字符
（做此題時，千萬不要開辟新空間，否則面試官可能認為你不適合做嵌入式開發）
3.判斷單鏈表中是否存在環。
?
91.
1.一道著名的毒酒問題
有1000桶酒，其中1桶有毒。而一旦吃了，毒性會在1周后發作。
現在我們用小老鼠做實驗，要在1周內找出那桶毒酒，問最少需要多少老鼠。
2.有趣的石頭問題
有一堆1萬個石頭和1萬個木頭，對于每個石頭都有1個木頭和它重量一樣，
把配對的石頭和木頭找出來。
?
?
92.
1.多人排成一個隊列,我們認為從低到高是正確的序列,但是總有部分人不遵守秩序。
如果說,前面的人比后面的人高(兩人身高一樣認為是合適的),
那么我們就認為這兩個人是一對“搗亂分子”,比如說,現在存在一個序列:
176, 178, 180, 170, 171
這些搗亂分子對為
<176, 170>, <176, 171>, <178, 170>, <178, 171>, <180, 170>, <180, 171>,
那么,現在給出一個整型序列,請找出這些搗亂分子對的個數(僅給出搗亂分子對的數目即可,不用具體的對)
要求：
輸入:
為一個文件(in)，文件的每一行為一個序列。序列全為數字，數字間用”,”分隔。
輸出：
為一個文件(out)，每行為一個數字，表示搗亂分子的對數。
詳細說明自己的解題思路，說明自己實現的一些關鍵點。
并給出實現的代碼 ，并分析時間復雜度。
限制：
輸入每行的最大數字個數為100000個，數字最長為6位。程序無內存使用限制。
?
93.在一個int數組里查找這樣的數，它大于等于左側所有數，小于等于右側所有數。
直觀想法是用兩個數組a、b。a[i]、b[i]分別保存從前到i的最大的數和從后到i的最小的數，
一個解答：這需要兩次遍歷，然后再遍歷一次原數組，
將所有data[i]>=a[i-1]&&data[i]<=b[i]的data[i]找出即可。
給出這個解答后，面試官有要求只能用一個輔助數組，且要求少遍歷一次。
?
94.微軟筆試題
求隨機數構成的數組中找到長度大于=3的最長的等差數列9 d- x' W) w9 ?" o3 b0 R
輸出等差數列由小到大:
如果沒有符合條件的就輸出
格式：
輸入[1,3,0,5,-1,6]
輸出[-1,1,3,5]
要求時間復雜度，空間復雜度盡量小
?
95.華為面試題
1 判斷一字符串是不是對稱的，如：abccba
2.用遞歸的方法判斷整數組a[N]是不是升序排列
?
96.08年中興校園招聘筆試題
1．編寫strcpy 函數
已知strcpy 函數的原型是
char *strcpy(char *strDest, const char *strSrc);
其中strDest 是目的字符串，strSrc 是源字符串。不調用C++/C 的字符串庫函數，請
編寫函數 strcpy
?
最后壓軸之戲，終結此微軟等100題系列V0.1版。
那就，
連續來幾組微軟公司的面試題，讓你一次爽個夠：
======================
97.第1組微軟較簡單的算法面試題
1.編寫反轉字符串的程序，要求優化速度、優化空間。
2.在鏈表里如何發現循環鏈接？
3.編寫反轉字符串的程序，要求優化速度、優化空間。
4.給出洗牌的一個算法，并將洗好的牌存儲在一個整形數組里。
5.寫一個函數，檢查字符是否是整數，如果是，返回其整數值。
（或者：怎樣只用4行代碼編寫出一個從字符串到長整形的函數？）
98.第2組微軟面試題
1.給出一個函數來輸出一個字符串的所有排列。
2.請編寫實現malloc()內存分配函數功能一樣的代碼。
3.給出一個函數來復制兩個字符串A和B。字符串A的后幾個字節和字符串B的前幾個字節重疊。
4.怎樣編寫一個程序，把一個有序整數數組放到二叉樹中？
5.怎樣從頂部開始逐層打印二叉樹結點數據？請編程。
6.怎樣把一個鏈表掉個順序（也就是反序，注意鏈表的邊界條件并考慮空鏈表）？
99.第3組微軟面試題
1.燒一根不均勻的繩，從頭燒到尾總共需要1個小時。
現在有若干條材質相同的繩子，問如何用燒繩的方法來計時一個小時十五分鐘呢？
2.你有一桶果凍，其中有黃色、綠色、紅色三種，閉上眼睛抓取同種顏色的兩個。
抓取多少個就可以確定你肯定有兩個同一顏色的果凍？（5秒-1分鐘）
3.如果你有無窮多的水，一個3公升的提捅，一個5公升的提捅，兩只提捅形狀上下都不均勻，
問你如何才能準確稱出4公升的水？（40秒-3分鐘）
一個岔路口分別通向誠實國和說謊國。
來了兩個人，已知一個是誠實國的，另一個是說謊國的。
誠實國永遠說實話，說謊國永遠說謊話。現在你要去說謊國，
但不知道應該走哪條路，需要問這兩個人。請問應該怎么問？（20秒-2分鐘）
100.第4組微軟面試題，挑戰思維極限
1.12個球一個天平，現知道只有一個和其它的重量不同，問怎樣稱才能用三次就找到那個球。
13個呢？（注意此題并未說明那個球的重量是輕是重，所以需要仔細考慮）（5分鐘-1小時）
2.在9個點上畫10條直線，要求每條直線上至少有三個點？（3分鐘-20分鐘）
3.在一天的24小時之中，時鐘的時針、分針和秒針完全重合在一起的時候有幾次？
都分別是什么時間？你怎樣算出來的？（5分鐘-15分鐘）
?
終結附加題：
微軟面試題，挑戰你的智商
==========
說明：如果你是第一次看到這種題，并且以前從來沒有見過類似的題型，
并且能夠在半個小時之內做出答案，說明你的智力超常..）
1.第一題 . 五個海盜搶到了100顆寶石，每一顆都一樣大小和價值連城。他們決定這么分：
抽簽決定自己的號碼（1、2、3、4、5）
?????????????????????????
首先，由1號提出分配方案，然后大家表決，當且僅當超過半數的人同意時，
按照他的方案進行分配，否則將被扔進大海喂鯊魚
如果1號死后，再由2號提出分配方案，然后剩下的4人進行表決，
當且僅當超過半數的人同意時，按照他的方案進行分配，否則將被扔入大海喂鯊魚。
依此類推
條件：每個海盜都是很聰明的人，都能很理智地做出判斷，從而做出選擇。
問題：第一個海盜提出怎樣的分配方案才能使自己的收益最大化？
?
2.一道關于飛機加油的問題，已知：
每個飛機只有一個油箱，?
飛機之間可以相互加油（注意是相互，沒有加油機）?
一箱油可供一架飛機繞地球飛半圈，
問題：
為使至少一架飛機繞地球一圈回到起飛時的飛機場，至少需要出動幾架飛機？
（所有飛機從同一機場起飛，而且必須安全返回機場，不允許中途降落，中間沒有飛機場）
? //歡迎，關注另外不同的更精彩的100題V0.2版，和此V0.1版的答案等后續內容。
?本微軟等面試100題系列V0.1版，完。
======================
更多請參見此100題V0.2版：微軟、谷歌、百度等公司經典面試100題[第1-60題]。
---------------------------------------------------------------------------------????
???????????????? 致各位網友
一、關于本微軟等100題系列V0.1版的鄭重聲明???????
??? ? http://blog.csdn.net/v_JULY_v/archive/2010/12/02/6050133.aspx
?
二、歡迎，希望，各位網友能更多的、更好的提出你的個人思路、算法，
???? 思路回復地址：
????? 本微軟等100題系列V0.1版，永久維護地址
?? ? http://topic.csdn.net/u/20101126/10/b4f12a00-6280-492f-b785-cb6835a63dc9.html
?? ??謝謝。
?
三、目前前60題的答案參考早已公布上傳，第61-100題的答案在整理中。
所有的資源下載（題目+答案）地址：??
????? http://v_july_v.download.csdn.net/
?
四、而后，請大家務必尊重本人近2個月的勞動成果。不論你是引用我帖子上，博客上，
還是各資源上的題目或答案，
????? 凡是以July為名發表的博客、帖子，資源，引用都請注明作者本人July及出處。
????? 若私自據為己有者，不標明出處及作者本人，必究。
????? 永遠，向您的厚道，致以最崇高的敬意。
?
五、目前，針對本100題系列，我已建一個100題永久討論組（后面的朋友加Algorithms_14群，見博客副標題。）
????? 專門針對這100題各個版本中任何一道題進行討論、交流、維護、修正。
???? //預計本微軟等面試100題系列V0.2版，相信，會在明年2011年與大家見面，具體待定。
?
六、一切的詳情，還是在本博客里。歡迎，永久關注，此博客。
????? 本博客致力于數據結構之法、算法優化之道?
???? ?請參見本人博客：
???? My Blog：??
??? ?http://blog.csdn.net/v_JULY_v
?? ? 謝謝，各位。
=====
歡迎，任何人，就以上任何內容，題目與答案思路，或其它任何問題、
回復到上述本100題系列永久維護帖子上，或者與我聯系：
本人郵箱：
zhoulei0907@yahoo.cn
786165179@qq.com
=================================================
更多請參見此100題V0.2版：微軟、谷歌、百度等公司經典面試100題[第1-60題]。
- 微軟、谷歌、百度等公司經典面試100題[第1-60題]? （微軟100題第二版前60題）
- 微軟、Google等公司非常好的面試題及解答[第61-70題]? （微軟100題第二版第61-70題）
- 十道海量數據處理面試題與十個方法大總結? （十道海量數據處理面試題）
- 海量數據處理面試題集錦與Bit-map詳解?（十七道海量數據處理面試題）
- 九月騰訊，創新工場，淘寶等公司最新面試十三題（2011年度9月最新面試30題）
- 十月百度，阿里巴巴，迅雷搜狗最新面試十一題（2011年度十月最新面試題集錦）
?
作者聲明:
本人July對以上所有任何內容和資料享有版權，轉載請注明作者本人July及出處。
向您的厚道致敬。謝謝。二零一零年十二月六日。
總結
以上是生活随笔為你收集整理的微软公司等数据结构+算法面试100题2010版全部出炉的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： VS2013 MFC基于对话框编程（创建
- 下一篇： x264函数调用关系图