騰訊社招面試經(jīng)歷與問題總結(jié)

發(fā)布時間：2019-11-27 12:36:57 作者：hong2511

這篇文章主要介紹了騰訊社招面試經(jīng)歷與問題,總結(jié)分析了騰訊社招面試過程中所遇到的各種問題及相應(yīng)的參考答案,具有一定參考借鑒價值,需要的朋友可以參考下

　　前提：本人2011年畢業(yè)于一個普通本科，工作不到2年。

　　15號晚上7點多，正在炒菜做飯，騰訊忽然打電話來問我對他們的Linux C++的職位是否感興趣，我表達了我感興趣之后，就開始了一段簡短的電話面試，電話面試主要內(nèi)容：C++和TCP socket通信的一些基礎(chǔ)知識。之后就問我一道算法題：10億個整數(shù)，隨機生成，可重復(fù)，求最大的前1萬個。當(dāng)時我一下子就蒙了，沒反應(yīng)過來，何況我還正在燒著菜呢，所以我就沒細想，說了一個連我都鄙視我的思路：我說導(dǎo)入數(shù)據(jù)庫，然后用select語句選出最大的前1萬個。可能我的答案連面試官都無語了，所以他就沒再往下問了，不過他還是通知我明天16號早上去騰訊大廈筆試，由于我明天沒空，就推遲到了17號早上10點。至此，整個電話面試就結(jié)束了。過后，我想了想，10億個整數(shù)選前1萬個大數(shù)，其實可以用：分治法+hash+多路歸并排序來做，比如說，先把10億個整數(shù)對1000取模，存儲到1000個文件中，然后對每一個文件進行內(nèi)部排序(比如快速排序，從大到小排序)，然后再對這1000個文件進行多路歸并，取出前1萬個最大的數(shù)即可。

　　17號早上，懷著忐忑不安的心情，終于來到了騰訊大廈，在前臺說明情況后，領(lǐng)了一個臨時訪問牌，一個看起來30多歲的中年人(暫且稱為面試官A)接待了我，給我一份筆試題，時間為1小時。5道程序輸出寫結(jié)果或者程序找錯，5道編程題。這5道編程題大概為：

　　1、將一個4字節(jié)的整數(shù)的二進制表示中的001替換為011，輸出替換后的整數(shù)。

　　2、將一個數(shù)組右移幾位，比如數(shù)組為1 2 3 4，右移一位即為4 1 2 3。

　　3、輸入一個表示十六進制的字符串，轉(zhuǎn)換為十進制的整數(shù)輸出。

　　4、單鏈表反轉(zhuǎn)。

　　5、一個8*8的方格子，A點在左下角，B點在右上角，求A點到B點的最短路徑有多少條。

　　第1題，我理解錯題意了，順便鄙視一下自己，我當(dāng)時的想法是這樣的：整數(shù)有正有負，不能拿該整數(shù)直接右移，所以我用了一個unsigned int mode = 7進行左移，是直接拿整數(shù)與mode相與，得到的結(jié)果與001比較，相同就替換，不同就把mode左移3位再與整數(shù)相與。面試官A直接指出我的思路有問題，相等替換后mode左移3位，不相等應(yīng)該將mode左移1位，而不是左移3位，只有相等才把mode左移3位。這里順便說一下，筆試完之后，面試官A是拿著你的筆試題一題一題的問你，根據(jù)你的題目結(jié)果要你說出你的計算過程的。

題目：將一個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題，由于這道題我之前做過，思路就是：先把左邊反轉(zhuǎn)，再把右邊反轉(zhuǎn)，最后把整個數(shù)組反轉(zhuǎn)就可以得到結(jié)果。但是悲劇的是，面試官A要我用數(shù)學(xué)證明我這種方法的正確性，o(╯□╰)o，最后我只能說：我之前做過這道題。如果當(dāng)時，我能套用線性代數(shù)中矩陣的轉(zhuǎn)置的思想來說明這道題，那么這道題的證明可能說得過去。所以說，要對你寫的代碼負責(zé)，要知其然，更要知其所以然。類似題目：

