?十月百度，阿里巴巴，迅雷搜狗最新面試十一題

引言

???當即早已進入10月份，十一過后，招聘，筆試，面試，求職漸趨火熱。而在這一系列過程背后浮出的各大IT公司的筆試/面試題則蘊含著諸多思想與設計，細細把玩，思考一番亦能有不少收獲。

??? 上個月，本博客著重整理九月騰訊，創新工場，淘寶等公司最新面試十三題，此次重點整理百度，阿里巴巴，迅雷和搜索等公司最新的面試題。同上篇一樣，答案望諸君共同討論之，個人亦在慢慢思考解答。多謝。

??? 本人正在一步一步整理本文中50多道題的答案，希望諸君各位與我一起做這些題。已經做出來的題目我會把答案即時更新到文章中。諸君，一起努力吧。謝謝。July、2011.10.14更新。

最新面試十一題

1. 十月百度：一個數組保存了N個結構，每個結構保存了一個坐標，結構間的坐標都不相同，請問如何找到指定坐標的結構（除了遍歷整個數組，是否有更好的辦法）？（要么預先排序，二分查找。要么哈希。hash的話，坐標(x,y)你可以當做一個2位數，寫一個哈希函數，把（x,y）直接轉成“(x,y)”作為key，默認用string比較。或如Edward Lee所說，將坐標(x, y)作為 Hash 中的 key。例如(m, n)，通過 (m,n) 和 (n, m) 兩次查找看是否在 HashMap 中。也可以在保存時就規定 (x, y) , x < y ，在插入之前做個判斷。）
2. 百度最新面試題：現在有1千萬個隨機數，隨機數的范圍在1到1億之間。現在要求寫出一種算法，將1到1億之間沒有在隨機數中的數求出來。（編程珠璣上有此類似的一題，如果有足夠的內存的話可以用位圖法，即開一個1億位的bitset，內存為100m/8== 12.5m, 然后如果一個數有出現，對應的bitset上標記為1，最后統計bitset上為0的即可。）
3. Alibaba筆試題：給定一段產品的英文描述，包含M個英文字母，每個英文單詞以空格分隔，無其他標點符號；再給定N個英文單詞關鍵字，請說明思路并編程實現方法
   ??? String extractSummary(String description,String[] key words)
   目標是找出此產品描述中包含N個關鍵字（每個關鍵詞至少出現一次）的長度最短的子串，作為產品簡介輸出。（不限編程語言）20分。（掃描過程始終保持一個[left,right]的range,初始化確保[left,right]的range里包含所有關鍵字則停止。然后每次迭代：
   1，試圖右移動left，停止條件為再移動將導致無法包含所有關鍵字。
   2，比較當前range's length和best length，更新最優值。
   3，右移right，停止條件為使任意一個關鍵字的計數+1。
   4，重復迭代。
   編程之美有最短摘要生成的問題，與此問題類似，讀者可作參考。）
4. 搜狗：有N個正實數(注意是實數，大小升序排列) x1 , x2 ... xN，另有一個實數M。 需要選出若干個x，使這幾個x的和與 M 最接近。 請描述實現算法，并指出算法復雜度（參考：第五章、尋找滿足條件的兩個或多個數）。
5. 迅雷：給你10臺機器，每個機器2個cpu，2g內存，現在已知在10億條記錄的數據庫里執行一次查詢需要5秒，問用什么方法能讓90%的查詢能在100毫秒以內返回結果。（@geochway：將10億條記錄排序,然后分到10個機器中,分的時候是一個記錄一個記錄的輪流分，
   確保每個機器記錄大小分布差不多,每一次查詢時,同時提交給10臺機器,同時查詢，
   因為記錄已排序,可以采用二分法查詢。
   如果無法排序,只能順序查詢,那就要看記錄本身的概率分布，否則不可能實現。
   一個機器2個CPU未必能起到作用,要看這兩個CPU能否并行存取內存,取決于系統架構。）
6. 給定一個函數rand()能產生0到n-1之間的等概率隨機數，問如何產生0到m-1之間等概率的隨機數？
7. 騰訊：五筆的編碼范圍是a ~ y的25個字母，從1位到4位的編碼，如果我們把五筆的編碼按字典序排序，形成一個數組如下：
   ??? a, aa, aaa, aaaa, aaab, aaac, … …, b, ba, baa, baaa, baab, baac … …, yyyw, yyyx, yyyy
   其中a的Index為0，aa的Index為1，aaa的Index為2，以此類推。
   1）編寫一個函數，輸入是任意一個編碼，比如baca，輸出這個編碼對應的Index；
   2）編寫一個函數，輸入是任意一個Index，比如12345，輸出這個Index對應的編碼。
