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

面試問題（職位：大數(shù)據(jù)創(chuàng)新中心爬蟲方向?qū)嵙暎?/p>

一面：

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

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

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

二面：

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

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

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

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

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

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

最新評論