2014微軟實習生面試經曆

     28号結束了最後的三面。因為三個面試官都沒有要求我對面試内容保密，是以現在就将自己面試微軟的整個過程記錄為博文，供以後的面試者作為參考。轉載請注明出處:http://blog.csdn.net/xiefubao。

     開學的時候了解到微軟今年在西安沒有宣講會和筆試現場，以為微軟不準備在西安招人了。後來才在官網看到今年是網上筆試。大概是3月底投的履歷，中文履歷早就準備好了，當時臨時趕了一份很粗糙的英文履歷。四月初收到了第一輪筆試的通知。第一輪筆試2個小時，四道英文程式設計題目，難度要比acm簡單。當時做的比較遺憾的是第三題，預處理資料寫了個n^2的算法，隻得了10分，當時還以為逾時了就沒管，後來聽說院裡有個同學第三題完全暴力寫了個n^3的程式居然拿了100分，sigh，也許當時再繼續查下程式的bug筆試就可以至少拿300分了，各種囧，，，不過還是在四月中旬收到了第二次線上測試的通知。第二次測試分為兩類題，一類是數學能力測試題：都是一些很簡單的統計類的數學題，但是題目比較多，大概不到一分鐘就得做一道，有的還要用到電腦去算結果。另一類是語言能力測試：國文中學就不太好，最怕這個了。大概就是先給一段話a，然後再給一段話b，根據a判斷b正确錯誤還是不确定，時間也比較緊。

   大概四月20号收到了24号面試的通知，是線上面試。然後就去網上看了好多微軟的面經。

   一面的面試官是個jj，雖然隻能聽到對方聲音，但是感覺應該很年輕。一面微軟jj很和藹可親，喜歡笑，這也多少減少了點我的緊張程度。一上來我大概介紹了下自己，然後微軟jj開始問我問題：第一個籠統地問了一句如果程式輸出錯誤的結果，我會怎麼檢錯。根據平時做題的經曆，我說如果是在oj上交題目，我會根據傳回的結果是wa、tle還是re等等類型去檢視程式可能存在的bug，balabala....（感覺很naive，根據jj問的當時也想不到該怎麼回答）。後來jj說如果程式輸入資料不變，代碼不變，但是多次運作的結果不一樣可能會是什麼原因，（說實話，相對于具體算法，我自己是比較怕這種開放的問題的）。憋了半天，大概說了幾種可能性：程式用了new，

malloc等申請堆記憶體的指令，程式調用了擷取系統時間函數，程式讀取網絡或檔案中資料，程式用了随機算法等。但是jj一直讓我說下去，後來真想不到其他的了，姐姐就換了問題。結束後發現有個很關鍵很明顯的多線程當時沒說（估計這個點扣分不少）。

     後來jj就給了一個具體的題目：給一個漢字字元串和拼音字元串，問如何判斷漢字字元串和拼音字元串是否比對。

一眼看，覺得好簡單，我說首先要有每個漢字讀音的資料存儲，然後漢字和拼音字元串從左向右掃一遍，如果有一個沒比對上就說明不能比對。jj說會有多音字，瞬間覺得剛才自己又naive了。我就說那就搜尋吧，遇到多音字的話就嘗試每種走法，每條路走不通就回溯。然後jj問我這種方法大概的時間複雜度，我說理論上最差會是指數級的時間複雜度，但是實際應該不會有那種極限的資料。我感覺和掃一遍差不多，因為多音字走不下去就會很快回溯回來，不會走太深。然後jj就讓我開始把這個代碼在白闆上寫出來。當時懵了一下，白闆相當于沒有tab鍵的txt啊。我問jj可不可以在本地的ide上寫，jj說可以。讀入資料我說不是關鍵，就主要寫了那個dfs搜尋函數，寫的過程中jj還說出去買了個東西。下面是當時寫的代碼的主要部分：