8. 2011.10.09百度筆試題（下述第8-12題）：linux/unix遠程登陸都用到了ssh服務，當網絡出現錯誤時服務會中斷，linux/unix端的程序會停止。為什么會這樣？說下ssh的原理，解釋中斷的原理。
9. 一個最小堆，也是完全二叉樹，用按層遍歷數組表示。
   ? 1.? 求節點a[n]的子節點的訪問方式
   ? 2.? 插入一節點的程序void add_element(int *a,int size,int val);
   ? 3.? 刪除最小節點的程序。
10. a）求一個全排列函數：如p([1,2,3])?，輸出：? [123],[132],[213],[231],[321],[323]。
    b）求一個組合函數：??? 如p([1,2,3])?，輸出：[1],[2],[3],[1,2],[2,3],[1,3],[1,2,3]。
    這兩問可以用偽代碼（全排列請參考這里的第67題：微軟、Google等公司非常好的面試題及解答[第61-70題]?）。
11. 
12. 有這樣一種編碼：如，N=134，M=f(N)=143,N=020,M=fun(N)=101,其中N和M的位數一樣，N,M可以均可以以0開頭，N,M的各位數之和要相等，即1+3+4=1+4+3，且M是大于N中最小的一個，
    現在求這樣的序列S,N為一個定值，其中S(0)=N，S(1)=fun(N),S(2)=fun(S(1))。
13. 有1000萬條URL，每條URL　50字節，只包含主機前綴，要求實現URL提示系統：
    （１）要求實時更新匹配用戶輸入的地址，每輸出一個字符，輸出最新匹配URL
    （2）每次只匹配主機前綴，例如對 www.abaidu.com和www.baidu.com，用戶輸入www.b時只提示www.baidu.com（3）每次提供10條匹配的URL
    （4）以用戶需求為主。
14. 海量記錄，記錄形式如下： TERMID URLNOCOUNT urlno1 urlno2?? ..., urlnon?
    怎么考慮資源和時間這兩個因素，實現快速查詢任意兩個記錄的交集，并集等，設計相關的數據結構和算法。
15. 百度最新筆試題（感謝xiongyangwan提供的題目）：利用互斥量和條件變量設計一個消息隊列，具有以下功能：
    ? ?1 創建消息隊列（消息中所含的元素）
    ? ?2 消息隊列中插入消息
    ? ?3 取出一個消息（阻塞方式）
    ? ?4 取出第一消息（非阻塞方式）
16. 百度移動終端研發筆試：系統設計題（40分）
    對已排好序的數組A，一般來說可用二分查找可以很快找到。現有一特殊數組A[]，它是循環遞增的，如A[]={ 17 19 20 25 1 4 7 9}，試在這樣的數組中找一元素x，看看是否存在。
    請寫出你的算法，必要時可寫偽代碼，并分析其空間、時間復雜度。
17. #include<stdio.h>
    #include <string.h>
    void main()
    {
    ?int a[2000];
    ?char *p = (char *)a;
    ?int i ;
    ?for( i = 0; i < 2000; i++)
    ? a[i] = -i -1;
    ?printf("%d\n", strlen(p));
    }
    寫出輸出結果
    （onlyice：i?=?FFFFFF00H?的時候，才有'\0'出現，就是最后一個字節，C風格字符串讀到'\0'就終止了。FFFFFF00H?是?-256，就是?i?的值為255時a[i]?=?FFFFFF00H）....