題目：左旋轉(zhuǎn)字符串

要求：對長度為n的字符串操作的時間復(fù)雜度為O(n)，輔助內(nèi)存為O(1)。

舉例：把字符串a(chǎn)bcdef左旋轉(zhuǎn)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題，進制轉(zhuǎn)換，簡單，不過要分別考慮大小寫字母。

　　第4題：

題目：單鏈表逆置

舉例：原來鏈表為1->2->3->4->5翻轉(zhuǎn)為5->4->3->2->1

鏈表結(jié)點定義如下：

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;
};

//構(gòu)造鏈表
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;
    }
}

//翻轉(zhuǎn)單鏈表
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<<"翻轉(zhuǎn)的鏈表：";
    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ù)，要用回溯法(后面我會給出代碼)。想想當(dāng)時面試的時候還振振有詞的向面試官A講解我的思路，也不知道面試官A是怎么想的，也不指出我的錯誤，怕是怕我難堪吧。

　　面試官A面完之后已經(jīng)是12點多了，這是又來了一個27、8歲的大哥(暫且稱為面試官B)來面試我，一上來就給我一道編程題，實現(xiàn)大數(shù)相加，給出代碼。我又刷刷的寫了20多分鐘，認為沒問題了，就拿給面試官B看，看了一小會，就指出我的代碼錯在什么地方了，(哎，畢竟是手寫代碼，錯誤肯定很多)，要我改正，一步一步的引導(dǎo)我將我的代碼改正，非常和藹的一位大哥哥，也是和我聊的最久的，聊到了下午2點多，差不多兩個鐘頭，期間主要問的問題各種各樣都有：

　　1、技術(shù)相關(guān)：map的實現(xiàn)機制是怎么樣的啊；模板類的偏特化；動態(tài)加載dll和靜態(tài)加載dll的區(qū)別；線程和進程的區(qū)別；TCP的四次揮手協(xié)議；給定兩個數(shù)組a和b，求所有在a數(shù)組中不在b數(shù)組的元素；快速排序的平均時間復(fù)雜度是多少，證明它的平均時間復(fù)雜度等。這些問題我都一一說出了我的答案，主要是我看過一點<stl源碼剖析>、<算法導(dǎo)論>，所以沒覺的有什么難度，好像他也覺得我回答的還不錯。

　　2、其他：3點一刻，求此時時針和分針夾角的度數(shù)；對騰訊這個公司怎么看；為什么離職；個人規(guī)劃等。

　　面試官B面完之后，叫我先出去吃午飯，下午回來還有一次面試。吃飯歸來之后，又來了一位也是27、8歲的大哥(暫且稱為面試官C)，給我?guī)椎肋壿嬵}，要我20分鐘寫出答案，在我和他講解我的邏輯題之后，他問了幾個我不熟悉的或者已經(jīng)記不清答案的問題：一個進程由哪些方面構(gòu)成，我記得<windows核心編程>一書上有講，但我記不清了，吱吱嗚嗚也沒說出一個所以然來，之后又問了一個我不懂怎樣回答的問題：你認為你的優(yōu)勢是什么？作為一個二流學(xué)校畢業(yè)的屌絲，工作還不到2年，沒學(xué)歷，項目經(jīng)驗又沒什么亮點。實在不懂怎么說，憋了半天只說出一句：我基礎(chǔ)還行。之后就沒在問問題了，最后面試官B通知我可以回去了。哎，這可能就是導(dǎo)致我最后悲劇的原因吧。

總結(jié)：

　　1、沒有大公司面試經(jīng)驗，并且由于事先也完全沒有做準備，好像趕鴨子上架

　　2、基礎(chǔ)一定要扎實，C++，數(shù)據(jù)結(jié)構(gòu)和算法，操作系統(tǒng)，網(wǎng)絡(luò)編程要熟悉。

　　3、對自己寫的代碼負責(zé)

　　4、騰訊的員工非常友好

近期目標(biāo)：

　　1、看數(shù)據(jù)結(jié)構(gòu)和算法

　　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] = '*'; //標(biāo)記該點已訪問
        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;
}

運行界面如下：