Tuesday, July 21, 2015

2011 北京微軟面試之旅

說起來這也是篇故事回味


電話面試篇


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


後記


因為機票回去的時間是自己選的,微軟也好心地把旅館訂到面試的隔天,不會馬上趕你走。之後兩天就和姑丈在北京市內玩一玩,也順便去爬了長城,吃了烤鴨等。在聖誕夜那晚又回來了台北,結束這短短幾天的北京之旅。

0 意見: