面完了hulu有點(diǎn)悲劇，找工作算是告一段落了?，F(xiàn)在寫寫面經(jīng)，給學(xué)弟學(xué)妹們點(diǎn)借鑒。另外人人上神牛太多，我這么水容易被鄙視，就發(fā)到這里吧。
Experience&Insight 先是一些建議。首先是自我介紹部分，好多面試官會(huì)跳過(guò)這一部分，但是為了保險(xiǎn)還是準(zhǔn)備一下吧。自我介紹里一定要說(shuō)自己是本科！否則很多面試官會(huì)大量問(wèn)你機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘的內(nèi)容。 另外，最好再提到到自己最突出一兩個(gè)亮點(diǎn)，對(duì)于我來(lái)說(shuō)就是競(jìng)賽和MSRA實(shí)習(xí)。這個(gè)部分差不多就行了，畢竟是面碼農(nóng)。 隨后面試官一般會(huì)問(wèn)一問(wèn)簡(jiǎn)歷上的項(xiàng)目。對(duì)于簡(jiǎn)歷上的項(xiàng)目你不僅要十分熟悉，而且要能夠非常清晰有條理的講出來(lái)。不要怕講得羅嗦，講明白是最重要的。我覺得需要注意的幾點(diǎn)就是要先充分的介紹問(wèn)題背景，這樣才能比較自然的進(jìn)入項(xiàng)目的實(shí)質(zhì)內(nèi)容。講述項(xiàng)目的實(shí)現(xiàn)時(shí)要自頂向下，逐步細(xì)化，讓人先有總體的把握，再關(guān)注細(xì)節(jié)。對(duì)于項(xiàng)目中抽象的概念要盡量舉一些例子，還是不要怕羅嗦。最后就是對(duì)于項(xiàng)目的主體，要有適當(dāng)?shù)闹貜?fù)與強(qiáng)調(diào)，防止聽者遺忘。這些有好多都是我實(shí)習(xí)時(shí)的mentor告訴我的，在實(shí)踐中我也覺得這很有道理。另外，光知道這些是遠(yuǎn)遠(yuǎn)不夠的，關(guān)鍵是要多練習(xí)，大不了準(zhǔn)備好幾套方案背下來(lái)。多找人練練，最好是能給父母講明白你的項(xiàng)目。 下一環(huán)節(jié)就是技術(shù)面的面試題了。當(dāng)然這個(gè)是最重要的部分，這個(gè)跪了前面的表現(xiàn)就白費(fèi)了。紙上寫代碼是要面臨的第一個(gè)問(wèn)題，這就只能多練練了。另外的一個(gè)問(wèn)題就是題目如何作出來(lái)。多看些面試題的書籍，比如 《編程之美》《cracking the coding interview》或者在leetcode上多刷刷題，至少百度阿里的等級(jí)的公司還是能秒掉的。做題時(shí)先盡量自己想，看了答案之后要認(rèn)真分析不會(huì)的原因，最好每道題都要敲一遍，因?yàn)橛械膖rick不敲是很難發(fā)現(xiàn)的。面試時(shí)最重要的是兩點(diǎn)，一是不要理解錯(cuò)題意，二是想好細(xì)節(jié)再開始寫。 最后就是提問(wèn)時(shí)間了。我個(gè)人認(rèn)為這個(gè)環(huán)節(jié)沒(méi)有必要去刻意提問(wèn)來(lái)表現(xiàn)自己對(duì)什么東西有獨(dú)到的見解。這只是一個(gè)了解你以后工作內(nèi)容和環(huán)境的好機(jī)會(huì)。如果你沒(méi)準(zhǔn)備好自己真正關(guān)心的問(wèn)題的話你在match offer 的時(shí)候會(huì)后悔的。所以我覺得最后提問(wèn)就是想問(wèn)什么問(wèn)什么，尖銳一些就尖銳一些。 其實(shí)從頭至尾關(guān)鍵是要表現(xiàn)出你對(duì)要做的事情的喜愛，和你確實(shí)很聰明，有著很強(qiáng)的學(xué)習(xí)能力與對(duì)事情鉆研的熱情。
墨跡完了開始上干貨。
從實(shí)習(xí)面開始！ Google&MSRA
處女面是面谷歌實(shí)習(xí)，是電面，一點(diǎn)面試經(jīng)驗(yàn)都沒(méi)有，注定悲劇。這次面試都有點(diǎn)給我留下陰影了，前半小時(shí)只有2句對(duì)話。面試官：“實(shí)現(xiàn)下大整數(shù)開根號(hào)。” 我:"我先說(shuō)下思路吧。" 面試官：“不用了，你先把代碼寫出來(lái)吧?！?我：“。。。?！?這題目，就是讓我把高精度運(yùn)算都寫一遍啊，第一次脫離IDE寫這么碼的題目，實(shí)在是捉雞。教訓(xùn)就是寫代碼時(shí)不要著急，時(shí)時(shí)刻刻注意代碼風(fēng)格，換行和縮進(jìn)，要么容易寫到后來(lái)連某個(gè)變量叫什么名字都找不到。當(dāng)時(shí)我就是十分焦急的一頓碼，代碼中留下了許多細(xì)節(jié)問(wèn)題和bug，最后被面試官平均每四五行挑出一個(gè)錯(cuò)誤。寫完代碼后面試官直接就問(wèn)你還有什么問(wèn)題么，然后凄慘的面試就這么結(jié)束了。兩三天后收到拒信。
自從谷歌實(shí)習(xí)面跪了之后，我有一段時(shí)間每天都會(huì)在記事本上把高精度運(yùn)算敲一遍，嘗試用不同的方法實(shí)現(xiàn)。稍稍提高了點(diǎn)代碼能力，另外一個(gè)好處就是熟悉了不用IDE寫代碼的感覺。
隨后投了一發(fā)MSRA的實(shí)習(xí)，也是很快收到答復(fù)，約了面試時(shí)間。這次面試因?yàn)橛辛私?jīng)驗(yàn)，和我們組當(dāng)時(shí)確實(shí)比較缺人面試題比較水，全程進(jìn)行的比較順利。面試官（我現(xiàn)在的mentor）貌似先是問(wèn)了點(diǎn)我簡(jiǎn)歷里的項(xiàng)目，有點(diǎn)記不清了，主要就是講了講我寫的黑白棋的博弈搜索的算法，和對(duì)局面好壞的估值方法。然后又問(wèn)了問(wèn)以后準(zhǔn)備讀PHD還是工作，又提到我們組在這兩方面都有比較好的機(jī)會(huì)。當(dāng)時(shí)本來(lái)以為這就是個(gè)呵呵面，但是后來(lái)過(guò)了快半小時(shí)我mentor突然才讓我寫幾個(gè)題。廢話不多說(shuō)了，直接上題。第一題是MSRA喜聞樂(lè)見反轉(zhuǎn)字符串，舉個(gè)例子，就是給你“Hello world ！”你返回“！ world Hello”（單詞間以空格間隔）。瞬秒，用一個(gè)棧，從后向前掃描字符串，遇見非空格則把字符壓棧，遇見空格就把棧彈空，字符的出棧順序就是所求結(jié)果。第二題也是大水題，給你一個(gè)邊和坐標(biāo)軸平行的矩形和一個(gè)圓，讓你判斷二者是否相交。繼續(xù)瞬秒，先用一點(diǎn)小技巧求出矩形上距離圓心最近的一點(diǎn)，然后判斷改點(diǎn)在不在圓內(nèi)。第三題是求樹上距離最大的兩個(gè)點(diǎn)，喜聞樂(lè)見的兩遍DFS，然后我還證明了一下這個(gè)方法。最后問(wèn)問(wèn)題，數(shù)據(jù)可視化是干啥的，我mentor大概講了講就結(jié)束了。不久接到二面通知。二面更是水，都沒(méi)有寫代碼的題目，只有一個(gè)說(shuō)算法的題目。給你一個(gè)無(wú)序的數(shù)組和一個(gè)數(shù)K，讓你求出所有的ai aj 使ai+aj=k，都是經(jīng)典水題了，掃描數(shù)組，第一遍hash插入ai，第二遍hash查找K-ai。剩下的還是問(wèn)問(wèn)簡(jiǎn)歷，隨便聊聊，面試就結(jié)束了。大概拖了一段時(shí)間后收到實(shí)習(xí)offer。
Baidu&Alibaba&Tencent
有了MSRA實(shí)習(xí)后，基本上心里已經(jīng)決定去了，但是為了積累下面試經(jīng)驗(yàn)，多了解一下其他公司，我還是弄了弄BAT這三家公司的實(shí)習(xí)，希望能拿一些備胎實(shí)習(xí)offer，結(jié)果卻是一家沒(méi)拿到，都悲劇了。
最開始面的是騰訊。先是聽說(shuō)有騰訊筆試，然后被同學(xué)拉著去筆試，隨后收到了面試通知，地方離得挺近的，不去白不去。一面面試官應(yīng)該是soso的，一開始沒(méi)讓自我介紹，讓我先寫個(gè)很簡(jiǎn)單的題，有一個(gè)小trick，然后寫了個(gè)很水的DP，具體的題我都忘了，因?yàn)樘?jiǎn)單沒(méi)啥印象。然后問(wèn)了一個(gè)開放題，如何估計(jì)文檔的相似度，找出相似文檔，答得不好當(dāng)時(shí)也不了解topic model或者文本挖掘啥的，一頓瞎扯。然后聊一聊上大學(xué)期間都在干什么，由于已經(jīng)有了實(shí)習(xí)去處，我比較隨意，基本上就是想說(shuō)什么說(shuō)什么，大量吐槽學(xué)校，鄙視自己學(xué)校。但是總體還是相談甚歡的感覺。結(jié)果，晚上查面試結(jié)果，被十動(dòng)然拒了。一面被騰訊拒。
隨后就是百度的什么人才庫(kù)計(jì)劃。雖然大家都吐槽這個(gè)竟然用QQ郵箱通知，但我還是回復(fù)了那個(gè)郵件，把簡(jiǎn)歷發(fā)了過(guò)去。然后我又推薦了幾個(gè)人，換來(lái)了hr送的一個(gè)百度的小音箱，被我當(dāng)成鬧鐘用了。不久接到了電面通知，一面面試官應(yīng)該是個(gè)java的研發(fā)工程師，問(wèn)了各種碼農(nóng)問(wèn)題。java 中Vector 和List哪個(gè)是線程安全的，如何設(shè)計(jì)java虛擬機(jī)的垃圾回收機(jī)制，java的HashSet內(nèi)部是如何實(shí)現(xiàn)的。還問(wèn)了些數(shù)據(jù)庫(kù)的東西，在數(shù)據(jù)有什么特點(diǎn)的時(shí)候你應(yīng)該使用索引，剩下的有點(diǎn)忘了。總之就是答得很不好，我對(duì)這種問(wèn)題以前也不怎么關(guān)心，就隨口答一答。最后讓寫了幾道題，前幾道都是一分鐘瞬秒的節(jié)奏。第一題，給你一堆數(shù)其中只有一個(gè)數(shù)出現(xiàn)了奇數(shù)次，用O(1)額外空間找出這個(gè)數(shù)，異或一遍就好。其他題都忘了，只需知道題水的不能再水就是了。最后一題是在一個(gè)字符串里查找一個(gè)子串，允許使用庫(kù)函數(shù)，我當(dāng)時(shí)覺得就把這些題這么快秒了實(shí)在沒(méi)意思，就對(duì)面試官說(shuō)，我習(xí)慣自己寫，不用調(diào)用庫(kù)函數(shù)，不到20分鐘現(xiàn)敲了個(gè)KMP，寫的這么慢主要還是因?yàn)楹镁脹](méi)寫過(guò)字符串的題了。然后面試結(jié)束。忘了過(guò)了多長(zhǎng)時(shí)間接到現(xiàn)場(chǎng)面通知，當(dāng)時(shí)想既然報(bào)銷火車票倒不如去看看百度怎么樣，雖然正好編譯原理快結(jié)課了，我還是決定帶著龍書路上復(fù)習(xí)去百度面試了。
二面在百度大廈，上午下了火車很早就到了百度大廈，頓感高大上，覺得碼農(nóng)貌似沒(méi)有那么苦逼，至少還有前臺(tái)妹子養(yǎng)養(yǎng)眼。在大廳繼續(xù)看了好幾小時(shí)的編譯原理的書。隨后到了面試時(shí)間，被面試官領(lǐng)上了樓，然后我看到了我面試的職位是C++研發(fā)工程師，頓時(shí)覺得被一面面試官鄙視了java方面的技術(shù)。然后問(wèn)了些C++語(yǔ)言細(xì)節(jié)，指針與引用的差別，C++程序內(nèi)存都有那些不同的區(qū)域，常量字符串被存在哪個(gè)區(qū)域。后來(lái)問(wèn)了一道題，不算很難，但是竟然沒(méi)一開始就想到最優(yōu)的方法，估計(jì)是因?yàn)榛疖嚿蠜](méi)睡好。給你一個(gè)大的字符串A，和小的字符串B，C，讓你把A中所有的包含B的位置替換成C。要求額外空間為O（1）的。最優(yōu)方法是在我寫完一個(gè)不夠好的方法之后才想起來(lái)的，只是說(shuō)了說(shuō)想法。方法就是對(duì)A先計(jì)算出B的出現(xiàn)次數(shù)，算出替換之后A的尾部的位置，然后從后向前在A中匹配B，并替換，這樣就可以做到不利用額外空間進(jìn)行移動(dòng)了。這輪面試的收獲就是體會(huì)了紙上寫代碼也是一件很蛋疼的事情，寫完的東西一修改就亂了。三面是經(jīng)理面，問(wèn)了我和別人如何相處，如何處理矛盾啥的，然后我在面試結(jié)束前表達(dá)了我對(duì)純碼農(nóng)職位不感興趣，然后面試結(jié)束。回去之后拖了好久把火車票寄過(guò)去報(bào)銷了。
最終的結(jié)果是傳說(shuō)中的默拒。
最后的實(shí)習(xí)面是面的阿里。也許是筆試成績(jī)?cè)谶吘?，收到面試通知比較晚，一面直接是現(xiàn)場(chǎng)面，面試官來(lái)自支付寶，面試從頭到尾純粹是閑聊，談人生談理想，最后問(wèn)了下所有的排序算法都適用于哪些情況，面試結(jié)束。過(guò)了一段時(shí)間收到終面通知，終面竟然是電面，實(shí)在是搞不明白到底怎么回事。面試的時(shí)候面試官問(wèn)了好多機(jī)器學(xué)習(xí)的東西，估計(jì)以為我是研究生什么的，我只憑借大概的了解答了答，問(wèn)到SVM的一個(gè)什么優(yōu)化時(shí)，我當(dāng)時(shí)就表示沒(méi)有聽說(shuō)過(guò)，只知道最原始的SVM和soft-margin SVM。然后面試官問(wèn)給你offer你實(shí)習(xí)會(huì)來(lái)么，我當(dāng)時(shí)就直說(shuō)了我會(huì)去MSRA實(shí)習(xí)，然后就木有然后了。又是傳說(shuō)中的默拒。
下面是找工作的面試。
Google SDE
第一個(gè)工作面試竟然還是谷歌，看來(lái)谷歌是注定要跪的。另外一個(gè)奇葩的事情就是HR給我安排的模擬面試坊活動(dòng)的時(shí)間竟然是在面試之后！！這次面試發(fā)生在實(shí)習(xí)的時(shí)候，平時(shí)時(shí)間比較緊，只能通過(guò)壓縮睡眠時(shí)間來(lái)準(zhǔn)備面試，就準(zhǔn)備了幾天，幾乎算是沒(méi)準(zhǔn)備吧。
第一個(gè)面試官是個(gè)滿頭白發(fā)的大概40多歲的人，谷歌就是高大上啊，還有40多歲的碼農(nóng)。先是問(wèn)了一個(gè)接口設(shè)計(jì)的問(wèn)題，如何設(shè)計(jì)一個(gè)發(fā)送郵件的函數(shù)接口，防止調(diào)用者將發(fā)送方和接收方地址傳反，我的方法是把所有的參數(shù)打包，然后讓調(diào)用者顯式的賦值，會(huì)比較明顯的意識(shí)到每個(gè)參數(shù)是干什么的，而不容易弄反。然后有一個(gè)算法題，讓我設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)，支持在集合中插入一個(gè)元素，刪除一個(gè)元素，和隨機(jī)返回集合中的一個(gè)元素（當(dāng)然要求每個(gè)元素的被返回概率均等）。我先給了個(gè)平衡樹維護(hù)的方法，然后給了一個(gè)利用hash的均攤復(fù)雜度O(1)的方法，然后面試官讓我想有沒(méi)有更優(yōu)的更穩(wěn)定的方法，沒(méi)想出來(lái)，一面結(jié)束。實(shí)際上在休息時(shí)我就想到了最優(yōu)的方法，就是先把所有的元素放入數(shù)組，用數(shù)組這個(gè)結(jié)構(gòu)維護(hù)從數(shù)組腳標(biāo)到值的這個(gè)映射，用哈希表維護(hù)從值到數(shù)組角標(biāo)這個(gè)映射，插入就直接把元素放在數(shù)組末尾，再維護(hù)哈希表。刪除就直接用數(shù)組最末尾的元素替換被刪除的元素，再維護(hù)哈希表。隨機(jī)返回的話就隨機(jī)產(chǎn)生一個(gè)1到數(shù)組大小的隨機(jī)數(shù)返回以該數(shù)為角標(biāo)的值（因?yàn)閿?shù)組中沒(méi)有空隙）。
隨后二面面試官來(lái)了，一個(gè)估計(jì)也快40的女面試官，說(shuō)話語(yǔ)氣特別犀利，思維也很犀利。上來(lái)問(wèn)了個(gè)我不太會(huì)的題，已知有n行代碼，其中一行有bug，現(xiàn)在要通過(guò)2種操作找到這個(gè)bug，第一種操作是在某一行插入一個(gè)輸出語(yǔ)句耗時(shí)為a個(gè)單位，第二種操作是把代碼編譯運(yùn)行耗時(shí)為b個(gè)單位，如果某個(gè)輸出語(yǔ)句輸出正確，那么說(shuō)明該語(yǔ)句之前的代碼都是正確的，讓求出最短的時(shí)間找到有問(wèn)題的代碼。這個(gè)首先第一需要注意的是可以多次插入代碼之后再進(jìn)行編譯操作，這個(gè)我當(dāng)時(shí)注意到了。然后我的重心放在利用數(shù)學(xué)的方法解決這個(gè)問(wèn)題，直接把問(wèn)題轉(zhuǎn)換過(guò)去，后來(lái)發(fā)現(xiàn)優(yōu)化的目標(biāo)實(shí)在是有點(diǎn)復(fù)雜，才發(fā)現(xiàn)自己走偏了。最后只是給了個(gè)一般的O（n*n）動(dòng)態(tài)規(guī)劃的方法，就是對(duì)于某一個(gè)規(guī)模的代碼，枚舉要將這段代碼平均（不難想到一定要均分）分成幾塊，然后遞歸到更小的塊，用一個(gè)數(shù)組記錄不同規(guī)模所求出的最小時(shí)間是多少，記憶化搜索就好。對(duì)于這道題我表現(xiàn)的很不好，加上面試官語(yǔ)氣有點(diǎn)強(qiáng)硬，弄的我很不舒服，注意力沒(méi)法集中，心里特別亂。隨后問(wèn)了一個(gè)很水的題，給一個(gè)字符串s，和一個(gè)字母的集合A，求s中最長(zhǎng)的只由A中字母組成的子串，嗯，就是用一個(gè)可以伸縮的區(qū)間從s開頭滑到結(jié)尾，區(qū)間內(nèi)如果出現(xiàn)了A中沒(méi)有的字母，則從區(qū)間的頭部彈出字母，即區(qū)間頭部向后移，其他情況則從區(qū)間尾部加入字母，即區(qū)間尾部向后移。整個(gè)過(guò)程區(qū)間取得最大的長(zhǎng)度的位置就是子串所在位置。秒掉了。最后提問(wèn)題，G公司的碼農(nóng)一天都會(huì)干些什么，聽回答大致感覺就是啥都干。
然后面試結(jié)束，等三四面通知。過(guò)了大概半個(gè)月，不出意外收到recruiter的電話：“歡迎你明年再來(lái)面”。TT。
Baidu Speech
隨后是面了一個(gè)百度的語(yǔ)音技術(shù)部?jī)?nèi)推，本來(lái)時(shí)間安排在面谷歌的第二天，但是HR發(fā)的面試郵件我沒(méi)收到，再加上那幾天準(zhǔn)備谷歌面試，我也忘提醒HR了，于是就推后了幾天。當(dāng)時(shí)面的時(shí)候也比較隨意，毫無(wú)準(zhǔn)備，因?yàn)楣雀杳娴貌缓眯那橐膊皇呛芎?，但是語(yǔ)音組給我的總體印象還是很好的。
一面是個(gè)中科大少年班的面試官，態(tài)度極其好，貌似在百度工作了5年只比我大一歲。先問(wèn)了一道簡(jiǎn)單的DP，給一排格子，現(xiàn)在有三種顏色紅、白、黑，給這一排格子涂色，要求相鄰格子的顏色不能相同，而且對(duì)于每個(gè)白色的格子必須滿足左邊相鄰格子是黑色，右邊相鄰格子是紅色，問(wèn)一共有多少涂色方案。方法就是動(dòng)態(tài)規(guī)劃，一個(gè)格子一個(gè)格子的涂，狀態(tài)就是涂到了哪一個(gè)格子，當(dāng)前格子的前2個(gè)格子都是什么顏色，轉(zhuǎn)移就按題目規(guī)定的合法條件進(jìn)行轉(zhuǎn)移。隨后問(wèn)了問(wèn)簡(jiǎn)歷里的項(xiàng)目，我就說(shuō)了一下來(lái)MSRA的對(duì)Skype用戶反饋的可視化的項(xiàng)目。然后問(wèn)了一個(gè)只需說(shuō)算法的題，在n-gram語(yǔ)言模型里如何快速的求出一個(gè)句子的出現(xiàn)概率，當(dāng)時(shí)先說(shuō)了個(gè)最直白的hash查找然后乘在一起，之后想到了利用ac自動(dòng)機(jī)的一個(gè)方法，對(duì)于k-gram會(huì)比hash優(yōu)化掉k這個(gè)常數(shù)。這個(gè)方法就是將n-gram的所有參數(shù)插入ac自動(dòng)機(jī)權(quán)值就是對(duì)應(yīng)的參數(shù)值，然后直接做查找，將所有查找到的子串的權(quán)值相乘。當(dāng)然還有一點(diǎn)細(xì)節(jié)需要處理?？疵嬖嚬俚姆磻?yīng)，我答的還可以。然后又問(wèn)了一個(gè)布局算法，參見今年百度筆試最后一題，說(shuō)起來(lái)太麻煩了。然后一面結(jié)束
二面的題目成題比較多，除了一個(gè)三個(gè)門后面猜羊，開了一扇門問(wèn)你換不換這個(gè)題卡了一會(huì)，其他都是比較快速答上來(lái)，所以沒(méi)什么印象。然后自我感覺有點(diǎn)過(guò)于良好，說(shuō)了一個(gè)不夠保險(xiǎn)的東西，用EM算法對(duì)隱馬爾科夫模型參數(shù)進(jìn)行估值，以前確實(shí)花了好大功夫弄明白了，但是當(dāng)時(shí)好久沒(méi)接觸了，公式?jīng)]推明白，然后就放棄了，面試官安慰了我一下說(shuō)他也不是很熟。然后是三面貌似是經(jīng)理面，隨便聊了聊，期間問(wèn)到我有沒(méi)有對(duì)象，然后提醒我說(shuō)要抓緊，提到組里有2個(gè)女生實(shí)習(xí)，估計(jì)會(huì)留下來(lái)，好囧。然后面試結(jié)束。 8月底面的，9月初給的offer?？傊@次面試讓我對(duì)百度印象很好。
Alibaba 算法工程師
隨后就是比較重要的阿里面試了，筆試的時(shí)候發(fā)現(xiàn)周圍密密麻麻的清華碩士，覺得果然北京競(jìng)爭(zhēng)比較激烈。筆試等待的時(shí)候和一個(gè)清華研究生妹子聊了聊，她極力勸我找個(gè)學(xué)校繼續(xù)讀，額...
然后就是一面，貌似我筆試成績(jī)還不錯(cuò)，面試被安排在第一天，一面面試強(qiáng)度不是很大，隨便問(wèn)問(wèn)項(xiàng)目，問(wèn)了個(gè)并行的算法問(wèn)題，就是如何把離散化這個(gè)過(guò)程改成并行的算法。我對(duì)這種問(wèn)題以前沒(méi)想過(guò)，于是用一般的離散化方法，也就是排2次序，然后把排序并行化一下，當(dāng)時(shí)還用了不是很容易并行的多路歸并排序。其實(shí)也可以用MapReduce很簡(jiǎn)單的搞一下。然后面試官讓我寫個(gè)快速排序，速寫之，面試官看了一眼啥也沒(méi)說(shuō)就告訴我一面結(jié)束了。隨后在阿里等面試的時(shí)候蹭了頓盒飯，又認(rèn)識(shí)了些人，感覺就算被拒也值了。等了好久終于等到了終面，純粹的呵呵面，讓我講講數(shù)據(jù)可視化是干啥的，聊聊人生，就這么結(jié)束了。
2天后接到了面試官請(qǐng)吃飯的電話，大概一共20多人，果斷去蹭飯。吃飯期間主要是看一個(gè)中科院的博士和我終面面試官談笑風(fēng)生，然后作為桌上唯一一個(gè)本科生我只能反復(fù)賣萌。基本上確定了offer。后來(lái)過(guò)了好久才收到正式offer。
MSRA RSDE
其實(shí)這個(gè)我只是隨口和mentor一說(shuō)，結(jié)果mentor真就給我推薦了，大組的老大面我。之前聽從mentor的建議練了練講述問(wèn)題的邏輯，改觀也不大挺捉雞的。還好面的時(shí)候不算太差，沒(méi)有毀mentor的聲譽(yù)。面試時(shí)講了講實(shí)習(xí)時(shí)做的項(xiàng)目，項(xiàng)目那么水也沒(méi)什么可講的，談了談人生，就結(jié)束了。由于是轉(zhuǎn)正面，沒(méi)什么參考價(jià)值。從mentor那得知不出意外果斷沒(méi)過(guò)。
Hulu SDE
HULU是最近面的，先是因?yàn)檫@公司太高大上覺得成功概率不大而不是很注意，忘投了。最近組里有同學(xué)不想讀博要開始找工作，發(fā)現(xiàn)HULU還可以投，于是我就跟著他投了一下HULU。兩天后收到HR姐姐電話，約了面試時(shí)間，這次又遇上HR姐姐沒(méi)發(fā)我面試郵件了，只能推后兩天。近期心情不爽加上組里項(xiàng)目進(jìn)入關(guān)鍵時(shí)期，所以面試只準(zhǔn)備了一晚上，刷夜刷的快刷出人命了。又是喜聞樂(lè)見的無(wú)準(zhǔn)備的逆風(fēng)裸面。
無(wú)準(zhǔn)備是注定要跪的，一面第一題就把題意弄錯(cuò)了，相當(dāng)于做了一個(gè)完全不同的題。題目是給你一個(gè)完全二叉樹，求其中滿足BST條件的最大的子樹，這里子樹的定義是以樹中某一節(jié)點(diǎn)為根，包含其所有后代節(jié)點(diǎn)的樹。DFS然后合并就行，DFS的時(shí)候維護(hù)每棵子樹的最大最小值。隨后忘了問(wèn)的什么了，總之好像不是很難。后來(lái)問(wèn)了問(wèn)項(xiàng)目相關(guān)的東西，感覺自己講的比之前面試有邏輯多了。
隨后休息幾分鐘迎來(lái)第二個(gè)面試官。第二個(gè)面試能更年輕些，也是先問(wèn)了問(wèn)項(xiàng)目。隨后問(wèn)了下如何用二分寫整數(shù)開根號(hào)，嗯，你沒(méi)有聽錯(cuò) int范圍內(nèi)的非高精度的開根號(hào)，我的回答就是要注意一下乘法不溢出，設(shè)好上限。然后問(wèn)如何實(shí)現(xiàn)double型小數(shù)的開根號(hào)，精確到小數(shù)點(diǎn)后指定位數(shù)（多少位是由一個(gè)整數(shù)給出），然后我就無(wú)腦的寫成和整數(shù)幾乎一樣的了，結(jié)果獲得了“面試時(shí)二分寫殘了”的稱號(hào)。這個(gè)問(wèn)題容易犯得是這么幾個(gè)錯(cuò)誤，一個(gè)是精確位數(shù)為負(fù)數(shù)時(shí)如何讓這個(gè)數(shù)還有意義，一個(gè)是在被開方數(shù)小于1的時(shí)候二分初始上下界如何確定。再一個(gè)爭(zhēng)取做到如果二分時(shí)恰好碰到相等時(shí)，最好直接返回，使答案更精確。感覺hulu的面試都不算太難，就是都很注重細(xì)節(jié)。然后問(wèn)了個(gè)經(jīng)典小清新題，有一個(gè)數(shù)組，已知其中有一個(gè)數(shù)的出現(xiàn)次數(shù)超出了總次數(shù)的一半，以O(shè)（1）的附加空間求出這個(gè)數(shù)，然后面試官讓我證明方法的正確性，這個(gè)真是有一種方法在嘴邊卻說(shuō)不出的感覺，卡了好久，面試官給了一個(gè)比較直觀還嚴(yán)謹(jǐn)?shù)淖C明。可以把找這個(gè)數(shù)的過(guò)程當(dāng)成是這樣的，掃描整個(gè)數(shù)組，一旦發(fā)現(xiàn)有兩個(gè)不相同的數(shù)那么就把這兩個(gè)數(shù)綁在一起扔掉，最后剩下的數(shù)中一定是出現(xiàn)次數(shù)超過(guò)一半的數(shù)。然后問(wèn)了個(gè)推廣，有長(zhǎng)度為n的數(shù)組，一直有數(shù)出現(xiàn)次數(shù)超出n/3求所有滿足這個(gè)條件的數(shù)，解法就是用相似的方法，掃描數(shù)組，一旦發(fā)現(xiàn)三個(gè)互不相同的數(shù)，那么就把他們綁在一起扔掉，最后會(huì)剩一個(gè)或兩個(gè)數(shù)，那么再重新掃描一遍，對(duì)這兩個(gè)數(shù)進(jìn)行計(jì)數(shù)，產(chǎn)生結(jié)果。最后是問(wèn)問(wèn)題，問(wèn)了問(wèn)在hulu都有什么活。從回答來(lái)看，真是什么活都有，面試官還小吐槽了下公司的一些平臺(tái)。然后二面結(jié)束。
三面之前有較長(zhǎng)的休息，三面問(wèn)了好多題。面試官現(xiàn)讓我寫了個(gè)鏈表的快排，有一個(gè)小bug，還算過(guò)得去。隨后問(wèn)了幾個(gè)楊氏矩陣相關(guān)的問(wèn)題。楊氏矩陣就是一個(gè)矩陣，其中元素滿足每行從左到右遞增，每列從上到下遞增。 第一個(gè)問(wèn)題是如何在這里查找一個(gè)數(shù)。如果這個(gè)矩陣有n行m列的話，最優(yōu)方法復(fù)雜度是O(m+n)的，方法自行百度吧。下一個(gè)問(wèn)題是如何對(duì)楊氏矩陣中元素進(jìn)行排序，我給了2個(gè)方法，一個(gè)是簡(jiǎn)單的K路歸并排序，另一個(gè)是利用分治法，把矩陣均分成4塊，先對(duì)左上角也就是值最小的那一塊排序，在最左下角和右上角的2塊進(jìn)行排序后歸并，再對(duì)右下角值最大的那一塊排序，把這三部分接起來(lái)就是結(jié)果?？上н@2種方法都是O（n*n*logn）的復(fù)雜度，后來(lái)面試官說(shuō)，他也不知道有沒(méi)有O（n*n）的方法。之后又問(wèn)了一個(gè)題，就是給一個(gè)數(shù)組，如何根據(jù)這個(gè)數(shù)組構(gòu)造出楊氏矩陣。我只給了了一個(gè)先把數(shù)組排序，然后由小到大現(xiàn)填矩陣第一行和第一列，不斷減小問(wèn)題規(guī)模的方法。最后又問(wèn)了一個(gè)問(wèn)題，對(duì)于一個(gè)楊氏矩陣，如果把其中的一個(gè)元素用最小值替代，如何用最少的時(shí)間維護(hù)楊氏矩陣的性質(zhì)。我給了一個(gè)和堆的下沉操作比較相似的方法，最小值元素只能向下或者向右走，走的方向就是相鄰元素值較小的那個(gè)方向，然后把對(duì)應(yīng)的相鄰元素與最小值元素交換，之后繼續(xù)走，最多走O（m+n）步。面完之后我才發(fā)現(xiàn)原來(lái)這種題這么常見，題解這么多。隨后面試官飛快的跑掉了，沒(méi)等我來(lái)得及問(wèn)問(wèn)題。
幾分鐘后HR姐姐進(jìn)來(lái)告訴我面試結(jié)束了，我也不知道是否走完了整個(gè)面試流程，是不是中途就被拒了。
總結(jié)起來(lái)就是還是太弱了。
本站僅提供存儲(chǔ)服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)
點(diǎn)擊舉報(bào)。
