Re: [閒聊] interview 心得

[yzugsr (miaout17)]

背景介紹：我是後端工程師，不特別專精資料庫。
目前離職休息三個月，最近比較少碰程式。

未婚妻不是資工人，但她的興趣是逛論壇拿各種題目考我 XD
一早沒睡醒就被她挖起來回答問題
除了1NF一時忘掉精確定義，只能說明正規化的概念
其他應該都自信有答對。

因此，我想以資工系背景來說，如果當初是選擇花些工夫在基本功上，
儘管離開學校幾年後，理論上都還能回答出來，算是很合理跟用心的面試題。

不過，晚上回來看到板上眾多回應，也想分享幾點看法

* 關於很多人覺得像聯考

一言以敝之：我覺得聯考般的筆試與面試有關鍵的差異。

考題是死的，考官是活的。
優秀的考官能從談話中了解對方是死背還是活記。

對方答得極流暢時，有經驗的考官總是能看出對方是死背還是真理解，
或者換個角度問個相關的應用問題，看看對方能不能正確的運用自己知道的概念。
即便對方答不太出來時，考官也可以選擇從旁引導，
看看對方是不是知道概念但一時忘了定義。

以normalization及join為例，
大學時認真修過資料庫（或認真自學）的話都會有個印象。
如果對方第一時間答不出來，但經過引導後可以講出概念，也可能會算是不錯的表現。

反倒是如果面試者的心態停留在面試題只有對與否，只有說對才過關，
這樣才是真正停留在非黑即白的聯考心態。

* 關於很多人覺得台灣業界用不到

DK大的例子大多是DB及資料結構的基礎知識。
如果「台灣業界用不到」指的是：用不到這些底層、基礎、細節的知識與概念。
甚至就連應徵相關工作的人也不需要對其有更扎實地了解，
我覺得這是很堪慮的一件事。

這代表台灣的業界大多數在做一些表淺的軟體工作。
做專案容易流於把現成技術兜一兜
而不去理解底層實作，運用演算法及資料結構上等底層技術改善問題的解法。

別誤會，我不是說表淺的軟體工作不好。
市場上是的確需要這樣的工作，也需要有人具備技術及管理的經驗。
但整個業界都在做表淺工作的話，那就代表我們的業界很缺乏多元性，容易抑制不同方向
的創造能量。
而一個健康的產業是需要有各式各樣的人做各式各樣的工作

但人要正面思考，
所以我想不是台灣業界都不用到啦，至少DK大的公司就有用啊。

* 記起來或查出來？這是一個程度問題

所有工程師都必須承認，我們就是沒辦法記起所有領域內的知識。
但這不代表熟悉並內化領域知識不重要，
儘管還是會忘，真正了解的人其回復速度還是要快得多。

事實上，當你腦海裡這些真正了解的東西越多，
通常就越容易找到貼近本質問題的解法。
寫出來的程式架構也越簡單，需要的程式碼量也越少，
不容出易錯。

（這邊原本想舉個例子來說明，但怕文章太長，我把例子放到下面，
    如果有興趣的再看，我想說的結論差不多也如上述了）

==例子分隔線例子分隔線例子分隔線例子分隔線例子分隔線例子分隔線==

在以下的例子中，我預設所謂的記起來，都是真的有一定程度的理解，
不是當成單純背英文單字。
畢竟驗證面試者究竟死背還是活記當然是面試官的責任。

你在線上遊戲「鬼島online中」實作一個「鬼島無雙」的遊戲活動。
在15分鐘活動內，維持每分鐘都有殺人且越久不死的積分排名越高。
超過一分鐘沒殺人或被殺時移出排行榜並積分歸零。
每個玩家隨時可以看到自己前後五名的玩家積分。
（MMORPG通常是分散式系統，但假設「鬼島無雙」由一台server控管
  其他server會把擊殺event送到這台server處理）
（這當然不是一個精確的spec，只是粗略的例子）

把每次擊殺記錄放進用資料庫嗎？
但短短15分鐘的活動不需要persistence，用資料庫只是白白增加複雜度。

如果自己寫code處理呢？
回憶自己知道的資料結構
或許可以找出更新排行榜O(N)或O(logN) time complexity的解法

