【文章內(nèi)容簡介】 分析：這是一道很有意思的面試題。該題以及它的變體經(jīng)常出現(xiàn)在各大公司的面試、筆試題中。題目：用C++設計一個不能被繼承的類。分析：這是Adobe公司2007年校園招聘的最新筆試題。這道題除了考察應聘者的C++基本功底外，還能考察反應能力，是一道很好的題目。（1）時間內(nèi)刪除鏈表結(jié)點。題目：給定鏈表的頭指針和一個結(jié)點指針，在O(1)時間刪除該結(jié)點。鏈表結(jié)點的定義如下：struct ListNode{ int m_nKey。 ListNode* m_pNext。}。函數(shù)的聲明如下：void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted)。分析：這是一道廣為流傳的Google面試題，能有效考察我們的編程基本功，還能考察我們的反應速度，更重要的是，還能考察我們對時間復雜度的理解。題目：一個整型數(shù)組里除了兩個數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。請寫程序找出這兩個只出現(xiàn)一次的數(shù)字。要求時間復雜度是O(n)，空間復雜度是O(1)。分析：這是一道很新穎的關于位運算的面試題。題目：兩個單向鏈表，找出它們的第一個公共結(jié)點。鏈表的結(jié)點定義為：struct ListNode{ int m_nKey。 ListNode* m_pNext。}。分析：這是一道微軟的面試題。微軟非常喜歡與鏈表相關的題目，因此在微軟的面試題中，鏈表出現(xiàn)的概率相當高。題目：輸入兩個字符串，從第一字符串中刪除第二個字符串中所有的字符。例如，輸入”They are students.”和”aeiou”，則刪除之后的第一個字符串變成”Thy r stdnts.”。分析：這是一道微軟面試題。在微軟的常見面試題中，與字符串相關的題目占了很大的一部分，因為寫程序操作字符串能很好的反映我們的編程基本功。64. 尋找丑數(shù)。題目：我們把只包含因子3和5的數(shù)稱作丑數(shù)（Ugly Number）。例如8都是丑數(shù)，但14不是，因為它包含因子7。習慣上我們把1當做是第一個丑數(shù)。求按從小到大的順序的第1500個丑數(shù)。分析：這是一道在網(wǎng)絡上廣為流傳的面試題，據(jù)說google曾經(jīng)采用過這道題。題目：輸入數(shù)字n，按順序輸出從1最大的n位10進制數(shù)。比如輸入3，則輸出3一直到最大的3位數(shù)即999。分析：這是一道很有意思的題目?？雌饋砗芎唵?，其實里面卻有不少的玄機。題目：用遞歸顛倒一個棧。例如輸入棧{1, 2, 3, 4, 5}，1在棧頂。顛倒之后的棧為{5, 4, 3, 2, 1}，5處在棧頂。從撲克牌中隨機抽5張牌，判斷是不是一個順子，即這5張牌是不是連續(xù)的。210為數(shù)字本身，A為1，J為11，Q為12，K為13，而大小王可以看成任意數(shù)字。 。把n個骰子扔在地上，所有骰子朝上一面的點數(shù)之和為S。輸入n，打印出S的所有可能的值出現(xiàn)的概率。題目：輸入一個正整數(shù)數(shù)組，將它們連接起來排成一個數(shù)，輸出能排出的所有數(shù)字中最小的一個。例如輸入數(shù)組{32, 321}，則輸出這兩個能排成的最小數(shù)字32132。請給出解決問題的算法，并證明該算法。分析：這是09年6月份百度的一道面試題，從這道題我們可以看出百度對應聘者在算法方面有很高的要求。題目：把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個排好序的數(shù)組的一個旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。例如數(shù)組{3, 4, 5, 1, 2}為{1, 2, 3, 4, 5}的一個旋轉(zhuǎn)，該數(shù)組的最小值為1。 分析：這道題最直觀的解法并不難。從頭到尾遍歷數(shù)組一次，就能找出最小的元素，時間復雜度顯然是O(N)。但這個思路沒有利用輸入數(shù)組的特性，我們應該能找到更好的解法。ANSWER 簡單的回溯就可以實現(xiàn)了。當然排列的產(chǎn)生也有很多種算法，去看看組合數(shù)學，還有逆序生成排列和一些不需要遞歸生成排列的方法。印象中Knuth的TAOCP第一卷里面深入講了排列的生成。這些算法的理解需要一定的數(shù)學功底，也需要一定的靈感，有興趣最好看看。題目：實現(xiàn)函數(shù)double Power(double base, int exponent)，求base的exponent次方。不需要考慮溢出。分析：這是一道看起來很簡單的問題?？赡苡胁簧俚娜嗽诳吹筋}目后30秒寫出如下的代碼：double Power(double base, int exponent){ double result = 。 for(int i = 1。 i = exponent。 ++i) result *= base。 return result。}72.題目：設計一個類，我們只能生成該類的一個實例。分析：只能生成一個實例的類是實現(xiàn)了Singleton模式的類型。題目：輸入一個字符串，輸出該字符串中對稱的子字符串的最大長度。比如輸入字符串“google”，由于該字符串里最長的對稱子字符串是“goog”，因此輸出4。分析：可能很多人都寫過判斷一個字符串是不是對稱的函數(shù)，這個題目可以看成是該函數(shù)的加強版。題目：數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過了數(shù)組長度的一半，找出這個數(shù)字。分析：這是一道廣為流傳的面試題，包括百度、微軟和Google在內(nèi)的多家公司都曾經(jīng)采用過這個題目。要幾十分鐘的時間里很好地解答這道題，除了較好的編程能力之外，還需要較快的反應和較強的邏輯思維能力。題目：二叉樹的結(jié)點定義如下：struct TreeNode{ int m_nvalue。 TreeNode* m_pLeft。 TreeNode* m_pRight。}。輸入二叉樹中的兩個結(jié)點，輸出這兩個結(jié)點在數(shù)中最低的共同父結(jié)點。分析：求數(shù)中兩個結(jié)點的最低共同結(jié)點是面試中經(jīng)常出現(xiàn)的一個問題。這個問題至少有兩個變種。題目：有一個復雜鏈表，其結(jié)點除了有一個m_pNext指針指向下一個結(jié)點外，還有一個m_pSibling指向鏈表中的任一結(jié)點或者NULL。其結(jié)點的C++定義如下：struct ComplexNode{ int m_nValue。 ComplexNode* m_pNext。 ComplexNode* m_pSibling。}。下圖是一個含有5個結(jié)點的該類型復雜鏈表。圖中實線箭頭表示m_pNext指針，虛線箭頭表示m_pSibling指針。為簡單起見，指向NULL的指針沒有畫出。 請完成函數(shù)ComplexNode* Clone(ComplexNode* pHead)，以復制一個復雜鏈表。 分析：在常見的數(shù)據(jù)結(jié)構上稍加變化，這是一種很新穎的面試題。要在不到一個小時的時間里解決這種類型的題目，我們需要較快的反應能力，對數(shù)據(jù)結(jié)構透徹的理解以及扎實的編程功底。：，檢測是否有環(huán)。使用兩個指針p1,p2從鏈表頭開始遍歷，p1每次前進一步，p2每次前進兩步。如果p2到達鏈表尾部，說明無環(huán)，否則pp2必然會在某個時刻相遇(p1==p2)，從而檢測到鏈表中有環(huán)。(head1, head2)，檢測兩個鏈表是否有交點，如果有返回第一個交點。 如果head1==head2，那么顯然相交，直接返回head1。否則，分別從head1,head2開始遍歷兩個鏈表獲得其長度len1與len2，假設len1=len2，那么指針p1由head1開始向后移動len1len2步，指針p2=head2，下面pp2每次向后前進一步并比較p1p2是否相等，如果相等即返回該結(jié)點，否則說明兩個鏈表沒有交點。(head)，如果有環(huán)的話請返回從頭結(jié)點進入環(huán)的第一個節(jié)點。 運用題一，我們可以檢查鏈表中是否有環(huán)。 如果有環(huán)，那么p1p2重合點p必然在環(huán)中。從p點斷開環(huán)，方法為：p1=p, p2=pnext, pnext=NULL。此時，原單鏈表可以看作兩條單鏈表，一條從head開始，另一條從p2開始，于是運用題二的方法，我們找到它們的第一個交點即為所求。(并非最后一個結(jié)點，即pnext!=NULL)指針，刪除該結(jié)點。辦法很簡單，首先是放p中數(shù)據(jù),然后將pnext的數(shù)據(jù)copy入p中，接下來刪除pnext即可。(非空結(jié)點)，在p前面插入一個結(jié)點。 辦法與前者類似，首先分配一個結(jié)點q，將q插入在p后，接下來將p中的數(shù)據(jù)copy入q中，然后再將要插入的數(shù)據(jù)記錄在p中。？分析：主要在基本概念上的理解。但是最好能考慮的全面一點，現(xiàn)在公司招人的競爭可能就在細節(jié)上產(chǎn)生，誰比較仔細，誰獲勝的機會就大。79.。說明為什么你會選擇用這樣的方法？。說明為什么你會選擇用這樣的方法？()函數(shù)功能的代碼。 問題描述:12個高矮不同的人,排成兩排,每排必須是從矮到高排列,而且第二排比對應的第一排的人高,問排列方式有多少種?這個筆試題,很YD,因為把某個遞歸關系隱藏得很深。先來幾組百度的面試題：===================，里面數(shù)據(jù)無任何限制，要求求出所有這樣的數(shù)a[i]，其左邊的數(shù)都小于等于它，右邊的數(shù)都大于等于它。能否只用一個額外數(shù)組和少量其它空間實現(xiàn)。，內(nèi)含一千萬行字符串，每個字符串在1K以內(nèi)，要求找出所有相反的串對，如abc和cba。？為什么不用hash？，其中集合A={name}，集合B={age、sex、scholarship、address、...}，要求：問題根據(jù)集合A中的name查詢出集合B中對應的屬性信息；問題根據(jù)集合B中的屬性信息（單個屬性，如age20等），查詢出集合A中對應的name。，里面包含兩個字段{url、size}，即url為網(wǎng)址，size為對應網(wǎng)址訪問的次數(shù)，要求：問題利用Linux Shell命令或自己設計算法，查詢出url字符串中包含“baidu”子字符串對應的size字段值；問題根據(jù)問題1的查詢結(jié)果，對其按照size由大到小的排列。（說明：url數(shù)據(jù)量很大，100億級以上）百度筆試：給定一個存放整數(shù)的數(shù)組，重新排列數(shù)組使得數(shù)組左邊為奇數(shù)，右邊為偶數(shù)。要求：空間復雜度O(1)，時間復雜度為O（n）。用C語言實現(xiàn)函數(shù)void * memmove(void *dest, const void *src, size_t n)。memmove函數(shù)的功能是拷貝src所指的內(nèi)存內(nèi)容前n個字節(jié)到dest所指的地址上。分析：由于可以把任何類型的指針賦給void類型的指針這個函數(shù)主要是實現(xiàn)各種數(shù)據(jù)類型的拷貝。2010年3道百度面試題[相信，你懂其中的含金量]~z包括大小寫與0~9組成的N個數(shù)用最快的方式把其中重復的元素挑出來。，產(chǎn)生0的概率是p，產(chǎn)生1的概率是1p，現(xiàn)在要你構造一個發(fā)生器，使得它構造0和1的概率均為1/2；構造一個發(fā)生器，使得它構造3的概率均為1/3；...，構造一個發(fā)生器，使得它構造...n的概率均為1/n，要求復雜度最低。，每個文件1G，每個文件的每一行都存放的是用戶的query，每個文件的query都可能重復。要求按照query的頻度排序.字符串A的后幾個字節(jié)和字符串B的前幾個字節(jié)重疊。分析：記住，這種題目往往就是考你對邊界的考慮情況。，比如asderwsde,尋找其中的一個子字符串比如sde的個數(shù)，如果