[Interview] 17 Media Backend

以下是網路上找到的 17 Media 後端面試題目，並且加上個人的解法。

面試流程

1. Codility
2. On Site 白板題
3. Behavior Question
4. chat with CEO

Questions

leetcode類型

Q1.

對 string 格式儲存的數字做減法，e.g. s1 “1234”, s2 “234”，回傳 “1000”。

ANS.

考慮到s1, s2有可能是一串非常長的字串，轉換回數字有可能超出int的上限，因此不能直接用字串轉數字再轉回字串的方式，必須要用digit operation再append到結果。
pseudo code如下

def sub(s1:tr, s2:str) -> str:
   if len(s1) < len(s2):
      return "-" + sub(s2, s1)
   # 紀錄是否需要借位
   carry=0
   res=""
   # 從最右邊開始
   for i in range(len(s2)-1,-1,-1):
    # 反向遍歷 
        digit = int(s1[i]) - int(s2[i]) - carry
        carry = 0
        if digit<0:
            digit+=10
            carry=1
        res=str(digit)+res
    # post process
    if len(s1)==len(s2) and carry == 1:
        return "-"+ res
    if len(s1) > len(s2): 
        return sub(s1[:len(s1)-len(s2)], str(carry))+res
    if res[0]=="0":
        return res[1:]

Q2.

pair number 取交集

ANS.

略

Q3.

氣泡排序法

ANS.

略

Q4.

數列中有個數字的次數出現了一半以上，請找出該數字

ANS.

Time: O(n) Space: O(1)的解法，用一個變數cnt儲存數字出現的次數，另一個變數res儲存候選人，從頭開始遍歷數列， 假如遍歷到的數字和候選人一樣，則cnt加一，如果兩者不同則cnt減一，當cnt為零時，將候選人改為當前的數字，且初始化cnt為1，最後留下來的候選人即為所求。

Q5.

給一個不重複數列與數字K，找出三個數字使此三數總和小於K

ANS.

先對數列排序，再來用雙指標從頭尾開始遍歷，時間複雜度是O(n*log(n))

Q6.

給一個字串的陣列，找出出現在所有字串的共同的最長字首

ANS.

暴力法，map reduce整個陣列，兩兩比對找出共同字首，遍歷完後就能得到最長共同字首。

Q7.

給一個已排序數列，找出其中某數字的開始(頭)跟結束(尾)的index

ANS.

Binary Search，做兩次binary search，第一次找頭，第二次找尾，時間複雜度是O(log(n))

distributed system

Q1.

如何在多個 DB 間打 transaction，假設跨 DB 的款項轉移

ANS.

Distributed Transaction
https://rickhw.github.io/2020/05/16/DistributedSystems/Distributed-Transactions/
分佈式交易涉及多個 DB 時，無法在同一個Transaction裡頭進行原子性操作，只能透過以下的方式保證最終一致性。

• 2PC
• 3PC
• Message Queue
• Database
• Q1.
• 如何在 DB 紀錄樹狀結構，快速取出子樹
• ANS.
• 參考答案如下，最佳解是 NESTED SET MODEL，另外最常見用來在DB儲存樹狀結構的方式是self reference model，再透過multi query根據樹高拿資料， 很明顯後者不是面試官要的答案。

1. self join
2. CTE wtih語法(遞迴)
3. store procedure或function
4. 透過程式做遞迴查詢
5. 反正規劃設計資料庫,平面化資料
6. nested set model
   https://columns.chicken-house.net/2019/06/01/nested-query/
   https://www.sitepoint.com/hierarchical-data-database-2/
   (推薦) 飛鳥實驗室-用 Nested Set Model 建立巢狀資料表 http://asika.windspeaker.co/post/3488-nested-set-model

System Design

Q1.

簡單設計一個通話軟體

This was originally posted on my own site.