閱讀屋>面試> 網際網路開發面試題

網際網路開發面試題

1一共有100萬，抽中的2萬，每月增加4萬，問20個月能抽中的機率為：?

2 for(int i=0;i<strlen(s);i++){n+=i;}時間複雜度o(n)< p="">

3 手機wifi(A)….wifi ap….區域網(B)…..路由器…ADSL(C)…..網際網路…..伺服器

斷掉上述ABC哪些點TCP連結會立刻斷掉?

4 12345入棧，出棧結果 21543 31245 43215 12534 可能的為?(第一個和第三個)

5 x^n+a1x^n-1+…+an-1x+an,最少要做—乘法?題目中a1，a2，an為常數。

9月26日，百度一二面：

1、給定一陣列，輸出滿足2a=b(a，b代表陣列中的數)的數對，要求時間複雜度儘量低。

2、搜尋引擎多執行緒中每個執行緒佔用多少記憶體?如果搜尋引擎儲存網頁記憶體佔用太大怎麼解決?

3、有很多url，例如*.baidu.com，*.sina.com ......

現在給你一個sports.sina.com 快速匹配出是*.sina.com。點評：老題，此前blog內曾整理過。

4、找出字串的編輯距離，即把一個字串s1最少經過多少步操作變成程式設計字串s2，操作有三種，新增一個字元，刪除一個字元，修改一個字元(只要聽過編輯距離，知道往動態規劃上想，很快就可以找到解法)。

點評：請看連結：http://blog.csdn.net/Lost_Painting/article/details/6457334。

5、程式設計實現memcopy，注意考慮目標記憶體空間和源空間重疊的時候。

6、實現簡單的一個查詢二叉樹的深度的函式。

9月26日晚，優酷土豆筆試題一道：

優酷是一家影片網站，每天有上億的影片被觀看，現在公司要請研發人員找出最熱門的影片。

該問題的輸入可以簡化為一個字串檔案，每一行都表示一個影片id，然後要找出出現次數最多的前100個影片id，將其輸出，同時輸出該影片的出現次數。

1.假設每天的影片播放次數為3億次，被觀看的影片數量為一百萬個，每個影片ID的長度為20位元組，限定使用的記憶體為1G。請簡述做法，再寫程式碼。

2.假設每個月的影片播放次數為100億次，被觀看的影片數量為1億，每個影片ID的長度為20位元組，一臺機器被限定使用的記憶體為1G。

點評：有關海量資料處理的題目，請到此文中找方法(無論題目形式怎麼變，基本方法不變，當然，最最常用的方法是：分而治之/Hash對映 + Hash統計 + 堆/快速/歸併排序)：http://blog.csdn.net/v_july_v/article/details/7382693。注：上題第二問檔案太大，則可如模1000，把整個大檔案對映為1000個小檔案再處理 ....

9月26日，baidu面試題：

1.程序和執行緒的區別

2.一個有序陣列(從小到大排列)，陣列中的資料有正有負，求這個陣列中的最小絕對值

3.連結串列倒數第n個元素

4.有一個函式fun能返回0和1兩個值，返回0和1的機率都是1/2，問怎麼利用這個函式得到另一個函式fun2，使fun2也只能返回0和1，且返回0的機率為1/4,返回1的機率為3/4。(如果返回0的機率為0.3而返回1的機率為0.7呢)

5.有8個球，其中有7個球的質量相同，另一個與其他球的質量不同(且不知道是比其他球重還是輕)，請問在最壞的情況下，最少需要多少次就能找出這個不同質量的球

6.資料庫索引

7.有一個數組a，設有一個值n。在陣列中找到兩個元素a[i]和a[j]，使得a[i]+a[j]等於n，求出所有滿足以上條件的i和j。

8.1萬個元素的陣列，90%的元素都是1到100的數，10%的元素是101--10000的數，如何高效排序。

小米的web開發筆試題：

一場星際爭霸比賽，共8個人，每個人的實力用分數表示，要分成兩隊，如何保證實力最平均?給定一個浮點數的序列，F1,F2,……，Fn(1<=n<=1000),定義P(s,e)為子序列Fi(s<=i<=e)的積，求P的最大值。

9月27日，趨勢科技面試題：

馬路口，30分鐘內看到汽車的機率是95%，那麼在10分鐘內看不到汽車的機率是?

9月27日晚，IGT筆試題：

給定一個字串裡面只有"R" "G" "B" 三個字元，請排序，最終結果的順序是R在前 G中 B在後。

要求：空間複雜度是O(1)，且只能遍歷一次字串。

點評：本質是荷蘭國旗問題，類似快排中partition過程，具體思路路分析及程式碼可以參考此文第8節：http://blog.csdn.net/v_july_v/article/details/6211155。

9月27日，人人兩面：

一面

1 實現atoi

2 單鏈表變形如 1 2 3 4 5 變為 1 3 5 4 2 如1 2 3 4 變為 1 3 4 2

(就是拆分連結串列把偶數為反過來接在奇數位後面)

二面

1 二叉樹查詢不嚴格小於一個值的最大值(返回節點)。

2 有序數組裡二分查詢一個數(如果有相同的找最後一次出現的)。

3 等價於n*n的矩陣，填寫0，1，要求每行每列的都有偶數個1 (沒有1也是偶數個)，問有多少種方法。

評論：開始以為是演算法題，想了狂搜，遞推(dp，可以用xor表示一行的列狀態，累加),分治，(拆兩半，然後上半段下半段的列有相同的奇偶性)。後來，自己算了幾個發現n = 1 n = 2 n = 3 的結果，他告訴了我n = 4是多少，然後發現f(n) = 2^((n - 1) ^2) 。最後我給出了一個巧妙的證明。然後發現如果是m*n的矩陣也是類似的答案，不侷限於方陣。此外，題目具體描述可以看看這裡：http://blog.himdd.com/?p=2480。

9月27日，小米兩面：

一面：

除了聊研究，就一道題

1 數組裡找到和最接近於0的兩個值。

二面：

1 行列有序的矩陣查詢一個數

2 直方圖最大矩形。點評：這裡有此題的具體表述及一份答案：http://blog.csdn.net/xybsos/article/details/8049048。

3 next_permutation

4 字串匹配含有* ? (寫程式碼)

5 實現strcpy memmove (必須寫程式碼)

//void * memmove ( void * destination, const void * source, size_t num );)

//是的標準函式，其作用是把從source開始的num個字元複製到destination。

//最簡單的方法是直接複製，但是由於它們可能存在記憶體的重疊區，因此可能覆蓋了原有資料。

//比如當source+count>=dest&&source<dest時，dest可能覆蓋了原有source的資料。< p="">

