? 九月十月百度人搜，阿里巴巴，騰訊華為小米搜狗筆試面試八十題
（參與算法&面試題交流與討論，請加群：30382647）
?
引言
? ? 自發表上一篇文章至今（事實上，上篇文章更新了近3個月之久），blog已經停了3個多月，而在那之前，自開博以來的21個月每月都不曾斷過。正如上一篇文章支持向量機通俗導論（理解SVM的三層境界）末尾所述：”額，blog許久未有更新了，因為最近實在忙，無暇顧及blog。“與此同時，工作之余，也一直在閑心研究數據挖掘："神經網絡將可能作為Top 10 Algorithms in Data Mining之番外篇第1篇，同時，k-最近鄰法(k-nearest neighbor，kNN)算法談到kd樹將可能作為本系列第三篇。這是此系列接下來要寫的兩個算法，剛好項目中也要用到KD樹“。
? ? 但很顯然，若要等到下一篇數據挖掘系列的文章時，說不定要到年底去了，而最近的這段時間，9月、10月，正是各種校招/筆試/面試火熱進行的時節，自己則希望能幫助到這些找工作的朋友，故此，怎能無動于衷，于是，3個多月后，blog今天更新了。
? ? 再者，雖然如我的這條微博：http://weibo.com/1580904460/yzs72mmFZ所述，blog自10年10月開通至11年10月，一年的時間內整理了300多道面試題(這300道題全部集錦在此文中第一部分：http://blog.csdn.net/v_july_v/article/details/6543438)。但畢竟那些題已經是前年或去年的了，筆試面試題雖然每年類型變化不大，但畢竟它年年推陳出新，存著就有其合理性。
? ? OK，以下是整理自8月下旬至10月份內的各大公司的筆試面試三十題（注：所有題目基本上全部為軟件開發方向，題目來源：網絡收集），相信一定能給正在參加各種校招的諸多朋友多少幫助，學習參考或借鑒（如果你手頭上有好的筆試/面試題，歡迎通過微博私信：http://weibo.com/julyweibo，或郵箱：zhoulei0907@yahoo.cn發給我，或者干脆直接評論在本文下；同時，若你對以下任何一題有任何看法.想法.思路或建議，歡迎留言評論，大家一起討論，共同享受思考的樂趣，謝謝）。
九月十月百度人搜，阿里巴巴，騰訊華為小米搜狗筆試面試八十題
「我正在一點一點做.整理下面的筆試面試題，歡迎讀者朋友們跟我一起做，你可以把你的答案或代碼直接評論在本文之下，也可以通過私信或郵件發給我，感謝諸位。同時，以下所有任何題目所給的點評里的答案，尤其是所給的外部鏈接若有任何問題，歡迎在本文評論下留言指正，謝謝。答題除了讓你感受到思考的樂趣以外，還有獎哦，請君自看。July、二零一二年十月十一日」
-
9月11日， 京東：
談談你對面向對象編程的認識
- 8月20日，金山面試，題目如下：
? ? 數據庫1中存放著a類數據，數據庫2中存放著以天為單位劃分的表30張（比如table_20110909,table_20110910,table_20110911）,總共是一個月的數據。表1中的a類數據中有一個字段userid來唯一判別用戶身份，表2中的30張表（每張表結構相同）也有一個字段userid來唯一識別用戶身份。如何判定a類數據庫的多少用戶在數據庫2中出現過？
來源：http://topic.csdn.net/u/20120820/23/C6B16CCF-EE15-47C0-9B15-77497291F2B9.html。 - 百度實習筆試題（2012.5.6）
?1、一個單詞單詞字母交換，可得另一個單詞，如army->mary，成為兄弟單詞。提供一個單詞，在字典中找到它的兄弟。描述數據結構和查詢過程。評點：同去年9月份的一道題，見此文第3題：http://blog.csdn.net/v_july_v/article/details/6803368。
2、線程和進程區別和聯系。什么是“線程安全”
3、C和C++怎樣分配和釋放內存，區別是什么
4、算法題1
一個url指向的頁面里面有另一個url,最終有一個url指向之前出現過的url或空，這兩種情形都定義為null。這樣構成一個單鏈表。給兩條這樣單鏈表，判斷里面是否存在同樣的url。url以億級計，資源不足以hash。
5、算法題2
數組al[0,mid-1] 和 al[mid,num-1]，都分別有序。將其merge成有序數組al[0,num-1]，要求空間復雜度O(1)
6、系統設計題
百度搜索框的suggestion，比如輸入“北京”，搜索框下面會以北京為前綴，展示“北京愛情故事”、“北京公交”、“北京醫院”等等搜索詞，輸入“結構之”，會提示“結構之法”，“結構之法 算法之道”等搜索詞。
請問，如何設計此系統，使得空間和時間復雜度盡量低。
評點：老題，直接上Trie樹「Trie樹的介紹見：從Trie樹（字典樹）談到后綴樹」+TOP K「hashmap+堆，hashmap+堆 統計出如10個近似的熱詞，也就是說，只存與關鍵詞近似的比如10個熱詞」？ or ?Double-array trie tree？同時，StackOverflow上也有兩個討論帖子：http://stackoverflow.com/questions/2901831/algorithm-for-autocomplete，http://stackoverflow.com/questions/1783652/what-is-the-best-autocomplete-suggest-algorithm-datastructure-c-c。此外，這里有一篇關于“拼寫錯誤檢查”問題的介紹，或許對你有所啟示：http://blog.afterthedeadline.com/2010/01/29/how-i-trie-to-make-spelling-suggestions/。 - 人搜筆試 1. 快排每次以第一個作為主元，問時間復雜度是多少？（O(N*logN)）
-
?
- ? 2. T(N) = N + T(N/2)+T(2N), 問T(N)的時間復雜度是多少？
點評：O(N*logN) or O(N)？
- ? 3. 從（0,1）中平均隨機出幾次才能使得和超過1？（e）
?
- ? 4.編程題：
?
- ?一棵樹的節點定義格式如下：
?
- ?struct Node{
?
- ? ? Node* parent;
?
- ? ? Node* firstChild; // 孩子節點
?
- ? ? Node* sibling; // 兄弟節點?
?
- }
?
- 要求非遞歸遍歷該樹。
?
- 思路：采用隊列存儲，來遍歷節點。
?
- ? 5. 算法題：
?
- 有N個節點，每兩個節點相鄰，每個節點只與2個節點相鄰，因此，N個頂點有N-1條邊。每一條邊上都有權值wi，定義節點i到節點i+1的邊為wi。
?
- 求：不相鄰的權值和最大的邊的集合。
- 人搜面試，所投職位：搜索研發工程師：面試題回憶?
? ? ?1、刪除字符串開始及末尾的空白符，并且把數組中間的多個空格（如果有）符轉化為1個。
? ? ?2、求數組（元素可為正數、負數、0）的最大子序列和。?
? ? ?3、鏈表相鄰元素翻轉，如a->b->c->d->e->f-g，翻轉后變為：b->a->d->c->f->e->g?
? ? ?4、鏈表克隆。鏈表的結構為：?
? ? ?typedef struct list {?
? ? ? ? ?int data; //數據字段?
? ? ?list *middle; //指向鏈表中某任意位置元素(可指向自己)的指針?
? ? ?list *next;//指向鏈表下一元素?
? ? ?} list;?
? ? ?5、100萬條數據的數據庫查詢速度優化問題，解決關鍵點是：根據主表元素特點，把主表拆分并新建副表，并且利用存儲過程保證主副表的數據一致性。（不用寫代碼）?
? ? ?6、求正整數n所有可能的和式的組合（如；4=1+1+1+1、1+1+2、1+3、2+1+1、2+2）。點評：這里有一參考答案：http://blog.csdn.net/wumuzi520/article/details/8046350。
? ? ?7、求旋轉數組的最小元素（把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個排好序的數組的一個旋轉，輸出旋轉數組的最小元素。例如數組{3, 4, 5, 1, 2}為{1, 2, 3, 4, 5}的一個旋轉，該數組的最小值為1）?
? ? ?8、找出兩個單鏈表里交叉的第一個元素?
? ? ?9、字符串移動（字符串為*號和26個字母的任意組合，把*號都移動到最左側，把字母移到最右側并保持相對順序不變），要求時間和空間復雜度最小?
? ? ?10、時間復雜度為O(1)，怎么找出一個棧里的最大元素 ??
? ? ?11、線程、進程區別?
? ? ?12、static在C和C++里各代表什么含義?
? ? ?13、const在C/C++里什么意思?
? ? ?14、常用linux命令?
? ? ?15、解釋Select/Poll模型? - 網易有道二面：
判斷一個數字序列是BST后序遍歷的結果，現場寫代碼。
來源：http://blog.csdn.net/hopeztm/article/category/1201028； - 8月30日，網易有道面試題
var tt = 'aa';
function test()
{
? alert(tt);
? var tt = 'dd';
? alert(tt);
}
test();?? - 8月31日，百度面試題：不使用隨機數的洗牌算法，詳情：http://topic.csdn.net/u/20120831/10/C837A419-DFD4-4326-897C-669909BD2086.html；
- 9月6日，阿里筆試題：平面上有很多點，點與點之間有可能有連線，求這個圖里環的數目。
- 9月7日，一道華為上機題：
題目描述: 選秀節目打分，分為專家評委和大眾評委，score[] 數組里面存儲每個評委打的分數，judge_type[] 里存儲與 score[] 數組對應的評委類別，judge_type == 1，表示專家評委，judge_type == 2，表示大眾評委，n表示評委總數。打分規則如下：專家評委和大眾評委的分數先分別取一個平均分（平均分取整），然后，總分 = 專家評委平均分 * 0.6 + 大眾評委 * 0.4，總分取整。如果沒有大眾評委，則 總分 = 專家評委平均分，總分取整。函數最終返回選手得分。
函數接口 int cal_score(int score[], int judge_type[], int n) ?
?上機題目需要將函數驗證，但是題目中默認專家評委的個數不能為零，但是如何將這種專家數目為0的情形排除出去。
來源：http://topic.csdn.net/u/20120907/15/c30eead8-9e49-41c2-bd11-c277030ad17a.html； - 9月8日，騰訊面試題：
假設兩個字符串中所含有的字符和個數都相同我們就叫這兩個字符串匹配，
?比如：abcda和adabc,由于出現的字符個數都是相同，只是順序不同，
?所以這兩個字符串是匹配的。要求高效！
又是跟上述第3題中簡單題一的兄弟節點類似的一道題，我想，你們能想到的，這篇blog里：http://blog.csdn.net/v_JULY_v/article/details/6347454都已經有了。 - 阿里云，搜索引擎中5億個url怎么高效存儲；
- 一道C++筆試題，求矩形交集的面積：
在一個平面坐標系上，有兩個矩形，它們的邊分別平行于X和Y軸。
其中，矩形A已知， ax1(左邊), ax2（右邊）, ay1（top的縱坐標）, ay2（bottom縱坐標）. 矩形B，類似，就是 bx1, bx2, by1, by2。這些值都是整數就OK了。
要求是，如果矩形沒有交集，返回-1， 有交集，返回交集的面積。
int area(rect const& a, rect const& b)
{
??...
}
點評：
healer_kx：
補齊代碼，最好是簡潔的，別用庫。你可以寫你的輔助函數，宏定義，代碼風格也很重要。
ri_aje：
下面是一個簡短的證明。struct rect {// axis alignment assumed// bottom left is (x[0],y[0]), top right is (x[1],y[1])double x [2];double y [2]; };template <typename T> T const& min (T const& x, T const& y) { return x<y ? x : y; } template <typename T> T const& max (T const& x, T const& y) { return x>y ? x : y; }// return type changed to handle non-integer rects double area (rect const& a, rect const& b) {// perfectly adjacent rects are considered having an intersection of 0 areadouble const dx = min(a.x[1],b.x[1]) - max(a.x[0],b.x[0]);double const dy = min(a.y[1],b.y[1]) - max(a.y[0],b.y[0]);return dx>=0&&dy>=0 ? dx*dy : -1; }
對于平行于坐標軸的矩形 r，假設其左下角點坐標為 (rx0,ry0)，右上角點坐標為 (rx1,ry1)，那么由 r 定義的無限有界點集為：{(x,y)|x in [rx0,rx1] && y in [ry0,ry1]}。
根據交集的定義，則任意二維點 (x,y) 在矩形 a,b 的交集內等價于
{(x,y)|(x,y) in a 并且 (x,y) in b} <==>
{(x,y)|x in [ax0,ax1] && x in [bx0,bx1] 并且 y in [ay0,ay1] && y in [by0,by1]} <==>
{(x,y)|x in [max(ax0,bx0),min(ax1,bx1)] 并且 y in [max(ay0,by0),min(ay1,by1)]}
因此，交集矩形的邊長分別為 min(ax1,bx1)-max(ax0,bx0) 和 min(ay1,by1)-max(ay0,by0)。注意當交集為空時(a,b 不相交)，則經此法計算出來的交集邊長為負值，此事實可用于驗證 a,b 的相交性。
鑒于笛卡爾積各個維度上的不相關性，此方法可擴展到任意有限維線性空間，比如，三維空間中平行于坐標軸的長方體的交集體積可以用類似的方法計算。
來源：http://topic.csdn.net/u/20120913/18/bc669d60-b70a-4008-be65-7c342789b925.html。 - 2012年創新工場校園招聘最后一道筆試題：工場很忙
?? ?創新工場每年會組織同學與項目的雙選會，假設現在有M個項目，編號從1到M，另有N名同學，編號從1到N，每名同學能選擇最多三個、最少一個感興趣的項目。選定之后，HR會安排項目負責人和相應感興趣的同學一對一面談，每次面談持續半小時。由于大家平時都很忙，所以咱們要盡量節約時間，請你按照以下的條件設計算法，幫助HR安排面試。
1）同學很忙。項目負責人一次只能與一名同學面談，而同學會在自己第一個面試開始時達到工場，最后一個面試結束后離開工場，如果參加一個項目組的面試后不能立即參加下一個項目組的面試，就必須在工場等待。所以請盡可能讓同學的面試集中在某一時間段，減少同學在工場等待的時間。
2）項目負責人很忙。眾所周知，創業團隊的負責人會有很多事情要做，所以他們希望能夠將自己參與的面試集中在某一段時間內，請在保證1）的情況下，使得項目負責人等待的時間最少。
3）HR很忙。從第一輪面試開始以后，所有HR都必須等到最后一輪面試結束，所以需要在保證1）和2）的同時，也能盡快解放掉所有的HR，即讓第一輪面試到最后一輪面試之間持續的時間最短。
輸入(以文件方式輸入，文件名為iw，例如iw.in)：
?? ?第1行...第n行：同學的編號 項目的編號
?? ?樣例（數據間用空格隔開,兩個0表示輸入結束）： ? ? ? ? ??
1 1
12
1 3
2 1
3 1
3 2
0 0 ? ? ? ? ? ??
?? ?表示M=3，N=3，編號為1的同學選擇了項目1,2和3，編號為2的同學選擇了項目1，編號為3的同學選了項目1和2
輸出(以文件方式輸出，文件名為iw，例如iw.out)：
?? ?第1行：編號為1的項目依次面試新同學的編號序列
?? ?第2行：編號為2的項目依次面試新同學的編號序列
?? ?...
?? ?第n行：編號為n的項目依次面試新同學的編號序列
?? ?樣例（數據間用空格隔開，0表示沒有面試）：
13 2
3 1 0
0 0 1
?? ?表示編號為1的項目在第一輪面試編號為1的同學，第二輪面試編號為3的同學，第三輪面試編號為2的同學
?? ?編號為2的項目在第一輪面試編號為3的同學，第二輪面試編號為1的同學，第二輪不用面試
?? ?編號為3的項目在第一輪和第二輪都不用面試，第三輪面試編號為1的同學
鏈接：http://t.qq.com/p/t/108332110988802； -
4**9 的筆試題，比較簡單：
1.求鏈表的倒數第二個節點
2.有一個整數數組，求數組中第二大的數 - 阿里巴巴二道題第一道：
對于給定的整數集合S，求出最大的d，使得a+b+c=d。a,b,c,d互不相同，且都屬于S。集合的元素個數小于等于2000個，元素的取值范圍在[-2^28，2^28?- 1]，假定可用內存空間為100MB，硬盤使用空間無限大，試分析時間和空間復雜度，找出最快的解決方法。
點評：
@綠色夾克衫：兩兩相加轉為多項式乘法，比如(1 2 4 6) + (2 3 4 5) => (x + x^2 + x^4 + x^6)*(x^2 + x^3 + x^4 + x^5)?。更多思路請見這：http://www.51nod.com/answer/index.html#!answerId=569。阿里巴巴第二道(研發類)
筆試題1，原題大致描述有一大批數據，百萬級別的。數據項內容是：用戶ID、科目ABC各自的成績。其中用戶ID為0~1000萬之間，且是連續的，可以唯一標識一條記錄。科目ABC成績均在0~100之間。有兩塊磁盤，空間大小均為512M，內存空間64M。
1)?為實現快速查詢某用戶ID對應的各科成績，問磁盤文件及內存該如何組織；
2)?改變題目條件，ID為0~10億之間，且不連續。問磁盤文件及內存該如何組織；
3)?在問題2的基礎上，增加一個需求。在查詢各科成績的同時，獲取該用戶的排名，問磁盤文件及內存該如何組織。
筆試題2：代碼實現計算字符串的相似度。
點評：和計算兩字符串的最長公共子序列相似。
設Ai為字符串A(a1a2a3 … am)的前i個字符（即為a1,a2,a3 … ai）
設Bj為字符串B(b1b2b3 … bn)的前j個字符（即為b1,b2,b3 … bj）
設 L(i , j)為使兩個字符串和Ai和Bj相等的最小操作次數。
當ai等于bj時 顯然L(i, j)=L(i-1, j-1)
當ai不等于bj時
? 若將它們修改為相等，則對兩個字符串至少還要操作L(i-1, j-1)次
? 若刪除ai或在Bj后添加ai，則對兩個字符串至少還要操作L(i-1, j)次
? 若刪除bj或在Ai后添加bj，則對兩個字符串至少還要操作L(i, j-1)次
? 此時L(i, j)=min( L(i-1, j-1), L(i-1, j), L(i, j-1) ) ?+ 1
顯然，L(i, 0)=i，L(0, j)=j, 再利用上述的遞推公式，可以直接計算出L(i, j)值。具體代碼請見這：http://blog.csdn.net/flyinghearts/article/details/5605996。? - 9月14日，小米筆試，給一個浮點數序列，取最大乘積子序列的值，例如 -2.5，4，0，3，0.5，8，-1，則取出的最大乘積子序列為3，0.5，8。
點評：
解法一、
?? ? 或許，讀者初看此題，自然會想到最大乘積子序列問題類似于最大子數組和問題：http://blog.csdn.net/v_JULY_v/article/details/6444021，然實則具體處理起來諸多不同，為什么呢，因為乘積子序列中有正有負也還可能有0。
?? ?既如此，我們可以把問題簡化成這樣：數組中找一個子序列，使得它的乘積最大；同時找一個子序列，使得它的乘積最小（負數的情況）。因為雖然我們只要一個最大積，但由于負數的存在，我們同時找這兩個乘積做起來反而方便。也就是說，不但記錄最大乘積，也要記錄最小乘積。So，
我們讓maxCurrent表示當前最大乘積的candidate，
minCurrent反之，表示當前最小乘積的candidate。
（用candidate這個詞是因為只是可能成為新一輪的最大/最小乘積），
而maxProduct則記錄到目前為止所有最大乘積candidates的最大值。
?? ?由于空集的乘積定義為1，在搜索數組前，maxCurrent,minCurrent,maxProduct都賦為1。
假設在任何時刻你已經有了maxCurrent和minCurrent這兩個最大/最小乘積的candidates，新讀入數組的元素x(i)后，新的最大乘積candidate只可能是maxCurrent或者minCurrent與x(i)的乘積中的較大者，如果x(i)<0導致maxCurrent<minCurrent，需要交換這兩個candidates的值。
?? ?當任何時候maxCurrent<1，由于1（空集）是比maxCurrent更好的candidate，所以更新maxCurrent為1，類似的可以更新minCurrent。任何時候maxCurrent如果比最好的maxProduct大，更新maxProduct。
?? ?具體代碼如下：
解法二、template <typename Comparable> Comparable maxprod( const vector<Comparable>&v) {int i;Comparable maxProduct = 1;Comparable minProduct = 1;Comparable maxCurrent = 1;Comparable minCurrent = 1;//Comparable t;for( i=0; i< v.size() ;i++){maxCurrent *= v[i];minCurrent *= v[i];if(maxCurrent > maxProduct) maxProduct = maxCurrent;if(minCurrent > maxProduct)maxProduct = minCurrent;if(maxCurrent < minProduct)minProduct = maxCurrent;if(minCurrent < minProduct)minProduct = minCurrent;if(minCurrent > maxCurrent)swap(maxCurrent,minCurrent);if(maxCurrent<1)maxCurrent = 1;//if(minCurrent>1)// minCurrent =1;}return maxProduct; }
?? ?本題除了上述類似最大子數組和的解法，也可以直接用動態規劃求解（其實，上述的解法一本質上也是動態規劃，只是解題所表現出來的具體形式與接下來的解法二不同罷了。這個不同就在于下面的解法二會寫出動態規劃問題中經典常見的狀態轉移方程，而解法一是直接求解）。具體解法如下：
?? ?假設數組為a[]，直接利用動歸來求解，考慮到可能存在負數的情況，我們用Max[i]來表示以a[i]結尾的最大連續子序列的乘積值，用Min[i]表示以a[i]結尾的最小的連續子序列的乘積值，那么狀態轉移方程為：
? ? ? ?Max[i]=max{a[i], Max[i-1]*a[i], Min[i-1]*a[i]};
? ? ? ?Min[i]=min{a[i], Max[i-1]*a[i], Min[i-1]*a[i]};
?? ?初始狀態為Max[1]=Min[1]=a[1]。代碼如下：
變種/*給定一個整數數組，有正有負數，0，正數組成,數組下標從1算起求最大連續子序列乘積，并輸出這個序列，如果最大子序列乘積為負數，那么就輸出-1用Max[i]表示以a[i]結尾乘積最大的連續子序列用Min[i]表示以a[i]結尾乘積最小的連續子序列 因為有復數，所以保存這個是必須的 */ void longest_multiple(int *a,int n){int *Min=new int[n+1]();int *Max=new int[n+1]();int *p=new int[n+1]();//初始化for(int i=0;i<=n;i++){p[i]=-1;}Min[1]=a[1];Max[1]=a[1];int max_val=Max[1];for(int i=2;i<=n;i++){Max[i]=max(Max[i-1]*a[i],Min[i-1]*a[i],a[i]);Min[i]=min(Max[i-1]*a[i],Min[i-1]*a[i],a[i]);if(max_val<Max[i])max_val=Max[i];}if(max_val<0)printf("%d",-1);elseprintf("%d",max_val); //內存釋放delete [] Max;delete [] Min; }
?? ?此外，此題還有另外的一個變種形式，即給定一個長度為N的整數數組，只允許用乘法，不能用除法，計算任意（N-1）個數的組合中乘積最大的一組，并寫出算法的時間復雜度。
??我們可以把所有可能的（N-1）個數的組合找出來，分別計算它們的乘積，并比較大小。由于總共有N個（N-1）個數的組合，總的時間復雜度為O（N2），顯然這不是最好的解法。
??OK，以下解答來自編程之美
解法1
解法2
? 此外，還可以通過分析，進一步減少解答問題的計算量。假設N個整數的乘積為P，針對P的正負性進行如下分析（其中，AN-1表示N-1個數的組合，PN-1表示N-1個數的組合的乘積）。
? ?1.P為0? ? ? ? ? 那么，數組中至少包含有一個0。假設除去一個0之外，其他N-1個數的乘積為Q，根據Q的正負性進行討論：
Q為0
說明數組中至少有兩個0，那么N-1個數的乘積只能為0，返回0；
Q為正數
返回Q，因為如果以0替換此時AN-1中的任一個數，所得到的PN-1為0，必然小于Q；
Q為負數
如果以0替換此時AN-1中的任一個數，所得到的PN-1為0，大于Q，乘積最大值為0。? ? ?2.????P為負數
根據“負負得正”的乘法性質，自然想到從N個整數中去掉一個負數，使得PN-1為一個正數。而要使這個正數最大，這個被去掉的負數的絕對值必須是數組中最小的。我們只需要掃描一遍數組，把絕對值最小的負數給去掉就可以了。
? ? ? 3.????P為正數
類似地，如果數組中存在正數值，那么應該去掉最小的正數值，否則去掉絕對值最大的負數值。
? ? 上面的解法采用了直接求N個整數的乘積P，進而判斷P的正負性的辦法，但是直接求乘積在編譯環境下往往會有溢出的危險（這也就是本題要求不使用除法的潛在用意），事實上可做一個小的轉變，不需要直接求乘積，而是求出數組中正數（+）、負數（-）和0的個數，從而判斷P的正負性，其余部分與以上面的解法相同。
? ? 在時間復雜度方面，由于只需要遍歷數組一次，在遍歷數組的同時就可得到數組中正數（+）、負數（-）和0的個數，以及數組中絕對值最小的正數和負數，時間復雜度為O（N）。 - 9月15日，中興面試：
小端系統
輸出結果為？（答案：32 20）union{int i;unsigned char ch[2]; }Student;int main() {Student student;student.i=0x1420;printf("%d %d",student.ch[0],student.ch[1]);return 0; } - 一道有趣的Facebook面試題：
給一個二叉樹，每個節點都是正或負整數，如何找到一個子樹，它所有節點的和最大？?
點評：
@某猛將兄:后序遍歷，每一個節點保存左右子樹的和加上自己的值。額外一個空間存放最大值。
@陳利人：同學們，如果你面試的是軟件工程師的職位，一般面試官會要求你在短時間內寫出一個比較整潔的，最好是高效的，沒有什么bug的程序。所以，光有算法不夠，還得多實踐。
寫完后序遍歷，面試官可能接著與你討論，a). 如果要求找出只含正數的最大子樹，程序該如何修改來實現？b). 假設我們將子樹定義為它和它的部分后代，那該如何解決？c). 對于b，加上正數的限制，方案又該如何？總之，一道看似簡單的面試題，可能能變換成各種花樣。
比如，面試管可能還會再提兩個要求：第一，不能用全局變量；第一，有個參數控制是否要只含正數的子樹。其它的，隨意，當然，編程風格也很重要。 - 谷歌面試題：
有幾百億的整數，分布的存儲到幾百臺通過網絡連接的計算機上，你能否開發出一個算法和系統，找出這幾百億數據的中值？就是在一組排序好的數據中居于中間的數。顯然，一臺機器是裝不下所有的數據。也盡量少用網絡帶寬。 - 小米，南京站筆試（原第20題）：
一個數組里，數都是兩兩出現的，但是有三個數是唯一出現的，找出這三個數。
點評：
3個數唯一出現，各不相同。由于x與a、b、c都各不相同，因此x^a、x^b、x^c都不等于0。具體答案請參看這兩篇文章：1、http://blog.csdn.net/w397090770/article/details/8032898，2、http://zhedahht.blog.163.com/blog/static/25411174201283084246412/。 - 9月19日，IGT面試：你走到一個分叉路口，有兩條路，每個路口有一個人，一個說假話，一個說真話，你只能問其中一個人僅一個問題，如何問才能得到正確答案？點評：答案是，問其中一個人：另一個人會說你的路口是通往正確的道路么？
- 9月19日，創新工廠筆試題：
給定一整型數組，若數組中某個下標值大的元素值小于某個下標值比它小的元素值，稱這是一個反序。
即：數組a[]; 對于i < j 且 a[i] > a[j],則稱這是一個反序。
給定一個數組，要求寫一個函數，計算出這個數組里所有反序的個數。
點評：
歸并排序，至于有的人說是否有O（N）的時間復雜度，我認為答案是否定的，正如老夢所說，下限就是nlgn，n個元素的數組的排列共有的排列是nlgn，n！（算法導論里面也用遞歸樹證明了：O(n*logn)是最優的解法，具體可以看下這個鏈接：）。然后，我再給一個鏈接，這里有那天筆試的兩道題目：http://blog.csdn.net/luno1/article/details/8001892。 - 9月20日，創新工廠南京站筆試：
已知字符串里的字符是互不相同的，現在任意組合，比如ab，則輸出aa，ab，ba，bb，編程按照字典序輸出所有的組合。
點評：非簡單的全排列問題（跟全排列的形式不同,abc 全排列的話，只有６個不同的輸出：http://blog.csdn.net/v_july_v/article/details/6879101）。本題可用遞歸的思想，設置一個變量表示已輸出的個數，然后當個數達到字符串長度時，就輸出。//假設str已經有序，from 一直很安靜 void perm(char *str, int size, int resPos) {if(resPos == size)print(result);else{for(int i = 0; i < size; ++i){result[resPos] = str[i];perm(str, size, resPos + 1);}} } - 9月21日，小米，電子科大&西安交通大學筆試題：
問：最后程序輸出是多少？點評：此題有陷阱，答題需謹慎！void fun() {unsigned int a = 2013;int b = -2;int c = 0;while (a + b > 0){a = a + b;c++;}printf("%d", c); }
點評：
針對上述第3題朋友圈的問題，讀者@互聯網的飛蟲提供的解法及代碼如下（有任何問題，歡迎指正，多謝）：#include <STDIO.H> #include <WINDOWS.H>int Friends(int n, int m , int* r[]);int main(int argc,char** argv) { int r[5][2] = {{1,2},{4,3},{6,5},{7,8},{7,9}};printf("有%d個朋友圈。\n",Friends(0,5,(int**)r));return 0; }int Friends(int n, int m, int* r[]) // 注意這里的參數很奇葩 {int *p = (int*)malloc(sizeof(int)*m*3);memset(p,0,sizeof(int)*m*3);int i = 0;int iCount = 0;int j = 0;int * q = (int*)r; // 這里很巧妙 將二維指針 強轉為一維指針for (i=0;i<m;++i){for (j=0;j<2;++j){p[i*3+j]=q[i*2+j]; // 注意這里二維數組向一維數組的轉換}p[i*3+j] = 0;}bool bFlag = false;for (i=0;i<m;++i){bFlag = false;if (p[i*3+2]==1){bFlag = true;}p[i*3+2] = 1;for (j=0;j<m;++j){if (i==j){continue;} if (p[i*3]==p[j*3] ||p[i*3] == p[j*3+1] ||p[i*3+1] == p[j*3+0] ||p[i*3+1] == p[j*3+1]){if (p[j*3+2]==1){bFlag = true;}p[j*3+2] = 1;}}if (!bFlag){++iCount;}}free(p); return iCount; } - 9月21日晚，海豚瀏覽器筆試題：
1、有兩個序列A和B,A=(a1,a2,...,ak),B=(b1,b2,...,bk),A和B都按升序排列，對于1<=i,j<=k，求k個最小的（ai+bj），要求算法盡量高效。
2、輸入：
L:“shit”“fuck”“you”
S:“shitmeshitfuckyou”
輸出：S中包含的L一個單詞，要求這個單詞只出現一次，如果有多個出現一次的，輸出第一個這樣的單詞
怎么做？ - 9月22日上午，百度西安站全套筆試題如下：
點評：上述的系統設計題簡單來講，是建立起按鍵號碼數字到人名(手機號)的映射關系，具體講，步驟解法如下圖所示：
3.算法與程序設計
第一題：
某個公司舉行一場羽毛球賽，有1001個人參加，現在為了評比出“最厲害的那個人”，進行淘汰賽，請問至少需要進行多少次比賽。
第二題
有100個燈泡，第一輪把所有燈泡都開啟，第二輪把奇數位的燈泡滅掉，第三輪每隔兩個燈泡，滅一個，開一個，依此類推。求100輪后還亮的燈泡。
點評：完全平方數，本人去58面試時，也遇到過與此類似的題。
第三題
有20個數組，每個數組里面有500個數組，降序排列，每個數字是32位的unit,求出這10000個數字中最大的500個。
點評：http://www.51nod.com/question/index.html#!questionId=647。
4.系統設計題
類似做一個手機鍵盤，上面有1到9個數字，每個數字都代表幾個字母（比如1代表abc三個字母，z代表wxyz等等），現在要求設計當輸入某幾個數字的組合時，查找出通訊錄中的人名及電話號碼。
其它的還有三道簡答題，比如線程的死鎖，內存的管理等等。最后，附一討論帖子：http://topic.csdn.net/u/20120923/18/7fd148b2-c000-4326-93a6-cb3bb8675702.html。 - 9月22日，微軟筆試：
T(n)=1(n<=1),T(n) = 25*T(n/5) + n^2，求算法的時間復雜度。更多題目請參見：http://blog.csdn.net/wonderwander6642/article/details/8008209。 - 9月23日，騰訊校招部分筆試題(特別提醒:下述試卷上的答案只是一考生的解答,非代表正確答案.如下面第11題答案選D,第12題答案選C,至于解釋可看這里:http://coolshell.cn/articles/7965.html)：
點評：根號九說，不過最后兩道大的附加題，全是秒殺99%海量數據處理面試題里的：http://blog.csdn.net/v_july_v/article/details/7382693，太感謝July了。 - 9月23日，搜狗校招武漢站筆試題：
一、已知計算機有以下原子操作
1、 賦值操作：b = a;
2、 ++a和a+1;
3、for( ){ ***}有限循環；
4、操作數只能為0或者正整數；
5、定義函數
實現加減乘操作
二、對一個鏈表進行排序，效率越高越好，LinkedList<Integer>.
附：9月15日，搜弧校招筆試題：http://blog.csdn.net/hackbuteer1/article/details/8015964。 - 搜狗校招筆試題：
100個任務，100個工人每人可做一項任務，每個任務每個人做的的費用為t[100][100],求一個分配任務的方案使得總費用最少。
點評：匈牙利算法，可以看看這篇文章：http://www.byvoid.com/blog/hungary/，及這個鏈接：http://www.51nod.com/question/index.html#!questionId=641。 - 9月24日，Google南京等站全套筆試題如下：
點評：
谷歌的筆試從易到難，基礎到復雜，涵蓋操作系統 網絡 數據結構 語言 數學思維 編程能力 算法能力，基本上能把一個人的能力全面考察出來。
至于上述2.1尋找3個數的中位數,請看讀者sos-phoenix給出的思路及代碼：
最壞情況下的比較次數：3 （次）2.1 // 采用兩兩比較的思路（目前沒想到更好的） if (a <= b) { if (b <= c) return b; else { if (a <=c) return c; else return a; } } else { if (a <= c) return a; else { if (b <= c) return c; else return b; } }
平均情況下的比較次數：(2×2 + 4*3)/6 = 8/3 （次）
此外這題，微博上的左耳朵耗子后來也給出了一個鏈接:http://stackoverflow.com/questions/1582356/fastest-way-of-finding-the-middle-value-of-a-triple，最后是微博上的梁斌penny的解答：http://weibo.com/1497035431/yFusm7obQ。其余更多參考答案請看本文評論下第93樓。 - 讀者來信，提供的幾個hulu面試題：
9月19號,hulu電面：
問題1 兩個骰子，兩個人輪流投，直到點數和大于6就停止，最終投的那個人獲勝。問先投那個人獲勝概率？
問題2 ?平面上n個圓，任意兩個都相交，是否有一條直線和所有的圓都有交點。
9月22號,上午hulu面試
問題1 100個人，每人頭上戴一頂帽子，寫有0..99的一個數，數可能重復，每個人都只能看到除自己以外其他人的帽子。每個人需要說出自己的帽子的數，一個人說對就算贏。點評：參考答案請看這個鏈接：http://www.51nod.com/question/index.html#!questionId=642。
問題2 n臺機器，每臺有負載，以和負載成正比的概率，隨機選擇一臺機器。「原題是希望設計O(1)的算法（預處理O(n)不可少，要算出每臺機器的比例），因為非O(1)的話，就trivial了：可以產生隨機數例如[0,1)然后，根據負載比例，2分或者直接循環檢查落入哪個區間，決定機器。 面試官想問，有沒更好的辦法，避免那種查找。即能否多次（常數次）調用隨機函數，擬合出一個概率分布」
問題3 ?行列都遞增的矩陣，求中位數。點評：http://www.51nod.com/question/index.html#!questionId=643，http://blog.csdn.net/v_july_v/article/details/7085669（楊氏矩陣查找問題）。 - 西安百度軟件研發工程師：
一面(2012.9.24)：
問的比較廣，涉及操作系統、網絡、數據結構。比較難的就2道題。
(1)10億個int型整數，如何找出重復出現的數字；
(2)有2G的一個文本文檔，文件每行存儲的是一個句子，每個單詞是用空格隔開的。問：輸入一個句子，如何找到和它最相似的前10個句子。（提示：可用倒排文檔）。
二面(2012.9.25)：
(1)一個處理器最多能處理m個任務。現在有n個任務需要完成，每個任務都有自己完成所需的時間。此外每個任務之間有依賴性，比如任務Ａ開始執行的前提是任務Ｂ必須完成。設計一個調度算法，使得這n這任務的完成時間最小；
(2)有一個排序二叉樹，數據類型是int型，如何找出中間大的元素；
(3)一個N個元素的整形數組，如何找出前K個最大的元素。
(4)給定一個凸四邊形，如何判斷一個點在這個平面上。
點評：本題的討論及參考答案請見這：http://www.51nod.com/question/index.html#!questionId=669。
運維部(2012.9.27)：
(1)堆和棧的區別；
(2)問如何數出自己頭上的頭發。 - 9月25日，人人網筆試題：
點評：參考答案請見，http://www.51nod.com/question/index.html#!questionId=671。 - 9月25日晚，創新工場校園招聘北郵站筆試：
- 9月25日，小米大連站筆試題：
1一共有100萬，抽中的2萬，每月增加4萬，問20個月能抽中的概率為：？
2 for(int i=0;i<strlen(s);i++){n+=I;}時間復雜度O（n）
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 (必須寫代碼）
??更多，還可以參見此文第三節節末：http://blog.csdn.net/v_july_v/article/details/6417600，或此文:http://www.360doc.com/content/11/0317/09/6329704_101869559.shtml。//void * memmove ( void * destination, const void * source, size_t num );) //是<string.h>的標準函數，其作用是把從source開始的num個字符拷貝到destination。 //最簡單的方法是直接復制，但是由于它們可能存在內存的重疊區，因此可能覆蓋了原有數據。 //比如當source+count>=dest&&source<dest時，dest可能覆蓋了原有source的數據。 //解決辦法是從后往前拷貝。 //對于其它情況，則從前往后拷貝。void* memmove(void* dest, void* source, size_t count){void* ret = dest;if (dest <= source || dest >= (source + count)){//正向拷貝//copy from lower addresses to higher addresseswhile (count --)*dest++ = *source++;}else{//反向拷貝//copy from higher addresses to lower addressesdest += count - 1;source += count - 1;while (count--)*dest-- = *source--;}return ret;}
??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/index.html#!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/index.html#!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
?lowermidupper
0612
7912
778
888
比較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 .讓你設計一個算法對數組排序，要求時間復雜度最小，O （nlogn）不得分，O（nk）得2分，如下圖所示：
讀者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、一段程序，求輸出。（考察靜態變量和模版類）
3、（1）實現二進制轉十進制。int g = 0; template<typename T> class B { public:int static fun(){static int value = ++g;return value;} };int main() {cout << B<int>::fun() << endl;cout << B<char>::fun() << endl;cout << B<float>::fun() << endl;cout << B<int>::fun() << endl;cout << B<long>::fun() << endl;return 0; }
（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/index.html#!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個作為密碼，請輸出所有可能組合。（偽碼\C\C++\JAVA）（10分）?
點評：如本文評論下第198樓所述，即從26+10=36個不同字符中選取3個字符的組合，用遞歸及非遞歸兩種方法，可以參照以下鏈接：
http://blog.csdn.net/wumuzi520/article/details/8087501（從n個數中選取m個數的組合數），主要代碼如下：
2、實現字符串反轉函數（10分）?//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] << "\t"; } 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); delete [] out; }
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%。設計一個系統來解決存儲和計算下面三個問題。可用分布式系統。
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)，問如何優化？
第二個，怎么樣求一個數的根號
點評：你是不是會想到一系列有關數學的東西，什么泰勒級數啊，什么牛頓法啊，具體編程可以如下代碼所示：
鏈接：http://www.51nod.com/question/index.html#!questionId=660。static void Main(string[] args){double k = 5;double n = 2, m = k;while (n != m){m = k / n;n = (m + n) / 2;}}
第三個，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」：
@綠色夾克衫：跟這個問題：http://www.51nod.com/question/index.html#!questionId=487?，是同一個問題。西芹_new<huangxy10@qq.com> 0:55:40 // 10_15.cpp : 定義控制臺應用程序的入口點。 //#include "stdafx.h" #include <iostream> 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 rightif( p1x+1<N && p2x+1<N ){p1x++;p2x++;int sum = map[p1x][p1y]+map[p2x][p2y];curMax += sum;dfs(index+1);curMax -= sum;p1x--;p2x--;}//down downif( p1y+1<N && p2y+1<N ){p1y++;p2y++;int sum = map[p1x][p1y]+map[p2x][p2y];curMax += sum;dfs(index+1);curMax -= sum;p1y--;p2y--;}//rdif( p1x+1<N && p2y+1<N ) {p1x++;p2y++;int sum = map[p1x][p1y]+map[p2x][p2y];curMax += sum;dfs(index+1);curMax -= sum;p1x--;p2y--;}//drif( p1y+1<N && 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;return 0; }?1、用動態規劃可以求解，大概思路就是同時DP 2次所走的狀態。先來分析一下這個問題，為了方便討論，先對矩陣做一個編號，且以5*5的矩陣為例（給這個矩陣起個名字叫M1）：M10 1 2 3 41 2 3 4 52 3 4 5 63 4 5 6 74 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）：2、N個整數（數的大小為0-255）的序列，把它們加密為K個整數（數的大小為0-255）.再將K個整數順序隨機打亂，使得可以從這亂序的K個整數中解碼出原序列。設計加密解密算法,且要求K<=15*N.M20 0 0 0 01 1 1 1 12 2 2 2 23 3 3 3 34 4 4 4 4M10 1 2 3 41 2 3 4 52 3 4 5 63 4 5 6 74 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)個狀態。M10 1 2 3 41 2 3 4 52 3 4 5?63 4 5?6?74 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/index.html#!answerId=598。
如果是：
1，N<=16,要求K<=16*N.
2，N<=16,要求K<=10*N.
3，N<=64,要求K<=15*N.
點評：http://www.51nod.com/question/index.html#!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)); assert(!(pdst<=psrc && psrc<pdst+count)); 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/index.html#!questionId=662。
2、補充：上述問題類似于編程之美上的下述一題「以下內容摘自編程之美第3.3節」：//動態規劃：//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個（相同就不用替換）。
許多程序會大量使用字符串。對于不同的字符串，我們希望能夠有辦法判斷其相似程度。我們定義了一套操作方法來把兩個不相同的字符串變得相同，具體的操作方法為：
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; elsereturn pBEnd – pBBegin + 1;}if(pBBegin > pBEnd){if(pABegin > pAEnd)return 0;elsereturn 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。
BTW，群友braveheart89也整理了這套筆試題：http://blog.csdn.net/braveheart89/article/details/8074657。
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） - 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的冪來弄：鏈接：1，http://www.51nod.com/question/index.html#!questionId=278；2、這里也有一參考答案：http://blog.csdn.net/yuan8080/article/details/5705567。
@方程：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; - 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萬首歌的曲庫中為他們隨機選擇一首，同一用戶不能推送重復的，設計方案，內存盡可能小，寫出數據結構與算法。 - ?
-
從今天開始，在繼續整理筆試面試題的同時，將整理上面已經收錄的一系列筆試面試題的答案，歡迎諸君與我共同討論.思考.做之「參與的方式為：你除了可以直接評論在本文之下,你也可以通過郵件：zhoulei0907@yahoo.cn或私信：http://weibo.com/julyweibo?給我，或自己寫一篇博文把鏈接發給我收錄,無任何語言限制」2012.10.19...
?? ? ? ? ? ?本blog算法交流群：30382647；高級C/C++程序員群：125706194；Machine Learning讀書會·上海：215665171。
注意：
?? ?請所有凡是已經在本文評論下show 出了你的代碼code(含思路)的朋友：「10.13日之前第一批：zhutou100hao，zzran，yuankangjian_2，caopengcs，iamzhaiwei，milo_zhang_bs， tpm0513， huangxy10，宇智波鼬，sos-phoenix，aini201，aini201，xsfrank，zz198808 ，Dracula777，li850221，ghostjay0216，a81895898，donghang0535， iamzhaiwei，fengchaokobe，umissmesomuch，believe3，aini201， liuliuliu11，qichi_bj」+ 「10月13日以后第2批： 杜，litaoye，smilearchery，jiadong1125，nwpulei，wumuzi520，..，盡快發“ID號+你在本文評論下做的題目的題號”到我郵箱「zhoulei0907@yahoo.cn」或者聯系QQ：786 165 179，我會在盡快發給你 十五個經典算法研究的 可自行編輯修改的WORD文檔，或者直接轉發加群下載得到：http://weibo.com/1580904460/z4fqHcWDV，歡迎各位及其他朋友們繼續參與，感謝諸位。
?? ?本文評論下的所有代碼未經仔細驗證，如果讀者發現其中任何問題或錯誤，歡迎指正，經驗證后，我也會給你發送文檔，其他此前通過私信或郵件或QQ發過我題目或答案的朋友們如若需要也請發郵件：“名字+ 原文中的題號” 給我以便傳送文檔。July、二零一二年十月十六日。
?
?
后記
? ? 經過上面這么多筆試面試題目的了解，你自會看到，除了少部分特別難的算法題，大部分都是考察的基礎，故校招筆試面試的關鍵是你的80%的基礎知識和編程實踐能力 + 20%的算法能力（特別強調算法能力的則此項比例加大）。
最后，告訴諸位一個好消息，微軟面試100題系列(截取此文：http://blog.csdn.net/v_july_v/article/details/6543438第一部分編輯而成，共計11篇文章，300多道面試題)的PDF文檔近期已經制作出來，其下載地址為：http://download.csdn.net/detail/v_july_v/4583815。
? ? OK，以上的一切都是我喜歡且我樂意做的，我愿同各位朋友享受這一切.(如果你身邊有正在參加校招/筆試/面試的朋友，歡迎把此文轉給他/她，舉手之勞，助人無限)，謝謝。July，二零一二年九月。
?
updated
??? 近期九月十月的筆試面試題已經整理的差不多了，10月也即將過去，衷心祝愿各位都能拿到滿意的offer，當然，若還能與我分享你的快樂，則再高興不過了！
??? 分享幾點體會：
- 編碼能力是你以后干任何開發工作的基礎，剛開始時不要去糾結是否該去學算法，若是想干開發，多coding就是了（現在，就把你的代碼評論到本文之下吧）！
- 找到你的興趣和熱愛之所在，它們會為你指導一切！我搞研究便是瞎弄，幾乎沒有任何什么學習方法，一切完全憑借興趣和熱愛！當你慢慢開始有獨立思考的意識時，你就知道一切該如何下手了！
??? 感謝所有在本文下評論，show出你思路和代碼的朋友，下篇blog，再見！July、二零一二年十月二十九日，老媽生日之際。
![[.NET] 建構子中傳遞子對象的對象](http://pic.xiahunao.cn/[.NET] 建構子中傳遞子對象的對象)
方法和iteritems()方法有什么不同?【面試題詳解】...)
)
函數和fetchall()函數的區別)