九月騰訊，創新工場，淘寶等公司最新面試三十題（更新至10.04）

????????九月騰訊，創新工場，淘寶等公司最新面試三十題

引言???

??? 曾記否，去年的10月份也同此刻一樣，是找工作的高峰期，本博客便是最初由整理微軟等公司面試題而發展而來的。如今，又即將邁入求職高峰期--10月份，而本人也正在找下一份工作中，所以，也不免關注了網上和我個人建的算法群Algorithms1-12群內朋友發布和討論的最新面試題。特此整理，以饗諸位。至于答案，望諸位共同討論與思考。

后續整理

??? 以下是后續整理的最新面試題，不斷更新中（2011.09.26）.....

14、騰訊最新面試題：服務器內存1G，有一個2G的文件，里面每行存著一個QQ號（5-10位數），怎么最快找出出現過最多次的QQ號。

以下是個人所建第Algorithms_12群內朋友的聊天記錄：

??? 首先你要注意到，數據存在服務器，存儲不了（內存存不了），要想辦法統計每一個qq出現的次數。
比如，因為內存是1g，首先你用hash 的方法，把qq分配到10個（這個數字可以變動，比較）文件（在硬盤中）。
??? 相同的qq肯定在同一個文件中，然后對每一個文件，只要保證每一個文件少于1g的內存，統計每個qq的次數，可以使用hash_map(qq, qq_count)實現。然后，記錄每個文件的最大訪問次數的qq，最后，從10個文件中找出一個最大，即為所有的最大。更多讀者可以參見此文：海量數據處理面試題集錦與Bit-map詳解?。

??? 那若面試官問有沒有更高效率的解法之類的?這時，你可以優化一下，但是這個速度很快，hash函數，速度很快，他肯定會問，你如何設計，用bitmap也行。

15、百度今天的筆試題：在一維坐標軸上有n個區間段，求重合區間最長的兩個區間段。

16、華為社招現場面試1：請使用代碼計算1234567891011121314151617181920*2019181716151413121110987654321 。

華為面試2：1分2分5分的硬幣，組成1角，共有多少種組合。

17、百度筆試題：

一、系統有很多任務，任務之間有依賴，比如B依賴于A，則A執行完后B才能執行
? （1）不考慮系統并行性，設計一個函數（Task *Ptask,int Task_num）不考慮并行度，最快的方法完成所有任務。
? （2）考慮并行度，怎么設計
? typedef struct{
???? ?int ID;
?? ? int * child;
??? ? int child_num;
? }Task;
? 提供的函數:
??? bool doTask(int taskID);無阻塞的運行一個任務；
? ? int waitTask(int timeout);返回運行完成的任務id，如果沒有則返回-1；
?? ?bool killTask(int taskID);殺死進程

二、必答題（各種const）
1、解釋下面ptr含義和不同
double* ptr = &value;
? ? //ptr是一個指向double類型的指針，ptr的值可以改變，ptr所指向的value的值也可以改變?
const double* ptr = &value
? ? //ptr是一個指向const double類型的指針，ptr的值可以改變，ptr所指向的value的值不可以改變
double* const ptr=&value
? ? //ptr是一個指向double類型的指針，ptr的值不可以改變，ptr所指向的value的值可以改變
const double* const ptr=&value
? ? //ptr是一個指向const double類型的指針，ptr的值不可以改變，ptr所指向的value的值也不可以改變2、去掉const屬性，例： ?const double value = 0.0f; ?double* ptr = NULL;怎么才能讓ptr指向value？
? ? 強制類型轉換，去掉const屬性，如ptr = <const_cast double *>(&value);

http://topic.csdn.net/u/20110925/16/e6248e53-1145-4815-8d24-9c9019d24bd8.html?seed=1665205011&r=75709169#r_75709169

18、如果用一個循環數組q[0..m-1]表示隊列時,該隊列只有一個隊列頭指針front,不設隊列尾指針rear，求這個隊列中從隊列投到隊列尾的元素個數（包含隊列頭、隊列尾）（華賽面試題、騰訊筆試題）。

19、昨晚淘寶筆試題：