//解決辦法是從後往前複製。

//對於其它情況，則從前往後複製。

void* memmove(void* dest, void* source, size_t count)

{

void* ret = dest;

if (dest <= source || dest >= (source + count))

{

//正向複製

//copy from lower addresses to higher addresses

while (count --)

*dest++ = *source++;

}

else

{

//反向複製

//copy from higher addresses to lower addresses

dest += count - 1;

source += count - 1;

while (count--)

*dest-- = *source--;

}

return ret;

}

更多，還可以參見此文第三節節末：http://blog.csdn.net/v_july_v/article/details/6417600，或此文:http://www.360doc.com/content/11/0317/09/6329704_101869559.shtml。

6 讀數 (千萬億，百萬億……)變為數字 (說思路即可，字串查詢，填寫各個權值的欄位，然後判斷是否合法，讀前面那些×權值，累加)。

9月27日，Hulu 2013北京地區校招筆試題

填空題：

1、中序遍歷二叉樹，結果為ABCDEFGH，後序遍歷結果為ABEDCHGF，那麼前序遍歷結果為?

2、對字串HELL0_HULU中的字元進行二進位制編碼，使得字串的編碼長度儘可能短，最短長度為?

3、對長度12的有序陣列進行二分查詢，目標等機率出現在陣列的每個位置上，則平均比較次數為?

4、一副撲克(去王)，每個人隨機的摸兩張，則至少需要多少人摸牌，才能保證有兩個人抽到同樣的花色。

5、x個小球中有唯一一個球較輕，用天平秤最少稱量y次能找出這個較輕的球，寫出y和x的函式表示式y=f(x)

6、3的方冪及不相等的3的方冪的和排列成遞增序列1,3,4,9,10,12,13……，寫出數列第300項

7、無向圖G有20條邊，有4個度為4的頂點，6個度為3的頂點，其餘頂點度小於3，則G有多少個頂點

8、桶中有M個白球，小明每分鐘從桶中隨機取出一個球，塗成紅色(無論白或紅都塗紅)再放回，問小明將桶中球全部塗紅的期望時間是?

9、煤礦有3000噸煤要拿到市場上賣，有一輛火車可以用來運煤，火車最多能裝1000噸煤，且火車本身需要燒煤做動力，每走1公里消耗1噸煤，如何運煤才能使得運到市場的煤最多，最多是多少?

10、1,2,3,4…..n，n個數進棧，有多少種出棧順序，寫出遞推公式(寫出通項公式不得分)

11、宇宙飛船有100,000位的儲存空間，其中有一位有故障，現有一種Agent可以用來檢測故障，每個Agent可以同時測試任意個位數，若都沒有故障，則返回OK，若有一位有故障，則失去響應。如果有無限多個Agent可供使用，每個Agent進行一次檢測需要耗費1小時，現在有2個小時時間去找出故障位，問最少使用多少個Agent就能找出故障。

(總共12道填空題，還有一道太複雜，題目很長，還有示意圖，這裡沒有記錄下來)

大題：

1、n個數，找出其中最小的k個數，寫出程式碼，要求最壞情況下的時間複雜度不能高於O(n logk)

2、寫程式輸出8皇后問題的所有排列，要求使用非遞迴的深度優先遍歷

3、有n個作業，a1,a2…..an，作業aj的處理時間為tj，產生的效益為pj，最後完成期限為dj，作業一旦被排程則不能中斷，如果作業aj在dj前完成，則獲得效益pj，否則無效益。給出最大化效益的作業排程演算法。點評：參考答案請看這個連結：http://www.51nod.com/question/#!questionId=645。

有道的一個筆試題，1-9，9個數組成三個三位數，且都是完全平方數(三個三位數佔據 9個數)求解法。

點評@林晚楓&歸雲見鴻：

(a*10+b)(a*10+b)

100a^2+20ab+b^2

a 屬於 [1,2,3]

a=3,b=1 31 961,

a=2,b=3 23 529 400+40b+b^2

25 625

27 729

28 784

29 841

a=1,b=3 13 169 100+20b+b^2

14 196

16 256

17 289

18 324

19 361

=>最終唯一解 529 784 361

具體程式碼如下(3個for迴圈，然後hash)：

9月28日，大眾點評北京筆試題目：

1.一個是跳臺階問題，可以1次一級，1次兩級，1次三級，求N級的跳法一共多少種?

點評：老題，參考答案請見：http://blog.csdn.net/v_july_v/article/details/6879101。

2.一個檔案有N個單詞，每行一個，其中一個單詞出現的次數大於N/2，怎麼樣才能快速找出這個單詞?

點評：還是老題，參見：http://blog.csdn.net/v_july_v/article/details/6890054。

大眾點評前面還有30道邏輯題，15道文字推理，15道數學推理，一共只給20min。

9月28日，網易筆試題：

1、英雄升級，從0級升到1級，機率100%。

從1級升到2級，有1/3的可能成功;1/3的可能停留原級;1/3的可能下降到0級;

從2級升到3級，有1/9的可能成功;4/9的可能停留原級;4/9的可能下降到1級。

每次升級要花費一個寶石，不管成功還是停留還是降級。

求英雄從0級升到3級平均花費的寶石數目。

點評：題目的意思是，從第n級升級到第n+1級成功的機率是(1/3)^n(指數)，停留原級和降級的機率一樣，都為[1-(1/3)^n]/2)。

2、將一個很長的字串，分割成一段一段的子字串，子字串都是迴文字串。

有迴文字串就輸出最長的，沒有迴文就輸出一個一個的字元。

例如：

habbafgh

輸出h,abba,f,g,h。

點評：程式設計藝術第十五章有這個迴文問題的解答，參見：http://blog.csdn.net/v_july_v/article/details/6712171。此外，一般的人會想到用字尾陣列來解決這個問題，其餘更多的方法請見：http://dsqiu.iteye.com/blog/1688736。最後，還可以看下這個連結：http://www.51nod.com/question/#!questionId=672。

10月9日，騰訊一面試題：

有一個log檔案，裡面記錄的格式為：

QQ號：時間： flag：

如123456 14：00：00 0

123457 14：00：01 1

其中flag=0表示登入 flag=1表示退出

問：統計一天平均線上的QQ數。

點評：類似於此文中：http://blog.csdn.net/hackbuteer1/article/details/7348968，第8題後的騰訊面試題，讀者可以參看之。

10月9日，騰訊面試題：

1.有一億個數，輸入一個數，找出與它編輯距離在3以內的書，比如輸入6(0110)，找出0010等數，數是32位的。

