Re: [閒聊] interview 心得
背景介紹:我是後端工程師,不特別專精資料庫。
目前離職休息三個月,最近比較少碰程式。
未婚妻不是資工人,但她的興趣是逛論壇拿各種題目考我 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
推
08/02 19:26, , 1F
08/02 19:26, 1F
推
08/02 20:37, , 2F
08/02 20:37, 2F
推
08/02 20:58, , 3F
08/02 20:58, 3F
推
08/02 22:23, , 4F
08/02 22:23, 4F
謝謝,已訂正
推
08/02 22:35, , 5F
08/02 22:35, 5F
→
08/02 22:37, , 6F
08/02 22:37, 6F
→
08/02 22:37, , 7F
08/02 22:37, 7F
→
08/02 22:38, , 8F
08/02 22:38, 8F
→
08/02 22:40, , 9F
08/02 22:40, 9F
→
08/02 22:40, , 10F
08/02 22:40, 10F
推
08/02 22:44, , 11F
08/02 22:44, 11F
→
08/02 22:44, , 12F
08/02 22:44, 12F
→
08/02 22:45, , 13F
08/02 22:45, 13F
→
08/02 22:45, , 14F
08/02 22:45, 14F
→
08/02 22:46, , 15F
08/02 22:46, 15F
→
08/02 22:46, , 16F
08/02 22:46, 16F
→
08/02 22:48, , 17F
08/02 22:48, 17F
→
08/02 22:49, , 18F
08/02 22:49, 18F
→
08/02 22:49, , 19F
08/02 22:49, 19F
→
08/02 22:50, , 20F
08/02 22:50, 20F
→
08/02 22:51, , 21F
08/02 22:51, 21F
→
08/02 22:51, , 22F
08/02 22:51, 22F
→
08/02 22:52, , 23F
08/02 22:52, 23F
→
08/02 22:55, , 24F
08/02 22:55, 24F
→
08/02 22:57, , 25F
08/02 22:57, 25F
→
08/02 23:01, , 26F
08/02 23:01, 26F
→
08/02 23:01, , 27F
08/02 23:01, 27F
→
08/02 23:02, , 28F
08/02 23:02, 28F
→
08/02 23:03, , 29F
08/02 23:03, 29F
→
08/02 23:04, , 30F
08/02 23:04, 30F
→
08/02 23:05, , 31F
08/02 23:05, 31F
→
08/02 23:06, , 32F
08/02 23:06, 32F
推
08/02 23:07, , 33F
08/02 23:07, 33F
→
08/02 23:07, , 34F
08/02 23:07, 34F
→
08/02 23:08, , 35F
08/02 23:08, 35F
→
08/02 23:08, , 36F
08/02 23:08, 36F
→
08/02 23:09, , 37F
08/02 23:09, 37F
→
08/02 23:10, , 38F
08/02 23:10, 38F
→
08/02 23:14, , 39F
08/02 23:14, 39F
推
08/02 23:24, , 40F
08/02 23:24, 40F
→
08/02 23:24, , 41F
08/02 23:24, 41F
→
08/02 23:25, , 42F
08/02 23:25, 42F
→
08/02 23:26, , 43F
08/02 23:26, 43F
→
08/02 23:26, , 44F
08/02 23:26, 44F
→
08/02 23:28, , 45F
08/02 23:28, 45F
→
08/02 23:28, , 46F
08/02 23:28, 46F
推
08/03 05:24, , 47F
08/03 05:24, 47F
→
08/03 19:20, , 48F
08/03 19:20, 48F
不知道是不是問題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)
====
這個例子或許不夠真實跟完備,造成一些誤解。
但我想說明的是,這並不是一個面試問題。
基本功扎實的人,在解決實際問題時,更有機會找到不一樣的解法。
推
08/03 22:34, , 49F
08/03 22:34, 49F
※ 編輯: yzugsr (111.248.88.223), 08/04/2014 00:19:46
※ 編輯: yzugsr (111.248.88.223), 08/04/2014 00:21:26
推
08/04 03:42, , 50F
08/04 03:42, 50F
前面有寫hash map,查詢和插入都amortized O(1)
推
08/04 08:13, , 51F
08/04 08:13, 51F
→
08/04 08:14, , 52F
08/04 08:14, 52F
抱歉規則寫的不夠清楚(我加了一句話,但原本想表達的意思沒變)
進排行榜越久的人分數越高,越接近最後一瞬間殺人的
例如殺人事件以「A殺人 -> B殺人 -> C殺人 -> A被殺 -> C殺人」順序發生
排行綁上是先B再C,A因為被殺所以被踢出去了
但如果接下來大家都殺不到人,那B會先因為一分鐘規則而被踢出排行榜
※ 編輯: yzugsr (61.230.7.161), 08/04/2014 10:44:18
→
08/04 12:28, , 53F
08/04 12:28, 53F
推
08/04 14:33, , 54F
08/04 14:33, 54F
推
08/04 23:35, , 55F
08/04 23:35, 55F
討論串 (同標題文章)
完整討論串 (本文為第 20 之 24 篇):