1. 設計相應的數據結構和算法，盡量高效的統計一片英文文章（總單詞數目）里出現的所有英文單詞，按照在文章中首次出現的順序打印輸出該單詞和它的出現次數。

2、有一棵樹（樹上結點為字符串或者整數），請寫代碼將樹的結構和數據寫到一個文件中，并能通過讀取該文件恢復樹結構?。

20、13個球一個天平，現知道只有一個和其它的重量不同，問怎樣稱才能用三次就找到那個球?（http://zhidao.baidu.com/question/66024735.html
）。

21、搜狗筆試題：一個長度為n的數組a[0],a[1],...,a[n-1]。現在更新數組的名個元素，即a[0]變為a[1]到a[n-1]的積，a[1]變為a[0]和a[2]到a[n-1]的積，...，a[n-1]為a[0]到a[n-2]的積（就是除掉當前元素，其他所有元素的積）。
程序要求：
要求具有線性復雜度。
不能使用除法運算符。

??? 思路：left[i]存儲a[i]之前的乘積，right[i]存儲a[i]之后的乘積，那么a[i]=left[i]*right[i] 。

??? 不過，left的計算從左往右掃的時候得出，right是從右往左掃得出。因為就是當中某個元素的左邊所有元素與右邊所有元素的乘積，就這么簡單。所以計算a[i]=left[i]*right[i]時，直接出結果。

22、騰訊高水平復試題：

1.有不同的手機終端，如iphone，安卓，Symbian，不同的終端處理不一樣，設計一種服務器和算法實現對不同的終端的處理。
2.設計一種內存管理算法。?
3.A向B發郵件，B收到后讀取并發送收到，但是中間可能丟失了該郵件，怎么設計一種最節省的方法，來處理丟失問題。?
4.設計一種算法求出算法復雜度。

23、人人筆試1：一個人上臺階可以一次上1個，2個，或者3個，問這個人上n層的臺階，總共有幾種走法？

? ? ? ?人人筆試2：在人人好友里，A和B是好友，B和C是好友，如果A　和C不是好友，那么C是A的二度好友，在一個有１０萬人的數據庫里，如何在時間０（ｎ）里，找到某個人的十度好友。

24、淘寶算法面試題：兩個用戶之間可能互相認識，也可能是單向的認識，用什么數據結構來表示？如果一個用戶不認識別人，而且別人也不認識他，那么他就是無效節點，如何找出這些無效節點？自定義數據接口并實現之，要求盡可能節約內存和空間復雜度。

25、淘寶筆試題：對于一顆完全二叉樹，要求給所有節點加上一個pNext指針，指向同一層的相鄰節點；如果當前節點已經是該層的最后一個節點，則將pNext指針指向NULL；給出程序實現，并分析時間復雜度和空間復雜度。

26、騰訊面試題：給你5個球，每個球被抽到的可能性為30、50、20、40、10，設計一個隨機算法，該算法的輸出結果為本次執行的結果。輸出A，B，C，D，E即可。

27、搜狐筆試題：給定一個實數數組，按序排列（從小到大）,從數組從找出若干個數，使得這若干個數的和與M最為接近，描述一個算法，并給出算法的復雜度。

28、蘋果面試題：write a function that will trigger a prefetch address abort exception。

29、阿里巴巴研究院（2009）：

1. 有無序的實數列V[N]，要求求里面大小相鄰的實數的差的最大值，關鍵是要求線性空間和線性時間

2. 25匹賽馬，5個跑道，也就是說每次有5匹馬可以同時比賽。問最少比賽多少次可以知道跑得最快的5匹馬

3. 有一個函數int getNum()，每運行一次可以從一個數組V[N]里面取出一個數，N未知，當數取完的時候，函數返回NULL。現在要求寫一個函數int get()，這個函數運行一次可以從V[N]里隨機取出一個數，而這個數必須是符合1/N平均分布的，也就是說V[N]里面任意一個數都有1/N的機會被取出，要求空間復雜度為O（1）

Given a head pointer pointing to a linked list ,please write a function that sort the list
in increasing order. You are not allowed to use temporary array or memory copy
struct
{
? int data;
? struct S_Node *next;
}Node;
Node * sort_link_list_increasing_order (Node *pheader):