2.每個城市的IP段是固定的，新來一個IP，找出它是哪個城市的，設計一個後臺系統。

10月9日，YY筆試題：

1 輸出一個字串中沒有重複的字元。如“baaca”輸出“bac”。

2 對於一個多叉樹，設計TreeNode節點和函式，返回先序遍歷情況下的下一個節點。

函式定義為TreeNode* NextNode(TreeNode* node)

3 分割字串。

對於一個字串，根據分隔符seperator，把字串分割，如果存在多個分隔符連在一起，則當做一個分隔符。如果分隔符出現在" "符號之間，則不需要分割" "之間的字元。

比如a++abc ，分隔符為+，輸出a abc

a+"hu+" 輸出a hu+

a++"HU+JI 輸出a "HU JI。

請根據上述需求完成函式：void spiltString(string aString，char aSeperator)。

10月9日，趕集網筆試

10月9日，阿里巴巴2013校園招聘全套筆試題(注：下圖中所標答案不代表標準答案，有問題，歡迎留言評論)

上述第15題，填空：lower+ (upper-lower)/2

lower mid upper

0 6 12

7 9 12

7 7 8

8 8 8

比較4次

上述第16題，解答如下圖所示：

上述第17題，解答如下圖所示：

18、甲包8個紅球 2個藍球，乙包2個紅球 8個藍球。拋硬幣決定從哪個包取球，取了11次，7紅4藍。注，每次取後還放進去，只拋一次硬幣。問選的是甲包的機率?

點評：

