騰訊面試經驗2

時間：2017年10月16日11:30面試。

地點：重慶萬達艾美酒店。

信息：女，本科應屆生，面試后臺開發崗位。

?

　　在深圳的面試已經全部結束了，偶然間聽朋友說重慶、長沙等場地的面試還在進行中，只要修改面試地點，仍然有機會拿到面試機會。所以我抱著試一試的心態，在騰訊校招官網上修改面試地點為重慶。10月13日中午收到了騰訊的面試通知，面試時間是10月16日11:30，面試地點在重慶萬達艾美酒店。

　　收到短信通知的那一刻就已經有點緊張了，一開始我也很猶豫到底要不要跑回重慶去面試，電話里我爸說我既然那么喜歡騰訊，就應該抓住每一次機會去嘗試，不看結果，至少我們經歷過嘛。所以14日一大早就買上了15早上飛往重慶的機票。我也不斷提醒自己，緊張只會影響發揮，就當自己是回重慶改善飲食、度度假的。抱著這種心態，一直到走進萬達艾美酒店之前我都再沒有任何的緊張感。當酒店正門在視野中出現的那一刻還是忍不住緊張，所以我努力使自己保持微笑，一有機會就跟身邊的人閑聊，漸漸熟悉周圍環境之后也就忘記緊張這個名詞了。

　　電梯里遇到兩個小哥哥，兩個都是面試產品經理的，其中一個也是跟我一樣來自深圳，酒店服務員讓我們來到4樓，一出電梯就看到一組二維放置的椅子，里面稀稀落落的坐了不少來面試的，他們全是霸面的，凡事有正式通知面試的同學直接被送到里面房間掃碼簽到等待。跟我帶路的是騰訊的小哥哥，面帶微笑詢問我是面試什么崗位，我說后臺，他臉上的表情很豐富，非常驚訝我作為一個女生來面后臺！我說我是本科生，他的表情更加夸張了......驚訝轉佩服，他估計是佩服我的勇氣，說看好我并未我加油。

　　簽到后，里面房間的位置也就坐著一個同學在等待面試，我徑直走到他旁邊的位置坐下，主動跟他搭話，他是面試前端的研究生，一邊跟我說著話一邊不停地敲著鍵盤，看他很專心地在研究他的代碼，我也就沒再打擾了。靜坐了一分鐘左右，又進來一個男生，坐在我們后面的位置，主動向我們兩個搭話，他是來復試后臺的重慶大學研究生，旁邊男生一聽是后臺，立馬讓我跟他好好交流，我也很識趣地移到后面男生的旁邊坐下。這個男生很nice，得知我是本科生，看了看我的簡歷，然后向我分享了他的經歷——他在本科畢業之后也向我一樣來面試了騰訊，但是被拒，拖了一年后開始準備考研，考了兩次之后成功考上了重慶大學的研究生，直到現在他自己手上已經有其他公司的offer，然后再來面試騰訊。言語之間已經感受到他十足的信心了。可能覺得這個時候的我很像當年的他，所以給了我很多建議。還沒來得及互相留聯系方式，他就被叫去面試了。他走后立馬又來了一個復試后臺的重慶郵電研究生，坐在我旁邊，得知我是一面且是本科生，不再感興趣，于是掏出手機開始看資料，一邊看一邊告訴我讓我看看XXX，一面可能會被問到。不怕丟臉，講真的，他說的那兩個名詞我都沒聽過......這也許就是本科生和三年研究生的差距吧！

　　終于輪到我面試了，地點是7樓，走出等候室，仍然是剛剛的小哥哥給我帶路，幫我刷卡按電梯，并一直夸贊和鼓勵我，我苦笑一句說我自己也覺得很意外，而且我看過來面試的都是研究生，他很溫柔地告訴我沒關系，面試官對研究生的要求和本科生的要求是不一樣的哦～最后送了我一個微笑和好運祝福后讓我關上了電梯門。

　　電梯到達7樓，做了一次深呼吸后，我面帶微笑走進了726房間，面試房間的布局和我想象中的一樣，面試官的狀態也和我想象中的一樣 —— 一副剛起床的狀態！面試官坐在書桌的電腦前等我的到來，我在走向他的途中用余光掃到旁邊床上被子是凌亂的，床邊他的靴子東倒西歪并向外吐著襪子，床頭柜上還有打開未吃完的薯片。面試官看起來沒有很好相處，我會這么覺得，大概是因為他沒有回應我的微笑吧。從進門開始我就介紹了我自己的名字，并一直面帶微笑。

