# xarefit 第一階段問卷測驗
求職者：杜蕙伶
應徵職位：後端工程師 Backend Engineer
語言：python

## 1. 如何寫一個循環，然後把它轉換成遞迴函數？
以印出 0 ~ 2 為例：

- 循環的寫法

n = 0

while(n < 3):
    print(n)
    n += 1

- 遞迴的寫法

n = 0


def count_to_two(n):
    if n >= 3:
        return

    print(n)
    return count_to_two(n + 1)


count_to_two(n)

## 2. 如何找出 slow query？ MySQL 如何進行效能分析？
可以在 MySQL 設定 slow_query 相關的參數，紀錄 slow_query 的 log，然後搭配一些效能檢測工具，對 log 做進一步分析

## 3. 索引的優缺點?
優點：
- 加快查詢速度（SQL 查詢語句需要符合某些條件，才會用索引進行查詢）

缺點：
- 需用額外空間儲存索引
- 資料有修改時，索引也需要一並更新，較花時間

## 4. 什麼是 Deadlock？ (用程式碼表示)。
比較粗略地說，Deadlock 是指所有程序都在等別的程序釋放資源給他，導致所有程序都無法執行完畢。

process_A 和 process_B，都需要同時擁有 source_A 和 source_B 才能完成工作。但兩個 process 目前各自擁有一個 source 並且不肯釋出，導致兩個 process 都沒辦法完成工作，變成無限迴圈

source_A = {'is_asscessable': False, 'occupier': 'process_A'}
source_B = {'is_asscessable': False, 'occupier': 'process_B'}

is_process_A_done = False
is_process_B_done = False


def process_A():
    global source_A
    global source_B
    global is_process_A_done
    if source_A['is_asscessable']:
        source_A['is_asscessable'] = False
    elif source_A['occupier'] != process_A.__name__:
        return

    if source_B['is_asscessable']:
        source_B['is_asscessable'] = False
    elif source_B['occupier'] != process_A.__name__:
        return

    # do something
    is_process_A_done = True
    source_A['is_asscessable'] = True
    source_B['is_asscessable'] = True
    source_A['occupier'] = ''
    source_B['occupier'] = ''
    return


def process_B():
    global source_A
    global source_B
    global is_process_B_done
    if source_A['is_asscessable']:
        source_A['is_asscessable'] = False
    elif source_A['occupier'] != process_B.__name__:
        return

    if source_B['is_asscessable']:
        source_B['is_asscessable'] = False
    elif source_B['occupier'] != process_B.__name__:
        return

    # do something
    is_process_B_done = True
    source_A['is_asscessable'] = True
    source_B['is_asscessable'] = True
    source_A['occupier'] = ''
    source_B['occupier'] = ''
    return


while(not is_process_A_done and not is_process_B_done):
    process_A()
    process_B()

## 5. 寫一段有 memory leak 的示例程式 (用程式碼表示)。
發生 circular reference 的時候，garbage collection 沒辦法收回記憶體

a = {'0': 'memory leak'}
b = {'1': a}
a['0'] = b

del a
del b

## 6. 查詢列表中的第一個非重複整數 (用程式表示)
> 列表：[3, 6, 6, 3, 2, 1]

from typing import Union
from collections import OrderedDict

nums = [3, 6, 6, 3, 2, 1]


def find_first_single_number(nums: list) -> Union[int, None]:
    counter = OrderedDict()
    
    for i in range(len(nums)):
        num = nums[i]
        
        if counter.get(num) is None:
            counter[num] = True
        else:
            del counter[num]

    for i in counter.keys():
        return i

    return None


print(find_first_single_number(nums))  # 結果：2

## 7. string = "hgijjigihdgjggeddeihjdji"，如何將字串去重複並排序？並顯示結果

string = "hgijjigihdgjggeddeihjdji"


def sort_and_deduplicate(string: str) -> str:
    result = ['' for i in range(26)]
    diff = ord('a')

    for i in range(len(string)):
        index = ord(string[i]) - diff
        
        if result[index] == '':
            result[index] = string[i]

    return ''.join(result)


print(sort_and_deduplicate(string))  # 結果：deghij

## 8. 麻煩寫一段程式將[1,4,7,9] 和 [2,3,6,8] 合併為 [1,2,3,4,6,7,8,9]
觀察：給定的兩個 list 已經各自遞增排序完畢了

list1 = [1, 4, 7, 9]
list2 = [2, 3, 6, 8]


def merge_list(list1: list, list2: list) -> list:
    result = []
    
    for i in range(len(list1) + len(list2)):
        if len(list1) == 0:
            result.extend(list2)
            break

        if len(list2) == 0:
            result.extend(list1)
            break

        if list1[0] < list2[0]:
            result.append(list1.pop(0))
        else:
            result.append(list2.pop(0))

    return result


print(merge_list(list1, list2))  # 結果：[1, 2, 3, 4, 6, 7, 8, 9]

## 9. 寫一個簡單的垃圾回收系統。
構想：計算記憶體被 reference 的次數，次數為 0 的時候就釋放記憶體。

補充：在 JSDC.tw 2021 年會，「Memory Leak 與你的距離」的講者Kuan，有介紹 javascript 的垃圾回收系統，還有做 young generation、old generation 的清除機制

## 10. 如何設計 REST API ？
以部落格貼文 post 此資源為例：

| 操作 | 方法 | 路由 |
| ---------- | ------ | ------------------- |
| 瀏覽所有貼文 | GET | posts |
| 瀏覽一篇貼文 | GET | posts/\<string:id\> |
| 發表一篇貼文 | POST | posts |
| 更新一篇貼文 | PUT | posts/\<string:id\> |
| 刪除一篇貼文 | DELETE | posts/\<string:id\> |