數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)筆試面試題10.doc

選擇題 第一題，兩臺(tái)電腦在局域網(wǎng)中，機(jī)器為千兆網(wǎng)卡，一臺(tái)作服務(wù)器里面有一張網(wǎng)頁(yè)為1K字節(jié)，問(wèn)另一臺(tái)下載這個(gè)網(wǎng)頁(yè)的速度。我答：我不知道1K是指1024還是1000不過(guò)按我的算法沒(méi)區(qū)別，1000 000000/8/1k我選了10 000張/秒 第二題，單鏈表插入一個(gè)節(jié)點(diǎn)的問(wèn)題。在p指向的節(jié)點(diǎn)后插入一個(gè)q指向的節(jié)點(diǎn)。 我答：q-next=p-next;p-next=q; 之后亂序，我記不清楚題號(hào)了。 有一題，地圖染色問(wèn)題，每個(gè)國(guó)家用矩形表示，讓相鄰國(guó)家顏色不同。離散里面有 有一題，問(wèn)快速排序達(dá)到最壞情況時(shí)間復(fù)雜度n2的原數(shù)數(shù)組的具體情形。見(jiàn)數(shù)據(jù)結(jié)構(gòu) 有一題，很扯的指針取址符號(hào)混亂，選項(xiàng)卻很白癡。 有一題，入棧序列1,2,3,4,5,.,n，第一個(gè)出棧的是n，問(wèn)第i個(gè)出棧的是多少。我答：n-i+1 最后一題，給中綴和后綴表達(dá)式，求前綴表達(dá)式。 填空題 第一題：數(shù)組(a1,a2,a3,a4.,an)，刪除任意一個(gè)的概率相同，問(wèn)平均刪除一個(gè)要移動(dòng)多少個(gè)。 我答：(n-1)/2第二題：一個(gè)程序填空，程序大意是在數(shù)組里面找第二大的數(shù)。注：不難 第三題：大致如下一個(gè)程序片段：void xxx(x) int countx=0; while(x) countx+; x=x&(x-1); coutcountxendl;問(wèn)xxx(9999)輸出什么。我答：8，記得做ACM的時(shí)候碰到過(guò)那個(gè)式子，貌似關(guān)于排列的，具體意思忘記了，搞一下可以明白是x變成二進(jìn)制，里面有多少個(gè)1就是答案。 第四題：大致如下一個(gè)代碼 inta32=1,2,3,4,5,6; int*p3; p0=a1; 問(wèn)*(p0+1)是個(gè)什么東西 我答：4，蠻基礎(chǔ)嗯。 簡(jiǎn)答題 第一題：7公斤米，50克砝碼，200克砝碼各一個(gè)，稱(chēng)1350克米問(wèn)最少要多少次，并編程回答。我答，6次，可能一開(kāi)始會(huì)想到 1350/250 + 2 = 7次，說(shuō)明貪心無(wú)效。我不知道我的方法是不是很笨，用了遞推，或者你可以看成是動(dòng)態(tài)規(guī)劃。轉(zhuǎn)化一下題目的意思就是1克和4克砝碼，問(wèn)多少次稱(chēng)出27克大米，F(xiàn)N代表N克大米最少需要多少次。則有：FN=minFN-1,FN-4,FN-5+1代碼如下：int findmin(int weight) int v= weight/50; int f150; f0=0;f1=1;f2=2;f3=3;f4=1; if (v5) return fv; int i; for (i=5;i=v;i+) fi=min(fi-1+1,fi-4+1,fi-5+1); return fv; 注：我一開(kāi)始愣了很久，我在想，稱(chēng)好的大米可以作為砝碼來(lái)用嗎？這樣就是另一種問(wèn)題了吧。 第二題，n個(gè)雞蛋放到m個(gè)籃子，每個(gè)籃子不能為空，問(wèn)所有可能的擺放方法，使得滿(mǎn)足對(duì)于任意一個(gè)不大于n的數(shù)可以又若干個(gè)籃子里面的雞蛋數(shù)加起來(lái)。 我答：不能想出算出所有擺放方法的方法，期待ACM大牛路過(guò)。 第三題，大意淘寶網(wǎng)的評(píng)論系統(tǒng)，原先只有一個(gè)評(píng)論表，對(duì)于現(xiàn)在大用戶(hù)，大數(shù)據(jù)量，大訪問(wèn)量，請(qǐng)?jiān)O(shè)計(jì)一個(gè)合理可行的架構(gòu)來(lái)優(yōu)化關(guān)于評(píng)論的數(shù)據(jù)庫(kù)。 我答：哥蒙了，哥胡言亂語(yǔ)的。 附加題：前端設(shè)計(jì)師必答 第一題：圖片默認(rèn)為半透明，鼠標(biāo)移上去變成不透明。 我注：img標(biāo)簽onfocus和onblur的應(yīng)用，注意這個(gè)透明的屬性在IE和FireFox下是不同的。而且用js控制的時(shí)候，屬性名也要注意 第二題：一個(gè)輸入框，和一個(gè)列表框，列表框里面有很多字符串，在輸入框里面輸入字符串時(shí)，列表框中字符串前綴是該字符串的做高亮或者其他顯著表示。最后回車(chē)選擇或者鼠標(biāo)雙擊列表框選擇。1.把二元查找樹(shù)轉(zhuǎn)變成排序的雙向鏈表（樹(shù)） 題目：輸入一棵二元查找樹(shù)，將該二元查找樹(shù)轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只調(diào)整指針的指向。 10 / 6 14 / / 4 8 12 16 轉(zhuǎn)換成雙向鏈表4=6=8=10=12=14=16。 首先我們定義的二元查找樹(shù) 節(jié)點(diǎn)的數(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; 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ù)組都有一個(gè)和。求所有子數(shù)組的和的最大值。要求時(shí)間復(fù)雜度為O(n)。例如輸入的數(shù)組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數(shù)組為3, 10, -4, 7, 2，因此輸出為該子數(shù)組的和18。 4.在二元樹(shù)中找出和為某一值的所有路徑（樹(shù)）題目：輸入一個(gè)整數(shù)和一棵二元樹(shù)。從樹(shù)的根結(jié)點(diǎn)開(kāi)始往下訪問(wèn)一直到葉結(jié)點(diǎn)所經(jīng)過(guò)的所有結(jié)點(diǎn)形成一條路徑。打印出和與輸入整數(shù)相等的所有路徑。例如 輸入整數(shù)22和如下二元樹(shù) 10 / 5 12 / 4 7則打印出兩條路徑：10, 12和10, 5, 7。二元樹(shù)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)定義為：struct BinaryTreeNode / a node in the binary treeint m_nValue; / value of nodeBinaryTreeNode *m_pLeft; / left child of nodeBinaryTreeNode *m_pRight; / right child of node; 5.查找最小的k個(gè)元素（數(shù)組）題目：輸入n個(gè)整數(shù)，輸出其中最小的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ù)，在其下排填出對(duì)應(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,0 0在下排出現(xiàn)了6次，1在下排出現(xiàn)了2次， 2在下排出現(xiàn)了1次，3在下排出現(xiàn)了0次. 以此類(lèi)推. 第7題（鏈表）微軟亞院之編程判斷倆個(gè)鏈表是否相交給出倆個(gè)單向鏈表的頭指針，比如h1，h2，判斷這倆個(gè)鏈表是否相交。為了簡(jiǎn)化問(wèn)題，我們假設(shè)倆個(gè)鏈表均不帶環(huán)。問(wèn)題擴(kuò)展：1.如果鏈表可能有環(huán)列?2.如果需要求出倆個(gè)鏈表相交的第一個(gè)節(jié)點(diǎn)列? 第8題（算法）此貼選一些 比較怪的題，由于其中題目本身與算法關(guān)系不大，僅考考思維。特此并作一題。1.有兩個(gè)房間，一間房里有三盞燈，另一間房有控制著三盞燈的三個(gè)開(kāi)關(guān)，這兩個(gè)房間是 分割開(kāi)的，從一間里不能看到另一間的情況?，F(xiàn)在要求受訓(xùn)者分別進(jìn)這兩房間一次，然后判斷出這三盞燈分別是由哪個(gè)開(kāi)關(guān)控制的。有什么辦法呢？2.你讓一些人為你工作了七天，你要用一根金條作為報(bào)酬。金條被分成七小塊，每天給出一塊。如果你只能將金條切割兩次，你怎樣分給這些工人?3.用一種算法來(lái)顛倒一個(gè)鏈接表的順序?，F(xiàn)在在不用遞歸式的情況下做一遍。用一種算法在一個(gè)循環(huán)的鏈接表里插入一個(gè)節(jié)點(diǎn)，但不得穿越鏈接表。用一種算法整理一個(gè)數(shù)組。你為什么選擇這種方法?用一種算法使通用字符串相匹配。顛倒一個(gè)字符串。優(yōu)化速度。優(yōu)化空間。顛倒一個(gè)句子中的詞的順序，比如將“我叫克麗絲”轉(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è)你只能對(duì)這個(gè)數(shù)組做一次處理，用一種算法找出重復(fù)的那個(gè)數(shù)字。如果你在運(yùn)算中使用了輔助的存儲(chǔ)方式，那么你能找到不用這種方式的算法嗎?不用乘法或加法增加8倍。現(xiàn)在用同樣的方法增加7倍。 第9題（樹(shù)）判斷整數(shù)序列是不是二元查找樹(shù)的后序遍歷結(jié)果題目：輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二元查找樹(shù)的后序遍歷的結(jié)果。如果是返回true，否則返回false。例如輸入5、7、6、9、11、10、8，由于這一整數(shù)序列是如下樹(shù)的后序遍歷結(jié)果： 8 / 6 10 / / 5 7 9 11因此返回true。如果輸入7、4、6、5，沒(méi)有哪棵樹(shù)的后序遍歷的結(jié)果是這個(gè)序列，因此返回false。 第10題（字符串）翻轉(zhuǎn)句子中單詞的順序。題目：輸入一個(gè)英文句子，翻轉(zhuǎn)句子中單詞的順序，但單詞內(nèi)字符的順序不變。句子中單詞以空格符隔開(kāi)。為簡(jiǎn)單起見(jiàn)，標(biāo)點(diǎn)符號(hào)和普通字母一樣處理。例如輸入“I am a student.”，則輸出“student. a am I”。 第11題（樹(shù)）求二叉樹(shù)中節(jié)點(diǎn)的最大距離.如果我們把二叉樹(shù)看成一個(gè)圖，父子節(jié)點(diǎn)之間的連線看成是雙向的，我們姑且定義距離為兩節(jié)點(diǎn)之間邊的個(gè)數(shù)。寫(xiě)一個(gè)程序，求一棵二叉樹(shù)中相距最遠(yuǎn)的兩個(gè)節(jié)點(diǎn)之間的距離。 第12題（語(yǔ)法）題目：求1+2+n，要求不能使用乘除法、for、while、if、else、switch、case等關(guān)鍵字以及條件判斷語(yǔ)句（A?B:C）。 第13題（鏈表）：題目：輸入一個(gè)單向鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。鏈表的倒數(shù)第0個(gè)結(jié)點(diǎn)為鏈表的尾指針。鏈表結(jié)點(diǎn)定義如下： struct ListNode int m_nKey; ListNode* m_pNext; 第14題（數(shù)組）：題目：輸入一個(gè)已經(jīng)按升序排序過(guò)的數(shù)組和一個(gè)數(shù)字，在數(shù)組中查找兩個(gè)數(shù)，使得它們的和正好是輸入的那個(gè)數(shù)字。要求時(shí)間復(fù)雜度是O(n)。如果有多對(duì)數(shù)字的和等于輸入的數(shù)字，輸出任意一對(duì)即可。例如輸入數(shù)組1、2、4、7、11、15和數(shù)字15。由于4+11=15，因此輸出4和11。 第15題（樹(shù)）：題目：輸入一顆二元查找樹(shù)，將該樹(shù)轉(zhuǎn)換為它的鏡像，即在轉(zhuǎn)換后的二元查找樹(shù)中，左子樹(shù)的結(jié)點(diǎn)都大于右子樹(shù)的結(jié)點(diǎn)。用遞歸和循環(huán)兩種方法完成樹(shù)的鏡像轉(zhuǎn)換。 例如輸入： 8 / 6 10 / /5 7 9 11輸出： 8 / 10 6 / /11 9 7 5定義二元查找樹(shù)的結(jié)點(diǎn)為：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題（樹(shù)）：題目（微軟）：輸入一顆二元樹(shù)，從上往下按層打印樹(shù)的每個(gè)結(jié)點(diǎn)，同一層中按照從左往右的順序打印。 例如輸入 8 / 6 10/ / 5 7 9 11輸出8 6 10 5 7 9 11。 第17題（字符串）：題目：在一個(gè)字符串中找到第一個(gè)只出現(xiàn)一次的字符。如輸入abaccdeff，則輸出b。 分析：這道題是2006年google的一道筆試題。 第18題（數(shù)組）：題目：n個(gè)數(shù)字（0,1,n-1）形成一個(gè)圓圈，從數(shù)字0開(kāi)始，每次從這個(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) 見(jiàn)識(shí)過(guò)了。 第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語(yǔ)言教科書(shū)中講到遞歸函數(shù)的時(shí)候，都會(huì)用Fibonacci作為例子。因此很多程序員對(duì)這道題的遞歸解法非常熟悉，但.呵呵，你知道的。 第20題（字符串）：題目：輸入一個(gè)表示整數(shù)的字符串，把該字符串轉(zhuǎn)換成整數(shù)并輸出。例如輸入字符串345，則輸出整數(shù)345。 第21題（數(shù)組）2010年中興面試題編程求解：輸入兩個(gè)整數(shù) n 和 m，從數(shù)列1，2，3.n 中 隨意取幾個(gè)數(shù),使其和等于 m ,要求將其中所有的可能組合列出來(lái). 第22題（推理）：有4張紅色的牌和4張藍(lán)色的牌，主持人先拿任意兩張，再分別在A、B、C三人額頭上貼任意兩張牌，A、B、C三人都可以看見(jiàn)其余兩人額頭上的牌，看完后讓他們猜自己額頭上是什么顏色的牌，A說(shuō)不知道，B說(shuō)不知道，C說(shuō)不知道，然后A說(shuō)知道了。請(qǐng)教如何推理，A是怎么知道的。如果用程序，又怎么實(shí)現(xiàn)呢？ 第23題（算法）：用最簡(jiǎn)單，最快速的方法計(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題（字符串）：寫(xiě)一個(gè)函數(shù),它的原形是int continumax(char *outputstr,char *intputstr)功能：在字符串中找出連續(xù)最長(zhǎng)的數(shù)字串，并把這個(gè)串的長(zhǎng)度返回，并把這個(gè)最長(zhǎng)數(shù)字串付給其中一個(gè)函數(shù)參數(shù)outputstr所指內(nèi)存。例如：abcd12345ed125ss123456789的首地址傳給intputstr后，函數(shù)將返回9，outputstr所指的值為123456789 26.左旋轉(zhuǎn)字符串（字符串）題目：定義字符串的左旋轉(zhuǎn)操作：把字符串前面的若干個(gè)字符移動(dòng)到字符串的尾部。如把字符串a(chǎn)bcdef左旋轉(zhuǎn)2位得到字符串cdefab。請(qǐng)實(shí)現(xiàn)字符串左旋轉(zhuǎn)的函數(shù)。要求時(shí)間對(duì)長(zhǎng)度為n的字符串操作的復(fù)雜度為O(n)，輔助內(nèi)存為O(1)。 27.跳臺(tái)階問(wèn)題（遞歸）題目：一個(gè)臺(tái)階總共有n級(jí)，如果一次可以跳1級(jí)，也可以跳2級(jí)。求總共有多少總跳法，并分析算法的時(shí)間復(fù)雜度。這道題最近經(jīng)常出現(xiàn)，包括MicroStrategy等比較重視算法的公司都曾先后選用過(guò)個(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)的很多公司都曾采用過(guò)這道題。 29.棧的push、pop序列（棧）題目：輸入兩個(gè)整數(shù)序列。其中一個(gè)序列表示棧的push順序，判斷另一個(gè)序列有沒(méi)有可能是對(duì)應(yīng)的pop順序。為了簡(jiǎn)單起見(jiàn)，我們假設(shè)push序列的任意兩個(gè)整數(shù)都是不相等的。 比如輸入的push序列是1、2、3、4、5，那么4、5、3、2、1就有可能是一個(gè)pop系列。因?yàn)榭梢杂腥缦碌膒ush和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出現(xiàn)的次數(shù)。例如輸入12，從1到12這些整數(shù)中包含1 的數(shù)字有1，10，11和12，1一共出現(xiàn)了5次。分析：這是一道廣為流傳的google面試題。 31.華為面試題（搜索）：一類(lèi)似于蜂窩的結(jié)構(gòu)的圖，進(jìn)行搜索最短路徑（要求5分鐘） 32.（數(shù)組、規(guī)劃）有兩個(gè)序列a,b，大小都為n,序列元素的值任意整數(shù)，無(wú)序；要求：通過(guò)交換a,b中的元素，使序列a元素的和與序列b元素的和之間的差最小。例如: var a=100,99,98,1,2, 3;var b=1, 2, 3, 4,5,40; 33.（字符串）實(shí)現(xiàn)一個(gè)挺高級(jí)的字符匹配算法：給一串很長(zhǎng)字符串，要求找到符合要求的字符串，例如目的串：1231*3*2 ,12*3這些都要找出來(lái)其實(shí)就是類(lèi)似一些和諧系統(tǒng)。 34.（隊(duì)列）實(shí)現(xiàn)一個(gè)隊(duì)列。隊(duì)列的應(yīng)用場(chǎng)景為：一個(gè)生產(chǎn)者線程將int類(lèi)型的數(shù)入列，一個(gè)消費(fèi)者線程將int類(lèi)型的數(shù)出列 35.（矩陣）求一個(gè)矩陣中最大的二維矩陣(元素和最大).如:1 2 0 3 42 3 4 5 11 1 5 3 0中最大的是:4 55 3要求:(1)寫(xiě)出算法;(2)分析時(shí)間復(fù)雜度;(3)用C寫(xiě)出關(guān)鍵代碼 第36題-40題（有些題目搜集于CSDN上的網(wǎng)友，已標(biāo)明）：36.引用自網(wǎng)友：longzuo（運(yùn)算）谷歌筆試：n支隊(duì)伍比賽，分別編號(hào)為0，1，2。n-1，已知它們之間的實(shí)力對(duì)比關(guān)系，存儲(chǔ)在一個(gè)二維數(shù)組wnn中，wij 的值代表編號(hào)為i，j的隊(duì)伍中更強(qiáng)的一支。所以wij=i 或者j，現(xiàn)在給出它們的出場(chǎng)順序，并存儲(chǔ)在數(shù)組ordern中，比如ordern = 4,3,5,8,1.，那么第一輪比賽就是 4對(duì)3， 5對(duì)8。.勝者晉級(jí)，敗者淘汰，同一輪淘汰的所有隊(duì)伍排名不再細(xì)分，即可以隨便排，下一輪由上一輪的勝者按照順序，再依次兩兩比，比如可能是4對(duì)5,直至出現(xiàn)第一名編程實(shí)現(xiàn)，給出二維數(shù)組w，一維數(shù)組order 和 用于輸出比賽名次的數(shù)組resultn，求出result。 37.（字符串）有n個(gè)長(zhǎng)為m+1的字符串，如果某個(gè)字符串的最后m個(gè)字符與某個(gè)字符串的前m個(gè)字符匹配，則兩個(gè)字符串可以聯(lián)接，問(wèn)這n個(gè)字符串最多可以連成一個(gè)多長(zhǎng)的字符串，如果出現(xiàn)循環(huán)，則返回錯(cuò)誤。 38.（算法）百度面試：1.用天平（只能比較，不能稱(chēng)重）從一堆小球中找出其中唯一一個(gè)較輕的，使用x次天平，最多可以從y個(gè)小球中找出較輕的那個(gè)，求y與x的關(guān)系式。2.有一個(gè)很大很大的輸入流，大到?jīng)]有存儲(chǔ)器可以將其存儲(chǔ)下來(lái)，而且只輸入一次，如何從這個(gè)輸入流中隨機(jī)取得m個(gè)記錄。3.大量的URL字符串，如何從中去除重復(fù)的，優(yōu)化時(shí)間空間復(fù)雜度 39.（樹(shù)、圖、算法）網(wǎng)易有道筆試：(1).求一個(gè)二叉樹(shù)中任意兩個(gè)節(jié)點(diǎn)間的最大距離，兩個(gè)節(jié)點(diǎn)的距離的定義是 這兩個(gè)節(jié)點(diǎn)間邊的個(gè)數(shù)，比如某個(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)和與其相關(guān)的邊，有向圖不再連通，描述算法。 40.百度研發(fā)筆試題（棧、算法）引用自：zp1553348771)設(shè)計(jì)一個(gè)棧結(jié)構(gòu)，滿(mǎn)足一下條件：min，push，pop操作的時(shí)間復(fù)雜度為O(1)。2)一串首尾相連的珠子(m個(gè))，有N種顏色(N2-3 和 2-3-5 并為 1-2-3-5另外只能輸出結(jié)果，不能修改兩個(gè)鏈表的數(shù)據(jù)。 43.遞歸和非遞歸倆種方法實(shí)現(xiàn)二叉樹(shù)的前序遍歷。 44.騰訊面試題（算法）：1.設(shè)計(jì)一個(gè)魔方（六面）的程序。2.有一千萬(wàn)條短信，有重復(fù)，以文本文件的形式保存，一行一條，有重復(fù)。請(qǐng)用5分鐘時(shí)間，找出重復(fù)出現(xiàn)最多的前10條。3.收藏了1萬(wàn)條url，現(xiàn)在給你一條url，如何找出相似的url。（面試官不解釋何為相似） 45.雅虎（運(yùn)算、矩陣）：1.對(duì)于一個(gè)整數(shù)矩陣，存在一種運(yùn)算，對(duì)矩陣中任意元素加一時(shí)，需要其相鄰（上下左右）某一個(gè)元素也加一，現(xiàn)給出一正數(shù)矩陣，判斷其是否能夠由一個(gè)全零矩陣經(jīng)過(guò)上述運(yùn)算得到。2.一個(gè)整數(shù)數(shù)組，長(zhǎng)度為n，將其分為m份，使各份的和相等，求m的最大值 比如3，2，4，3，6 可以分成3，2，4，3，6 m=1; 3,62,4,3 m=2 3,32,46 m=3 所以m的最大值為3 46.搜狐（運(yùn)算）：四對(duì)括號(hào)可以有多少種匹配排列方式？比如兩對(duì)括號(hào)可以有兩種：（）（）和（）47.創(chuàng)新工場(chǎng)（算法）：求一個(gè)數(shù)組的最長(zhǎng)遞減子序列 比如9，4，3，2，5，4，3，2的最長(zhǎng)遞減子序列為9，5，4，3，2 48.微軟（運(yùn)算）：一個(gè)數(shù)組是由一個(gè)遞減數(shù)列左移若干位形成的，比如4，3，2，1，6，5是由6，5，4，3，2，1左移兩位形成的，在這種數(shù)組中查找某一個(gè)數(shù)。 49.一道看上去很?chē)樔说乃惴嬖囶}（排序、算法）：如何對(duì)n個(gè)數(shù)進(jìn)行排序，要求時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1) 50.網(wǎng)易有道筆試（sorry，與第39題重復(fù)）：1.求一個(gè)二叉樹(shù)中任意兩個(gè)節(jié)點(diǎn)間的最大距離，兩個(gè)節(jié)點(diǎn)的距離的定義是 這兩個(gè)節(jié)點(diǎn)間邊的個(gè)數(shù)，比如某個(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)和與其相關(guā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.二元樹(shù)的深度（樹(shù)）。題目：輸入一棵二元樹(shù)的根結(jié)點(diǎn)，求該樹(shù)的深度。從根結(jié)點(diǎn)到葉結(jié)點(diǎn)依次經(jīng)過(guò)的結(jié)點(diǎn)（含根、葉結(jié)點(diǎn)）形成樹(shù)的一條路徑，最長(zhǎng)路徑的長(zhǎng)度為樹(shù)的深度。例如：輸入二元樹(shù)： 10 / 6 14 / / 4 12 16輸出該樹(shù)的深度3。二元樹(shù)的結(jié)點(diǎn)定義如下：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;分析：這道題本質(zhì)上還是考查二元樹(shù)的遍歷。 53.字符串的排列（字符串）。題目：輸入一個(gè)字符串，打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc，則輸出由字符a、b、c所能排列出來(lái)的所有字符串a(chǎn)bc、acb、bac、bca、cab和cba。分析：這是一道很好的考查對(duì)遞歸理解的編程題，因此在過(guò)去一年中頻繁出現(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.（語(yǔ)法）題目：類(lèi)CMyString的聲明如下：class CMyStringpublic: CMyString(char* pData = NULL); CMyString(const CMyString& str); CMyString(void); CMyString& operator = (const CMyString& str);private: char* m_pData;請(qǐng)實(shí)現(xiàn)其賦值運(yùn)算符的重載函數(shù)，要求異常安全，即當(dāng)對(duì)一個(gè)對(duì)象進(jìn)行賦值時(shí)發(fā)生異常，對(duì)象的狀態(tài)不能改變。 56.最長(zhǎng)公共字串（算法、字符串）。題目：如果字符串一的所有字符按其在字符串中的順序出現(xiàn)在另外一個(gè)字符串二中，則字符串一稱(chēng)之為字符串二的子串。注意，并不要求子串（字符串一）的字符必須連續(xù)出現(xiàn)在字符串二中。請(qǐng)編寫(xiě)一個(gè)函數(shù)，輸入兩個(gè)字符串，求它們的最長(zhǎng)公共子串，并打印出最長(zhǎng)公共子串。例如：輸入兩個(gè)字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它們的最長(zhǎng)公共子串，則輸出它們的長(zhǎng)度4，并打印任意一個(gè)子串。分析：求最長(zhǎng)公共子串（Longest Common Subsequence, LCS）是一道非常經(jīng)典的動(dòng)態(tài)規(guī)劃題，因此一些重視算法的公司像MicroStrategy都把它當(dāng)作面試題。 57.用倆個(gè)棧實(shí)現(xiàn)隊(duì)列（棧、隊(duì)列）。 題目：某隊(duì)列的聲明如下：template class CQueuepublic: 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;分析：從上面的類(lèi)的聲明中，我們發(fā)現(xiàn)在隊(duì)列中有兩個(gè)棧。因此這道題實(shí)質(zhì)上是要求我們用兩個(gè)棧來(lái)實(shí)現(xiàn)一個(gè)隊(duì)列。相信大家對(duì)棧和隊(duì)列的基本性質(zhì)都非常了解了：棧是一種后入先出的數(shù)據(jù)容器，因此對(duì)隊(duì)列進(jìn)行的插入和刪除操作都是在棧頂上進(jìn)行；隊(duì)列是一種先入先出的數(shù)據(jù)容器，我們總是把新元素插入到隊(duì)列的尾部，而從隊(duì)列的頭部刪除元素。 58.從尾到頭輸出鏈表（鏈表）。題目：輸入一個(gè)鏈表的頭結(jié)點(diǎn)，從尾到頭反過(guò)來(lái)輸出每個(gè)結(jié)點(diǎn)的值。鏈表結(jié)點(diǎn)定義如下：struct ListNode int m_nKey; ListNode* m_pNext;分析：這是一道很有意思的面試題。該題以及它的變體經(jīng)常出現(xiàn)在各大公司的面試、筆試題中。 59.不能被繼承的類(lèi)（語(yǔ)法）。題目：用C+設(shè)計(jì)一個(gè)不能被繼承的類(lèi)。分析：這是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)的定義如下：struct ListNode int m_nKey; ListNode* m_pNext;函數(shù)的聲明如下：void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);分析：這是一道廣為流傳的Google面試題，能有效考察我們的編程基本功，還能考察我們的反應(yīng)速度，更重要的是，還能考察我們對(duì)時(shí)間復(fù)雜度的理解。- 61.找出數(shù)組中兩個(gè)只出現(xiàn)一次的數(shù)字（數(shù)組）題目：一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。請(qǐng)寫(xiě)程序找出這兩個(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)。鏈表的結(jié)點(diǎn)定義為：struct ListNode int m_nKey; ListNode* m_pNext;分析：這是一道微軟的面試題。微軟非常喜歡與鏈表相關(guān)的題目，因此在微軟的面試題中，鏈表出現(xiàn)的概率相當(dāng)高。 63.在字符串中刪除特定的字符（字符串）。題目：輸入兩個(gè)字符串，從第一字符串中刪除第二個(gè)字符串中所有的字符。例如，輸入”They are students.”和”aeiou”，則刪除之后的第一個(gè)字符串變成”Thy r stdnts.”。分析：這是一道微軟面試題。在微軟的常見(jiàn)面試題中，與字符串相關(guān)的題目占了很大的一部分，因?yàn)閷?xiě)程序操作字符串能很好的反映我們的編程基本功。 64. 尋找丑數(shù)（運(yùn)算）。題目：我們把只包含因子2、3和5的數(shù)稱(chēng)作丑數(shù)（Ugly Number）。例如6、8都是丑數(shù)，但14不是，因?yàn)樗蜃?。習(xí)慣上我們把1當(dāng)做是第一個(gè)丑數(shù)。求按從小到大的順序的第1500個(gè)丑數(shù)。分析：這是一道在網(wǎng)絡(luò)上廣為流傳的面試題，據(jù)說(shuō)google曾經(jīng)采用過(guò)這道題。 65.輸出1到最大的N位數(shù)（運(yùn)算）題目：輸入數(shù)字n，按順序輸出從1最大的n位10進(jìn)制數(shù)。比如輸入3，則輸出1、2、3一直到最大的3位數(shù)即999。分析：這是一道很有意思的題目。看起來(lái)很簡(jiǎn)單，其實(shí)里面卻有不少的玄機(jī)。 66.顛倒棧（棧）。題目：用遞歸顛倒一個(gè)棧。例如輸入棧1, 2, 3, 4, 5，1在棧頂。顛倒之后的棧為5, 4, 3, 2, 1，5處在棧頂。 67.倆個(gè)閑玩娛樂(lè)（運(yùn)算）。1.撲克牌的順子從撲克牌中隨機(jī)抽5張牌，判斷是不是一個(gè)順子，即這5張牌是不是連續(xù)的。2-10為數(shù)字本身，A為1，J為11，Q為12，K為13，而大小王可以看成任意數(shù)字。 2.n個(gè)骰子的點(diǎn)數(shù)。把n個(gè)骰子扔在地上，所有骰子朝上一面的點(diǎn)數(shù)之和為S。輸入n，打印出S的所有可能的值出現(xiàn)的概率。 68.把數(shù)組排成最小的數(shù)（數(shù)組、算法）。題目：輸入一個(gè)正整數(shù)數(shù)組，將它們連接起來(lái)排成一個(gè)數(shù)，輸出能排出的所有數(shù)字中最小的一個(gè)。例如輸入數(shù)組32, 321，則輸出這兩個(gè)能排成的最小數(shù)字32132。請(qǐng)給出解決問(wèn)題的算法，并證明該算法。分析：這是09年6月份百度的一道面試題，從這道題我們可以看出百度對(duì)應(yīng)聘者在算法方面有很高的要求。 69.旋轉(zhuǎn)數(shù)組中的最小元素（數(shù)組、算法）。題目：把一個(gè)數(shù)組最開(kāi)始的若干個(gè)元素搬到數(shù)組的末尾，我們稱(chēng)之為數(shù)組的旋轉(zhuǎn)。輸入一個(gè)排好序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。例如數(shù)組3, 4, 5, 1, 2為1, 2, 3, 4, 5的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為1。 分析：這道題最直觀的解法并不難。從頭到尾遍歷數(shù)組一次，就能找出最小的元素，時(shí)間復(fù)雜度顯然是O(N)。但這個(gè)思路沒(méi)有利用輸入數(shù)組的特性，我們應(yīng)該能找到更好的解法。 70.給出一個(gè)函數(shù)來(lái)輸出一個(gè)字符串的所有排列（經(jīng)典字符串問(wèn)題）。ANSWER 簡(jiǎn)單的回溯就可以實(shí)現(xiàn)了。當(dāng)然排列的產(chǎn)生也有很多種算法，去看看組合數(shù)學(xué)，還有逆序生成排列和一些不需要遞歸生成排列的方法。印象中Knuth的第一卷里面深入講了排列的生成。這些算法的理解需要一定的數(shù)學(xué)功底，也需要一定的靈感，有興趣最好看看。 71.數(shù)值的整數(shù)次方（數(shù)字、運(yùn)算）。題目：實(shí)現(xiàn)函數(shù)double Power(double base, int exponent)，求base的exponent次方。不需要考慮溢出。分析：這是一道看起來(lái)很簡(jiǎn)單的問(wèn)題。可能有不少的人在看到題目后30秒寫(xiě)出如下的代碼：double Power(double base, int exponent) double result = 1.0; for(int i = 1; i =len2，那么指針p1由head1開(kāi)始向后移動(dòng)len1-len2步，指針p2=head2，下面p1、p2每次向后前進(jìn)一步并比較p1p2是否相等，如果相等即返回該結(jié)點(diǎn)，否則說(shuō)明兩個(gè)鏈表沒(méi)有交點(diǎn)。3.給定單鏈表(head)，如果有環(huán)的話請(qǐng)返回從頭結(jié)點(diǎn)進(jìn)入環(huán)的第一個(gè)節(jié)點(diǎn)。 運(yùn)用題一，我們可以檢查鏈表中是否有環(huán)。 如果有環(huán)，那么p1p2重合點(diǎn)p必然在環(huán)中。從p點(diǎn)斷開(kāi)環(huán)，方法為：p1=p, p2=p-next, p-next=NULL。此時(shí)，原單鏈表可以看作兩條單鏈表，一條從head開(kāi)始，另一條從p2開(kāi)始，于是運(yùn)用題二的方法，我們找到它們的第一個(gè)交點(diǎn)即為所求。4.只給定單鏈表中某個(gè)結(jié)點(diǎn)p(并非最后一個(gè)結(jié)點(diǎn)，即p-next!=NULL)指針，刪除該結(jié)點(diǎn)。 辦法很簡(jiǎn)單，首先是放p中數(shù)據(jù),然后將p-next的數(shù)據(jù)copy入p中，接下來(lái)刪除p-next即可。5.只給定單鏈表中某個(gè)結(jié)點(diǎn)p(非空結(jié)點(diǎn))，在p前面插入一個(gè)結(jié)點(diǎn)。 辦法與前者類(lèi)似，首先分配一個(gè)結(jié)點(diǎn)q，將q插入在p后，接下來(lái)將p中的數(shù)據(jù)copy入q中，然后再將要插入的數(shù)據(jù)記錄在p中。 78.鏈表和數(shù)組的區(qū)別在哪里（鏈表、數(shù)組）？分析：主要在基本概念上的理解。但是最好能考慮的全面一點(diǎn)，現(xiàn)在公司招人的競(jìng)爭(zhēng)可能就在細(xì)節(jié)上產(chǎn)生，誰(shuí)比較仔細(xì)，誰(shuí)獲勝的機(jī)會(huì)就大。 79.（鏈表、字符串）1.編寫(xiě)實(shí)現(xiàn)鏈表排序的一種算法。說(shuō)明為什么你會(huì)選擇用這樣的方法？2.編寫(xiě)實(shí)現(xiàn)數(shù)組排序的一種算法。說(shuō)明為什么你會(huì)選擇用這樣的方法？3.請(qǐng)編寫(xiě)能直接實(shí)現(xiàn)strstr()函數(shù)功能的代碼。 80.阿里巴巴一道筆試題（運(yùn)算、算法）問(wèn)題描述:12個(gè)高矮不同的人,排成兩排,每排必須是從矮到高排列,而且第二排比對(duì)應(yīng)的第一排的人高,問(wèn)排列方式有多少種?這個(gè)筆試題,很YD,因?yàn)榘涯硞€(gè)遞歸關(guān)系隱藏得很深。 先來(lái)幾組百度的面試題：=81.第1組百度面試題1.一個(gè)int數(shù)組，里面數(shù)據(jù)無(wú)任何限制，要求求出所有這樣的數(shù)ai，其左邊的數(shù)都小于等于它，右邊的數(shù)都大于等于它。能否只用一個(gè)額外數(shù)組和少量其它空間實(shí)現(xiàn)。2.一個(gè)文件，內(nèi)含一千萬(wàn)行字符串，每個(gè)字符串在1K以?xún)?nèi)，要求找出所有相反的串對(duì)，如abc和cba。3.STL的set用什么實(shí)現(xiàn)的？為什么不用hash？ 82.第2組百度面試題1.給出兩個(gè)集合A和B，其中集合A=name，集合B=age、sex、scholarship、address、.，要求：?jiǎn)栴}1、