　　面對著他坐下后，首先被要求做個簡單的自我介紹，名字＋大學＋專業，然后說明我是深圳過來重慶面試的，他很驚訝我來自深圳，同時也很好奇，我原本以為他是知道我9月份在深圳已經面試過的，而且對于每個已經面試過的同學面試官都會寫一份評語，我也以為他已經看過評語，看他的反應大概是什么都不知道，所以我做了一個詳細的說明之后便接著我的自我介紹模版說下去。待我說完，他估計是看到了之前面試官對我的評語之類的，沒有再問我簡歷上的內容，直奔主題——做題！一共做了三道題。

第一題 ?合并多個有序數組

　　第一道題是算法設計題：有N個數組，每個數組有M個元素且呈升序，求這N個數組的并集。例如：第一個數組有｛1，2，3｝，第二個數組有｛2，3，5｝，則合并后為｛1，2，3，5｝。

（1）我首先想到的是犧牲空間節約時間的辦法，申請一個超大的數組A，初始化為0，遍歷這N和數組，將元素作為A數組的下標訪問A數組并置1；N個數組訪問結束之后，再遍歷一次A數組，其中值為1的下標的集合就是合并后的結果。聽我講完，他首先問我時間復雜度和空間復雜度，時間復雜度是O(N*M)，空間復雜度是元素的取值范圍。面試官提示我本道題是在64位系統下實現，而我需要的空間大小為元素取值的范圍，也就是說最多能達到2^64遠大于1Gb，所以這個方法是不可行的。

（2）我知道我一直沒有利用到“有序”這個關鍵詞，所以我抓緊這關鍵詞，首先想到的是二分查找：以兩個數組A、B合并為例，以A數組為基準，遍歷B數組的元素，利用二分查找，將B的元素在A中找到最適合的位置，

• 若A中不存在且處于A數組下標為0的位置，則直接記錄該B數組的元素；
• 若A中不存在且處于A數組末尾，則返回整個A數組＋該B數組元素；
• 若A中存在且此處A的元素和該B數組的元素不等，則返回此處及其此處以前的A元素＋該B數組的元素；
• 若A中存在且此處A的元素和該B數組的元素想等，則返回此處及其此處以前的A元素。

　　說完思路，他接著問我，那N個數組怎么合并呢，我回答的是遞歸拆分，直到只剩兩個數組為止，然后再逐次往上合并。回答完遞歸后，我自己都覺得太過復雜了。他繼續問了下時間和空間復雜度，兩個數組合并的時間復雜度主要取決于二分查找的復雜度O(logM)，總共要找M個關鍵字，所以兩個數組合并的復雜度是O(MlogM)，再加上N的數組的遞歸拆分大概就是O(N*MlogM)的復雜度了，空間復雜度為常數。能由“有序”關鍵詞想到了二分查找，面試官也勉勉強強接受了。

（3）我看他的表情不太滿意，于是我主動表現出對巧妙方法的興趣與渴望，于是面試官就給了我一個提示：“就以你兩個數組為例，你每次無非就是在確認一個數。”靈光一閃！我知道了！

• 用兩個指針指向這兩個數組的頭節點，指針內容進行比較，
• 如果內容相等，則記錄其中一個元素，兩個指針同時向后移動一個位置；
• 如果第一個小，記錄該元素，該指針向后移動；
• 如果第一個大，記錄另一指針指向的元素，另一指針向后移動。

　　那么N個呢？遞歸的話容易實現，但不一定是最好的，如果每個數組一個指針會不會空間太大呢？只有N個數組，只需要N個指針，N個指針同時進行比較，每次找最小的一個數記錄（問題簡化了，相當于在N個數中尋找最小的一個數）。顯然N的指針更佳令人滿意。那這N的指針如何進行比較？我先說的是快排的拆分函數（以一個數為基準，比該數小的在左邊、大的在右邊），而這個基準數是隨機的，所以調用一次拆分函數，返回函數中基準值下標，如果下標大于1，再對下標的左邊部分繼續調用函數；如果下標小于等于1，直接返回下標為0的元素。這樣的做法減少了遞歸次數，不必使得整個序列有序。但是這個做法還是不能讓面試官滿意。N個數中，只是找一個最小的數，我還能想到的是堆，但是我對于堆不熟悉，只知道當記錄數很多的時候用堆最合適。我也是這樣同跟面試官說的，最后再次問了時間和空間的復雜度，我理解的堆排序時間復雜度是O(nlogn)，但是這個復雜度是將整個序列變得有序的復雜度，而我們只需要找一個最小的，所以我的回答是，若堆排序的時間復雜度是X，那么這種解法的時間復雜度是O(N*M*X)，空間復雜度為常數。