仔細想想或許會靈光一現，LRU Cache和這個問題好像有點像
LRU Cache常用一個linked list+一個hash map實作
鬼島無雙也可以用一個linked list最後一次殺人時間的順序。
再用一個hash map記住玩家ID與資料的對映（含linked list node pointer）。
與LRU Cache不同的是，再多用一個linked list記住排行榜順序。

在這個資料結構下，所有排行榜的更新都可以在constant time完成。
（包含計算排名變動時，有哪些前後五名的玩家需要被通知）

好啦，這個例子可能有bug或不清楚的地方，請不要跟小弟計較 XD
但相信大家應該可以理解我想說什麼。

把一個應用問題（鬼島無雙）化為正規的抽象問題。
思考各種可以應用的資料結構特性、時間空間複雜度是否適合解決這個問題。
試著在記憶中尋找表面毫不相關但本質相似類似的問題（LRU cache）取得靈感。
改變現有的方法以解決自己的應用問題，甚至從頭構思方法。

這些能力都需要充足的基本功，在腦海中搜尋可用的知識。
而不是要用的時候再一一去查。
（至少google「鬼島」「殺人」應該找不到LRU cache啦 XD）
就面試官或公司的角度而言，有時候期望的不只是找到單純能接工作的人
而是潛力十足、有機會青出於藍的人

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.248.88.223
※ 文章網址: http://www.ptt.cc/bbs/Soft_Job/M.1406978307.A.C23.html
推 kkdlin:推
推 dophin332:
推 LetDogDay:推
推 stonehomelaa:小錯字 不需要presistance => persistence
謝謝，已訂正
推 lovdkkkk:例子的部份我覺得比較像 #1Jt8xivt 的考法
→ lovdkkkk:OO 問題 -> 可以用 XX, YY + ABC..., 問題 -> 解法這樣
→ lovdkkkk:不過擅常這種的, 不見得擅常 "XX 跟 YY 的差別" 這種問題
→ lovdkkkk:(甚至可能反而更不擅常...)
→ lovdkkkk:"廣、多、實測、活用" 與 "熟記、深入細節"
→ lovdkkkk:有一定程度上的衝突
推 chrisyanglom:推這篇 很多人覺得工作用不到的，或許是真的不需要
→ chrisyanglom:但也有可能你從來沒有仔細想過是不是可以用到這些東
→ chrisyanglom:西去改善自己的程式 其他很多領域也是一樣
→ chrisyanglom:當一個人心存反正用到再去查的時候
→ chrisyanglom:其實也有可能代表真正要用到的情況他卻沒有想到可以
→ chrisyanglom:這樣用
→ chrisyanglom:真正看重的不是一個員工會不會implement某個資料結構
→ chrisyanglom:而是他是不是能在適當的時機想到要用哪個結構
→ chrisyanglom:但如果還需要google才知道這些結構是什麼
→ chrisyanglom:我覺得應該很難自己判斷何時需要用
→ lovdkkkk:我覺得前面講估狗的指的是很細節的部份
→ lovdkkkk:就是例如排序, 知道有 quick 跟 merge 比較快
→ lovdkkkk:但是兩者差別不是很清楚這種
→ lovdkkkk:至少我是這個意思, 之所以提到沒學過去估狗也很快是強調
→ lovdkkkk:對沒學過的人來說都不難, 學過只是忘記的人回熟更沒問題
→ chrisyanglom:所以說有實力的面試官應該要能分辨得出是不是死背的
→ chrisyanglom:另外如果真的理解的人，面試前花點時間準備一下
→ chrisyanglom:也不會太麻煩吧，就像我們也要整理履歷自傳一樣
→ chrisyanglom:如果只知道quick、merge比較快，再問下去卻都不知道
→ chrisyanglom:反而容易讓人懷疑是用背的，不是嗎?
→ lovdkkkk:嗯嗯, 對, 知道方向的話有複習應該就 ok 才對
→ lovdkkkk:痾, 不過那是我都沒複習下最記得的事耶 XDD
推 chrisyanglom:哈哈，我好像也是，面試突然被問到如果又有點緊張
→ chrisyanglom:我也不確定是不是能馬上想起來
→ chrisyanglom:可是話說回來，我認為比我厲害的那些高手
→ chrisyanglom:我覺得有可能不需要準備也能從容回答，因為他們已經
→ chrisyanglom:可以運用自如了，就像公車搭久了就不用特別查時刻表
→ chrisyanglom:所以關鍵還是能不能判斷出是死背還是真的懂XD
→ pest:推
推 greatroy:每每看到這類討論，總覺得台灣的軟體業其實是很有希望的
→ greatroy:但不知為何，我們遇到的國內軟體廠商卻完全不是這麼一回
→ greatroy:事...
→ greatroy:一家號稱國內前幾大的軟體公司，卻連支轉檔程式寫了半年
→ greatroy:到現在都快8個月了，還不時出現問題...
→ greatroy:希望各位有志之士，有機會的話可以留個名合作，
→ greatroy:省的老是遇到這種XXX的廠商.
推 chrisyanglom:因為大學時認識資工領域最強的幾個朋友幾乎都出國了
→ michaelz:這更新得要O(n)吧  constant time應該不行
不知道是不是問題spec不清楚造成誤解
試著以C++說明…