然後jj問我代碼的時間複雜度，我說的和剛才的分析差不多，最差指數級，平均應該是o(n)。後來就說了點其他與技術無關的東西就結束了。後來和bw的讨論中發現，其實寫的那個代碼加個二維數組的記憶化就可以避免理論上的指數級複雜度（平時寫了那麼多記憶化搜尋的題目，關鍵的這次面試居然沒想到，也許jj一直問複雜度就等我說那個優化呢）。有了這次教訓，以後面試時肯定會注意要更加冷靜思考，還要想想面試官問每個問題的用意，敏感地察覺到面試官的引導方向。

      二面的面試官是個gg。gg說話很有條理，有時信号不太好還可以感覺到gg在說問題時候，故意放慢語速以讓我聽清楚。二面問的問題都比較碎，可能有個别已經記不得了，就寫自己記得的吧。

    他先問了個假設性的問題，就是有一個新聞釋出平台，每時每刻最多隻能有一個使用者在發資訊，問我會如何實作。一聽有點摸不準gg的核心在哪，不會就是問如何避免互斥的吧。硬着頭皮，我說用一個釋出資訊的鎖，一個使用者發完資訊後才可以把鎖釋放，而發資訊之前必須先獲得這個鎖。然後gg也沒說啥就換問題了。下面問了這樣一個問題：有個不定長的整型數組，每個整數在1-1000之間，問如何去重。（心中一陣竊喜，怎麼問這麼簡單的問題）。我向gg确認了此問題核心是去重而不是如何處理數組不定長之後就說出了開一個1000長度bool類型數組用來去重的方法，時間複雜度是o(n)(已經達到下限不可能再優化了)。gg說方法是正确的，然後問我有沒有辦法優化空間複雜度。又懵了，o(n)的空間複雜度還可以優化？難道o(1)，o(0)?後來說了還可以先排序然後去重，空間就優化到了o(0),但是時間增加到了nlogn。gg隻說了句這是個優化空間的辦法就又換問題了。（至今想想當時秀逗的自己bit位優化空間都給忘了，而gg說優化空間的時候也一定等的是這個方法啊，囧）。

   然後gg問了個幾何問題：給兩個三角形，問如何判斷兩個三角形是否有重疊部分。做過acm裡的簡單計算幾何題目的應該都可以秒掉這道題吧。然後我就說了自己的解法：分為兩種重疊情況：

    一、判斷是否存在嵌套的情況（判斷是否一個三角形的三個點都在另一個三角形裡面）。然後我說了判斷一個點是否在一個三角形内部的辦法:順時針計算此點與三條線段的有向角度和，三角形内部的話和是360度，外部點會得到0度（或是求有向面積，内部有向面積和等于三角形面積本身，外部的話有向面積和是0）。

    二、如果不存在嵌套的情況，那麼兩個三角形有重疊部分則必有線段相交。這時兩兩判斷線段是否相交就可以了。然後我就說了判斷兩條線段相交的方法：如果兩條線段ab與cd相交，則點a、b必在直線cd兩側，同時點c、d必在直線ab兩側。判斷兩點a、b是否在直線cd兩側的辦法：求ac和ad向量的叉積和bc和bd向量的叉積相乘，結果是負數就說明a,b在cd兩側，得到正數說明在同側，0的話就說明至少有一個在直線cd上。說完後gg肯定了我的方法并換了問題。

  在微軟的各種技術面中，當場寫程式好像是不能少的。二面gg最後一個問題是程式設計題：一個二叉樹的根節點定義為第0層，寫一個函數，輸入根節點位址和m，實作儲存第m層節點的資料的任務。很基礎的一個遞歸題目，寫完交過去後gg說可以了就結束了二面。

下面是二面代碼的關鍵部分：

  二面後的第二天收到了三面通知，時間是在28号下午。

  三面的面試官還是個gg，他說他是西電的，離我們學校不遠。由于這次三面gg主動開了視訊功能，我就也開了自己的視訊功能，這樣可以互相看到對方（其實最好别開，看到對方會變得更加緊張，這是我的親身感覺）。上來gg還開了幾句玩笑，可能是讓面試者放松下來好發揮吧。但是自己好像一直比較緊張（當時清楚地知道這将是自己的生死面）。開始十幾分鐘大概就閑聊幾句，gg問了履歷上的幾個點，我也大概說了下自己的大學生活。後來聊完後，gg說按微軟的慣例，程式是一定要寫的。然後問我是否知道大數乘法（這是acm裡比較基礎的工具），我說以前用數組寫過模拟大數運算的模版，重載過+-*/等符号。然後他說這次要寫用字元串來模拟大數乘法。我說我沒寫過這個，但是應該可以寫出來（當時真的感覺很虛，怕寫不好，差點拒絕下來，但是感覺拒絕寫差不多就意味着被淘汰了，就硬着頭皮答應了下來）。然後三面gg給了我我函數聲明，關了他的聲音說給我半個小時讓寫，但是我一直在他的監視下的。我大概在紙上畫了畫，思路清晰後開始寫，大概10多分鐘寫完了，然而一直出不來結果，有的資料輸入後輸出的還是亂碼，一直調到了20多分鐘時候才出了正确結果。測的幾組結果都正确後，就叫面試gg說寫完了。gg讓通過郵箱發過去。但是發送郵件有個延遲，他說在這延遲時間裡讓我先說說自己程式的思想。我就說了起來，blablabla。。。後來gg問怎麼還沒收到郵件，腦子一懵，自己隻顧說了，居然沒先發郵件，太囧了，趕緊發過去，gg當時也笑着說自己也犯過這樣的囧事。發完後，我才發現輸入0*0程式傳回了空字元串，連忙改了一下又發了一遍。下面是當時第二遍發的代碼的關鍵部分：

然後gg說如果我來測自己的程式會用什麼樣的資料，我大概說了會用0這樣的邊界資料（明顯剛才0*0就出錯了），還會用負數相乘（跟gg說了自己的程式沒處理負數的情況，但是很好修改，就開始判斷下符号就行，gg說沒有關系）。然後gg繼續問我會輸入什麼樣的資料，期間聲音信号不好gg還用打字的途徑讓我繼續補充這個問題的回答。自己也真想不到要用啥資料(當時想的是多試幾組資料呗，差不多就應該沒錯了吧。但是肯定不能這樣講)。後來面試官gg一直往那上面引導，最後還是他自己說了出來:說如果輸入0000000123456789乘上另一個數這樣的資料，函數裡會不會有很多無用計算（當時一直沒想到這個，gg一說出來我直接感覺就要跪了）。我說是的，如果有這樣的資料，在輸入的時候還要處理下以去掉字首0。後來面試gg也沒再問啥，就問我有沒有什麼問題，我就問了一下三面後大概幾天通知結果，gg說一周左右人力資源部會有通知。然後就寒暄挂掉了。

     現在還很難說三面的結果，反正自己感覺是很沒把握，期間三面面試官還說他前邊的面的全是研究所學生，一個大三狗壓力真的好大。如果三面挂了的話可能就是資料測試上自己回答的沒讓gg滿意吧，如果過了的話真的運氣很好了。現在也盡量安慰着自己把每次機遇當做一種恩賜而不是理所應得，盡最大努力就沒有遺憾了。

   面試前自己在網上看了好多微軟面經，現在僅以此文供以後的學弟妹參考吧。