貝葉斯公式 + 全機率公式作答(參看連結：http://www.doc88.com/p-132711202556.html)。具體解答如下圖所示：

注：上述第15~18的解答全部來自讀者Lei Lei來信給出的解答，他的部落格地址是：http://blog.csdn.net/nwpulei，特此感謝。有任何問題，歡迎隨時討論&指正，同時，更歡迎其他朋友也一起來做這些題目(你的答案一經選用，我可以根據你的要求，貼出你的個人主頁或微博地址或部落格地址)。

19、已知一個n個元素的陣列，第i個元素在排序後的位置在[i-k,i+k]區間，k<<n p="" (nlogn)不得分，o(nk)得2分，如下圖所示：<="" o="">

讀者twtsa毛遂自薦，這是他給出的上述第19~20題的個人題解：http://blog.csdn.net/twtsa/article/details/8055143。有任何問題，歡迎隨時討論&指正。

10月10日，暴風影音筆試：

都是非常基礎的題目，這是其中一道：一個整數轉換成二進位制後，問裡面有多少個1。

10月10日，2013亞馬遜線上筆試題目

題目及參考答案請見這：http://blog.chinaunix.net/uid-26750075-id-3370694.html。(感謝讀者freeloki來信提供)。

10月10日人人網面試題

第一面：

1、(1)++i 和 i++，那個效率高?

(2)++++i，i++++，哪個是合法的?

(3)實現int型的++i 和 i++操作。

2、一段程式，求輸出。(考察靜態變數和模版類)

int g = 0;

template

class B

{

public:

int static fun()

{

static int value = ++g;

return value;

}

};

int main()

{

cout << B::fun() << endl;

return 0;

}

3、(1)實現二進位制轉十進位制。

(2)如果有下面這種能直接求二進位制轉十進位制的程式碼，是怎麼實現的?

binary<1>::value; // 結果為1

binary<11>::value; // 結果為3

4、volatile、explicit、mutable表示的含義。

5、求整形陣列的一個子陣列，使得該子陣列所有元素的和的絕對值最大。

6、(1)寫求單鏈表是否有環的演算法。

(2)如果有環，如何找出環的第一個結點。

7、實現單例模式。

二面：

1、一個文字，一萬行，每行一個詞，統計出現頻率最高的前10個詞(詞的平均長度為Len)。並分析時間複雜度。

2、求陣列中最長遞增子序列。

10月10日，網易2013校園招聘全套筆試題：

10月10日，網易，資料探勘工程師：

1，簡述你對資料與處理的認識;

2，簡述你對中文分詞的理解，說明主要難點和常用演算法;

3，常見的分類演算法有哪些;

4，簡述K-MEANS演算法;

5，設計一個智慧的商品推薦系統;

6，簡述你對觀點挖掘的認識。

點評：其它題目與上述第56題第一部分(http://blog.csdn.net/hackbuteer1/article/details/8060917)所述相同。

10月11日，阿里巴巴筆試部分題目：

1. 甲乙兩個人上街，撿到一張10塊錢的購物卡，兩人就想出一個辦法來分配這張卡。兩個分別將自己出的價格寫在紙上，然後看誰出的價高就給誰，並且那個出價高的人要把出的`錢給對方。現在甲有6塊錢，乙有8塊錢。問誰獲得的錢多。(多選)

A 甲多 B 乙多 C 一樣多 D 有可能出現有人賠錢的情況

2. 有一個怪物流落到一個荒島上，荒島上有n條鱷魚。每條鱷魚都有實力單獨吃掉怪物。但是吃掉怪物是有風險的，會造成體力值下降，然後會有可能被掉其他鱷魚吃。問，最後那個怪物是危險的還是安全的?

3. 演算法題：

A[i]是一個有序遞增陣列，其中所有的數字都不相等，請設計一種演算法，求出其中所有的A[i]=i的數字並分析時間複雜度，不分析複雜度不得分。

4. 大題

你在瀏覽器中輸入網址：http://blog.csdn.net/v_JULY_v，按下回車鍵後，會發生什麼事情，請一一描述(20分)。包括瀏覽器，網路，伺服器等等發生的事情，及各項關鍵技術。

點評：這樣的題考過很多次，參考答案如下圖所示：

10月11日，華為一面：

1、將一個普通的二叉樹轉換為二叉排序樹?

2、隨便寫一個排序演算法。

10月11日，完美筆試題：

1.為什麼解構函式應該設為虛擬函式

2.大數字乘法問題

3.雙向連結串列模擬佇列操作push pop find

4.求 a/3 不能用除法

5.多核下多執行緒同步問題，使用鎖應該注意什麼

6.三個寶箱有一個裡面有珠寶，現在拿第一寶箱，然後開啟第二個寶箱後發現沒有珠寶，用機率論原理解釋為什麼現在拿第三個寶箱，裡面有珠寶的機率比拿第一個寶箱高。

10月11日，搜狐暢遊旗下第七大道筆試題：

演算法題

1.一個數是否是另一個數的平方。

2.N進位制換成M進位制

3.設計一個大數乘法

綜合題

1.N個數，出棧有幾種情況

2.程序死鎖原因及條件.

騰迅一個非常有意思的面試題：

N個數組，每個陣列中的元素都是遞增的順序，現在要找出這N個數組中的公共元素部分，如何做? 注：不能用額外輔助空間。

點評：

討論了半天：http://weibo.com/1580904460/z08mT0aFj，沒個好的結果，發現還是上午想到的N個指標逐步向後移動，輔以二分，然後N路歸併更靠譜，類似這裡的第5題所述的辦法：http://www.cnblogs.com/BeyondAnyTime/archive/2012/07/17/2593224.html。若讀者有更好的思路，歡迎賜教。

10月12日，迅雷2013校園招聘「廣州站」C++方向全套筆試題

(注：若照片看不清楚，請右鍵點選“圖片另存為”到桌面，然後再開啟圖片，便可以隨意放大縮小圖片拉)

10月12日晚，微策略北京站筆試題(根據讀者回憶整理)：

1、魔術定義：整數N以基數B表示，如21以基數3表示為210，那麼21是基數3的一個魔術，210三個位的值都不一樣。設計函式，輸入引數N和B(B介於2到10之間)，返回是否為魔術。

2、斐波那契數列的變形，一個賊每次上樓梯1或者2，一個27層的樓梯需要多少種方法，記住賊不能經過5,8,13層，否則會被抓住。點評：還是可以用斐波那契來推算，f(n) = f(n-1) + f(n-2)，只是f(5) f(8) f(13) = 0，http://www.51nod.com/answer/#!answerId=596。

3、給定一棵樹根節點，每個節點裡面的值都不相同，查詢iKEY的節點，並使用一個給定的節點將查詢到的節點替換掉。節點內有兩個孩子節點和一個父節點。

4、字串陣列S，全是0和1表示的，字串都是n位的，且1的個數小於等於l，返回index的字串。(這個比較奇怪，如果S中字串都是符合1的個數小於等於l，則直接可以得到index的字串啊，難道是要先求這個字串陣列?那就比較麻煩了)

5、降序排列的陣列，找到其中兩個不同的值，其乘積最接近一個給定的值M，感覺和加法求和很類似。

6、序列123...N，N介於3和9之間，在其中加入+-或者空格，使其和為0，

如123456 1-2 3-4 5+6 7 等價於1-23-45+67=0。請問，如何獲得所有組合?

10月12日，大眾點評筆試一題：

讀者私信，昨日(12號)美團的筆試題：

1、一副撲克52張(去了大小王)，洗牌，求最頂一張和最底一張是A的機率

2、知道兩個數的異或以及這兩個數的和，問可以確定這對數嗎?為什麼?給出推理過程

3、A、B兩個檔案各存50億個商品名稱，每個50個字元，求這兩個檔案中相同名稱的商品名，記憶體限制4G(看過您的《教你如何迅速秒殺掉：99%的海量資料處理面試題》中的第6題，無壓力，非常感謝)

4、給一個二叉樹的後序遍歷和中序遍歷，畫出這顆二叉樹，寫出前序遍歷結果，並給出推理過程

5、一個有序陣列array，給一個數x，可重複，求這個數在array中出現的區間，演算法思路和程式碼實現

6、一個對映檔案中存了ip地址區間和城市名稱，形如：

10.0.0.1 10.0.1.27 北京

10.0.2.1 10.0.2.27 北京

201.0.1.12 201.0.2.124 上海

給你一個ip地址，獲取城市名稱，要求：1)給出演算法思想 2)程式碼實現。

10月12日晚，360 2013校招部分筆試題(注：圖中所標答案不代表正確答案)：

int main()

{

fork()||fork();

return 0;

}

問，上述程式建立了幾個程序?

程式設計題、傳教士人數m，野人c，m≥c，開始都在岸左邊，

①船隻能載兩人，傳教士和野人都會划船，當然必須有人划船

②兩岸邊保證野人人數不能大於傳教士人數

把所有人都送過河，設計一方案，要求程式設計實現。

點評：

讀者huangxy10於本文評論下第169樓提供了一種解法：http://blog.csdn.net/huangxy10/article/details/8066408。再附一個討論帖子：http://topic.csdn.net/u/20121012/22/70226713-A669-4F03-80B7-BFFF12A330EB.html。

10月13日，百度2013校招北京站筆試題：

一、簡答題(30分)

1、用簡單語句描述資料庫操作的步驟

2、寫出TCP/IP的四層結構

3、什麼是MVC結構，並描述各層結構的作用

二、演算法與程式設計題(40分)

1、字母a-z，數字0-9，現需要其中任意3個作為密碼，請輸出所有可能組合。(偽碼CC++JAVA)(10分)

點評：如本文評論下第198樓所述，即從26+10=36個不同字元中選取3個字元的組合，用遞迴及非遞迴兩種方法，可以參照以下連結：

http://blog.csdn.net/wumuzi520/article/details/8087501(從n個數中選取m個數的組合數)，主要程式碼如下：

//copyright @wumuzi520

//從n個數中選取m個數的組合數

void Combination(int arr[], int nLen, int m, int out[], int outLen)

{

if(m == 0)

{

for (int j = 0; j < outLen; j++)

{

cout << out[j] << " ";

}

cout << endl;

return;

}

for (int i = nLen; i >= m; --i) //從後往前依次選定一個

{

out[m-1] = arr[i-1]; //選定一個後

Combination(arr,i-1,m-1,out,outLen); // 從前i-1個裡面選取m-1個進行遞迴

}

void PrintCombination(int arr[], int nLen, int m)

{

int* out = new int[m];

Combination(arr,nLen,m,out,m);

[] out;

}

2、實現字串反轉函式(10分)

3、給定字元函式a、插入 b、刪除 c、替換

例如字串A=acegf，字串B=adef，最少需要2步操作將A轉換為B，

即第一步將c替換為d，第二步將g刪除;

(1)請問將字串A=gumbo轉換為字串B=gambol，最少需要幾步操作，列出如何操作(2分)

(2)任意字串A和字串B，如何計算最小操作次數，計算思路，並給出遞迴公式(3分)

(3)實現程式碼(注意程式碼風格與效率)(15分)

點評：請參看上文第38題第4小題：9月26日，百度一二面試題。

三、系統設計題(30分)

RSA SecurID安全系統

應用場景：這是一種使用者登入驗證手段，例如銀行登入系統，這個裝置顯示6位數字，每60秒變一次，再經過伺服器認證，透過則允許登入。問How to design this system?

1)系統設計思路?伺服器端為何能有效認證動態密碼的正確性?

2)如果是千萬量級永固，給出系統設計圖示或說明，要求子功能模組劃分清晰，給出關鍵的資料結構或資料庫表結構。

考慮使用者量級的影響和擴充套件性，使用者密碼的隨機性等，如果設計系統以支援這幾個因素.

3)系統演算法升級時，伺服器端和裝置端可能都要有所修改，如何設計系統，能夠使得升級過程(包括可能的裝置替換或重設)儘量平滑?

10月13日，百度移動開發筆試題

一、 1、什麼是RISC;

2、通過後序、中xu求前序

3、重寫與過載的區別

二、

1、反轉連結串列

2、判斷兩個陣列中是否有相同的數字

3、1000瓶水中找出有毒的那瓶，毒性一週後發作，一週內最少需要多少隻老鼠

三、系統設計 email客戶端，支援多賬戶和pop3等協議

1、請寫出可能的至少5個用例;

2、使用sqlite儲存帳戶、已收資訊、已發信息、附件、草稿，請設計合理的表結構

3、pop3等協議等介面已完成，請給出email客戶端的模組設計圖。

10月13日，人搜2013 校招北京站部分筆試題(讀者回憶+照片)：

1，二重歌德巴赫猜想

所有大於等於6的偶數都可以表示成兩個(奇)素數之和。

給定1-10000，找到可以用兩個素數之和表示每一個偶數的兩個素數，然後輸出這兩個素數，如果有多對，則只需要輸出其中之一對即可。

要求：複雜度較低，程式碼可執行。

2，城市遍歷

某人家住北京，想去青海玩，可能會經過許多城市，

現已知地圖上的城市連線，求經過M個城市到達青海的路線種類。

城市可以多次到達的，比如去了天津又回到北京，再去天津，即為3次。北京出發不算1次。

輸入：

N M S

N為城市總數，北京為0，青海為N-1;

M為經過的城市數目;

S為之後有S行

i j

表示第i個城市可以去第j個城市，是有方向的。

輸出：

表示路徑種類。

3，分散式系統設計

有1000億個URL，其中大約有5億個site。每天的更新大約2%-5%。設計一個系統來解決儲存和計算下面三個問題。可用分散式系統。

URL：http///site[port]*(key==?;key==?)

site:

.domain

URL：http://www.baidu.com/baidu?word=%E5%AE%A3%E8%AE%B2%E4%BC%9A&ie=utf-8

site：：www.baidu.com

domain：：baidu.com

key=baidu?word

a>檢測每個域名下的site數目，以及每個site下的URL數目，輸出site變化超過一定閾值的域名以及URL數目變化劇烈的site。找出泛域。

泛域：該域下的site數目超過500個，且每個site下的URL數目超過100個。

b>提取URL中key的特徵，對site進行聚類;

(每個site下面有多個URL，這些URL中有許多key，可以獲取這些key作為site的特徵，對site進行聚類，不過這應該是多機器聯合的)

c>對於給定的domain，輸出該domain下的所有site。

10月13日，創新工場筆試：

第一個，快排最壞情況下是O(n^2)，問如何最佳化?

第二個，怎麼樣求一個數的根號

點評：你是不是會想到一系列有關數學的東西，什麼泰勒級數啊，什麼牛頓法啊，具體程式設計可以如下程式碼所示：

static void Main(string[] args)

{

double k = 5;

double n = 2, m = k;

while (n != m)

{

m = k / n;

n = (m + n) / 2;

}

連結：http://www.51nod.com/question/#!questionId=660。

第三個，4個數字，用四則元素求結果能否為24。寫出這個判斷的函式。

10月14日，思科網訊旗下公司筆試題：

1、海量資料中，尋找最小的k個數。

請分情況，給出時間複雜度最優，或空間複雜度最優的方案，或時間複雜度/空間複雜度綜合考慮的可行方案。

點評：參見：第三章、尋找最小的k個數。

2、有兩座橋，其中一座可能是壞的，兩個守橋人分別守在這兩座橋的入口。他們一個總是會說實話，一個總是說謊話。

你現在需要找出哪一座橋可以透過。

1)，請問最少需要問守橋人幾個問題，可以找出可以透過的橋?如何問?

2)，請程式設計解決。

10月14日，騰訊杭州站筆試題：

1、http伺服器會在使用者訪問某一個檔案的時候，記錄下該檔案被訪問的日誌，網站管理員都會去統計每天每檔案被訪問的次數。寫一個小程式，來遍歷整個日誌檔案，計算出每個檔案被訪問的訪問次數

1)請問這個管理員設計這個演算法

2)該網站管理員後來加入騰訊從事運維工作，在騰訊，單臺http伺服器不夠用的，同樣的內容，會分佈在全國各地上百臺伺服器上。每臺伺服器上的日誌數量，都是之前的10倍之多，每天伺服器的效能更好，之前他用的是單核cpu，現在用的是8核的，管理員發現在這種的海量的分散式伺服器，基本沒法使用了，請重新設計一個演算法。

2、騰訊的qq遊戲當中，最多人玩的遊戲就是鬥地主了，每一句遊戲開始時，服務器端都要洗牌，以保證發牌的時每個人拿的牌都是隨機的，假設用1-54來表示54 張不同的拍，請你寫一個洗牌演算法，保證54張牌能隨機打散!

選擇題：

1)、下列RAID技術無法提高可靠性的是：

A：RAID0 B：RAID1 C：RAID10 D：RAID5

2)、長度為1的線段，隨機在其上選擇兩點，將線段分為三段，問這3個欄位能組成一個三角形的機率是：

1/2,1/3,1/4,1/8

3)、下面那種標記的包不會在三次握手的過程中出現()

A：SYN B：PSH C：ACK D:RST

10月14日，搜狗2013 校招筆試題：

1、有n*n個格子，每個格子裡有正數或者0，從最左上角往最右下角走，只能向下和向右，一共走兩次(即從左下角走到右下角走兩趟)，把所有經過的格子的數加起來，求最大值SUM，且兩次如果經過同一個格子，則最後總和SUM中該格子的計數只加一次。

點評：@西芹_new，一共搜(2n-2)步，每一步有四種走法，考慮不相交等條件可以剪去很多枝，程式碼如下「http://blog.csdn.net/huangxy10/article/details/8071242」：

西芹_new0:55:40

// 10_15.cpp : 定義控制檯應用程式的入口點。

#include "stdafx.h"

#include

using namespace std;

#define N 5

int map[5][5]={

{2,0,8,0,2},

{0,0,0,0,0},

{0,3,2,0,0},

{0,0,0,0,0},

{2,0,8,0,2}};

int sumMax=0;

int p1x=0;

int p1y=0;

int p2x=0;

int p2y=0;

int curMax=0;

void dfs( int index){

if( index == 2*N-2){

if( curMax>sumMax)

sumMax = curMax;

return;

}

if( !(p1x==0 && p1y==0) && !(p2x==N-1 && p2y==N-1))

{

if( p1x>= p2x && p1y >= p2y )

return;

}

//right right

if( p1x+1<n p="" ){<="" p2x+1

p1x++;p2x++;

int sum = map[p1x][p1y]+map[p2x][p2y];

curMax += sum;

dfs(index+1);

curMax -= sum;

p1x--;p2x--;

}

//down down

if( p1y+1<n p="" ){<="" &&="" p2y+1

p1y++;p2y++;

int sum = map[p1x][p1y]+map[p2x][p2y];

curMax += sum;

dfs(index+1);

curMax -= sum;

p1y--;p2y--;

}

//rd

if( p1x+1<n p="" &&="" p2y+1<n="" {<="">

p1x++;p2y++;

int sum = map[p1x][p1y]+map[p2x][p2y];

curMax += sum;

dfs(index+1);

curMax -= sum;

p1x--;p2y--;

}

//dr

if( p1y+1<n p="" p2x+1<n="" &&="" {<="">

p1y++;p2x++;

int sum = map[p1x][p1y]+map[p2x][p2y];

curMax += sum;

dfs(index+1);

curMax -= sum;

p1y--;p2x--;

}

int _tmain(int argc, _TCHAR* argv[])

{

curMax = map[0][0];

dfs(0);

cout <<summax-map[n-1][n-1]<<endl;< p="">

return 0;

}

@綠色夾克衫：跟這個問題：http://www.51nod.com/question/#!questionId=487 ，是同一個問題。

1、用動態規劃可以求解，大概思路就是同時DP 2次所走的狀態。先來分析一下這個問題，為了方便討論，先對矩陣做一個編號，且以5*5的矩陣為例(給這個矩陣起個名字叫M1)：

0 1 2 3 4

1 2 3 4 5

2 3 4 5 6

3 4 5 6 7

4 5 6 7 8

從左上(0)走到右下(8)共需要走8步(2*5-2)。為了方便討論，我們設所走的步數為s。因為限定了只能向右和向下走，因此無論如何走，經過8步後(s = 8)都將走到右下。而DP的狀態也是依據所走的步數來記錄的。

再來分析一下經過其他s步後所處的位置，根據上面的討論，可以知道經過8步後，一定處於右下角(8)，那麼經過5步後(s = 5)，肯定會處於編號為5的位置。3步後肯定處於編號為3的位置......。s = 4的時候，處於編號為4的位置，對於方格中，共有5(相當於n)個不同的位置，也是所有編號中最多的。推廣來說n*n的方格，總共需要走2n - 2步，當s = n - 1時，編號為n個，也是編號最多的。

如果用DP[s,i,j]來記錄2次所走的狀態獲得的最大值，其中s表示走s步，i表示s步後第1次走所處的位置，j表示s步後第2次走所處的位置。

為了方便討論，再對矩陣做一個編號(給這個矩陣起個名字叫M2)：

0 0 0 0 0

1 1 1 1 1

2 2 2 2 2

3 3 3 3 3

4 4 4 4 4

0 1 2 3 4

1 2 3 4 5

2 3 4 5 6

3 4 5 6 7

4 5 6 7 8

經過6步後，肯定處於M1中編號為6的位置。共有3個編號為6的，分別對應M2中的2 3 4。假設第1次經過6步走到了M2中的2，第2次經過6步走到了M2中的4，DP[s,i,j] 則對應 DP[6,2,4]。由於s = 2n - 2,0 <= i<= <= j <= n，所以這個DP共有O(n^3)個狀態。

0 1 2 3 4

1 2 3 4 5

2 3 4 5 6

3 4 5 6 7

4 5 6 7 8

再來分析一下狀態轉移，以DP[6,2,3]為例(就是上面M1中加粗的部分)，可以到達DP[6,2,3]的狀態包括DP[5,1,2]，DP[5,1,3]，DP[5,2,2]，DP[5,2,3]，加粗表示位置DP[5,1,2] DP[5,1,3] DP[5,2,2] DP[5,2,3] (加紅表示要達到的狀態DP[6,2,3])

0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4

1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5

2 3 4 5 6 2 3 4 5 6 2 3 4 5 6 2 3 4 5 6

3 4 5 6 7 3 4 5 6 7 3 4 5 6 7 3 4 5 6 7

4 5 6 7 8 4 5 6 7 8 4 5 6 7 8 4 5 6 7 8

因此，DP[6,2,3] = Max(DP[5,1,2] ，DP[5,1,3]，DP[5,2,2]，DP[5,2,3]) + 6,2和6,3格子中對應的數值 (式一)

2、上面(式一)所示的這個遞推看起來沒有涉及：“如果兩次經過同一個格子，那麼該數只加一次的這個條件”，討論這個條件需要換一個例子，以DP[6,2,2]為例。

DP[6,2,2]可以由DP[5,1,1]，DP[5,1,2]，DP[5,2,2]到達，但由於i = j，也就是2次走到同一個格子，那麼數值只能加1次。

所以當i = j時，DP[6,2,2] = Max(DP[5,1,1]，DP[5,1,2]，DP[5,2,2]) + 6,2格子中對應的數值 (式二)

3、故，綜合上述的(式一)，(式二)最後的遞推式就是

if(i != j)

DP[s, i ,j] = Max(DP[s - 1, i - 1, j - 1], DP[s - 1, i - 1, j], DP[s - 1, i, j - 1], DP[s - 1, i, j]) + W[s,i] + W[s,j]

else

DP[s, i ,j] = Max(DP[s - 1, i - 1, j - 1], DP[s - 1, i - 1, j], DP[s - 1, i, j]) + W[s,i]

其中W[s,i]表示經過s步後，處於i位置，位置i對應的方格中的數字。

複雜度分析：狀態轉移最多需要統計4個變數的情況，看做是O(1)的。共有O(n^3)個狀態，所以總的時間複雜度是O(n^3)的。空間上可以利用滾動陣列最佳化，由於每一步的遞推只跟上1步的情況有關，因此可以迴圈利用陣列，將空間複雜度降為O(n^2)。

OK，上述這個方法可能不算最優解法，但相對比較容易想一些。希望大家能夠提供更好的想法，也歡迎大家補充程式。連結：http://www.51nod.com/answer/#!answerId=598。

2、N個整數(數的大小為0-255)的序列，把它們加密為K個整數(數的大小為0-255).再將K個整數順序隨機打亂，使得可以從這亂序的K個整數中解碼出原序列。設計加密解密演算法,且要求K<=15*N.

如果是：

1，N<=16,要求K<=16*N.

2，N<=16,要求K<=10*N.

3，N<=64,要求K<=15*N.

點評：http://www.51nod.com/question/#!questionId=659。

人人網面試，只面一道題，要求5分鐘出思路，10分鐘出程式碼

面試題是：

兩個無序陣列分別叫A和B，長度分別是m和n，求中位數，要求時間複雜度O(m+n)，空間複雜度O(1) 。

10月15日，網新恆天筆試題

1.不要使用庫函式，寫出void *memcpy(void *dst, const void *src, size_t count)，其中dst是目標地址，src是源地址。

點評：下面是nwpulei寫的程式碼：

void* memcpy(void *dst, const void *src, size_t count)

{

assert(dst != NULL);

assert(src != NULL);

unsigned char *pdst = (unsigned char *)dst;

const unsigned char *psrc = (const unsigned char *)src;

assert(!(psrc<=pdst && pdst<psrc+count));< p="">

assert(!(pdst<=psrc && psrc<pdst+count));< p="">

while(count--)

{

*pdst = *psrc;

pdst++;

psrc++;

}

return dst;

}

連結：http://blog.csdn.net/nwpulei/article/details/8090136。

2.給定一個字串，統計一下哪個字元出現次數最大。

3.我們不知道Object型別的變數裡面會出現什麼內容，請寫個函式把Object型別轉換為int型別。

10月15日，Google 2013 校招全套筆試題：

1.寫一個函式，輸出前N個素數，函式原型：void print_prime(int N); 不需要考慮整數的溢位問題，也不需要使用大數處理演算法。

2.長度為N的陣列亂序存放著0帶N-1.現在只能進行0與其他數的swap操作，請設計並實現排序，必須透過交換實現排序。

3.給定一個源串和目標串，能夠對源串進行如下操作：

1.在給定位置上插入一個字元

2.替換任意字元

3.刪除任意字元

寫一個程式，返回最小運算元，使得對源串進行這些操作後等於目標串，源串和目標串的長度都小於2000。

點評：

1、此題反覆出現，如上文第38題第4小題9月26日百度一二面試題，10月9日騰訊面試題第1小題，及上面第69題10月13日百度2013校招北京站筆試題第二大道題第3小題，同時，還可以看下這個連結：http://www.51nod.com/question/#!questionId=662。

//動態規劃：

//f[i,j]表示s[0...i]與t[0...j]的最小編輯距離。

f[i,j] = min { f[i-1,j]+1, f[i,j-1]+1, f[i-1,j-1]+(s[i]==t[j]?0:1) }

//分別表示：新增1個，刪除1個，替換1個(相同就不用替換)。

2、補充：上述問題類似於程式設計之美上的下述一題「以下內容摘自程式設計之美第3.3節」：

許多程式會大量使用字串。對於不同的字串，我們希望能夠有辦法判斷其相似程度。我們定義了一套操作方法來把兩個不相同的字串變得相同，具體的操作方法為：

1. 修改一個字元(如把“a”替換為“b”);

2. 增加一個字元(如把“abdd ”變為“aebdd ”);

3. 刪除一個字元(如把“travelling”變為“traveling”)。

比如，對於“abcdefg”和“abcdef ”兩個字串來說，我們認為可以透過增加/減少一個“g”的方式來達到目的。上面的兩種方案，都僅需要一次操作。把這個操作所需要的次數定義為兩個字串的距離，而相似度等於“距離+1”的倒數。也就是說，“abcdefg”和“abcdef”的距離為1，相似度為1 / 2 = 0.5。

給定任意兩個字串，你是否能寫出一個演算法來計算出它們的相似度呢?

這樣，很快就可以完成一個遞迴程式，如下所示：

Int CalculateStringDistance(string strA, int pABegin, int pAEnd,

string strB, int pBBegin, int pBEnd)

{

if(pABegin > pAEnd)

{

if(pBBegin > pBEnd)

return 0;

else

return pBEnd – pBBegin + 1;

}

if(pBBegin > pBEnd)

{

if(pABegin > pAEnd)

return 0;

else

return pAEnd – pABegin + 1;

}

if(strA[pABegin] == strB[pBBegin])

{

return CalculateStringDistance(strA, pABegin + 1, pAEnd,

strB, pBBegin + 1, pBEnd);

}

else

{

int t1 = CalculateStringDistance(strA, pABegin, pAEnd, strB,

pBBegin + 1, pBEnd);

int t2 = CalculateStringDistance(strA, pABegin + 1, pAEnd,

strB,pBBegin, pBEnd);

int t3 = CalculateStringDistance(strA, pABegin + 1, pAEnd,

strB,pBBegin + 1, pBEnd);

return minValue(t1,t2,t3) + 1;

}

上面的遞迴程式，有什麼地方需要改進呢?在遞迴的過程中，有些資料被重複計算了。比如，如果開始我們呼叫CalculateStringDistance(strA,1, 2, strB, 1, 2)，下圖是部分展開的遞迴呼叫。

可以看到，圈中的兩個子問題被重複計算了。為了避免這種不必要的重複計算，可以把子問題計算後的解儲存起來。如何修改遞迴程式呢?還是DP!請看此連結：http://www.cnblogs.com/yujunyong/articles/2004724.html。

3、此外，關於這個“編輯距離”問題的應用：搜尋引擎關鍵字查詢中拼寫錯誤的提示，可以看下這篇文章：http://www.ruanyifeng.com/blog/2012/10/spelling_corrector.html。「關於什麼是“編輯距離”：一個快速、高效的Levenshtein演算法實現，這個是計算兩個字串的演算法，Levenshtein距離又稱為“編輯距離”，是指兩個字串之間，由一個轉換成另一個所需的最少編輯操作次數。當然，次數越小越相似。這裡有一個BT樹的資料結構，挺有意思的：http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees」

最後，Lucene中也有這個演算法的實現(我想，一般的搜尋引擎一般都應該會有此項拼寫錯誤檢查功能的實現)：http://www.bjwilly.com/archives/395.html。

4、擴充套件：面試官還可以繼續問下去：那麼，請問，如何設計一個比較兩篇文章相似性的演算法?(這個問題的討論可以看看這裡：http://t.cn/zl82CAH)

BTW，群友braveheart89也整理了這套筆試題：http://blog.csdn.net/braveheart89/article/details/8074657。

10月16日，UC的筆試題目：

1、有個長度為2n的陣列{a1,a2,a3,...,an,b1,b2,b3,...,bn}，希望排序後{a1,b1,a2,b2,....,an,bn}，要求時間複雜度o(n),空間複雜度0(1)。

點評：@綠色夾克衫：完美洗牌問題「關於洗牌演算法：http://blog.csdn.net/gogdizzy/article/details/4917488」，解決這個問題的關鍵在於如何解決置換群中的環。方法是微軟員工那篇論文中寫的：http://user.qzone.qq.com/414353346/blog/1243343118#!app=2&via=QZ.HashRefresh&pos=1243343118，大概意思是，用3的冪來弄：

@方程：

int index = arr.length / 2;

int temp = arr[index];

while(index != 1){

int tempIndex = (index + (index % 2) * (arr.length - 1)) / 2;

arr[index] = arr[tempIndex];

index = tempIndex;

}

arr[1] = temp;

連結：1，http://www.51nod.com/question/#!questionId=278;2、這裡也有一參考答案：http://blog.csdn.net/yuan8080/article/details/5705567。

10月17日，創新工場電話面試：

1，如何刪除一個搜尋二叉樹的結點;

2，如何找到一個數組中的兩個數，他們的和為0;

3，如何判斷兩條二維平面上的線段是否相交。

網易2013 校招筆試題：

10月19日，百度研發三面題：

百度地圖裡的路線查詢：給定兩個站點，如果沒有直達的路線，如何找到換乘次數最少的路線?

點評：螞蟻演算法?還是廣搜，或A*演算法?

10月20日，baidu廣州站筆試演算法題：

1. 有一箱蘋果，3個一包還剩2個，5個一包還剩3個，7個一包還剩2個，求N個滿足以上條件的蘋果個數。

2. 用遞迴演算法寫一個函式，求字串最長連續字元的長度，比如aaaabbcc的長度為4，aabb的長度為2，ab的長度為1。

3. 假設一個大小為100億個資料的陣列，該陣列是從小到大排好序的，現在該陣列分成若干段，每個段的資料長度小於20「也就是說：題目並沒有說每段資料的size 相同，只是說每個段的 size < 20 而已」，然後將每段的資料進行亂序(即：段內資料亂序)，形成一個新陣列。請寫一個演算法，將所有資料從小到大進行排序，並說明時間複雜度。

點評：

思路一、如@四萬萬網友所說：維護一個20個元素大小的小根堆，然後排序，每次pop取出小根堆上最小的一個元素(log20)，然後繼續遍歷原始陣列後續的(N-20)個元素，總共pop (N-20)次20個元素小根堆的log20的調整操作。

思路二@飄零蝦、如果原陣列是a[]，那麼a[i+20]>=a[i]恆成立(因為每段亂序區間都是小於20的，那麼向後取20，必然是更大的區間的元素)。

第一個陣列：取第0、20、40、60、80...

第二個陣列：取第1、21、41、61、81...

...

第20個數組：取第19、39、59、79... (上述每個陣列100億/20 個元素)

共計20個數組，每個陣列100億/20 個元素「注：這5億個元素已經有序，不需要再排序」，且這20個數組都是有序的，然後對這20個數組進行歸併，每次歸併20個元素。時間複雜度跟上述思路一一樣，也是N*logK(N=100億，K=20)。

此外，讀者@木葉漂舟直接按每組20個排序,將排好的20個與前20個調整拼接,調整兩端接頭處的元素,寫了個簡單地demo： http://t.cn/zlELAzs。不過，複雜度有點高，目前來說中規中矩的思路還是如上文中@四萬萬網友所說思路一「@張瑋-marihees按照思路一：http://weibo.com/1580904460/z1v5jxJ9P，寫了一份程式碼：http://codepad.org/T5jIUFPG，歡迎檢視」。

10月21日，完美筆試演算法題「同時，祝自己生日快樂!」：

1. 請設計一個演算法，當給出在2D平面中某個三角形ABC的頂點座標時能輸出位於該三角形內的一個隨機點(需要滿足三角形內均勻隨機)，無需寫出實現，只要能清楚地描述演算法即可。

2. 請自己用雙向連結串列實現一個佇列，佇列裡節點記憶體的值為int，要求實現入隊，出隊和查詢指定節點的三個功能。

3. 實現一個無符號任意大整數的類，實現兩個無符號超大整數的乘法。

10月22日，CSR掌微電子筆試題：

5.給定兩個字串s1和s2，要求判定s2是否能夠被透過s1做迴圈移位(rotate)得到字串包含。例如，S1=AABCD和s2=CDAA，返回true;給定s1=ABCD和s2=ACBD，返回false。用虛擬碼或流程圖敘述解法。

點評：老題，類似：http://blog.csdn.net/v_JULY_v/article/details/6322882。其餘題目見：http://blog.sina.com.cn/s/blog_3eb9f72801016llt.html。

10月23日，去哪兒網筆試：

1.將IPV4轉換成整數

2.定義一個棧的資料結構，實現min函式，要求push,pop,min時間複雜度是0(1);

點評：這是2010年整理的微軟100題的第2題，http://blog.csdn.net/v_JULY_v/article/details/6057286，答案見此文第2題：http://blog.csdn.net/v_JULY_v/article/details/6126406。

3.陣列a[n]裡存有1到n的所有樹，除了一個數removed，找出這個missing的樹。

4.找出字串中的最長子串，要求子串不含重複字元，並分析時間複雜度。

10月28日，微軟三面題「順祝，老媽明天生日快樂!」：

找一個點集中與給定點距離最近的點，同時，給定的二維點集都是固定的，查詢可能有很多次，時間複雜度O(n)無法接受，請設計資料結構和相應的演算法。

類似於@陳利人：附近地點搜尋，就是搜尋使用者附近有哪些地點。隨著GPS和帶有GPS功能的移動裝置的普及，附近地點搜尋也變得炙手可熱。在龐大的地理資料庫中搜索地點，索引是很重要的。但是，我們的需求是搜尋附近地點，例如，座標(39.91, 116.37)附近500米內有什麼餐館，那麼讓你來設計，該怎麼做?

點評：我看到這道題的時候，除了想到用R樹「從B樹、B+樹、B*樹談到R 樹」解決這個問題之外，還想起了之前一直要寫的KD樹仍未寫，但估計快要寫了，請讀者朋友們耐心等待些時日吧。

11月10日，百度筆試題：

1、20個排序好的陣列，每個陣列500個數，按照降序排序好的，讓找出500個最大的數。

2、一線上推送服務，同時為10萬個使用者提供服務，對於每個使用者服務從10萬首歌的曲庫中為他們隨機選擇一首，同一使用者不能推送重複的，設計方案，記憶體儘可能小，寫出資料結構與演算法。

【網際網路開發面試題】相關文章：