- 相關推薦
互聯網開發面試題
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+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日，暴風影音筆試：
都是非�；A的題目，這是其中一道：一個整數轉換成二進制后，問里面有多少個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
cout << B
cout << B
cout << B
cout << B
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塊錢的購物卡，兩人就想出一個辦法來分配這張卡。兩個分別將自己出的價格寫在紙上，然后看誰出的價高就給誰，并且那個出價高的人要把出的錢給對方�，F在甲有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個城市，是有方向的。
輸出：
N
表示路徑種類。
3，分布式系統設計
有1000億個URL，其中大約有5億個site。每天的更新大約2%-5%。設計一個系統來解決存儲和計算下面三個問題�？捎梅植际较到y。
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」：
西芹_new
// 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)：
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)：
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
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
經過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)個狀態。
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
再來分析一下狀態轉移，以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)的�？臻g上可以利用滾動數組優化，由于每一步的遞推只跟上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萬首歌的曲庫中為他們隨機選擇一首，同一用戶不能推送重復的，設計方案，內存盡可能小，寫出數據結構與算法。
【互聯網開發面試題】相關文章：
互聯網公司面試題總結07-12
web前端開發面試題07-12
我遇到的互聯網公司的面試題07-12
JAVA開發工程師面試題07-13
互聯網產品開發流程標準文檔07-10
單片機開發工程師面試題07-11
Google Android 開發工程師職位面試題07-13
關于互聯網新產品設計開發流程07-10
互聯網軟件應用與開發復習資料07-01
知名互聯網公司系統工程師面試題07-12