後臺開發工程師
今日頭條
後端研發工程師
找牛客大佬要了白金碼,跳過死亡筆試,直接視訊面,從3點開始,斷斷續續到晚上8點結束。
每個面試官給我的感覺都是怎麼這麼高冷啊。
一面:1.寫一個題,找一個無序陣列的中位數
2.寫了個快排,然後讓我找到無序陣列第k大的一個數,我說先排序再找,實際上可以用快排的partition函式。
3.快排的時間複雜度,最壞情況呢,最好情況呢,堆排序的時間複雜度呢,建堆的複雜度是多少,nlgn。
4.作業系統瞭解麼,linux和windows
5.說說Linux的磁碟管理,一臉懵逼
x有哪些程序通訊方式,五大件
x的共享記憶體如何實現,大概說了一下。
8.共享記憶體實現的具體步驟,我說沒用過
et網路程式設計,說一下TCP的三次握手和四次揮手,中間網路不好,面試官都沒聽清楚,很尷尬
10.跳過網路,問了專案的一些東西
11.問我如何把docker講的很清楚,我從物理機,虛擬機器到容器具體實現稍微說了下。
12.問我cgroup在linux的具體實現,不會。
13.多執行緒用過哪些,chm和countdownlatch在實習用過
14.不得不吐槽下今天牛客的視訊網速,不知道啥原因卡的一比,明明下載網速很正常啊,牛客視訊每秒才20k。。瘋狂掉線搞得很蛋疼。
二面:
1.自我介紹
的集合類哪些是執行緒安全
3.分別說說這些集合類,hashmap怎麼實現的,扯了很多
L索引的實現,innodb的索引,b+樹索引是怎麼實現的,為什麼用b+樹做索引節點,一個節點存了多少資料,怎麼規定大小,與磁碟頁對應。
L的事務隔離級別,分別解決什麼問題。
s瞭解麼,如果Redis有1億個key,使用keys命令是否會影響線上服務,我說會,因為是單執行緒模型,可以部署多個節點。
7.問我知不知道有一條命令可以實現上面這個功能。不知道
s的持久化方式,aod和rdb,具體怎麼實現,追加日誌和備份檔案,底層實現原理的話知道麼,不清楚。
s的list是怎麼實現的,我說用ziplist+quicklist實現的,ziplist壓縮空間,quicklist實現連結串列。
edset怎麼實現的,使用dict+skiplist實現的,問我skiplist的資料結構,大概說了下是個實現簡單的快速查詢結構。
11.瞭解什麼訊息佇列,rmq和kafka,沒細問
12.寫題時間到。第一題:寫一個層序遍歷。
13.第二題:寫一個插入樹節點到一顆排序樹的插入方法,使用遞迴方式找到插入位置即可。
14.第三題:一個有向圖用鄰接矩陣表示,並且是有權圖,現在問怎麼判斷圖中有沒有環。
15.我說直接dfs走到原點即為有環,剛開始寫的時候我又問了一嘴是不是隻要找到一個就行,面試官說是的,然後我說這樣應該用bfs,有一次訪問到原節點就是有環了。
16.面試官問我不用遞迴能不能做這個題,其實我都還沒開始寫。然後我就說沒有思路,他提示我拓撲圖。我沒明白拓撲圖能帶來什麼好處。現在一想,好像當訪問過程中找不到下一個節點時就說明有環。做一個訪問標記應該就可以。
17.第四題:一個二叉樹,找到二叉樹中最長的一條路徑。
我先用求樹高的方式求出了根節點的左右子樹高度,加起來便是。
18.然後面試官提示需要考慮某個子樹深度特別大的情況,於是我用遍歷的方式重新整理最大值,用上面那個方法遍歷完整個樹即可。
19.面試官說複雜度比較高,但是由於時間問題就說結束了。
三面:
三面的面試官真的高冷啊,不苟言笑就算了,我問他問他他都不愛搭理的,搞得我內心慌得一比,感覺涼涼。
1.介紹一下專案
2.你談到的併發技術,chm和countdownlatch怎麼使用的
3.為什麼要這麼處理,使用執行緒池是不是也可以。我說也可以
4.作業系統的程序通訊方式,殭屍程序和孤兒程序是什麼,如何避免殭屍程序,我說讓父程序顯示通知,那父程序怎麼知道子程序結束了,答不會。
5.計算機網路TCP和UDP有什麼區別,為什麼迅雷下載是基於UDP的,我說FTP是基於TCP,而迅雷是p2p不需要TCP那麼可靠的傳輸保證。
6.他說不對,我說是不是因為要建立連線,開銷比較大,他說不對
7.我說p2p的傳送節點很多,所以不是那麼需要各種傳輸保證,他說不對。
8.我說TCP會自動分包而TCP可以自己定義資料長度。。他還是說不對。
最後他說算了。我們問下一個吧。
9.作業系統的死鎖必要條件,如何避免死鎖。
10.寫一個LRU的快取,需要完成超時淘汰和LRU淘汰。
我說用lhm行不行,他說用linkedlist和hashmap可以。
於是我就寫了put和get函式,進行了隊頭隊尾操作。
他說get複雜度會不會太高,我瞎掰了半天沒找到辦法,他說那就這樣吧,今天面試到這。
11.媽蛋,過期淘汰的處理我還沒寫呢,你就說結束了,感覺涼了啊,我說我要不要把剩下邏輯下完,他說不用,心涼了一大截~
12.然後HR小姐姐讓我等結果了。溜了溜了