說起來這也是篇故事回味
電話面試篇
2011.12.09 一個周五的早上11點,接到 HR 的電話希望約當天下午兩點線上語音面談,當時是應徵北京微軟搜尋技術中心的 Software Development Engineer (就是Bing嗎~~)
時間來到兩點十分...
面: 可不可以說說您做過些什麼東西
(扯扯甲尚的case 扯扯計網的IM軟體 居然沒想到有Motion Planner)
扯到以前多媒體弄過搜尋引擎的時候,面試官就開始問有關搜尋的東西,像是爬下來的資料,如果還沒有任何使用者做過查詢,要怎麼決定優先順序之類的,講到某個程度瞎掰不下去就只好說研究領域不在這,順便提了一下在做什麼。
之後問了三個關於演算法的問題,由於個人腦細胞有限,最簡單的問題實在只記得大概了。這三個問題要順便說明複雜度。
1. 您知道數組吧~~ (是 array 嗎~~) 對 是 array ~~
給定一個二維數組 只會有 1 or 0 上下左右算是連通
ex:
00101
10100
11111
01000
10101
這個裡面總共有 5 塊連通的 1s (右上、最底下的三個、和那一片),這問題您有沒有辦法解 (開始拿 motion planner 解釋寫過類似甚至更難的東西)
不過面試官的電腦沒有 Java ,早知道早點把 Qt 那個 UI 介面做完了......
所以後來面試官請我晚上八點前寄 C++ 程式碼 + 執行檔 + 一組你設計的測資 給他
2. 給一個一維數組,會有正數負數或零,請問怎麼找出一個連續子陣列其和最大。這題夠簡單吧...不過只記得大方向的亂喇賽了,反正就是要那個 O(n) 的演算法嗎~~
3. 您知道串列吧 (是linked list嗎??) 欸~~對!! 是 linked list
串列很基本是吧 (不妙...) 假設有個串列很長
他的尾端可能不小心又指回來自己某個節點造成 cycle
,那要怎麼偵測出一個串列有沒有迴圈
3-1. 因為list很長 記錄下每個節點的記憶體位置是不可行的
3-2. 不能改變串列節點的資料結構
龜兔賽跑來囉~~
剩下就是問對微軟有沒有什麼問題想了解的
北京海淀區篇
收到面試通知後(微軟出的機票跟住宿),2011/12/21 一個人隻身前往北京,第一次有一種,阿原來這就是自己獨立出來行走的感覺阿。晚上到了北京,姑丈載我到微軟安排的飯店,準備隔天的面試。
面試當天一連串四小時的真是可怕,從下午一點到晚上快七點,中間有一段時間等最後一關的 "部門頭頭",所以先讓我休息了一個多小時。
四個人裡面 推測前面三個應該都是工程師類型的人,目測年齡 應該是 4 > 3 > 1 > 2。
以下問題,如果直覺想到暴力法能解決的,都不是想要的答案 XD
附註:還要大概說一下自己的算法複雜度是多少
第一位:
自介閒聊等
1) 給一個 Unsorted int array 和 S 請找出所有的 pair (i, j) such that
S = array[i] + array[j]; PS: (i, j) 和 (j, i) 視為相同
Hint: You can sorted if you like.
2) 一個平面上的正方形和圓形 要如何判斷是否重疊呢? (寫過Planner沒道理不會阿)
那兩個正方形呢?! (更簡單了)
第二位:
自介閒聊等
1) Thread 和 Process 有何不同 ? 盡量舉例 (這是OS吧)
Thread / Process 有無自己的 Stack/Heap 呢 ?
(其實沒把握的時候可以自己推 但是要有邏輯的推導)
2) C++和Java的差別 用C++遇過什麼瓶頸 virtual function知道怎麼實做的嗎?
vTable 是class存在一份 還是每個實體都有一份
3) 給一個 3L 和 5L 的水桶 (無刻度 形狀不規則) 還有一個無限供水的水龍頭,
如何裝出 4L 的水? (2L 2L倒入別的容器不算 要一次出現 4L)
擴展: 給 ML 和 NL 的水桶 如何到出 KL 的水? 具體的步驟
假設給定的 (M, N, K) 在有限的步數內保證有解
4) Java的GC機制如何,或者是說在 C++ 要如何實現 Garbage Collection的機制呢?
可以具體編程嗎?
5) 動態配置時 若是常常的 new / delete 會消耗蠻多的資源,因此我們會設計一個 ObjectPool 預先配置好空間,當有需要空間時 使用 getObj 跟這個 pool 申請,使用完畢用 returnObj 返回使用的空間。具體實現,這兩個函數的內容,且須支援 multi thread。
寫完後 getObj 裡面有沒有能加速的地方
第三位:
自介閒聊等
1) 一個環狀公路上 有N個加油站 這些加油站都有儲油 oil[N],這些加油站是隨機分布在這個環狀公路上,也就是非等距分布。假設有一台車走一單位的路需要耗一單位的油,且公路長為 D 且 Sigma(oil[i]) - D = 0 ( for i=0~N ) ,意即加油站的總油量足夠走完整圈路。
現在有一輛汽車油箱是空的,能找出從某個加油站出發,可以繞一圈回到原地,輸出該加油站的編號。
第四位: (部門頭頭)
自介閒聊等
原本以為他會問一些比較非程式的問題......結果.......
1)
我有一個 byte array 假設是 { 3, 2, 6, 6, 6, 6, 5 },裡面保證不會有 20 這個元素,可以試著壓縮這個 array 嗎? 壓縮的結果必須也是 byte array。你的算法 worst case 可以舉例嗎? 能更好嗎?
若是 20 亦會出現在此 array 中呢? 這樣算法結果勢必會差些 但有方法嗎?
PS: 此為串流所以不知道整個資料多大
頭頭: 恩 我只有一個問題要問你 今天就到這吧~~
Seminar時說的沒錯: 面試到後來已經不知道再說什麼鬼話了
整體說來面試過程不太像上對下的感覺,比較像是在實驗室討論,可以闡述想法和面試的人互動,他們會跟著你的思路去走。闡述久了,他們多少也會給些提示,有些東西要立馬想出來也是有難度,科科。
然後白板跟紙上 coding 一定要會 XD
後記
因為機票回去的時間是自己選的,微軟也好心地把旅館訂到面試的隔天,不會馬上趕你走。之後兩天就和姑丈在北京市內玩一玩,也順便去爬了長城,吃了烤鴨等。在聖誕夜那晚又回來了台北,結束這短短幾天的北京之旅。