魚骨頭的雲端圖書館 - Powered by Discuz! Board

繁體 | 簡體

Sclub交友聊天~加入聊天室當版主

(檢舉)

新浪微博

QQ空间

Facebook

Google+

Plurk

Twitter

Line

標題: 微軟公司等資料結構+演算法面試100題(第1-100題)全部出爐 [打印本頁]

作者: mhfo 時間: 2015-1-8 09:35 標題: 微軟公司等資料結構+演算法面試100題(第1-100題)全部出爐

原文連結

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[j] 的值代表編號為i，j的隊伍中更強的一支。
所以w[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，
其左邊的數都小於等於它，右邊的數都大於等於它。
能否只用一個額外陣列和少量其它空間實現。
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、b分別保存從前到i的最大的數和從後到i的最小的數，
一個解答：這需要兩次遍歷，然後再遍歷一次原陣列，
將所有data>=a[i-1]&&data<=b的data找出即可。
給出這個解答後，面試官有要求只能用一個輔助陣列，且要求少遍歷一次。

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道面試題的所有一切詳情，包括答案，資源下載，帖子維護，答案更新，都請參考此文：橫空出世，席捲Csdn [評微軟等資料結構+演算法面試100題]。

歡迎光臨魚骨頭的雲端圖書館 (http://mhfo.hotbbs.info/) Powered by Discuz! 7.0.0