騰訊互娛面試流程
15號晚上7點多，正在炒菜做飯，騰訊忽然打電話來問我對他們的Linux C++的職位是否感興趣，我表達了我感興趣之後，就開始了一段簡短的電話面試，電話面試主要內容：C++和TCP socket通訊的一些基礎知識。之後就問我一道演算法題：10億個整數，隨機生成，可重複，求最大的前1萬個。當時我一下子就蒙了，沒反應過來，何況我還正在燒著菜呢，所以我就沒細想，說了一個連我都鄙視我的思路：我說匯入資料庫，然後用select語句選出最大的前1萬個。可能我的答案連面試官都無語了，所以他就沒再往下問了，不過他還是通知我明天16號早上去騰訊大廈筆試，由於我明天沒空，就推遲到了17號早上10點。至此，整個電話面試就結束了。過後，我想了想，10億個整數選前1萬個大數，其實可以用：分治法+hash+多路歸併排序來做，比如說，先把10億個整數對1000取模，儲存到1000個檔案中，然後對每一個檔案進行內部排序(比如快速排序，從大到小排序)，然後再對這1000個檔案進行多路歸併，取出前1萬個最大的數即可。
17號早上，懷著忐忑不安的心情，終於來到了騰訊大廈，在前臺說明情況後，領了一個臨時訪問牌，一個看起來30多歲的中年人(暫且稱為面試官A)接待了我，給我一份筆試題，時間為1小時。5道程式輸出寫結果或者程式找錯，5道程式設計題。這5道程式設計題大概為：
1、將一個4位元組的整數的二進位制表示中的001替換為011，輸出替換後的整數。
2、將一個數組右移幾位，比如陣列為1 2 3 4，右移一位即為4 1 2 3。
3、輸入一個表示十六進位制的字串，轉換為十進位制的整數輸出。
4、單鏈表反轉。
5、一個8*8的方格子，A點在左下角，B點在右上角，求A點到B點的最短路徑有多少條。
第1題，我理解錯題意了，順便鄙視一下自己，我當時的想法是這樣的：整數有正有負，不能拿該整數直接右移，所以我用了一個unsigned int mode = 7進行左移，是直接拿整數與mode相與，得到的結果與001比較，相同就替換，不同就把mode左移3位再與整數相與。面試官A直接指出我的思路有問題，相等替換後mode左移3位，不相等應該將mode左移1位，而不是左移3位，只有相等才把mode左移3位。這裡順便說一下，筆試完之後，面試官A是拿著你的筆試題一題一題的問你，根據你的題目結果要你說出你的計算過程的。答案：將一個4位元組整數的二進位制表示中的001替換為011
第2題，由於這道題我之前做過，思路就是：先把左邊反轉，再把右邊反轉，最後把整個陣列反轉就可以得到結果。但是悲劇的是，面試官A要我用數學證明我這種方法的正確性，o(□)o，最後我只能說：我之前做過這道題。如果當時，我能套用線性代數中矩陣的轉置的思想來說明這道題，那麼這道題的證明可能說得過去。所以說，要對你寫的程式碼負責，要知其然，更要知其所以然。類似題目：左旋轉字串
第3題，進位制轉換，簡單，不過要分別考慮大小寫字母。
第4題，簡單，就不說了。答案在我的另一篇博文：單鏈表逆置
第5題，我也是想錯了方向，由於沒有時間了，程式碼我沒寫，我只寫了個思路：即從A點開始用廣度優先搜尋，第一個到達B點的肯定是最短路徑，記下此時A點到B點的步數，然後統計從A到B點等於這個步數的個數。其實，廣度優先搜尋只能求出最短路徑，但不能求出所有的最短路徑個數，要想求出所有最短路徑的個數，要用回溯法(後面我會給出程式碼)。想想當時面試的時候還振振有詞的向面試官A講解我的思路，也不知道面試官A是怎麼想的，也不指出我的錯誤，怕是怕我難堪吧。
面試官A面完之後已經是12點多了，這是又來了一個27、8歲的大哥(暫且稱為面試官B)來面試我，一上來就給我一道程式設計題，實現大數相加，給出程式碼。我又刷刷的寫了20多分鐘，認為沒問題了，就拿給面試官B看，看了一小會，就指出我的程式碼錯在什麼地方了，(哎，畢竟是手寫程式碼，錯誤肯定很多)，要我改正，一步一步的引導我將我的程式碼改正，非常和藹的一位大哥哥，也是和我聊的最久的，聊到了下午2點多，差不多兩個鐘頭，期間主要問的問題各種各樣都有：
1、技術相關：map的實現機制是怎麼樣的`啊;模板類的偏特化;動態載入dll和靜態載入dll的區別;執行緒和程序的區別;TCP的四次揮手協議;給定兩個陣列a和b，求所有在a陣列中不在b陣列的元素;快速排序的平均時間複雜度是多少，證明它的平均時間複雜度等。這些問題我都一一說出了我的答案，主要是我看過一點
2、其他：3點一刻，求此時時針和分針夾角的度數;對騰訊這個公司怎麼看;為什麼離職;個人規劃等。
面試官B面完之後，叫我先出去吃午飯，下午回來還有一次面試。吃飯歸來之後，又來了一位也是27、8歲的大哥(暫且稱為面試官C)，給我幾道邏輯題，要我20分鐘寫出答案，在我和他講解我的邏輯題之後，他問了幾個我不熟悉的或者已經記不清答案的問題：一個程序由哪些方面構成，我記得
總結：
1、沒有大公司面試經驗，並且由於事先也完全沒有做準備，好像趕鴨子上架
2、基礎一定要紮實，C++，資料結構和演算法，作業系統，網路程式設計要熟悉。
3、對自己寫的程式碼負責
4、騰訊的員工非常友好
近期目標：
1、看資料結構和演算法
2、熟悉C++程式設計規範。
3、多看別人寫的優秀原始碼，爭取自己寫的程式碼簡潔易懂
最後：
給出筆試的最後一道程式設計題的題目和我寫的答案，如果有任何問題，請指正。
題目：給定一個8*8的方格子，如下圖所示，求A點到B點的最短路徑有多少條?用演算法實現。
答：從圖中可以看出，A點到B點的最短路徑為16，即A點橫走8小格，縱走8小格才能最快到達B點，這是排列組合的問題，即從最短路徑16中選取8個橫走的小格子(或者從最短路徑16中選取8個縱走的小格子)。所以從A點到B點的最短路徑條數，直接可以算出來，即為：
程式碼如下：
size_t g_num = 0; //統計A點到B點的最短路徑條數
void shortestPathNumber(char grid[9][9], int row, int col, int &step)
{
if (row < 0 || row > 8 || col < 0 || col > 8 || grid[row][col] == '*' || step > 16)
{
return;
}
if (row == 0 && col == 8)
{
if (step == 16) //已到達B點，且等於最短路徑16，就累加
{
g_num++;
}
}
else
{
grid[row][col] = '*'; //標記該點已訪問
step++;
shortestPathNumber(grid, row, col + 1, step);
shortestPathNumber(grid, row + 1, col, step);
shortestPathNumber(grid, row, col - 1, step);
shortestPathNumber(grid, row - 1, col, step);
grid[row][col] = '.'; //回溯
step--;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
char grid[9][9] = {0};
int step = 0;
shortestPathNumber(grid, 8, 0, step); //從A點開始搜尋
cout<<"A點到B點的最短路徑條數為: "<<g_num<<endl;< p="">
return 0;
}
【騰訊互娛面試流程】相關文章：