騰訊社招面試經歷
前提:本人2011年畢業於一個普通本科,工作不到2年。
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;
}
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點的最短路徑條數爲: "<
return 0;
}
運行界面如下:
-
【薦】面試自我評價
在平時的學習、工作或生活中,我們經常會被要求寫一份自我評價,自我評價是個人對自己思想、願望、行爲和個性特點的判斷和評價。那麼你有了解過自我評價嗎?以下是小編收集整理的面試自我評價,歡迎閱讀,希望大家能夠喜歡。面試自我評價1【財務面試自我評價範例一】具...
-
面試自我評價 (13篇)
在學習、工作或生活中,我們都經常看到自我評價的身影,自我評價是一種重要的評價形式,它屬於人的自我概念的重要內容之一。相信寫自我評價是一個讓許多人都頭痛的問題,下面是小編精心整理的面試自我評價,歡迎大家分享。面試自我評價篇1我具有積極向上的生活態度,在工...
-
模擬面試大賽活動策劃
模擬面試大賽活動策劃1一、活動前言在當前社會就業形勢異常嚴峻的前提下,大學生普遍對於未來的職業生涯缺乏長遠的規劃和有針對性的準備,對社會就業方面的具體情況缺乏切身的體會,導致學習目標不明確,甚至失去對未來目標的追求,而企業也無法在應屆大學畢業生中補充...
-
文藝部面試三分鐘合集8篇
文藝部面試三分鐘1尊敬的領導和老師:我叫xxx,會計系a班學生,來自美麗的瓷都景德鎮,我自薦的學生會職務是文藝部(幹事)。水本無波,相蕩而起漣猗,石本無華,相撞而起火花。融入到學生會這個團體中,除了能以自身所長爲同學們服務,還能夠在工作實踐中吸取、借鑑和學習他人長...