定義資料結構

struct Player {
  int playerId;
  int lastKillTime;
  PlayerNode* killNode; // A pointer to killList. See below
  PlayerNode* rankNode; // A pointer to rankList. See below
}

struct PlayerNode { // Doubly linked list
  Player* player;
  PlayerNode* prev;
  PlayerNode* next;
}

hash_map<int, Player*> playerMap;
PlayerNode* killList; // list中越前面的玩家，最後殺人時間越晚
PlayerNode* rankList; // list中越前面的玩家，留在排行榜越短，名次越低

注意程式永遠保持playerMap, killList, rankList元素個數相同。
有在playerMap中的玩家就是在排行榜上的人。

幾個use case：

* 玩家殺人時
先透過playerMap查詢是不是已在榜上O(1) time
1.若不在榜上
  建立Player資料並插入playerMap O(1)
  再將兩個PlayerNode插入killList和rankList的前端 O(1)
  Player和兩個PlayerNode間要互相記住對方的指標
  並更新lastKillTime為目前timeStamp。
2.若在榜上
  從Player中取出killNode，將killNode從killList中移除 O(1)
  再將killNode插回killList前端。
  並更新lastKillTime為目前timeStamp。

* 玩家被殺時
先透過playerMap查詢是不是已在榜上O(1)
1.若不在榜上則不需處理
2.若在榜上則從hash table及兩個linked list中分別移除節點 O(1)

* server可每秒觸發「清除排行榜上一分鐘沒殺人的玩家」
從killList後端向前走訪。
檢查Player上的lastKillTime是否已在一分鐘前。
若已過期則清分別在hash map及兩個linked list中清除，並繼續走訪。
若未過期則可停止檢查。
除非edge case（一堆人最後殺人時間相同），否則average是constant time。

* 查找某玩家前後五名的玩家
就從rankList向前後走5個節點就好。 O(1)

====

這個例子或許不夠真實跟完備，造成一些誤解。
但我想說明的是，這並不是一個面試問題。
基本功扎實的人，在解決實際問題時，更有機會找到不一樣的解法。

推 stonehomelaa:資工的強者大多不是出國就是去ic design
※ 編輯: yzugsr (111.248.88.223), 08/04/2014 00:19:46
※ 編輯: yzugsr (111.248.88.223), 08/04/2014 00:21:26
推 bleed1979:map查詢插入時間複雜度。。。 這個map實作是用那種DS？
前面有寫hash map，查詢和插入都amortized O(1)
推 lovdkkkk:這分數怎麼算啊, 看起來規則好像變了 @@
→ lovdkkkk:變成越接近最後一瞬間殺人的排名越高
抱歉規則寫的不夠清楚（我加了一句話，但原本想表達的意思沒變）
進排行榜越久的人分數越高，越接近最後一瞬間殺人的
例如殺人事件以「A殺人 -> B殺人 -> C殺人 -> A被殺 -> C殺人」順序發生
排行綁上是先B再C，A因為被殺所以被踢出去了
但如果接下來大家都殺不到人，那B會先因為一分鐘規則而被踢出排行榜
※ 編輯: yzugsr (61.230.7.161), 08/04/2014 10:44:18
→ lovdkkkk:所以是沒有 "總分" 這回事, 本來以為會根據什麼算總分 XD
推 FukadaKyoko:推 沒用到不代表用不到 只是問題深淺的差異
推 kimmyariel:推...