18. 騰訊10.09測試筆試題：有Ｎ＋２個數，N個數出現了偶數次，２個數出現了奇數次（這兩個數不相等），問用O（1）的空間復雜度，找出這兩個數，不需要知道具體位置，只需要知道這兩個值。（@Rojay：xor一次，得到2個奇數次的數之和x。第二步，以x（展開成二進制）中有1的某位（假設第i位為1）作為劃分，第二次只xor第i位為1的那些數，得到y。然后x?xor?y以及y便是那兩個數。）
19. @well：一個整數數組，有n個整數，如何找其中m個數的和等于另外n-m個數的和？（與上面第4題類似，參考：第五章、尋找滿足條件的兩個或多個數）。
20. 阿里云筆試題：一個HTTP服務器處理一次請求需要500毫秒，請問這個服務器如何每秒處理100個請求。
21. 今天10.10阿里云筆試@土豆：1、三次握手；2、死鎖的條件。（互斥條件（Mutual exclusion）：1、資源不能被共享，只能由一個進程使用。2、請求與保持條件（Hold and wait）：已經得到資源的進程可以再次申請新的資源。3、非剝奪條件（No pre-emption）：已經分配的資源不能從相應的進程中被強制地剝奪。4、循環等待條件（Circular wait）：系統中若干進程組成環路，該環路中每個進程都在等待相鄰進程正占用的資源。處理死鎖的策略：1.忽略該問題。例如鴕鳥算法，該算法可以應用在極少發生死鎖的的情況下。為什么叫鴕鳥算法呢，因為傳說中鴕鳥看到危險就把頭埋在地底下，可能鴕鳥覺得看不到危險也就沒危險了吧。跟掩耳盜鈴有點像。2.檢測死鎖并且恢復。3.仔細地對資源進行動態分配，以避免死鎖。4.通過破除死鎖四個必要條件之一，來防止死鎖產生。）
22. 微軟2011最新面試題（以下三題，第22、23、24題皆摘自微軟亞洲研究院的鄒欣老師博客）：瀏覽過本人的程序員編程藝術系列的文章，一定對其中的這個問題頗有印象：第七章、求連續子數組的最大和。求數組最大子數組的和最初來源于編程之美，。我在編程藝術系列中提供了多種解答方式，然而這個問題若擴展到二維數組呢?再者，若數組首尾相連, 像一個輪胎一樣, 又怎么辦呢？聰明的同學還是給出了漂亮的答案, 并且用 SilverLight/WPF 給畫了出來， 如下圖所示：

    好，設想現在我們有一張紙帶，兩面都寫滿了像如上第一幅圖那樣的數字, 我們把紙帶的一端扭轉, 和另一端接起來, 構成一個莫比烏斯環 （M?bius Strip,如將一個長方形紙條ABCD的一端AB固定，另一端DC扭轉半周后，把AB和CD粘合在一起 ，得到的曲面就是麥比烏斯圈，也稱莫比烏斯帶。），如下圖所示：

    如上，盡管這個紙帶扭了一下,? 但是上面還是有數組, 還是有最大子數組的和，對么？ 在求最大子數組的和之前, 我們用什么樣的數據結構來表示這些數字呢? 你可以用 Java, C, C#， 或其他語言的數據結構來描述這個莫比烏斯環上的數組。數據結構搞好了, 算法自然就有了。（@風大哥：莫比烏斯帶，用環形數組或者鏈表可以表示。環型數組的話，1-N，到N特殊處理一下，連到1就是環型數組了，一個紙帶上正反兩面各有N個數，A1...An,B1...Bn,那么就可以構造一個新的數組：A1-An-B1-Bn.訪問到Bn下一位就是A1，就是環形的數組了。從某個位置k開始,用i,j向一個方向遍歷，直到i到達k位置，或者i=j，被追上，用數組需要一點技巧，就是J再次過k需要打個標志，以便計算終止條件和輸出。當然，如果用鏈表就更簡單了。把鏈表首尾相接即可，即An執行B1,Bn指向A1即可。） ?

23. 《編程之美》的第一題是讓Windows 任務管理器的CPU 使用率曲線畫出一個正弦波。我一直在想, 能不能把CPU 使用率邊上的網絡使用率也如法炮制一下呢?? 比如, 也來一個正弦曲線?

24. 如果你沒看過, 也至少聽說<人月神話>? (The Mythical Man-month) 這本在軟件工程領域很有影響的書.? 當你在微軟學術搜索中輸入 “manmonth” 這個詞的時候, 你會意外地碰到下面這個錯誤:

    經過幾次試驗之后, 你發現必須要輸入 “man-month” 才能得到希望的結果。 這不就是只差一個? ‘-’ 符號么?? 為什么這個搜索引擎不能做得聰明一些, 給一些提示 (Query Suggestion)? 或者自動把用戶想搜的結果展現出來 (Query Alteration)??? 我們在輸入比較長的英文單詞的時候, 也難免會敲錯一兩個字母, 網站應該幫助用戶, 而不是冷冰冰地拒絕用戶啊。

    微軟的學術搜索 (Microsoft Academic Search) 索引了超過 3千萬的文獻,? 2 千萬的人名, 怎么能以比較小的代價, 對經常出現的輸入錯誤提供提示? 或直接顯示相關結果, 避免用戶反復嘗試輸入的煩惱???

    你可能會說, 這很難吧,?? 但是另一家搜索引擎似乎輕易地解決了這個問題 (谷歌，讀者可以一試)。 所以, 還是有辦法的。

    這個題目要求你:
    ?1) 試驗不同的輸入, 反推出目前微軟的學術搜索是如何實現搜索建議 （Query Suggestion）的。
    ?2) 提出自己的改進建議,? 并論證這個解決方案在千萬級數據規模上能達到 “足夠好” 的時間 (speed) 和空間 （memory usage）效率。
    ?3) 估計這事需要幾個 人·月 （man-month） 才能做完?? （備注：順便給鄒欣老師傳個話，如果應屆畢業生可以能做好上述全部三個題目，便可直接找他。http://www.cnblogs.com/xinz/archive/2011/10/10/2205232.html）。

25. 今天10.10阿里云部分筆試題目：
    1、一個樹被序列化為數組，如何反序列化。
    2、如何將100百萬有序數據最快插入到STL的map里。
    3、有兩個線程a、b分別往一條隊列push和pop數據，在沒有鎖和信號量的情況下如何避免沖突訪問。
    4、寫一個函數，功能是從字符串s中查找出子串t，并將t從s中刪除。
26. 將長度為m和n的兩個升序數組復制到長度為m+n的數組里，升序排列。

27. tencent2012筆試題附加題
    問題描述： 例如手機朋友網有n個服務器，為了方便用戶的訪問會在服務器上緩存數據，因此用戶每次訪問的時候最好能保持同一臺服務器。
    已有的做法是根據ServerIPIndex[QQNUM%n]得到請求的服務器，這種方法很方便將用戶分到不同的服務器上去。但是如果一臺服務器死掉了，那么n就變為了n-1，那么ServerIPIndex[QQNUM%n]與ServerIPIndex[QQNUM%（n-1）]基本上都不一樣了，所以大多數用戶的請求都會轉到其他服務器，這樣會發生大量訪問錯誤。

    問： 如何改進或者換一種方法，使得：
    （1）一臺服務器死掉后，不會造成大面積的訪問錯誤，
    （2）原有的訪問基本還是停留在同一臺服務器上；
    （3）盡量考慮負載均衡。（思路：往分布式一致哈希算法方面考慮。關于此算法，可參見此文：http://blog.csdn.net/21aspnet/article/details/5780831）

28. ?騰訊面試題：A.txt和B.txt兩個文件，A.txt有1億個QQ號?， B.txt? 100W個QQ號， 用代碼實現交、并、差。

29. ?說出下面的運行結果
    #include <iostream>
    using namespace std;

    class A
    {
    public:
    ??? virtual void Fun(int number = 10)
    ??? {
    ??????? std::cout << "A::Fun with number " << number<<endl;
    ??? }
    };

    class B: public A
    {
    public:
    ??? virtual void Fun(int number = 20)
    ??? {
    ??????? std::cout << "B::Fun with number " << number<<endl;
    ??? }
    };

    int main()
    {
    ??? B b;
    ??? A &a = b;
    ??? a.Fun();
    ?return 0;
    }???????????????? //虛函數動態綁定=>B，非A，缺省實參是編譯時候確定的=>10，非20 。

30. ?今晚阿里云筆試：有101根電線?每根的一頭在樓底??另一端在樓頂??有一個燈泡?一個電池?無數根很短的電線??怎么樣在樓上一次在樓下去一次將電線的對應關系弄清楚。

31. 金山筆試題：
    ?1、C ++為什么經常將析構函數聲明為虛函數？
    ?2、inline和#define的如何定義MAX，區別是什么。
    ?3、const的用法，如何解除const限制。
    ?4、智能指針的作用和設計原理。
    ?5、STL中vetor如何自己設計，關鍵設計點，函數聲明，自定義刪除重復元素的函數。
    ?6、如何用一條SQL語句，刪除表中某字段重復的記錄。

32. ?淘寶：

    在現代web服務系統的設計中，為了減輕源站的壓力，通常采用分布式緩存技術，其原理如下圖所示，前端的分配器將針對不同內容的用戶請求分配給不同的緩存服務器向用戶提供服務。
    ????????????? ?分配器
    ???? ?/?????????????|???????? \
    緩存???????? 緩存 . ..緩存
    服務器1 服務器2 ...服務器n

    ?1）請問如何設置分配策略，可以保證充分利用每個緩存服務器的存儲空間（每個內容只在一個緩存服務器有副本）
    ?2）當部分緩存服務器故障，或是因為系統擴容，導致緩存服務器的數量動態減少或增加時，你的分配策略是否可以保證較小的緩存文件重分配的開銷，如果不能，如何改進？
    ?3）當各個緩存服務器的存儲空間存在差異時（如有4個緩存服務器，存儲空間比為4：9：15：7），如何改進你的策略，按照如上的比例將內容調度到緩存服務器？（思路：往memcached或者一致性hash算法方面考慮，但具體情況，具體分析。）

33. ?騰訊：50個臺階，一次可一階或兩階，共有幾種走法（老掉牙的題了，詳見微軟面試100題2010版。

    long long Fibonacci_Solution1(unsigned int n)
    {
    ????? int result[2] = {0, 1};
    ????? if(n < 2)
    ??????????? return result[n];

    ????? return Fibonacci_Solution1(n - 1) + Fibonacci_Solution1(n - 2);
    }）。

34. ?有兩個float型的數，一個為fmax,另一個為fmin,還有一個整數n,如果?(fmax?-?fmin)/n?,不能整除，怎么改變fmax,fmin,使改變后可以整除n 。

35. ?2011.10.11最新百度電面：
    ?1、動態鏈接庫與靜態鏈接庫的區別（? 靜態鏈接庫是.lib格式的文件，一般在工程的設置界面加入工程中，程序編譯時會把lib文件的代碼加入你的程序中因此會增加代碼大小，你的程序一運行lib代碼強制被裝入你程序的運行空間，不能手動移除lib代碼。
    ? 動態鏈接庫是程序運行時動態裝入內存的模塊，格式*.dll，在程序運行時可以隨意加載和移除，節省內存空間。
    ? 在大型的軟件項目中一般要實現很多功能，如果把所有單獨的功能寫成一個個lib文件的話，程序運行的時候要占用很大的內存空間，導致運行緩慢；但是如果將功能寫成dll文件，就可以在用到該功能的時候調用功能對應的dll文件，不用這個功能時將dll文件移除內存，這樣可以節省內存空間。）
    ?2、指針與引用的區別（相同點：1. 都是地址的概念；
    指針指向一塊內存，它的內容是所指內存的地址；引用是某塊內存的別名。

    區別：
    1. 指針是一個實體，而引用僅是個別名；
    2. 引用使用時無需解引用(*)，指針需要解引用；
    3. 引用只能在定義時被初始化一次，之后不可變；指針可變；
    4. 引用沒有 const，指針有 const；
    5. 引用不能為空，指針可以為空；
    6. “sizeof 引用”得到的是所指向的變量(對象)的大小，而“sizeof 指針”得到的是指針本身(所指向的變量或對象的地址)的大小；
    7. 指針和引用的自增(++)運算意義不一樣；
    8.從內存分配上看：程序為指針變量分配內存區域，而引用不需要分配內存區域。）
    ?3、進程與線程的區別（①從概念上：
    進程：一個程序對一個數據集的動態執行過程，是分配資源的基本單位。
    線程：一個進程內的基本調度單位。
    線程的劃分尺度小于進程，一個進程包含一個或者更多的線程。
    ②從執行過程中來看：
    進程：擁有獨立的內存單元，而多個線程共享內存，從而提高了應用程序的運行效率。
    線程：每一個獨立的線程，都有一個程序運行的入口、順序執行序列、和程序的出口。但是線程不能夠獨立的執行，必須依存在應用程序中，由應用程序提供多個線程執行控制。
    ③從邏輯角度來看：（重要區別）
    多線程的意義在于一個應用程序中，有多個執行部分可以同時執行。但是，操作系統并沒有將多個線程看做多個獨立的應用，來實現進程的調度和管理及資源分配。）
    ?4、函數調用入棧出棧的過程
    ?4、c++對象模型與虛表
    ?5、海量數據處理，以及如何解決Hash沖突等問題
    ?6、系統設計，概率算法

36. ?今天騰訊面試：
    一個大小為N的數組，里面是N個整數，怎樣去除重復，
    要求時間復雜度為O(n)，空間復雜度為O(1)（此題答案請見@作者hawksoft：http://blog.csdn.net/hawksoft/article/details/6867493）。

37. 一個長度為10000的字符串，寫一個算法，找出最長的重復子串，如abczzacbca,結果是bc（思路：后綴樹/數組的典型應用，@well：就是求后綴數組的height[]的最大值?
    ）。

38. 今晚10.11大華筆試題：建立一個data structure表示沒有括號的表達式，而且找出所有等價（equivalent）的表達式
    比如：
    3×5 == 5×3
    2+3 == 3+2
39. 今晚10.11百度二面：判斷一個數的所有因數的個數是偶數還是奇數（只需要你判斷因數的個數是偶數個還是奇數個，那么可以這么做@濱湖&&土豆：那只在計算質因數的過程中統計一下當前質因數出現的次數，如果出現奇數次則結果為偶，然后可以立即返回；如果每個質因數的次數都是偶數，那么結果為奇。如果該數是平方數 結果就為奇? 否則就為偶了）。
40. 比如A認識B，B認識C，但是A不認識C， 那么稱C是A的二度好友。找出某個人的所有十度好友.? 數據量為10萬（BFS，同時記錄已遍歷過的頂點，遍歷時遇到的已遍歷過的頂點不插入隊列。此是今晚10.11人人筆試題目，但它在上個月便早已出現在本人博客中，即此文第23題第2小題：九月騰訊，創新工場，淘寶等公司最新面試十三題）。
41. map在什么情況下會發生死鎖；stl中的map是怎么實現的？（有要參加淘寶面試的朋友注意，淘寶喜歡問STL方面的問題）
42. 昨日筆試：有四個人，他們每次一起出去玩的時候，用同時剪刀包袱錘的方式決定誰請客。設計一種方法，使得他們只需出一次，就可以決定請客的人，并且每個人請客的幾率相同，均為25%。
43. Given two sets of n numbers a1, a2…, an and b1, b2…bn, find, in polynomial time, a permutation Π such that ∑i |ai - b Π(i)| is minimized?? Prove your algorithm works.
    有兩個數組，在多項式時間里找到使 兩數組元素 的差 的絕對值 的和 最小 的一種置換。
    并證明算法的有效性。注意，關鍵是證明。（此題個人去年整理過類似的一題，詳見微軟面試100題2010版第32題：http://blog.csdn.net/v_JULY_v/archive/2011/01/10/6126444.aspx）
44. 對已排好序的數組A，一般來說可用二分查找?可以很快找到。
    現有一特殊數組A[]，它是循環遞增的，如A[]={?17?19?20?25?1?4?7?9},
    試在這樣的數組中找一元素x，看看是否存在。
    請寫出你的算法，必要時可寫偽代碼，并分析其空間?時間復雜度。
45. 網易：題意很簡單，寫一個程序，打印出以下的序列。
    (a),(b),(c),(d),(e)........(z)
    (a,b),(a,c),(a,d),(a,e)......(a,z),(b,c),(b,d).....(b,z),(c,d).....(y,z)
    (a,b,c),(a,b,d)....(a,b,z),(a,c,d)....(x,y,z)
    ....
    (a,b,c,d,.....x,y,z)（思路：全排列問題）

46. int global = 0;

    // thread 1
    for(int i = 0; i < 10; ++i)
    ?global -= 1;

    // thread 2
    for(int i = 0; i < 10; ++i)
    ?global += 1;

    之后global的可能的值是多少（多種可能）？

47. 今天10.13新浪筆試：
    ?1、用隱喻說明class和object的區別，要求有新意。
    ?2、DDL，DML，DCL的含義，和距離
    ?3、TCP建立連接的三次握手
    ?4、設計人民幣面值，要求種類最好，表示1——1000的所有數，平均紙幣張數最少
    ?5、UML
48. 一個數組。里面的數據兩兩相同，只有兩個數據不同，要求找出這兩個數據。要求時間復雜度0（N）空間復雜度O（1）。
49. 兩個數相乘，小數點后位數沒有限制，請寫一個高精度算法。
50. 面試基礎題：
    ?1、靜態方法里面為什么不能聲明靜態變量？
    ?2、如果讓你設計一個類，什么時候把變量聲明為靜態類型？
    ?3、抽象類和接口的具體區別是什么？

