公司就不說了，等下公司面試官看到不太好……

面試問題（職位：大數(shù)據(jù)創(chuàng)新中心爬蟲方向?qū)嵙?xí)）：

一面：

1.給一個(gè)數(shù)組，里面數(shù)據(jù)比如：2 3 4 1 1 1 1 1，值代表往后最多能跳多少次，問跳到最后一個(gè)的最少步數(shù)？（貪心）
答：這題剛開始想的dp，后面想不出方程，然后用了說dfs暴力搞時(shí)間復(fù)雜度n!，然后再想一下，我覺得是貪心，然后還沒說出他就說你想一下貪心，然后想了30秒就想到了，跟他說了下思路，然后他說對了，不用寫代碼了。然后又問我怎么證明對不對？這個(gè)想了好久不知道怎么證明，因?yàn)樨澬淖C明感覺是挺難的，然后說不會(huì)……

2.給一個(gè)樓梯，從最下面往上走，每次可以走1到n步，求總共有多少種走法？（dp或者公式）
答：這題我還給校賽出過題，所以記憶特別清晰，一看就知道是dp，而且方法特容易。
然后他說能不能更快一點(diǎn)的？
然后我說這好像有公式的吧，我推了一下，推的時(shí)間好像超過2分鐘了，然后他就提示了一下說用二進(jìn)制的方法試一下？
然后發(fā)現(xiàn)都是2^(n-1)。

3.還有什么問題我忘了……

二面：

1.給一個(gè)字符數(shù)組，字符包含a-z、1-9，比如：a b c 4 b 2 a c 1 1 3，求只出現(xiàn)一次的第一個(gè)出現(xiàn)的字符？（這題太坑，HashMap+queue）
答：這題我感覺太容易了，然后說就用一個(gè)數(shù)組統(tǒng)計(jì)一下字符出現(xiàn)的字?jǐn)?shù)，然后再遍歷一下這個(gè)統(tǒng)計(jì)的數(shù)組，第一個(gè)出現(xiàn)的就是了。
然后他說你能只遍歷一遍，然后O(1)輸出這個(gè)字符嗎？
然后想了好久，想過set、map、queue、list等，還是沒想出來，然后跟他說沒想出來。
然后他說你試試用你剛才的兩個(gè)數(shù)據(jù)結(jié)構(gòu)組合試一下，然后我又想啊想，也沒想出來。
然后他說你看看這個(gè)LRU Cache，這個(gè)里面就是用的HashMap和queue，你再試一下用這兩個(gè)。
然后我想，你不是說O(1)的嗎，現(xiàn)在這些最少也O(lgn)啊，不是坑我嘛！
然后我又想，也沒想出O(1)的方法。
然后他說queue統(tǒng)計(jì)次數(shù)，HashMap存儲(chǔ)queue的指針不就行了嘛，然后演示了一下，感覺會(huì)了，然后他讓我寫出代碼來……
然后發(fā)現(xiàn)雖然思路會(huì)了，但是HashMap怎么存指針不知道，然后還是說沒會(huì)，然后他感覺我指針不會(huì)還是啥地，就讓我寫一下單鏈表的結(jié)構(gòu)和查詢一個(gè)值的函數(shù)，然后1分鐘就搞定了，他說那還行吧……
（那時(shí)我都想跟他說了，剛才用的HashMap和queue不能達(dá)到O(1)的復(fù)雜度輸出結(jié)果，而且空間復(fù)雜度還非常大，雖然能降到O(lgn)，但是O(n)就只用了一個(gè)數(shù)組就行了，后面感覺不能頂撞他，所以不敢說……）

2.有一個(gè)html文本字符串，讓我取出<a href="提示我這個(gè)鏈接地址">sflkj</a>這個(gè)a標(biāo)簽里面的href的鏈接地址？
答：這個(gè)剛開始我直接for遍歷的，寫了十幾二十行代碼他看不下去了，說有如果有個(gè)find函數(shù)尋找字符串首地址，重新寫一下看看。
然后我又擦了重新寫，又跟他聊了bug，說鏈接地址里面可能有>什么特殊字符的，然后我又處理，寫了幾分鐘吧，寫好了，然后他說還行吧，不過還得優(yōu)化一下，讓代碼最少。（因?yàn)槲叶x了4，5個(gè)int的變量讓他不爽）
然后他又給我寫了一下最優(yōu)化的代碼，只用了一個(gè)Int變量就行了，代碼也比我的短。

3.用bfs把一個(gè)圖改成樹？二維數(shù)組表示圖這個(gè)直接隊(duì)列模擬一遍就行了。
但是我用的也是二維數(shù)組表示的樹，然后他說你能不能用一個(gè)結(jié)構(gòu)體表示一下樹，然后我想了一下只會(huì)二叉樹的結(jié)構(gòu)體，然后他提示說二叉樹不是一個(gè)左右結(jié)點(diǎn)嘛是吧，如果多叉樹的話，你放一個(gè)list存子結(jié)點(diǎn)不就有多個(gè)了嘛，然后才恍然大悟。

總的來說，比第一次面試其他公司好多了，第一次面試問的基本不會(huì)，因?yàn)榭嫉牟皇撬惴ê蛿?shù)據(jù)結(jié)構(gòu)方面的，都是問的框架或者別的東西，然后還沒復(fù)習(xí)到，所以這次還行吧。
但是他說，你寫的代碼多多少少都有點(diǎn)問題，寫一遍還要debug一遍，你之前比賽的時(shí)候?qū)懘a每次寫一遍還要debug嗎，不能一次就搞定嗎？
然后我說比較容易的題目一般都是寫一遍就行了，難的題目可能要debug一下，然后可能他覺得還行吧。
然后他又說，我發(fā)現(xiàn)你好像不太會(huì)舉一反三啊，數(shù)據(jù)結(jié)構(gòu)那些你都還行，但是組合起來就不行了，然后我只能語塞……

他問我能實(shí)習(xí)多久，這個(gè)之前我覺得實(shí)習(xí)3-5個(gè)月就好了，然后再去別的公司實(shí)習(xí)這樣；就跟他說3，4個(gè)月吧。然后他想了一下說，不能再久點(diǎn)了？我說因?yàn)槊髂?，5月要做畢設(shè)，所以明年四月之前都可以，然后他算了一下，感覺時(shí)間挺多的吧，但是之前說的3，4個(gè)月有點(diǎn)少。因?yàn)榘堰@個(gè)時(shí)間告訴學(xué)長們的時(shí)候，他們說一定要說半年以上，不然公司可能因?yàn)檫@個(gè)原因掛掉的！然后我才發(fā)現(xiàn)之前跟他說的3，4個(gè)月可能會(huì)影響面試結(jié)果，無語了，如果他真因?yàn)檫@個(gè)原因掛我的話，那只能再去面試別的公司了……

最后問我有什么問題有問的？我就問了大數(shù)據(jù)方面的，用的什么語言，他說用的go（一面的面試官挺膜拜他的，說他用go寫了一個(gè)分頁式的爬蟲框架，現(xiàn)在公司都在用他的，據(jù)學(xué)長們說他是行業(yè)的典范，出過書，而且從Hulu回來的）……

最新評論