- 相關(guān)推薦
互聯(lián)網(wǎng)開發(fā)面試題
1一共有100萬，抽中的2萬，每月增加4萬，問20個月能抽中的概率為：?
2 for(int i=0;i<strlen(s);i++){n+=i;}時間復(fù)雜度o(n)< p="">
3 手機wifi(A)….wifi ap….局域網(wǎng)(B)…..路由器…ADSL(C)…..互聯(lián)網(wǎng)…..服務(wù)器
斷掉上述ABC哪些點TCP鏈接會立刻斷掉?
4 12345入棧，出棧結(jié)果 21543 31245 43215 12534 可能的為?(第一個和第三個)
5 x^n+a1x^n-1+…+an-1x+an,最少要做—乘法?題目中a1，a2，an為常數(shù)。
9月26日，百度一二面：
1、給定一數(shù)組，輸出滿足2a=b(a，b代表數(shù)組中的數(shù))的數(shù)對，要求時間復(fù)雜度盡量低。
2、搜索引擎多線程中每個線程占用多少內(nèi)存?如果搜索引擎存儲網(wǎng)頁內(nèi)存占用太大怎么解決?
3、有很多url，例如*.baidu.com，*.sina.com ......
現(xiàn)在給你一個sports.sina.com 快速匹配出是*.sina.com。點評：老題，此前blog內(nèi)曾整理過。
4、找出字符串的編輯距離，即把一個字符串s1最少經(jīng)過多少步操作變成編程字符串s2，操作有三種，添加一個字符，刪除一個字符，修改一個字符(只要聽過編輯距離，知道往動態(tài)規(guī)劃上想，很快就可以找到解法)。
點評：請看鏈接：http://blog.csdn.net/Lost_Painting/article/details/6457334。
5、編程實現(xiàn)memcopy，注意考慮目標內(nèi)存空間和源空間重疊的時候。
6、實現(xiàn)簡單的一個查找二叉樹的深度的函數(shù)。
9月26日晚，優(yōu)酷土豆筆試題一道：
優(yōu)酷是一家視頻網(wǎng)站，每天有上億的視頻被觀看，現(xiàn)在公司要請研發(fā)人員找出最熱門的視頻。
該問題的輸入可以簡化為一個字符串文件，每一行都表示一個視頻id，然后要找出出現(xiàn)次數(shù)最多的前100個視頻id，將其輸出，同時輸出該視頻的出現(xiàn)次數(shù)。
1.假設(shè)每天的視頻播放次數(shù)為3億次，被觀看的視頻數(shù)量為一百萬個，每個視頻ID的長度為20字節(jié)，限定使用的內(nèi)存為1G。請簡述做法，再寫代碼。
2.假設(shè)每個月的視頻播放次數(shù)為100億次，被觀看的視頻數(shù)量為1億，每個視頻ID的長度為20字節(jié)，一臺機器被限定使用的內(nèi)存為1G。
點評：有關(guān)海量數(shù)據(jù)處理的題目，請到此文中找方法(無論題目形式怎么變，基本方法不變，當(dāng)然，最最常用的方法是：分而治之/Hash映射 + Hash統(tǒng)計 + 堆/快速/歸并排序)：http://blog.csdn.net/v_july_v/article/details/7382693。注：上題第二問文件太大，則可如模1000，把整個大文件映射為1000個小文件再處理 ....
9月26日，baidu面試題：
1.進程和線程的區(qū)別
2.一個有序數(shù)組(從小到大排列)，數(shù)組中的數(shù)據(jù)有正有負，求這個數(shù)組中的最小絕對值
3.鏈表倒數(shù)第n個元素
4.有一個函數(shù)fun能返回0和1兩個值，返回0和1的概率都是1/2，問怎么利用這個函數(shù)得到另一個函數(shù)fun2，使fun2也只能返回0和1，且返回0的概率為1/4,返回1的概率為3/4。(如果返回0的概率為0.3而返回1的概率為0.7呢)
5.有8個球，其中有7個球的質(zhì)量相同，另一個與其他球的質(zhì)量不同(且不知道是比其他球重還是輕)，請問在最壞的情況下，最少需要多少次就能找出這個不同質(zhì)量的球
6.數(shù)據(jù)庫索引
7.有一個數(shù)組a，設(shè)有一個值n。在數(shù)組中找到兩個元素a[i]和a[j]，使得a[i]+a[j]等于n，求出所有滿足以上條件的i和j。
8.1萬個元素的數(shù)組，90%的元素都是1到100的數(shù)，10%的元素是101--10000的數(shù)，如何高效排序。
小米的web開發(fā)筆試題：
一場星際爭霸比賽，共8個人，每個人的實力用分數(shù)表示，要分成兩隊，如何保證實力最平均?給定一個浮點數(shù)的序列，F(xiàn)1,F2,……，F(xiàn)n(1<=n<=1000),定義P(s,e)為子序列Fi(s<=i<=e)的積，求P的最大值。
9月27日，趨勢科技面試題：
馬路口，30分鐘內(nèi)看到汽車的概率是95%，那么在10分鐘內(nèi)看不到汽車的概率是?
9月27日晚，IGT筆試題：
給定一個字符串里面只有"R" "G" "B" 三個字符，請排序，最終結(jié)果的順序是R在前 G中 B在后。
要求：空間復(fù)雜度是O(1)，且只能遍歷一次字符串。
點評：本質(zhì)是荷蘭國旗問題，類似快排中partition過程，具體思路路分析及代碼可以參考此文第8節(jié)：http://blog.csdn.net/v_july_v/article/details/6211155。
9月27日，人人兩面：
一面
1 實現(xiàn)atoi
2 單鏈表變形 如 1 2 3 4 5 變?yōu)?1 3 5 4 2 如1 2 3 4 變?yōu)?1 3 4 2
(就是拆分鏈表 把偶數(shù)為反過來接在奇數(shù)位后面)
二面
1 二叉樹查找不嚴格小于一個值的最大值(返回節(jié)點)。
2 有序數(shù)組里二分查找一個數(shù)(如果有相同的找最后一次出現(xiàn)的)。
3 等價于n*n的矩陣，填寫0，1，要求每行每列的都有偶數(shù)個1 (沒有1也是偶數(shù)個)，問有多少種方法。
評論：開始以為是算法題，想了狂搜，遞推(dp，可以用xor表示一行的列狀態(tài)，累加),分治，(拆兩半，然后上半段下半段的列有相同的奇偶性)。后來，自己算了幾個發(fā)現(xiàn)n = 1 n = 2 n = 3 的結(jié)果，他告訴了我n = 4是多少，然后發(fā)現(xiàn)f(n) = 2^((n - 1) ^2) 。最后我給出了一個巧妙的證明。然后發(fā)現(xiàn)如果是m*n的矩陣也是類似的答案，不局限于方陣。此外，題目具體描述可以看看這里：http://blog.himdd.com/?p=2480。
9月27日，小米兩面：
一面：
除了聊研究，就一道題
1 數(shù)組里找到和最接近于0的兩個值。
二面：
1 行列有序的矩陣查找一個數(shù)
2 直方圖最大矩形。點評：這里有此題的具體表述及一份答案：http://blog.csdn.net/xybsos/article/details/8049048。
3 next_permutation
4 字符串匹配 含有* ? (寫代碼)
5 實現(xiàn)strcpy memmove (必須寫代碼)
//void * memmove ( void * destination, const void * source, size_t num );)
//是
//最簡單的方法是直接復(fù)制，但是由于它們可能存在內(nèi)存的重疊區(qū)，因此可能覆蓋了原有數(shù)據(jù)。
//比如當(dāng)source+count>=dest&&source<dest時，dest可能覆蓋了原有source的數(shù)據(jù)。< 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;
}
更多，還可以參見此文第三節(jié)節(jié)末：http://blog.csdn.net/v_july_v/article/details/6417600，或此文:http://www.360doc.com/content/11/0317/09/6329704_101869559.shtml。
6 讀數(shù) (千萬億，百萬億……)變?yōu)閿?shù)字 (說思路即可，字符串查找，填寫各個權(quán)值的字段，然后判斷是否合法，讀前面那些×權(quán)值，累加)。
9月27日，Hulu 2013北京地區(qū)校招筆試題
填空題：
1、中序遍歷二叉樹，結(jié)果為ABCDEFGH，后序遍歷結(jié)果為ABEDCHGF，那么前序遍歷結(jié)果為?
2、對字符串HELL0_HULU中的字符進行二進制編碼，使得字符串的編碼長度盡可能短，最短長度為?
3、對長度12的有序數(shù)組進行二分查找，目標等概率出現(xiàn)在數(shù)組的每個位置上，則平均比較次數(shù)為?
4、一副撲克(去王)，每個人隨機的摸兩張，則至少需要多少人摸牌，才能保證有兩個人抽到同樣的花色。
5、x個小球中有唯一一個球較輕，用天平秤最少稱量y次能找出這個較輕的球，寫出y和x的函數(shù)表達式y(tǒng)=f(x)
6、3的方冪及不相等的3的方冪的和排列成遞增序列1,3,4,9,10,12,13……，寫出數(shù)列第300項
7、無向圖G有20條邊，有4個度為4的頂點，6個度為3的頂點，其余頂點度小于3，則G有多少個頂點
8、桶中有M個白球，小明每分鐘從桶中隨機取出一個球，涂成紅色(無論白或紅都涂紅)再放回，問小明將桶中球全部涂紅的期望時間是?
9、煤礦有3000噸煤要拿到市場上賣，有一輛火車可以用來運煤，火車最多能裝1000噸煤，且火車本身需要燒煤做動力，每走1公里消耗1噸煤，如何運煤才能使得運到市場的煤最多，最多是多少?
10、1,2,3,4…..n，n個數(shù)進棧，有多少種出棧順序，寫出遞推公式(寫出通項公式不得分)
11、宇宙飛船有100,000位的存儲空間，其中有一位有故障，現(xiàn)有一種Agent可以用來檢測故障，每個Agent可以同時測試任意個位數(shù)，若都沒有故障，則返回OK，若有一位有故障，則失去響應(yīng)。如果有無限多個Agent可供使用，每個Agent進行一次檢測需要耗費1小時，現(xiàn)在有2個小時時間去找出故障位，問最少使用多少個Agent就能找出故障。
(總共12道填空題，還有一道太復(fù)雜，題目很長，還有示意圖，這里沒有記錄下來)
大題：
1、n個數(shù)，找出其中最小的k個數(shù)，寫出代碼，要求最壞情況下的時間復(fù)雜度不能高于O(n logk)
2、寫程序輸出8皇后問題的所有排列，要求使用非遞歸的深度優(yōu)先遍歷
3、有n個作業(yè)，a1,a2…..an，作業(yè)aj的處理時間為tj，產(chǎn)生的效益為pj，最后完成期限為dj，作業(yè)一旦被調(diào)度則不能中斷，如果作業(yè)aj在dj前完成，則獲得效益pj，否則無效益。給出最大化效益的作業(yè)調(diào)度算法。點評：參考答案請看這個鏈接：http://www.51nod.com/question/#!questionId=645。
有道的一個筆試題，1-9，9個數(shù)組成三個三位數(shù)，且都是完全平方數(shù)(三個三位數(shù) 占據(jù) 9個數(shù))求解法。
點評@林晚楓&歸云見鴻：
(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循環(huán)，然后hash)：
9月28日，大眾點評北京筆試題目：
1.一個是跳臺階問題，可以1次一級，1次兩級，1次三級，求N級的跳法一共多少種?
點評：老題，參考答案請見：http://blog.csdn.net/v_july_v/article/details/6879101。
2.一個文件有N個單詞，每行一個，其中一個單詞出現(xiàn)的次數(shù)大于N/2，怎么樣才能快速找出這個單詞?
點評：還是老題，參見：http://blog.csdn.net/v_july_v/article/details/6890054。
大眾點評前面還有30道邏輯題，15道文字推理，15道數(shù)學(xué)推理，一共只給20min。
9月28日，網(wǎng)易筆試題：
1、英雄升級，從0級升到1級，概率100%。
從1級升到2級，有1/3的可能成功;1/3的可能停留原級;1/3的可能下降到0級;
從2級升到3級，有1/9的可能成功;4/9的可能停留原級;4/9的可能下降到1級。
每次升級要花費一個寶石，不管成功還是停留還是降級。
求英雄從0級升到3級平均花費的寶石數(shù)目。
點評：題目的意思是，從第n級升級到第n+1級成功的概率是(1/3)^n(指數(shù))，停留原級和降級的概率一樣，都為[1-(1/3)^n]/2)。
2、將一個很長的字符串，分割成一段一段的子字符串，子字符串都是回文字符串。
有回文字符串就輸出最長的，沒有回文就輸出一個一個的字符。
例如：
habbafgh
輸出h,abba,f,g,h。
點評：編程藝術(shù)第十五章有這個回文問題的解答，參見：http://blog.csdn.net/v_july_v/article/details/6712171。此外，一般的人會想到用后綴數(shù)組來解決這個問題，其余更多的方法請見：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表示退出
問：統(tǒng)計一天平均在線的QQ數(shù)。
點評：類似于此文中：http://blog.csdn.net/hackbuteer1/article/details/7348968，第8題后的騰訊面試題，讀者可以參看之。
10月9日，騰訊面試題：
1.有一億個數(shù)，輸入一個數(shù)，找出與它編輯距離在3以內(nèi)的書，比如輸入6(0110)，找出0010等數(shù)，數(shù)是32位的。
2.每個城市的IP段是固定的，新來一個IP，找出它是哪個城市的，設(shè)計一個后臺系統(tǒng)。
10月9日，YY筆試題：
1 輸出一個字符串中沒有重復(fù)的字符。如“baaca”輸出“bac”。
2 對于一個多叉樹，設(shè)計TreeNode節(jié)點和函數(shù)，返回先序遍歷情況下的下一個節(jié)點。
函數(shù)定義為TreeNode* NextNode(TreeNode* node)
3 分割字符串。
對于一個字符串，根據(jù)分隔符seperator，把字符串分割，如果存在多個分隔符連在一起，則當(dāng)做一個分隔符。如果分隔符出現(xiàn)在" "符號之間，則不需要分割" "之間的字符。
比如a++abc ，分隔符為+，輸出a abc
a+"hu+" 輸出a hu+
a++"HU+JI 輸出a "HU JI。
請根據(jù)上述需求完成函數(shù)：void spiltString(string aString，char aSeperator)。
10月9日，趕集網(wǎng)筆試
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，特此感謝。有任何問題，歡迎隨時討論&指正，同時，更歡迎其他朋友也一起來做這些題目(你的答案一經(jīng)選用，我可以根據(jù)你的要求，貼出你的個人主頁或微博地址或博客地址)。
19、已知一個n個元素的數(shù)組，第i個元素在排序后的位置在[i-k,i+k]區(qū)間，k<<n p="" (nlogn)不得分，o(nk)得2分，如下圖所示：<="" o="">
讀者twtsa毛遂自薦，這是他給出的上述第19~20題的個人題解：http://blog.csdn.net/twtsa/article/details/8055143。有任何問題，歡迎隨時討論&指正。
10月10日，暴風(fēng)影音筆試：
都是非常基礎(chǔ)的題目，這是其中一道：一個整數(shù)轉(zhuǎn)換成二進制后，問里面有多少個1。
10月10日，2013亞馬遜在線筆試題目
題目及參考答案請見這：http://blog.chinaunix.net/uid-26750075-id-3370694.html。(感謝讀者freeloki來信提供)。
10月10日人人網(wǎng)面試題
第一面：
1、(1)++i 和 i++，那個效率高?
(2)++++i，i++++，哪個是合法的?
(3)實現(xiàn)int型的++i 和 i++操作。
2、一段程序，求輸出。(考察靜態(tài)變量和模版類)
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)實現(xiàn)二進制轉(zhuǎn)十進制。
(2)如果有下面這種能直接求二進制轉(zhuǎn)十進制的代碼，是怎么實現(xiàn)的?
binary<1>::value; // 結(jié)果為1
binary<11>::value; // 結(jié)果為3
4、volatile、explicit、mutable表示的含義。
5、求整形數(shù)組的一個子數(shù)組，使得該子數(shù)組所有元素的和的絕對值最大。
6、(1)寫求單鏈表是否有環(huán)的算法。
(2)如果有環(huán)，如何找出環(huán)的第一個結(jié)點。
7、實現(xiàn)單例模式。
二面：
1、一個文本，一萬行，每行一個詞，統(tǒng)計出現(xiàn)頻率最高的前10個詞(詞的平均長度為Len)。并分析時間復(fù)雜度。
2、求數(shù)組中最長遞增子序列。
10月10日，網(wǎng)易2013校園招聘全套筆試題：
10月10日，網(wǎng)易，數(shù)據(jù)挖掘工程師：
1，簡述你對數(shù)據(jù)與處理的認識;
2，簡述你對中文分詞的理解，說明主要難點和常用算法;
3，常見的分類算法有哪些;
4，簡述K-MEANS算法;
5，設(shè)計一個智能的商品推薦系統(tǒng);
6，簡述你對觀點挖掘的認識。
點評：其它題目與上述第56題第一部分(http://blog.csdn.net/hackbuteer1/article/details/8060917)所述相同。
10月11日，阿里巴巴筆試部分題目：
1. 甲乙兩個人上街，撿到一張10塊錢的購物卡，兩人就想出一個辦法來分配這張卡。兩個分別將自己出的價格寫在紙上，然后看誰出的價高就給誰，并且那個出價高的人要把出的錢給對方。現(xiàn)在甲有6塊錢，乙有8塊錢。問誰獲得的錢多。(多選)
A 甲多 B 乙多 C 一樣多 D 有可能出現(xiàn)有人賠錢的情況
2. 有一個怪物流落到一個荒島上，荒島上有n條鱷魚。每條鱷魚都有實力單獨吃掉怪物。但是吃掉怪物是有風(fēng)險的，會造成體力值下降，然后會有可能被掉其他鱷魚吃。問，最后那個怪物是危險的還是安全的?
3. 算法題：
A[i]是一個有序遞增數(shù)組，其中所有的數(shù)字都不相等，請設(shè)計一種算法，求出其中所有的A[i]=i的數(shù)字并分析時間復(fù)雜度，不分析復(fù)雜度不得分。
4. 大題
你在瀏覽器中輸入網(wǎng)址：http://blog.csdn.net/v_JULY_v，按下回車鍵后，會發(fā)生什么事情，請一一描述(20分)。包括瀏覽器，網(wǎng)絡(luò)，服務(wù)器等等發(fā)生的事情，及各項關(guān)鍵技術(shù)。
點評：這樣的題考過很多次，參考答案如下圖所示：
10月11日，華為一面：
1、將一個普通的二叉樹轉(zhuǎn)換為二叉排序樹?
2、隨便寫一個排序算法。
10月11日，完美筆試題：
1.為什么析構(gòu)函數(shù)應(yīng)該設(shè)為虛函數(shù)
2.大數(shù)字乘法問題
3.雙向鏈表模擬隊列操作push pop find
4.求 a/3 不能用除法
5.多核下多線程同步問題，使用鎖應(yīng)該注意什么
6.三個寶箱有一個里面有珠寶，現(xiàn)在拿第一寶箱，然后打開第二個寶箱后發(fā)現(xiàn)沒有珠寶，用概率論原理解釋為什么現(xiàn)在拿第三個寶箱，里面有珠寶的概率比拿第一個寶箱高。
10月11日，搜狐暢游旗下第七大道筆試題：
算法題
1.一個數(shù)是否是另一個數(shù)的平方。
2.N進制換成M進制
3.設(shè)計一個大數(shù)乘法
綜合題
1.N個數(shù)，出棧有幾種情況
2.進程死鎖原因及條件.
騰迅一個非常有意思的面試題：
N個數(shù)組，每個數(shù)組中的元素都是遞增的順序，現(xiàn)在要找出這N個數(shù)組中的公共元素部分，如何做? 注：不能用額外輔助空間。
點評：
討論了半天：http://weibo.com/1580904460/z08mT0aFj，沒個好的結(jié)果，發(fā)現(xiàn)還是上午想到的N個指針逐步向后移動，輔以二分，然后N路歸并更靠譜，類似這里的第5題所述的辦法：http://www.cnblogs.com/BeyondAnyTime/archive/2012/07/17/2593224.html。若讀者有更好的思路，歡迎賜教。
10月12日，迅雷2013校園招聘「廣州站」C++方向全套筆試題
(注：若照片看不清楚，請右鍵點擊“圖片另存為”到桌面，然后再打開圖片，便可以隨意放大縮小圖片拉)
10月12日晚，微策略北京站筆試題(根據(jù)讀者回憶整理)：
1、魔術(shù)定義：整數(shù)N以基數(shù)B表示，如21以基數(shù)3表示為210，那么21是基數(shù)3的一個魔術(shù)，210三個位的值都不一樣。設(shè)計函數(shù)，輸入?yún)?shù)N和B(B介于2到10之間)，返回是否為魔術(shù)。
2、斐波那契數(shù)列的變形，一個賊每次上樓梯1或者2，一個27層的樓梯需要多少種方法，記住賊不能經(jīng)過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、給定一棵樹根節(jié)點，每個節(jié)點里面的值都不相同，查找iKEY的節(jié)點，并使用一個給定的節(jié)點將查找到的節(jié)點替換掉。節(jié)點內(nèi)有兩個孩子節(jié)點和一個父節(jié)點。
4、字符串?dāng)?shù)組S，全是0和1表示的，字符串都是n位的，且1的個數(shù)小于等于l，返回index的字符串。(這個比較奇怪，如果S中字符串都是符合1的個數(shù)小于等于l，則直接可以得到index的字符串啊，難道是要先求這個字符串?dāng)?shù)組?那就比較麻煩了)
5、降序排列的數(shù)組，找到其中兩個不同的值，其乘積最接近一個給定的值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、知道兩個數(shù)的異或以及這兩個數(shù)的和，問可以確定這對數(shù)嗎?為什么?給出推理過程
3、A、B兩個文件各存50億個商品名稱，每個50個字符，求這兩個文件中相同名稱的商品名，內(nèi)存限制4G(看過您的《教你如何迅速秒殺掉：99%的海量數(shù)據(jù)處理面試題》中的第6題，無壓力，非常感謝)
4、給一個二叉樹的后序遍歷和中序遍歷，畫出這顆二叉樹，寫出前序遍歷結(jié)果，并給出推理過程
5、一個有序數(shù)組array，給一個數(shù)x，可重復(fù)，求這個數(shù)在array中出現(xiàn)的區(qū)間，算法思路和代碼實現(xiàn)
6、一個映射文件中存了ip地址區(qū)間和城市名稱，形如：
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)代碼實現(xiàn)。
10月12日晚，360 2013校招部分筆試題(注：圖中所標答案不代表正確答案)：
int main()
{
fork()||fork();
return 0;
}
問，上述程序創(chuàng)建了幾個進程?
編程題、傳教士人數(shù)m，野人c，m≥c，開始都在岸左邊，
①船只能載兩人，傳教士和野人都會劃船，當(dāng)然必須有人劃船
②兩岸邊保證野人人數(shù)不能大于傳教士人數(shù)
把所有人都送過河，設(shè)計一方案，要求編程實現(xiàn)。
點評：
讀者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、用簡單語句描述數(shù)據(jù)庫操作的步驟
2、寫出TCP/IP的四層結(jié)構(gòu)
3、什么是MVC結(jié)構(gòu)，并描述各層結(jié)構(gòu)的作用
二、算法與程序設(shè)計題(40分)
1、字母a-z，數(shù)字0-9，現(xiàn)需要其中任意3個作為密碼，請輸出所有可能組合。(偽碼CC++JAVA)(10分)
點評：如本文評論下第198樓所述，即從26+10=36個不同字符中選取3個字符的組合，用遞歸及非遞歸兩種方法，可以參照以下鏈接：
http://blog.csdn.net/wumuzi520/article/details/8087501(從n個數(shù)中選取m個數(shù)的組合數(shù))，主要代碼如下：
//copyright @wumuzi520
//從n個數(shù)中選取m個數(shù)的組合數(shù)
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、實現(xiàn)字符串反轉(zhuǎn)函數(shù)(10分)
3、給定字符函數(shù)a、插入 b、刪除 c、替換
例如字符串A=acegf，字符串B=adef，最少需要2步操作將A轉(zhuǎn)換為B，
即第一步將c替換為d，第二步將g刪除;
(1)請問將字符串A=gumbo轉(zhuǎn)換為字符串B=gambol，最少需要幾步操作，列出如何操作(2分)
(2)任意字符串A和字符串B，如何計算最小操作次數(shù)，計算思路，并給出遞歸公式(3分)
(3)實現(xiàn)代碼(注意代碼風(fēng)格與效率)(15分)
點評：請參看上文第38題第4小題：9月26日，百度一二面試題。
三、系統(tǒng)設(shè)計題(30分)
RSA SecurID安全系統(tǒng)
應(yīng)用場景：這是一種用戶登錄驗證手段，例如銀行登錄系統(tǒng)，這個設(shè)備顯示6位數(shù)字，每60秒變一次，再經(jīng)過服務(wù)器認證，通過則允許登錄。問How to design this system?
1)系統(tǒng)設(shè)計思路?服務(wù)器端為何能有效認證動態(tài)密碼的正確性?
2)如果是千萬量級永固，給出系統(tǒng)設(shè)計圖示或說明，要求子功能模塊劃分清晰，給出關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)或數(shù)據(jù)庫表結(jié)構(gòu)。
考慮用戶量級的影響和擴展性，用戶密碼的隨機性等，如果設(shè)計系統(tǒng)以支持這幾個因素.
3)系統(tǒng)算法升級時，服務(wù)器端和設(shè)備端可能都要有所修改，如何設(shè)計系統(tǒng)，能夠使得升級過程(包括可能的設(shè)備替換或重設(shè))盡量平滑?
10月13日，百度移動開發(fā)筆試題
一、 1、什么是RISC;
2、通過后序、中xu求前序
3、重寫與重載的區(qū)別
二、
1、反轉(zhuǎn)鏈表
2、判斷兩個數(shù)組中是否有相同的數(shù)字
3、1000瓶水中找 出有毒的那瓶，毒性一周后發(fā)作，一周內(nèi)最少需要多少只老鼠
三、系統(tǒng)設(shè)計 email客戶端，支持多賬戶和pop3等協(xié)議
1、請寫出可能的至少5個用例;
2、使用sqlite存儲帳戶、已收信息、已發(fā)信息、附件、草稿，請設(shè)計合理的表結(jié)構(gòu)
3、pop3等協(xié)議等接口已完成，請給出email客戶端的模塊設(shè)計圖。
10月13日，人搜2013 校招北京站部分筆試題(讀者回憶+照片)：
1，二重歌德巴赫猜想
所有大于等于6的偶數(shù)都可以表示成兩個(奇)素數(shù)之和。
給定1-10000，找到可以用兩個素數(shù)之和表示每一個偶數(shù)的兩個素數(shù)，然后輸出這兩個素數(shù)，如果有多對，則只需要輸出其中之一對即可。
要求：復(fù)雜度較低，代碼可運行。
2，城市遍歷
某人家住北京，想去青海玩，可能會經(jīng)過許多城市，
現(xiàn)已知地圖上的城市連接，求經(jīng)過M個城市到達青海的路線種類。
城市可以多次到達的，比如去了天津又回到北京，再去天津，即為3次。北京出發(fā)不算1次。
輸入：
N M S
N為城市總數(shù)，北京為0，青海為N-1;
M為經(jīng)過的城市數(shù)目;
S為之后有S行
i j
表示第i個城市可以去第j個城市，是有方向的。
輸出：
N
表示路徑種類。
3，分布式系統(tǒng)設(shè)計
有1000億個URL，其中大約有5億個site。每天的更新大約2%-5%。設(shè)計一個系統(tǒng)來解決存儲和計算下面三個問題�？捎梅植际较到y(tǒng)。
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數(shù)目，以及每個site下的URL數(shù)目，輸出site變化超過一定閾值的域名以及URL數(shù)目變化劇烈的site。找出泛域。
泛域：該域下的site數(shù)目超過500個，且每個site下的URL數(shù)目超過100個。
b>提取URL中key的特征，對site進行聚類;
(每個site下面有多個URL，這些URL中有許多key，可以獲取這些key作為site的特征，對site進行聚類，不過這應(yīng)該是多機器聯(lián)合的)
c>對于給定的domain，輸出該domain下的所有site。
10月13日，創(chuàng)新工場筆試：
第一個，快排最壞情況下是O(n^2)，問如何優(yōu)化?
第二個，怎么樣求一個數(shù)的根號
點評：你是不是會想到一系列有關(guān)數(shù)學(xué)的東西，什么泰勒級數(shù)啊，什么牛頓法啊，具體編程可以如下代碼所示：
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個數(shù)字，用四則元素求結(jié)果能否為24。寫出這個判斷的函數(shù)。
10月14日，思科網(wǎng)訊旗下公司筆試題：
1、海量數(shù)據(jù)中，尋找最小的k個數(shù)。
請分情況，給出時間復(fù)雜度最優(yōu)，或空間復(fù)雜度最優(yōu)的方案，或時間復(fù)雜度/空間復(fù)雜度綜合考慮的可行方案。
點評：參見：第三章、尋找最小的k個數(shù)。
2、有兩座橋，其中一座可能是壞的，兩個守橋人分別守在這兩座橋的入口。他們一個總是會說實話，一個總是說謊話。
你現(xiàn)在需要找出哪一座橋可以通過。
1)，請問最少需要問守橋人幾個問題，可以找出可以通過的橋?如何問?
2)，請編程解決。
10月14日，騰訊杭州站筆試題：
1、http服務(wù)器會在用戶訪問某一個文件的時候，記錄下該文件被訪問的日志，網(wǎng) 站管理員都會去統(tǒng)計每天每文件被訪問的次數(shù)。寫一個小程序，來遍歷整個日志 文件，計算出每個文件被訪問的訪問次數(shù)
1)請問這個管理員設(shè)計這個算法
2)該網(wǎng)站管理員后來加入騰訊從事運維工作，在騰訊，單臺http服務(wù)器不夠用的 ，同樣的內(nèi)容，會分布在全國各地上百臺服務(wù)器上。每臺服務(wù)器上的日志數(shù)量， 都是之前的10倍之多，每天服務(wù)器的性能更好，之前他用的是單核cpu，現(xiàn)在用的 是8核的，管理員發(fā)現(xiàn)在這種的海量的分布式服務(wù)器，基本沒法使用了，請重新設(shè)計一個算法。
2、騰訊的qq游戲當(dāng)中，最多人玩的游戲就是斗地主了，每一句游戲開始時，服務(wù) 器端都要洗牌，以保證發(fā)牌的時每個人拿的牌都是隨機的，假設(shè)用1-54來表示54 張不同的拍，請你寫一個洗牌算法，保證54張牌能隨機打散!
選擇題：
1)、下列RAID技術(shù)無法提高可靠性的是：
A：RAID0 B：RAID1 C：RAID10 D：RAID5
2)、長度為1的線段，隨機在其上選擇兩點，將線段分為三段，問這3個字段能組成一 個三角形的概率是：
1/2,1/3,1/4,1/8
3)、下面那種標記的包不會在三次握手的過程中出現(xiàn)()
A：SYN B：PSH C：ACK D:RST
10月14日，搜狗2013 校招筆試題：
1、有n*n個格子，每個格子里有正數(shù)或者0，從最左上角往最右下角走，只能向下和向右，一共走兩次(即從左下角走到右下角走兩趟)，把所有經(jīng)過的格子的數(shù)加起來，求最大值SUM，且兩次如果經(jīng)過同一個格子，則最后總和SUM中該格子的計數(shù)只加一次。
點評：@西芹_new，一共搜(2n-2)步，每一步有四種走法，考慮不相交等條件可以剪去很多枝，代碼如下「http://blog.csdn.net/huangxy10/article/details/8071242」：
西芹_new
// 10_15.cpp : 定義控制臺應(yīng)用程序的入口點。
//
#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、用動態(tài)規(guī)劃可以求解，大概思路就是同時DP 2次所走的狀態(tài)。先來分析一下這個問題，為了方便討論，先對矩陣做一個編號，且以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)。為了方便討論，我們設(shè)所走的步數(shù)為s。因為限定了只能向右和向下走，因此無論如何走，經(jīng)過8步后(s = 8)都將走到右下。而DP的狀態(tài)也是依據(jù)所走的步數(shù)來記錄的。
再來分析一下經(jīng)過其他s步后所處的位置，根據(jù)上面的討論，可以知道經(jīng)過8步后，一定處于右下角(8)，那么經(jīng)過5步后(s = 5)，肯定會處于編號為5的位置。3步后肯定處于編號為3的位置......。s = 4的時候，處于編號為4的位置，對于方格中，共有5(相當(dāng)于n)個不同的位置，也是所有編號中最多的。推廣來說n*n的方格，總共需要走2n - 2步，當(dāng)s = n - 1時，編號為n個，也是編號最多的。
如果用DP[s,i,j]來記錄2次所走的狀態(tài)獲得的最大值，其中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
經(jīng)過6步后，肯定處于M1中編號為6的位置。共有3個編號為6的，分別對應(yīng)M2中的2 3 4。假設(shè)第1次經(jīng)過6步走到了M2中的2，第2次經(jīng)過6步走到了M2中的4，DP[s,i,j] 則對應(yīng) DP[6,2,4]。由于s = 2n - 2,0 <= i<= <= j <= n，所以這個DP共有O(n^3)個狀態(tài)。
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
再來分析一下狀態(tài)轉(zhuǎn)移，以DP[6,2,3]為例(就是上面M1中加粗的部分)，可以到達DP[6,2,3]的狀態(tài)包括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] (加紅表示要達到的狀態(tài)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格子中對應(yīng)的數(shù)值 (式一)
2、上面(式一)所示的這個遞推看起來沒有涉及：“如果兩次經(jīng)過同一個格子，那么該數(shù)只加一次的這個條件”，討論這個條件需要換一個例子，以DP[6,2,2]為例。
DP[6,2,2]可以由DP[5,1,1]，DP[5,1,2]，DP[5,2,2]到達，但由于i = j，也就是2次走到同一個格子，那么數(shù)值只能加1次。
所以當(dāng)i = j時，DP[6,2,2] = Max(DP[5,1,1]，DP[5,1,2]，DP[5,2,2]) + 6,2格子中對應(yīng)的數(shù)值 (式二)
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]表示經(jīng)過s步后，處于i位置，位置i對應(yīng)的方格中的數(shù)字。
復(fù)雜度分析：狀態(tài)轉(zhuǎn)移最多需要統(tǒng)計4個變量的情況，看做是O(1)的。共有O(n^3)個狀態(tài)，所以總的時間復(fù)雜度是O(n^3)的�？臻g上可以利用滾動數(shù)組優(yōu)化，由于每一步的遞推只跟上1步的情況有關(guān)，因此可以循環(huán)利用數(shù)組，將空間復(fù)雜度降為O(n^2)。
OK，上述這個方法可能不算最優(yōu)解法，但相對比較容易想一些。希望大家能夠提供更好的想法，也歡迎大家補充程序。鏈接：http://www.51nod.com/answer/#!answerId=598。
2、N個整數(shù)(數(shù)的大小為0-255)的序列，把它們加密為K個整數(shù)(數(shù)的大小為0-255).再將K個整數(shù)順序隨機打亂，使得可以從這亂序的K個整數(shù)中解碼出原序列。設(shè)計加密解密算法,且要求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。
人人網(wǎng)面試，只面一道題，要求5分鐘出思路，10分鐘出代碼
面試題是：
兩個無序數(shù)組分別叫A和B，長度分別是m和n，求中位數(shù)，要求時間復(fù)雜度O(m+n)，空間復(fù)雜度O(1) 。
10月15日，網(wǎng)新恒天筆試題
1.不要使用庫函數(shù)，寫出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.給定一個字符串，統(tǒng)計一下哪個字符出現(xiàn)次數(shù)最大。
3.我們不知道Object類型的變量里面會出現(xiàn)什么內(nèi)容，請寫個函數(shù)把Object類型轉(zhuǎn)換為int類型。
10月15日，Google 2013 校招全套筆試題：
1.寫一個函數(shù)，輸出前N個素數(shù)，函數(shù)原型：void print_prime(int N); 不需要考慮整數(shù)的溢出問題，也不需要使用大數(shù)處理算法。
2.長度為N的數(shù)組亂序存放著0帶N-1.現(xiàn)在只能進行0與其他數(shù)的swap操作，請設(shè)計并實現(xiàn)排序，必須通過交換實現(xiàn)排序。
3.給定一個源串和目標串，能夠?qū)υ创M行如下操作：
1.在給定位置上插入一個字符
2.替換任意字符
3.刪除任意字符
寫一個程序，返回最小操作數(shù)，使得對源串進行這些操作后等于目標串，源串和目標串的長度都小于2000。
點評：
1、此題反復(fù)出現(xiàn)，如上文第38題第4小題9月26日百度一二面試題，10月9日騰訊面試題第1小題，及上面第69題10月13日百度2013校招北京站筆試題第二大道題第3小題，同時，還可以看下這個鏈接：http://www.51nod.com/question/#!questionId=662。
//動態(tài)規(guī)劃：
//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、補充：上述問題類似于編程之美上的下述一題「以下內(nèi)容摘自編程之美第3.3節(jié)」：
許多程序會大量使用字符串。對于不同的字符串，我們希望能夠有辦法判斷其相似程度。我們定義了一套操作方法來把兩個不相同的字符串變得相同，具體的操作方法為：
1. 修改一個字符(如把“a”替換為“b”);
2. 增加一個字符(如把“abdd ”變?yōu)椤癮ebdd ”);
3. 刪除一個字符(如把“travelling”變?yōu)椤皌raveling”)。
比如，對于“abcdefg”和“abcdef ”兩個字符串來說，我們認為可以通過增加/減少一個“g”的方式來達到目的。上面的兩種方案，都僅需要一次操作。把這個操作所需要的次數(shù)定義為兩個字符串的距離，而相似度等于“距離+1”的倒數(shù)。也就是說，“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;
}
}
上面的遞歸程序，有什么地方需要改進呢?在遞歸的過程中，有些數(shù)據(jù)被重復(fù)計算了。比如，如果開始我們調(diào)用CalculateStringDistance(strA,1, 2, strB, 1, 2)，下圖是部分展開的遞歸調(diào)用。
可以看到，圈中的兩個子問題被重復(fù)計算了。為了避免這種不必要的重復(fù)計算，可以把子問題計算后的解存儲起來。如何修改遞歸程序呢?還是DP!請看此鏈接：http://www.cnblogs.com/yujunyong/articles/2004724.html。
3、此外，關(guān)于這個“編輯距離”問題的應(yīng)用：搜索引擎關(guān)鍵字查詢中拼寫錯誤的提示，可以看下這篇文章：http://www.ruanyifeng.com/blog/2012/10/spelling_corrector.html�！戈P(guān)于什么是“編輯距離”：一個快速、高效的Levenshtein算法實現(xiàn)，這個是計算兩個字符串的算法，Levenshtein距離又稱為“編輯距離”，是指兩個字符串之間，由一個轉(zhuǎn)換成另一個所需的最少編輯操作次數(shù)。當(dāng)然，次數(shù)越小越相似。這里有一個BT樹的數(shù)據(jù)結(jié)構(gòu)，挺有意思的：http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees」
最后，Lucene中也有這個算法的實現(xiàn)(我想，一般的搜索引擎一般都應(yīng)該會有此項拼寫錯誤檢查功能的實現(xiàn))：http://www.bjwilly.com/archives/395.html。
4、擴展：面試官還可以繼續(xù)問下去：那么，請問，如何設(shè)計一個比較兩篇文章相似性的算法?(這個問題的討論可以看看這里：http://t.cn/zl82CAH)
BTW，群友braveheart89也整理了這套筆試題：http://blog.csdn.net/braveheart89/article/details/8074657。
10月16日，UC的筆試題目：
1、有個長度為2n的數(shù)組{a1,a2,a3,...,an,b1,b2,b3,...,bn}，希望排序后{a1,b1,a2,b2,....,an,bn}，要求時間復(fù)雜度o(n),空間復(fù)雜度0(1)。
點評：@綠色夾克衫：完美洗牌問題「關(guān)于洗牌算法：http://blog.csdn.net/gogdizzy/article/details/4917488」，解決這個問題的關(guān)鍵在于如何解決置換群中的環(huán)。方法是微軟員工那篇論文中寫的：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日，創(chuàng)新工場電話面試：
1，如何刪除一個搜索二叉樹的結(jié)點;
2，如何找到一個數(shù)組中的兩個數(shù)，他們的和為0;
3，如何判斷兩條二維平面上的線段是否相交。
網(wǎng)易2013 校招筆試題：
10月19日，百度研發(fā)三面題：
百度地圖里的路線查詢：給定兩個站點，如果沒有直達的路線，如何找到換乘次數(shù)最少的路線?
點評：螞蟻算法?還是廣搜，或A*算法?
10月20日，baidu廣州站筆試算法題：
1. 有一箱蘋果，3個一包還剩2個，5個一包還剩3個，7個一包還剩2個，求N個滿足以上條件的蘋果個數(shù)。
2. 用遞歸算法寫一個函數(shù)，求字符串最長連續(xù)字符的長度，比如aaaabbcc的長度為4，aabb的長度為2，ab的長度為1。
3. 假設(shè)一個大小為100億個數(shù)據(jù)的數(shù)組，該數(shù)組是從小到大排好序的，現(xiàn)在該數(shù)組分成若干段，每個段的數(shù)據(jù)長度小于20「也就是說：題目并沒有說每段數(shù)據(jù)的size 相同，只是說每個段的 size < 20 而已」，然后將每段的數(shù)據(jù)進行亂序(即：段內(nèi)數(shù)據(jù)亂序)，形成一個新數(shù)組。請寫一個算法，將所有數(shù)據(jù)從小到大進行排序，并說明時間復(fù)雜度。
點評：
思路一、如@四萬萬網(wǎng)友所說：維護一個20個元素大小的小根堆，然后排序，每次pop取出小根堆上最小的一個元素(log20)，然后繼續(xù)遍歷原始數(shù)組后續(xù)的(N-20)個元素，總共pop (N-20)次20個元素小根堆的log20的調(diào)整操作。
思路二@飄零蝦、如果原數(shù)組是a[]，那么a[i+20]>=a[i]恒成立(因為每段亂序區(qū)間都是小于20的，那么向后取20，必然是更大的區(qū)間的元素)。
第一個數(shù)組：取第0、20、40、60、80...
第二個數(shù)組：取第1、21、41、61、81...
...
第20個數(shù)組：取第19、39、59、79... (上述每個數(shù)組100億/20 個元素)
共計20個數(shù)組，每個數(shù)組100億/20 個元素「注：這5億個元素已經(jīng)有序，不需要再排序」，且這20個數(shù)組都是有序的，然后對這20個數(shù)組進行歸并，每次歸并20個元素。時間復(fù)雜度跟上述思路一一樣，也是N*logK(N=100億，K=20)。
此外，讀者@木葉漂舟直接按每組20個排序,將排好的20個與前20個調(diào)整拼接,調(diào)整兩端接頭處的元素,寫了個簡單地demo： http://t.cn/zlELAzs。不過，復(fù)雜度有點高，目前來說中規(guī)中矩的思路還是如上文中@四萬萬網(wǎng)友 所說思路一「@張瑋-marihees按照思路一：http://weibo.com/1580904460/z1v5jxJ9P，寫了一份代碼：http://codepad.org/T5jIUFPG，歡迎查看」。
10月21日，完美筆試算法題「同時，祝自己生日快樂!」：
1. 請設(shè)計一個算法，當(dāng)給出在2D平面中某個三角形ABC的頂點坐標時能輸出位于該三角形內(nèi)的一個隨機點(需要滿足三角形內(nèi)均勻隨機)，無需寫出實現(xiàn)，只要能清楚地描述算法即可。
2. 請自己用雙向鏈表實現(xiàn)一個隊列，隊列里節(jié)點內(nèi)存的值為int，要求實現(xiàn)入隊，出隊和查找指定節(jié)點的三個功能。
3. 實現(xiàn)一個無符號任意大整數(shù)的類，實現(xiàn)兩個無符號超大整數(shù)的乘法。
10月22日，CSR掌微電子筆試題：
5.給定兩個字符串s1和s2，要求判定s2是否能夠被通過s1做循環(huán)移位(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日，去哪兒網(wǎng)筆試：
1.將IPV4轉(zhuǎn)換成整數(shù)
2.定義一個棧的數(shù)據(jù)結(jié)構(gòu)，實現(xiàn)min函數(shù)，要求push,pop,min時間復(fù)雜度是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.數(shù)組a[n]里存有1到n的所有樹，除了一個數(shù)removed，找出這個missing的樹。
4.找出字符串中的最長子串，要求子串不含重復(fù)字符，并分析時間復(fù)雜度。
10月28日，微軟三面題「順祝，老媽明天生日快樂!」：
找一個點集中與給定點距離最近的點，同時，給定的二維點集都是固定的，查詢可能有很多次，時間復(fù)雜度O(n)無法接受，請設(shè)計數(shù)據(jù)結(jié)構(gòu)和相應(yīng)的算法。
類似于@陳利人：附近地點搜索，就是搜索用戶附近有哪些地點。隨著GPS和帶有GPS功能的移動設(shè)備的普及，附近地點搜索也變得炙手可熱。在龐大的地理數(shù)據(jù)庫中搜索地點，索引是很重要的。但是，我們的需求是搜索附近地點，例如，坐標(39.91, 116.37)附近500米內(nèi)有什么餐館，那么讓你來設(shè)計，該怎么做?
點評：我看到這道題的時候，除了想到用R樹「從B樹、B+樹、B*樹談到R 樹」解決這個問題之外，還想起了之前一直要寫的KD樹仍未寫，但估計快要寫了，請讀者朋友們耐心等待些時日吧。
11月10日，百度筆試題：
1、20個排序好的數(shù)組，每個數(shù)組500個數(shù)，按照降序排序好的，讓找出500個最大的數(shù)。
2、一在線推送服務(wù)，同時為10萬個用戶提供服務(wù)，對于每個用戶服務(wù)從10萬首歌的曲庫中為他們隨機選擇一首，同一用戶不能推送重復(fù)的，設(shè)計方案，內(nèi)存盡可能小，寫出數(shù)據(jù)結(jié)構(gòu)與算法。
【互聯(lián)網(wǎng)開發(fā)面試題】相關(guān)文章：
互聯(lián)網(wǎng)公司面試題總結(jié)07-12
web前端開發(fā)面試題07-12
我遇到的互聯(lián)網(wǎng)公司的面試題07-12
JAVA開發(fā)工程師面試題07-13
互聯(lián)網(wǎng)產(chǎn)品開發(fā)流程標準文檔07-10
單片機開發(fā)工程師面試題07-11
Google Android 開發(fā)工程師職位面試題07-13
關(guān)于互聯(lián)網(wǎng)新產(chǎn)品設(shè)計開發(fā)流程07-10