51. 谷歌昨晚10.13算法筆試三題：
    １.一個環形公路，上面有Ｎ個站點，A1, ..., AN，其中Ai和Ai+1之間的距離為Di,AN和A1之間的距離為D0。
    高效的求第i和第j個站點之間的距離，空間復雜度不超過O(N)
    它給出了部分代碼如下：
    #define N 25
    double D[N]
    ....
    void Preprocess()
    {
    ???? //Write your code1;
    }
    double Distance(int i, int j)
    {
    ????? //Write your code2;
    }

    2. 一個字符串，壓縮其中的連續空格為1個后，對其中的每個字串逆序打印出來。比如"abc?? efg? hij"打印為"cba gfe jih"。

    3. 將一個較大的錢，不超過1000000(10^6)的人民幣，兌換成數量不限的100、50、10、5、2、1的組合，請問共有多少種組合呢？（其它選擇題考的是有關：操作系統、樹、概率題、最大生成樹有關的題，另外聽老夢說，谷歌不給人霸筆的機會。）。

52. 谷歌在線筆試題：
    輸入兩個整數A和B，輸出所有A和B之間滿足指定條件的數的個數。指定條件：假設C=8675在A跟B之間，若（8+6+7+5）/?4?>?7，則計一個，否則不計。
    要求時間復雜度：log(A)+log(B)。
53. 
54. 十五道百度、騰訊面試基礎測試題@fengchaokobe：
    ?1、寫一個C的函數，輸入整數N，輸出整數M，M滿足：M是2的n次方，且是不大于N中最大的2的n次方。例如，輸入4,5,6,7，都是輸出4 。
    ?2、C++中虛擬函數的實現機制。
    ?3、寫出選擇排序的代碼及快速排序的算法。
    ?4、你認為什么排序算法最好？
    ?5、tcp/ip的那幾層協議，IP是否是可靠的？為什么？
    ?6、進程和線程的區別和聯系，什么情況下用多線程，什么時候用多進程?
    ?7、指針數組和數組指針的區別。
    ?8、查找單鏈表的中間結點。
    ?9、最近在實驗室課題研究或工作中遇到的技術難點，怎么解決的？
    ?10、sizeof和strlen的區別。
    ?11、malloc-free和new-delete的區別
    ?12、大數據量中找中位數。
    ?13、堆和棧的區別。
    ?14、描述函數調用的整個過程。
    ?15、在一個兩維平面上有三個不在一條直線上的點。請問能夠作出幾條與這些點距離相同的線？
    
55. 搜狐的一道筆試題：
    ?char *s="mysohu";
    ?s[0]=0; //..
    ?printf("%s",s);
    輸出是什么啊？
    搜狐的一道大題：
    ? 數組非常長，如何找到第一個只出現一次的數字，說明算法復雜度。（與個人之前整理的微軟面試100題中，第17題：在一個字符串中找到第一個只出現一次的字符。類似，讀者可參考。）
    
56. 百度筆試3. 假設有一臺迷你計算機，1KB的內存，1MHZ的cpu，已知該計算機執行的程序可出現確定性終止(非死循環)，問如何求得這臺計算機上程序運行的最長時間，可以做出任何大膽的假設。
    
57. 微軟10.15筆試：對于一個數組{1,2,3}它的子數組有{1,2}，{1,3}{2,3}，{1,2,3}，元素之間可以不是連續的，對于數組{5,9,1,7,2,6,3,8,10,4}，升序子序列有多少個？或者換一種表達為：數組int a[]={5,9,1,7,2,6,3,8,10,4} ?。求其所有遞增子數組(元素相對位置不變)的個數， ? 例如：{5，9}，{5，7，8，10}，{1，2，6，8}。
58. 今日騰訊南京筆試題：? M*M的方格矩陣，其中有一部分為障礙，八個方向均可以走，現假設矩陣上有Q+1節點，從(X0，Y0)出發到其他Q個節點的最短路徑。
    其中，1<=M<=1000，1<=Q<=100。
59. 另外一個筆試題：
    一個字符串S1：全是由不同的字母組成的字符串如：abcdefghijklmn
    另一個字符串S2：類似于S1，但長度要比S1短。
    問題是，設計一種算法，求S2中的字母是否均在S1中。（字符串包含問題，詳見程序員編程藝術系列第二章：http://blog.csdn.net/v_JULY_v/article/details/6347454）。
