### Q1: Algorithm Problem

【Does the fake coins exist?】

There are 12 coins, among which at least 11 are identical "real" coins, and at most one coin is "fake". This "fake" coin is either lighter or heavier than a "real" coin. You can use a balance scale to compare the total weight of any m coins with that of any other m coins. The problem is to find the "fake" coin or show that there is no such coin, by making some sequence of comparisons using the balance scale.

(1)Please design a scheme to find the "fake" coin (if there is one) with at most 3 comparisons using the balance scale and write the pseudo code for this scheme.

(2)Please prove that it is not possible to find the "fake" coin with just 2 comparisons.

#### P.S
a) You can complete the question(1) with pseudo code or any kind of programming language.
b) The question(2) can be answered by Chinese to clarify your thought.

:::info
Answer

func compare(coins []Coin, start1, end1, start2, end2 int) int {
	sum1, sum2 := 0, 0
	for i := start1; i < end1; i++ {
		sum1 += int(coins[i])
	}
	for i := start2; i < end2; i++ {
		sum2 += int(coins[i])
	}
	if sum1 < sum2 {
		return -1
	} else if sum1 == sum2 {
		return 0
	} else {
		return 1
	}
}

func findFake(coins []Coin) (int, Coin) {
	comp1 := compare(coins, 0, 4, 4, 8)

	switch comp1 {
	case 0: // Fake is in C (or doesn't exist)
		comp2 := compare(coins, 8, 10, 0, 2)
		switch comp2 {
		case 0:
			comp3 := compare(coins, 10, 11, 11, 12)
			return 10 + comp3, Coin(comp3)
		default:
			comp3 := compare(coins, 8, 9, 9, 10)
			return 8 + comp3, Coin(comp3)
		}
	case -1: // Fake is in B
		comp2 := compare(coins, 4, 7, 0, 3)
		switch comp2 {
		case -1:
			comp3 := compare(coins, 4, 5, 5, 6)
			return 4 + comp3, Coin(comp3)
		default:
			comp3 := compare(coins, 7, 8, 0, 1)
			return 7, Coin(comp3)
		}
	case 1: // Fake is in A
		comp2 := compare(coins, 0, 3, 4, 7)
		switch comp2 {
		case 1:
			comp3 := compare(coins, 0, 1, 1, 2)
			return 0 + comp3, Coin(comp3)
		default:
			comp3 := compare(coins, 3, 4, 4, 5)
			return 3, Coin(comp3)
		}
	}
	return -1, Real
}

:::

### Q2: Binary Searching Problem

【Which is the single element?】
In this question, you’re given a sorted array consisting of serial integers, every element arises twice, apart from one element which appears only once.

Please design a scheme to complete these conditions:
Target: Return the single element that appears only once.
Limitation: Time complexity=O(log n) and Space complexity=O(1)

#### P.S
Please complete the question with pseudo code or any kind of programming language. You can clarify your thoughts in Chinese if it's necessary.

-----
Example 1
| Input: nums = [1, 1, 3, 3, 6, 7, 7]
| Output: 6

Example 2:
| Input: nuts = [3, 3, 5, 5, 8, 8, 9, 9, 10]
| Output: 10

:::info
Answer

func BSNonDupNum(nums []int) int {
    left, right := 0, len(nums) - 1
    
    for left < right {
        mid := left + (right - left) / 2
        
        // Check if the mid index is even or odd.
        if mid % 2 == 0 {
            // If the mid index is even, its duplicate should be on its right (if it has a duplicate).
            if nums[mid] == nums[mid+1] {
                left = mid + 2
            } else {
                right = mid
            }
        } else {
            // If the mid index is odd, its duplicate should be on its left (if it has a duplicate).
            if nums[mid] == nums[mid-1] {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
    }
    
    return nums[left]
}

想法:
- 因為單獨出現的數字僅有一個，所以整個 array 的 element 數一定是奇數。奇數除以 2 有可能是奇數或偶數，以 Binary Search 的角度來看，這個特性剛好決定單獨出現的數字是出現在 array 的哪一側，以此為基礎進行跑迴圈判斷，可找到單獨出現的數字。
:::

### Q3: 是否有 git 相關使用經驗？
#### 包含但不限於以下：git clone / push / pull / merge / rebase / cherry-pick（可簡要說明）
有在業界擔任過後端工程師的實習，因此有基於 branch 做開發的經驗，熟悉基本的 clone 專案、push commit、pull 他人更改、merge 或 rebase 分支並解 conflict，並且也熟悉 checkout 切換分支或 branch 開分支或查詢分支等命令。cherry-pick 則沒有使用經驗。

### Q4: 曾實做過 CRUD？（可簡要說明）
有從頭搭建過後端系統的專案經驗，在專案中負責全端開發與部署維運，因此對於在後端寫 Create/Read/Update/Delete 資源操作有相當經驗，了解對應的 HTTP methods，主要以 RESTful API 的方式撰寫，資料庫的部分較熟悉關聯式資料庫。

### Q5: 是否有 HTTP Request Method: GET / POST / PUT / DELETE 等有相關實作經驗？（可簡要說明）
承上題的 CRUD 實作經驗，GET, POST, PUT, PATCH, DELETE 等資源操作方法皆有實作為 RESTful API 的經驗，有包含 complex query 的實作經驗。

### Q6: 是否清楚 HTTP / HTTPS 的差異？包含 port, SSL/TLS, certificate（可簡要說明）
- HTTP 是 client-server 通訊的協定，例如 browser 向 web server 傳送 HTTP request，web server 會以 HTTP 做回應，default port 為 `80`，資料傳輸過程未加密。HTTPS 在 HTTP 的基礎上結合 SSL/TLS 作為加密，使用 HTTPS 的網站需要透過第三方認證機構 (CA) 簽署的 certificate 作為認證，default port 為 `443`。

### Q7: 是否清楚基本 HTTP Status Code 意義？
### 包含但不限於以下：200 / 201 / 202 / 400 / 401 / 403 / 404 / 429 / 500 / 504（可簡要說明）
- 200: 正確請求。通常用於表示 GET/PUT/POST 操作沒有錯誤
- 201: 有新的 resource 成功被建立。通常用於表示 PUT/POST 操作沒有錯誤
- 202: server 端已接受 request，但尚未處理。不能保證該 request 最終會被處理。
- 400: 錯誤請求。
- 401: "Unauthorized"，代表 server 端不認識 client 端的 user 身分，因而無從判斷是否有權限。
- 403: "Forbidden"，代表 server 端知道 client 端的 user 身份，且該 user 不具有存取該資源的權限。
- 404: 找不到請求的資源。
- 429: user 在短時間內大量傳送 request，不予回應。
- 500: server 端內部出現問題。
- 504: 指 server 端的 Gateway 在時間內得不到回應。

### Q8: 是否有使用過 docker pull / push / tag / build 等相關經驗？（可簡要說明）
在過去的專案經驗中，因為有兩支微服務 (Node.js/Flask) 以及兩個資料庫 (Postgres/Redis) 需要部署，因此選擇使用 Docker 來建立各自的環境，對於後續各服務或資料庫要做升級或更新有較大的彈性，微服務的部分是撰寫 `Dockerfile` 並 `docker build / run` 執行，資料庫則是用 `docker pull / run` 選擇所需版本執行；在過去的實習經驗中，因為有研究開源工具的需求，有撰寫 `Dockerfile` 並 `docker build / tag / push` 快速建立測試環境、設 tag 並上傳至個人的 registry 以供他人使用的經驗。