程序員面試題

把二元查找樹轉變成排序的雙向鏈表題目：輸入一棵二元查找樹，將該二元查找樹轉換成一個排序的雙向鏈表要求不能創(chuàng)建任何新的結點，只調整指針的指向。10/\614/\/\81216轉換成雙向鏈表4=6=8=10=12=14=16。首先我們定義的二元查找樹節(jié)點的數據結構如下：structBSTreeNode{intm_nValue;//valueofnodeBSTreeNode*m_pLeft;//leftchildofnodeBSTreeNode*m_pRight;//rightchildofnode};2.設計包含min函數的棧。定義棧的數據結構，要求添加一個min函數，能夠得到棧的最小元素要求函數min、push以及pop的時間復雜度都是O(1)。求子數組的最大和題目：輸入一個整形數組，數組里有正數也有負數。數組中連續(xù)的一個或多個整數組成一個子數組，每個子數組都有一個和。求所有子數組的和的最大值。要求時間復雜度為O(n)。例如輸入的數組為1,-2,3,10,-4,7,2,-5，和最大的子數組為3,10,-4,7,2因此輸出為該子數組的和18。在二元樹中找出和為某一值的所有路徑題目：輸入一個整數和一棵二元樹。從樹的根結點開始往下訪問一直到葉結點所經過的所有結點形成一條路徑打印出和與輸入整數相等的所有路徑。例如輸入整數22和如下二元樹10/\12/\7則打印出兩條路徑：10,12和10,5,7。二元樹節(jié)點的數據結構定義為：structBinaryTreeNode//anodeinthebinarytree{intm_nValue;//valueofnodeBinaryTreeNode*m_pLeft;//leftchildofnodeBinaryTreeNode*m_pRight;//rightchildofnode};查找最小的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】初看此題，貌似很難，10分鐘過去了，可能有的人，題目都還沒看懂舉一個例子，數值:0,1,2,3,4,5,6,7,8,9分配:6,2,1,0,0,0,1,0,0,00在下排出現了6次，1在下排出現了2次，2在下排出現了1次，3在下排出現了0次 以此類推..昨天，用C++實現了此題。（*A_A*）第7題微軟亞院之編程判斷倆個鏈表是否相交給出倆個單向鏈表的頭指針，比如hl,h2，判斷這倆個鏈表是否相交。為了簡化問題，我們假設倆個鏈表均不帶環(huán)。問題擴展：如果需要求出倆個鏈表相交的第一個節(jié)點列?第8題此貼選一些比較怪的題，，由于其中題目本身與算法關系不大，僅考考思維。特此并作一題。有兩個房間，一間房里有三盞燈，另一間房有控制著三盞燈的三個開關，這兩個房間是分割開的，從一間里不能看到另一間的情況?，F在要求受訓者分別進這兩房間一次，然后判斷出這三盞燈分別是由哪個開關控制的。有什么辦法呢？你讓一些人為你工作了七天，你要用一根金條作為報酬。金條被分成七小塊，每天給出一塊。如果你只能將金條切割兩次，你怎樣分給這些工人?★用一種算法來顛倒一個鏈接表的順序?，F在在不用遞歸式的情況下做一遍?！镉靡环N算法在一個循環(huán)的鏈接表里插入一個節(jié)點，但不得穿越鏈接表?！镉靡环N算法整理一個數組。你為什么選擇這種方法?★用一種算法使通用字符串相匹配。★顛倒一個字符串。優(yōu)化速度。優(yōu)化空間。★顛倒一個句子中的詞的順序，比如將“我叫克麗絲”轉換為“克麗絲叫我”，實現速度最快，移動最少?！镎业揭粋€子字符串。優(yōu)化速度。優(yōu)化空間?！锉容^兩個字符串，用O(n)時間和恒量空間?！锛僭O你有一個用1001個整數組成的數組，這些整數是任意排列的，但是你知道所有的整數都在1到1000(包括1000)之間。此外，除一個數字出現兩次外，其他所有數字只出現一次。假設你只能對這個數組做一次處理，用一種算法找出重復的那個數字。如果你在運算中使用了輔助的存儲方式，那么你能找到不用這種方式的算法嗎?★不用乘法或加法增加8倍?，F在用同樣的方法增加7倍。第9題判斷整數序列是不是二元查找樹的后序遍歷結果題目：輸入一個整數數組，判斷該數組是不是某二元查找樹的后序遍歷的結果。如果是返回true，否則返回false。例如輸入5、7、6、9、11、10、8，由于這一整數序列是如下樹的后序遍歷結果：8/\10/\/\7911因此返回true。如果輸入7、4、6、5,沒有哪棵樹的后序遍歷的結果是這個序列，因此返回false。第10題翻轉句子中單詞的順序。題目：輸入一個英文句子，翻轉句子中單詞的順序，但單詞內字符的順序不變。句子中單詞以空格符隔開。為簡單起見，標點符號和普通字母一樣處理。例如輸入“Iamastudent.”，則輸出“student.aamI”。第11題求二叉樹中節(jié)點的最大距離...如果我們把二叉樹看成一個圖，父子節(jié)點之間的連線看成是雙向的，我們姑且定義"距離"為兩節(jié)點之間邊的個數。寫一個程序，求一棵二叉樹中相距最遠的兩個節(jié)點之間的距離。第12題題目：求1+2+...+n，要求不能使用乘除法、for、while、if、else、switch、case等關鍵字以及條件判斷語句(A?B:C)。第13題：題目：輸入一個單向鏈表，輸出該鏈表中倒數第k個結點。鏈表的倒數第0個結點為鏈表的尾指針。鏈表結點定義如下：structListNode{intm_nKey;ListNode*m_pNext;};第14題：題目：輸入一個已經按升序排序過的數組和一個數字，在數組中查找兩個數，使得它們的和正好是輸入的那個數字。要求時間復雜度是O(n)。如果有多對數字的和等于輸入的數字，輸出任意一對即可。例如輸入數組1、2、4、7、11、15和數字15。由于4+11=15，因此輸出4和11。第15題：題目：輸入一顆二元查找樹，將該樹轉換為它的鏡像，即在轉換后的二元查找樹中，左子樹的結點都大于右子樹的結點用遞歸和循環(huán)兩種方法完成樹的鏡像轉換。例如輸入：8/\10/\/\57911輸出：8/\106/\/\11975定義二元查找樹的結點為：structBSTreeNode//anodeinthebinarysearchtree(BST){intm_nValue;//valueofnodeBSTreeNode*m_pLeft;//leftchildofnodeBSTreeNode*m_pRight;//rightchildofnode};第16題：題目(微軟)：輸入一顆二元樹，從上往下按層打印樹的每個結點，同一層中按照從左往右的順序打印。例如輸入8/\610/\/\57911輸出861057911。第17題：題目：在一個字符串中找到第一個只出現一次的字符。如輸入abaccdeff,則輸出b。分析：這道題是2006年google的一道筆試題。第18題：題目：n個數字(0,1,???-1)形成一個圓圈，從數字0開始，每次從這個圓圈中刪除第m個數字(第一個為當前數字本身，第二個為當前數字的下一個數字)。當一個數字刪除后，從被刪除數字的下一個繼續(xù)刪除第m個數字。求出在這個圓圈中剩下的最后一個數字。July：我想，這個題目，不少人已經見識過了。第19題：題目：定義Fibonacci數列如下：/0n=0f(n)=1n=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,*.*)正方形:個角坐標;2:(*.*,0.0,*.*)3:(*.*,0.0,*.*)2:(*.*,0.0,*.*)3:(*.*,0.0,*.*)4:(*.*,0.0,*.*)第24題：鏈表操作，(1).單鏈表就地逆置(2)合并鏈表第25題：寫一個函數,它的原形是intcontinumax(char*outputstr,char*intputstr)功能：在字符串中找出連續(xù)最長的數字串，并把這個串的長度返回，并把這個最長數字串付給其中一個函數參數outputstr所指內存。例如："abcd12345ed125ss123456789"的首地址傳給intputstr后，函數將返回9,outputstr所指的值為12345678926.左旋轉字符串題目：定義字符串的左旋轉操作：把字符串前面的若干個字符移動到字符串的尾部。如把字符串abcdef左旋轉2位得到字符串cdefab。請實現字符串左旋轉的函數。要求時間對長度為n的字符串操作的復雜度為0(n)，輔助內存為0(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序列：push1，push2，push3，push4，pop，push5，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元素的和]之間的差最小。例如:vara=[100,99,98,1,2,3];varb=[1,2,3,4,5,40];33.實現一個挺高級的字符匹配算法：給一串很長字符串，要求找到符合要求的字符串，例如目的串：1231******3***2,12*****3這些都要找出來其實就是類似一些和諧系統(tǒng)。。。。。34.實現一個隊列。隊列的應用場景為：一個生產者線程將int類型的數入列，一個消費者線程將int類型的數出列35.求一個矩陣中最大的二維矩陣(元素和最大).如:120342345111530中最大的是:453要求：(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個字符串最多可以連成一個多長的字符串，如果出現循環(huán)，則返回錯誤。38.百度面試：1?用天平（只能比較，不能稱重）從一堆小球中找出其中唯一一個較輕的，使用x次天平，最多可以從y個小球中找出較輕的那個，求y與x的關系式有一個很大很大的輸入流，大到沒有存儲器可以將其存儲下來，而且只輸入一次，如何從這個輸入流中隨機取得m個記錄大量的URL字符串，如何從中去除重復的，優(yōu)化時間空間復雜度39.網易有道筆試(1).求一個二叉樹中任意兩個節(jié)點間的最大距離，兩個節(jié)點的距離的定義是這兩個節(jié)點間邊的個數，比如某個孩子節(jié)點和父節(jié)點間的距離是1，和相鄰兄弟節(jié)點間的距離是2，優(yōu)化時間空間復雜度。(2).求一個有向連通圖的割點，割點的定義是，如果除去此節(jié)點和與其相關的邊，有向圖不再連通，描述算法。百度研發(fā)筆試題引用自：zp155334877設計一個棧結構，滿足一下條件：min，push，pop操作的時間復雜度為O(1)—串首尾相連的珠子(m個)，有N種顏色(N<=10),設計一個算法，取出其中一段，要求包含所有N中顏色，并使長度最短。并分析時間復雜度與空間復雜度。設計一個系統(tǒng)處理詞語搭配問題，比如說中國和人民可以搭配，則中國人民人民中國都有效。要求：*系統(tǒng)每秒的查詢數量可能上千次；*詞語的數量級為10W；*每個詞至多可以與1W個詞搭配當用戶輸入中國人民的時候，要求返回與這個搭配詞組相關的信息。求固晶機的晶元查找程序晶元盤由數目不詳的大小一樣的晶元組成，晶元并不一定全布滿晶元盤，照相機每次這能匹配一個晶元，如匹配過，則拾取該晶元，若匹配不過，照相機則按測好的晶元間距移到下一個位置。求遍歷晶元盤的算法求思路。42.請修改append函數，利用這個函數實現：兩個非降序鏈表的并集，1->2->3和2->3->5并為1->2->3->5另外只能輸出結果，不能修改兩個鏈表的數據。遞歸和非遞歸倆種方法實現二叉樹的前序遍歷。騰訊面試題：1.設計一個魔方（六面）的程序。2.有一千萬條短信，有重復，以文本文件的形式保存，一行一條，有重復。請用5分鐘時間，找出重復出現最多的前10條。3?收藏了1萬條url,現在給你一條url,如何找出相似的url。（面試官不解釋何為相似）雅虎：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搜狐：四對括號可以有多少種匹配排列方式？比如兩對括號可以有兩種：（）（）和（（））47.創(chuàng)新工場：求一個數組的最長遞減子序列比如{9，4，3，2，5，4，3，2}的最長遞減子序列為{95，4，3，2}微軟：一個數組是由一個遞減數列左移若干位形成的，比如{4，3，2，1，6，5}是由{6，5，4，3，2，1}左移兩位形成的，在這種數組中查找某一個數。一道看上去很嚇人的算法面試題：如何對n個數進行排序，要求時間復雜度O（n），空間復雜度0（1）網易有道筆試：1.求一個二叉樹中任意兩個節(jié)點間的最大距離，兩個節(jié)點的距離的定義是這兩個節(jié)點間邊的個數，比如某個孩子節(jié)點和父節(jié)點間的距離是1，和相鄰兄弟節(jié)點間的距離是2，優(yōu)化時間空間復雜度。2.求一個有向連通圖的割點，割點的定義是，如果除去此節(jié)點和與其相關的邊，有向圖不再連通，描述算法。和為n連續(xù)正數序列。題目：輸入一個正數n,輸出所有和為n連續(xù)正數序列。例如輸入15，由于1+2+3+4+5=4+5+6=7+8=15，所以輸出3個連續(xù)序列1-5、4-6和7-8分析：這是網易的一道面試題。二元樹的深度。題目：輸入一棵二元樹的根結點,求該樹的深度。從根結點到葉結點依次經過的結點（含根、葉結點）形成樹的一條路徑,最長路徑的長度為樹的深度。例如：輸入二元樹：10/\14//\41216輸出該樹的深度3。二元樹的結點定義如下：structSBinaryTreeNode//anodeofthebinarytree{intm_nValue;//valueofnodeSBinaryTreeNode*m_pLeft;//leftchildofnodeSBinaryTreeNode*m_pRight;//r