60. ?檢索一英語全文，順序輸出檢測的單詞和單詞出現次數。
61. 今天10.15下午網易游戲筆試題：給一個有序數組array[n]，和一個數字m，判斷m是否是這些數組里面的數的和。（類似于微軟面試100題2010年版第4題，即相當于給定一棵樹，然后給定一個數，要求把那些 相加的和等于這個數的 所有節點打印出來）。
    
62. 一個淘寶的面試題
    文件A：
    uid username
    文件B：
    username password
    文件A是按照uid有序排列的，要求有序輸出合并后的A,B文件，格式為uid username password（A B 兩個文件都很大，內存裝不下。）
    
63. 百度可能會問問memcached（可下載此份文檔看看：http://tech.idv2.com/2008/08/17/memcached-pdf/。源碼下載地址：http://www.oschina.net/p/memcached）,apache之類的。
64. 今上午10.16百度筆試：1.C++ STL里面的vector的實現機制，
    （1）當調用push_back成員函數時，怎么實現？（粗略的說@owen，內存足則直接 placement new構造對象，否則擴充內存，轉移對象，新對象placement new上去。具體的參見此文：http://blog.csdn.net/v_july_v/article/details/6681522）
    （2）當調用clear成員函數時，做什么操作，如果要釋放內存該怎么做。（調用析構函數，內存不釋放。 clear沒有釋放內存，只是將數組中的元素置為空了，釋放內存需要delete。）
    2. 函數foo找錯，該函數的作用是將一個字符串中的a-z的字母的頻數找出來
    void foo(char a[100],int cnt[256])
    {
    memset(cnt ,0, sizeof(cnt));
    while (*a!='\0')
    {
    ++cnt[*a];
    ++a;
    }
    for ( char c='a';c<='z';++c)
    {
    printf("%c:%d\n",c,cnt[c]);
    }
    }
    int main()
    {
    char a[100]="百度abc";
    int cnt[256];
    foo(a,cnt);
    return 0;
    }
    
65. 騰訊長沙筆試：旅行商問題。
    
66. 今天完美10.16筆試題：2D平面上有一個三角形ABC，如何從這個三角形內部隨機取一個點，且使得在三角形內部任何點被選取的概率相同。
67. 不用任何中間變量，實現strlen函數
68. 筆試：聯合賦值問題：#include <stdio.h>
    union A{
    int i;
    char x[2];
    }a;
    int main()
    {
    a.x[0]=10;
    a.x[1]=1;
    printf("%d\n",a.i);
    return 0;
    }
    sizeof(a) = sizeof(int) = 4 byte
    4 * 8 = 32 bit
    a = > 00000000 00000000 00000000 00000000
    a.x[0]=10 => 00000000 00000000 00000000 00001010
    a.x[1]=1 => 00000000 00000000 00000001 00001010
    a.i = 1*256 + 1*8 + 1*2 = 256+10 = 266
69. 昨天做了中興的面試題：
    struct A{
    ? int a;
    ? char b;
    ? char c;
    };
    問sizeof(A)是多大？
70. 更新至2011.10.16下午.....
    

??? 更多面試題，參見橫空出世，席卷Csdn--評微軟等數據結構+算法面試100題?（在此文中，集結了本博客已經整理的236道面試題）。

后記???

??? 此些面試題看多了，自然會發現題目類型可能會千變萬化，但解決問題的思路卻只有那么幾種。再者，寫代碼的時候，很多的細節需要務必注意，如返回值，函數參數的檢查，特殊情況的處理等等，這是一個代碼規范性的問題。在結文之前，有三事須說明：

1. 結構之法算法之道全部博文集錦第4期CHM文件下載：http://download.csdn.net/detail/v_JULY_v/3660710。
2. 本博客算法交流群第16群：Algorithms_16，30382647。
3. 微軟面試全部100題的答案如今已由一朋友阿財做出，微軟面試100題2010年版全部答案集錦：http://blog.csdn.net/v_july_v/article/details/6870251，供諸君參考。

??? ok，日后一有最新的面試題，再整理，有任何問題，歡迎在本文評論下指出或來信指導（zhoulei0907@yahoo.cn），謝謝。July、2011.10.09。