1
人資:「我看了你的簡歷，你在 ASML 待了快兩年，待的時間也不算短了，怎麼會突然想換工作?」
2

3
我:「其實我當時畢業後就很想從事軟體業，我的大學畢業專題也是用 Python 寫的。只是當時沒有找到合適的機會，加上台灣半導體產業大舉徵才，所以選擇加入了 ASML。」
4

5
人資:「明白! 那你對 Google 的面試流程了解多少?」
6

7
我:「我知道 Google 有好幾輪面試，主要都是考 LeetCode 相關的題目，加上還有一輪行為面試用來評估所謂的 Googleyness?」
8

9
人資:「是的是的，你提到的行為面試就是 Google 的 G&L (Googleyness and Leadership) 面試。您目前累積的 LeetCode 題數大概是幾題呢?」
10

11
我:「大約 350 題。」
12

13
人資:「資料結構跟演算法都是熟悉的吧? 因為我們之前有遇到過一位面試者刷了 500 題的，但是他只刷單一類型的題目比如 linked-list，但是 tree, dynamic programming, stack/queue 都不太熟悉。」
14

15
我:「我懂你的意思，你不需要擔心，我都是按隨機來選擇題目的，妳剛剛提到的資結跟演算法我都有刷過。」
16

17
人資:「好的，那我就幫您安排第一輪面試了。先跟您說一下，第一輪面試會是 coding (編程)，面試過程採用全英文，而且不能使用任何 IDE 或是查詢資料。 第一輪面試通過了之後會同時安排後續的 4 輪面試，其中的 3 輪會是 coding，還有 1 輪是剛剛提到的 "G&L Interview"。」
18

19
我:「第一輪面試是甚麼時候?」
20

21
人資:「距離今天大約兩週後。」
22

23
我:「好的! 那再麻煩您發面試邀請給我，謝謝。」

1
Implement a restaurant waitlist data structure. It should support the
2
following features:
3

4
1. A party of customers can join the waitlist.
5
2. A party in the waitlist can leave the waitlist at any time.
6
3. The restaurant serves the first party whose size equals the empty table size (the table size is given as an argument).

1
面試官:「你先花點時間詳讀一下這道題目。然後說一下這道題會需要實現哪些函數?」
2

3
我:「首先會有一個 join 函數，然後 input 是 party_id 跟 party_size (party 的人數)。接著應該要有個 leave 函數，input 只需要 party_id。然後要有個 serve 函數，input 是 party_size，因為題目有說到餐廳會優先服務第一組 party_size 符合的 party。」
4

5
面試官:「好聽上去沒什麼問題，那麼你會用甚麼資料結構來解這道題?」
6

7
我:「我目前最直觀的想法是用 Doubly Linked-List 來解，每個 ListNode 就代表一個 party，然後每個 ListNode 會有 id 跟 size 這兩個屬性，分別代表 party_id 跟 party_size。」
8

9
面試官:「好，那你分析一下那三個函數的時間複雜度分別會是多少。」
10

11
我:「 join 的話會是 O(n)，因為我需要先跑過整個 Linked-List，如果發現同一個 party 已經在裡面就回傳 -1，如果不在裡面，就新增 party 到 Linked-List 的尾部。」
12

13
面試官: 「對，那 leave 呢?」
14

15
我:「 leave 的話我需要跑過一遍 Linked-List 去找到符合的 party_id 並移除，所以時間複雜度也是 O(n)。 serve 的話也是同理，我需要跑一遍並找到符合的 party_size 並把它移除。」
16

17
面試官:「很好! 那就開始寫吧」

1
面試官:「我覺得你寫的 code 沒什麼問題。你目前 join 跟 leave 函數的時間複雜度是 O(n)，有沒有甚麼方式可以優化它們?」
2

3
我:「我好像可以用 Hashmap/Dictionary 來優化，Dictionary 的 key 是 party_id，然後 value 是 party_id 對應到的 ListNode 物件，這樣我就不用跑一遍整個 Linked-List，直接用 map[party_id] 就能得到我要的 ListNode，我只需要確保新增/移除 ListNode 的時候去更新 map 就可以了。 這樣 join 跟 leave 函數的時間複雜度就能從 O(n) 降至 O(1)。」
4

5
面試官:「非常好!」

1
# Implement a restaurant waitlist data structure.
2
# It should support the following features:
3
# 1. A party of customers can join the waitlist.
4
# 2. A party in the waitlist can leave the waitlist at any time.
5
# 3. The restaurant serves the first party whose size equals the empty table size (the table size is given as an argument).
6

7
# join(ID, size) -> Bool
8
# leave(ID) -> Bool
9
# serve(size) -> ID or -1 (if no matching size)
10

11
class ListNode:
12
    def __init__(self, ID, size, prev=None, next=None):
13
        self.ID = ID
14
        self.size = size
15
        self.prev = prev
16
        self.next = next
17

18
class WaitList:
19
    def __init__(self):
20
        self.head, self.tail = ListNode(-1, 0), ListNode(-1, 0)
21
        self.head.next = self.tail
22
        self.tail.prev = self.head
23
        self.map = dict()
24

25
    def join(self, ID, size):
26
        if ID in self.map:
27
            return False
28
        prev = self.tail.prev
29
        node = ListNode(ID, size)
30
        prev.next = node
31
        node.prev = prev
32
        node.next = self.tail
33
        self.tail.prev = node
34
        self.map[ID] = node
35
        return True
36

37
    def leave(self, ID):
38
        if ID not in self.map:
39
            return False
40
        node = self.map[ID]
41
        prev, next = node.prev, node.next
42
        prev.next = next
43
        next.prev = prev
44
        del self.map[ID]
45
        return True
46

47
    def serve(self, size):
48
        node = self.head.next
49
        while node.ID != -1:
50
            if node.size == size:
51
                ID = node.ID
52
                prev, next = node.prev, node.next
53
                prev.next = next
54
                next.prev = prev
55
                del self.map[ID]
56
                return ID
57
            node = node.next
58
        return -1
59

60
"""
61
time complexity:
62
    join: O(1)
63
    leave : O(1)
64
    serve : O(n)
65
"""