騰訊社招面試經歷與問題總結
我要評論前提：本人2011年畢業(yè)于一個普通本科，工作不到2年。
15號晚上7點多，正在炒菜做飯，騰訊忽然打電話來問我對他們的Linux C++的職位是否感興趣，我表達了我感興趣之后，就開始了一段簡短的電話面試，電話面試主要內容：C++和TCP socket通信的一些基礎知識。之后就問我一道算法題：10億個整數(shù)，隨機生成，可重復，求最大的前1萬個。當時我一下子就蒙了，沒反應過來，何況我還正在燒著菜呢，所以我就沒細想，說了一個連我都鄙視我的思路：我說導入數(shù)據(jù)庫，然后用select語句選出最大的前1萬個?？赡芪业拇鸢高B面試官都無語了，所以他就沒再往下問了，不過他還是通知我明天16號早上去騰訊大廈筆試，由于我明天沒空，就推遲到了17號早上10點。至此，整個電話面試就結束了。過后，我想了想，10億個整數(shù)選前1萬個大數(shù)，其實可以用：分治法+hash+多路歸并排序來做，比如說，先把10億個整數(shù)對1000取模，存儲到1000個文件中，然后對每一個文件進行內部排序(比如快速排序，從大到小排序)，然后再對這1000個文件進行多路歸并，取出前1萬個最大的數(shù)即可。
17號早上，懷著忐忑不安的心情，終于來到了騰訊大廈，在前臺說明情況后，領了一個臨時訪問牌，一個看起來30多歲的中年人(暫且稱為面試官A)接待了我，給我一份筆試題，時間為1小時。5道程序輸出寫結果或者程序找錯，5道編程題。這5道編程題大概為：
1、將一個4字節(jié)的整數(shù)的二進制表示中的001替換為011，輸出替換后的整數(shù)。
2、將一個數(shù)組右移幾位，比如數(shù)組為1 2 3 4，右移一位即為4 1 2 3。
3、輸入一個表示十六進制的字符串，轉換為十進制的整數(shù)輸出。
4、單鏈表反轉。
5、一個8*8的方格子，A點在左下角，B點在右上角，求A點到B點的最短路徑有多少條。
第1題，我理解錯題意了，順便鄙視一下自己，我當時的想法是這樣的：整數(shù)有正有負，不能拿該整數(shù)直接右移，所以我用了一個unsigned int mode = 7進行左移，是直接拿整數(shù)與mode相與，得到的結果與001比較，相同就替換，不同就把mode左移3位再與整數(shù)相與。面試官A直接指出我的思路有問題，相等替換后mode左移3位，不相等應該將mode左移1位，而不是左移3位，只有相等才把mode左移3位。這里順便說一下，筆試完之后，面試官A是拿著你的筆試題一題一題的問你，根據(jù)你的題目結果要你說出你的計算過程的。
題目：將一個4字節(jié)整數(shù)的二進制表示中的001替換為011
答：
int replace(int num)
{
unsigned int mode3bit = 7;
unsigned int mode1bit = 1;
int shift = 0;
int result = 0;
while (shift < 32)
{
while (shift < 32 && (num & (mode3bit<<shift)) != (1<<shift))
{
result += (num & (mode1bit<<shift));
shift++;
}
if (shift >= 32)
{
break;
}
else if (32 - shift < 3) //高位不足3位
{
result += (num & (mode3bit<<shift));
break;
}
result += (3<<shift);
shift += 3;
}
return result;
}
int _tmain(int argc, _TCHAR* argv[])
{
int num = 12345678; //0b0000 0000 1011 1100 0110 0001 0100 1110
assert(29156190 == replace(num)); //29156190 0b0000 0001 1011 1100 1110 0011 0101 1110
num = 1227133513; //0b0100 1001 0010 0100 1001 0010 0100 1001
assert(1533916891 == replace(num)); //1533916891 0b0101 1011 0110 1101 1011 0110 1101 1011
num = 613566757; //0b0010 0100 1001 0010 0100 1001 0010 0101
assert(1840700269 == replace(num)); //1840700269 0b0110 1101 1011 0110 1101 1011 0110 1101
num = -809737911; //0b1100 1111 1011 1100 0110 0001 0100 1001
assert(-541269157 == replace(num)); //-541269157 0b1101 1111 1011 1100 1110 0011 0101 1011
num = -920350135; //0b1100 1001 0010 0100 1001 0010 0100 1001
assert(-613566757 == replace(num)); //-613566757 //0b1101 1011 0110 1101 1011 0110 1101 1011
return 0;
}
第2題，由于這道題我之前做過，思路就是：先把左邊反轉，再把右邊反轉，最后把整個數(shù)組反轉就可以得到結果。但是悲劇的是，面試官A要我用數(shù)學證明我這種方法的正確性，o(╯□╰)o，最后我只能說：我之前做過這道題。如果當時，我能套用線性代數(shù)中矩陣的轉置的思想來說明這道題，那么這道題的證明可能說得過去。所以說，要對你寫的代碼負責，要知其然，更要知其所以然。類似題目：
題目：左旋轉字符串
要求：對長度為n的字符串操作的時間復雜度為O(n)，輔助內存為O(1)。
舉例：把字符串abcdef左旋轉2位得到字符串cdefab。
答：
#include "stdafx.h"
#include <iostream>
using namespace std;
void swap(char *str, int begin, int end)
{
char ch;
while (begin < end)
{
ch = *(str + begin);
*(str + begin) = *(str + end);
*(str + end) = ch;
begin++;
end--;
}
}
void Rotate(char *str, int length ,int m)
{
if (NULL == str || length == 1)
{
return;
}
swap(str, 0, m - 1);
swap(str, m, length - 1);
swap(str, 0, length - 1);
}
int _tmain(int argc, _TCHAR* argv[])
{
char chArr[] = "abcdef";
char *p = chArr;
cout<<p<<endl;
Rotate(p, strlen(chArr), 2);
cout<<p<<endl;
return 0;
}
運行界面如下：
第3題，進制轉換，簡單，不過要分別考慮大小寫字母。
第4題：
題目：單鏈表逆置
舉例：原來鏈表為1->2->3->4->5翻轉為5->4->3->2->1
鏈表結點定義如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
答：
#include "stdafx.h"
#include <iostream>
#include <fstream>
using namespace std;
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
//構造鏈表
void CreateList(ListNode *&pHead)
{
fstream fin("list.txt");
ListNode *pNode = NULL;
ListNode *pTmp = NULL;
int data;
fin>>data;
while (data)
{
pNode = new ListNode;
pNode->m_nKey = data;
pNode->m_pNext = NULL;
if (NULL == pHead)
{
pHead = pNode;
pTmp = pNode;
}
else
{
pTmp->m_pNext = pNode;
pTmp = pNode;
}
fin>>data;
}
}
//翻轉單鏈表
void ReverseLink(ListNode *&pHead)
{
if (NULL == pHead)
{
return;
}
ListNode *pNode = pHead;
ListNode *Prev = NULL;
ListNode *pNext = NULL;
while (NULL != pNode)
{
pNext = pNode->m_pNext;
if (NULL == pNext)
{
pHead = pNode;
}
pNode->m_pNext = Prev;
Prev = pNode;
pNode = pNext;
}
}
void PrintList(ListNode *pHead)
{
if (NULL == pHead)
{
return;
}
ListNode *pNode = pHead;
while (NULL != pNode)
{
cout<<pNode->m_nKey<<" ";
pNode = pNode->m_pNext;
}
cout<<endl;
}
int _tmain(int argc, _TCHAR* argv[])
{
ListNode *pHead = NULL;
cout<<"原來的鏈表：";
CreateList(pHead);
PrintList(pHead);
ReverseLink(pHead);
cout<<"翻轉的鏈表：";
PrintList(pHead);
return 0;
}
運行界面如下：
建造鏈表的list.txt文件如下：
12 11 10 9 8 7 6 5 4 3 2 1 0
第5題，我也是想錯了方向，由于沒有時間了，代碼我沒寫，我只寫了個思路：即從A點開始用廣度優(yōu)先搜索，第一個到達B點的肯定是最短路徑，記下此時A點到B點的步數(shù)，然后統(tǒng)計從A到B點等于這個步數(shù)的個數(shù)。其實，廣度優(yōu)先搜索只能求出最短路徑，但不能求出所有的最短路徑個數(shù)，要想求出所有最短路徑的個數(shù)，要用回溯法(后面我會給出代碼)。想想當時面試的時候還振振有詞的向面試官A講解我的思路，也不知道面試官A是怎么想的，也不指出我的錯誤，怕是怕我難堪吧。
面試官A面完之后已經是12點多了，這是又來了一個27、8歲的大哥(暫且稱為面試官B)來面試我，一上來就給我一道編程題，實現(xiàn)大數(shù)相加，給出代碼。我又刷刷的寫了20多分鐘，認為沒問題了，就拿給面試官B看，看了一小會，就指出我的代碼錯在什么地方了，(哎，畢竟是手寫代碼，錯誤肯定很多)，要我改正，一步一步的引導我將我的代碼改正，非常和藹的一位大哥哥，也是和我聊的最久的，聊到了下午2點多，差不多兩個鐘頭，期間主要問的問題各種各樣都有：
1、技術相關：map的實現(xiàn)機制是怎么樣的啊；模板類的偏特化；動態(tài)加載dll和靜態(tài)加載dll的區(qū)別；線程和進程的區(qū)別；TCP的四次揮手協(xié)議；給定兩個數(shù)組a和b，求所有在a數(shù)組中不在b數(shù)組的元素；快速排序的平均時間復雜度是多少，證明它的平均時間復雜度等。這些問題我都一一說出了我的答案，主要是我看過一點<stl源碼剖析>、<算法導論>，所以沒覺的有什么難度，好像他也覺得我回答的還不錯。
2、其他：3點一刻，求此時時針和分針夾角的度數(shù)；對騰訊這個公司怎么看；為什么離職；個人規(guī)劃等。
面試官B面完之后，叫我先出去吃午飯，下午回來還有一次面試。吃飯歸來之后，又來了一位也是27、8歲的大哥(暫且稱為面試官C)，給我?guī)椎肋壿嬵}，要我20分鐘寫出答案，在我和他講解我的邏輯題之后，他問了幾個我不熟悉的或者已經記不清答案的問題：一個進程由哪些方面構成，我記得<windows核心編程>一書上有講，但我記不清了，吱吱嗚嗚也沒說出一個所以然來，之后又問了一個我不懂怎樣回答的問題：你認為你的優(yōu)勢是什么？作為一個二流學校畢業(yè)的屌絲，工作還不到2年，沒學歷，項目經驗又沒什么亮點。實在不懂怎么說，憋了半天只說出一句：我基礎還行。之后就沒在問問題了，最后面試官B通知我可以回去了。哎，這可能就是導致我最后悲劇的原因吧。
總結：
1、沒有大公司面試經驗，并且由于事先也完全沒有做準備，好像趕鴨子上架
2、基礎一定要扎實，C++，數(shù)據(jù)結構和算法，操作系統(tǒng)，網絡編程要熟悉。
3、對自己寫的代碼負責
4、騰訊的員工非常友好
近期目標：
1、看數(shù)據(jù)結構和算法
2、熟悉C++編程規(guī)范。
3、多看別人寫的優(yōu)秀源碼，爭取自己寫的代碼簡潔易懂
最后：
給出筆試的最后一道編程題的題目和我寫的答案，如果有任何問題，請指正。
題目：給定一個8*8的方格子，如下圖所示，求A點到B點的最短路徑有多少條？用算法實現(xiàn)。
答：從圖中可以看出，A點到B點的最短路徑為16，即A點橫走8小格，縱走8小格才能最快到達B點，這是排列組合的問題，即從最短路徑16中選取8個橫走的小格子(或者從最短路徑16中選取8個縱走的小格子)。所以從A點到B點的最短路徑條數(shù)，直接可以算出來，即為：
代碼如下：
size_t g_num = 0; //統(tǒng)計A點到B點的最短路徑條數(shù)
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點的最短路徑條數(shù)為: "<<g_num<<endl;
return 0;
}
運行界面如下：
相關文章
- 這篇文章主要介紹了騰訊后端面試經歷與經驗,總結分析了騰訊面試過程中所經歷的問題、面試流程、相關注意事項與失敗經驗總結,需要的朋友可以參考下2019-11-25
- 這篇文章主要介紹了2019年騰訊最新前端工程師面試題(附答案),小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2019-11-21
- 這篇文章主要介紹了騰訊面試算法題之編碼問題,結合具體案例形式分析了基于java的編碼轉換相關算法原理與操作技巧,需要的朋友可以參考下2019-10-08
- 這篇文章主要介紹了騰訊的外包c++面試經歷,總結記錄了一次騰訊C++面試的經歷,包括面試的流程、面試題目與相應的參考答案,需要的朋友可以參考下2019-09-29
- 這篇文章主要介紹了騰訊游戲客戶端開發(fā)面試經歷,整理記錄了騰訊游戲開發(fā)面試中遇到的各種問題與心得體會,需要的朋友可以參考下2019-09-24
- 這篇文章主要介紹了騰訊游戲客戶端開發(fā)面試經歷,總結分享了騰訊游戲客戶端開發(fā)面試所涉及到的考點與注意事項,需要的朋友可以參考下2019-09-20
9月最新184道阿里、百度、騰訊、頭條Java面試題合集(小結)
這篇文章主要介紹了9月最新184道阿里、百度、騰訊、頭條Java面試題合集，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2019-09-09- 這篇文章主要介紹了騰訊前端面試題相關知識點,整理總結了騰訊前端面試中所涉及的相關基礎知識點與疑難問題,需要的朋友可以參考下2019-08-27
這篇文章主要介紹了2019騰訊后臺開發(fā)詳細面試流程詳解,小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2019-08-09- 本文詳細的介紹了SpringMvc面試題，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2019-04-28