第二題 ?回文數函數實現

　　第二道題是寫代碼，讓我寫出回文數的代碼實現，給了我一個函數的定義，讓我實現該函數。當然我會故意問一位數的數字算不算回文數！這道題沒什么難度，所以我不慌不忙地寫，也把所有邊界情況都考慮到位。寫了一個最簡單的代碼：

//-1:異常
//0:不是回文數
//1:是回文數
#define N 100
int Palindromic(int value)
{
    int x = value, k = 0 ,start, end;
    int a[N] = {0};
    
    //拆分數字,將每一位存放進一個數組
    if(x==0)
        return 1;
    while(x!=0)
    {
        a[k++] = x%10;
        x = x/10;
    }
    
    //從兩頭開始比較
    start = 0, end = k-1;
    if(start > end)
        return -1;//不可能發生
    else if(start == end)
        return 1;
    else
    {
        while(start<end && a[start]==a[end])
        {
            start++;
            end--;
        }
        if(start<end)
            return 0;
        return 1;
    }
}

?　　后來仔細想想以前的代碼，還有更簡單不易錯的代碼：

//0:不是回文數
//1:是回文數
int Palindromic2(int value)
{
    int x = value;
    int remainder = 0;
    int reverse_value = 0;//反轉數字初始化為0，使得value＝0時函數也成立
    while(x!=0)
    {
        remainder = x%10;
        reverse_value = reverse_value*10 + remainder;
        x = x/10;
    }
    
    if(value == reverse_value)
        return 1;
        
    return 0;
}

?

第三題 ?服務器壓力測試設計

　　第三道題他說是設計題，讓我設計一種方法來測試服務器的壓力，聽完他的題目說明，我是一臉萌比的，大概是問的“假設：服務器tps＝100000，怎么測試服務器壓力”，很尷尬的向他求助，能不能給點提示，他又說“假設一個線程tps＝1000”，結合他的提示，我只能把與相關的知識全部說出來，如線程的通信方式：（1）管道（2）系統IPC（信號量、____、消息隊列）（3）套接字Socket，其中漏了一個，因為這個問題毫無頭緒，我已經有點著急了，接著繼續說，要想達到100000的tps，肯定需要多個線程，我想用信號量來實現，例如我100個進程就能達到想要的tps的話，我給這些進程100個鎖來實現。他忍不了，說用共享內存來實現多個進程的通信更快，我恍然大悟，哦！！我遺漏了共享內存......我急忙贊同他的說法，他又接著問我這多的線程要怎么管理呢？這...我只能認輸不知道。他告訴我，需要用一個線程來管理其他多線程的并發操作。

　　后來自己百度了下這個問題，原來是WeTest的測試大師http://wetest.qq.com/gaps/

　　三個問題問完之后，對于面試結果，我心里還是有點B數的，面試官并沒有走流程讓我問他問題，說今天的面試就到此吧。我起身拿起包打算離開，但還是很像問他問題，所以我先問他我能否向他提一個問題，他同意之后，我問他我們這樣的本科應屆生有什么建議和意見嗎？他還是很耐心的跟我講了一些對應屆本科生的建議，最后說我閱歷太少，經驗不夠，基礎功不扎實。我回應了幾句，并向他表示了真心的感謝之后離開了房間。

　　面試官的評價很到位，赤裸裸的現實，還是回校補補營養吧！不過這份經歷還是值的，一個毫無經驗的應屆本科生同幾個研究生來競爭同樣的職位，雖然結果很明顯，但還是非常感謝面試官給我這個面試機會，而且整個面試過程中還那么耐心的引導我！

?

　　我的博客即將同步至騰訊云+社區，邀請大家一同入駐。