距離收到錄取通知已經有兩個月了，決定來分享一下當初去 Dcard 面試的心得跟過程～

雖然我本來就有在新創公司工作，但是新創公司樣樣都要自己來，而且沒有一個 Mentor 帶領，產品也比較沒有流量，很難判斷自己做出的系統架構是不是一個好的架構，因此今年決定申請 Dcard 實習，來體驗看看高流量的 backend 開發！

面試流程

Dcard 的面試流程算是滿透明的，基本上分成 3 大關，履歷審查、第一次面試跟第二次面試。

整個流程走的也算滿快的，大概一個月就會把整個面試流程走完，而且各個階段有沒有通過都會寄信通知，非常棒～

題目

題目連結：https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

給定每一天的股價，第 i 天的股價為 prices[i]，求出最大的獲利為何。

可以進行多次的買賣，但手上一次只能握有一張股票。並且在股票賣出後，有一天的冷卻時間不能進行買賣。

範例說明

Example 1:

1
2
3

Input: prices = [1,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]

題目

題目連結：https://leetcode.com/problems/burst-balloons/

給一長度為 n 的序列 nums，依照任意順序刪除一個數字，直到所有數字消失。

每次刪除一個數字 x 時，假設 x 的左邊為 y，右邊為 z，則花費 x*y*z 元；當左邊沒有數字，y 視為 1，當右邊沒有數字時，z 視為 1。

求出最大花費。

範例說明

Example 1:

1
2
3
4
5

Input: nums = [3,1,5,8]
Output: 167
Explanation:
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167

題目

題目連結：https://leetcode.com/problems/palindrome-partitioning-ii/

給定一個字串 s，找出最少需要將字串 s 切成幾段使得每一段都是迴文。

範例說明

Example 1:

1
2
3

Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

題目

題目連結：https://leetcode.com/problems/guess-number-higher-or-lower-ii/

猜數字遊戲，答案在 $1 \sim n$ 之內。

每次猜測一個數字 $x$，如果猜對了則遊戲結束，若猜錯了則需要付 $x$ 元，並且會被告之正確答案大於 $x$ 或是小於 $x$。

找出一種猜數字的方式，使得不管答案是多少，花費都是最少的（也就是不管答案是多少，花費最大的那種答案要盡量小）。

範例說明

Example 1

題目

題目連結：https://leetcode.com/problems/redundant-connection-ii/

給定一個 N 個點的有根樹，再加上一條邊。

求出移除哪一條邊可以使得圖變回有根樹，若有多種解答，則輸出給定的邊中比較後面的那一條。

範例說明

Example 1:

1
2

Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]

題目

題目連結：https://leetcode.com/problems/longest-increasing-subsequence/

找到最長遞增子序列（LIS）的長度。

範例說明

Example 1:

1
2
3

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

題目

題目連結：https://leetcode.com/problems/sum-of-subarray-minimums/

給定一個序列，求出所有子區間的最小值的和。

範例說明

Example 1:

1
2
3
4
5
6

Input: arr = [3,1,2,4]
Output: 17
Explanation: 
Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. 
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.
Sum is 17.

題目

題目連結：https://leetcode.com/problems/valid-parentheses/

給定一個包含只包含 '('、')'、'{'、'}'、'['、']' 的字串，問給定的字串是不是一個合法的括號字串。

範例說明

Example 1:

1
2

Input: s = "()"
Output: true

Example 2:

1
2

Input: s = "()[]{}"
Output: true

題目

題目連結：https://leetcode.com/problems/132-pattern/

給定一個序列 nums，問是否能找到三個數字 nums[i]、nums[j] 與 nums[k]，使得 nums[i] < nums[k] < nums[j] 且 i < j < k。

範例說明

Example 1:

1
2
3

Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.