簡單輕鬆十分鐘學會 Greedy Algorithm (貪婪演算法) 刷 LeetCode

一、Greedy Algorithm

1.1 基本觀念介紹

Greedy Algorithm (貪婪演算法) 是指在對問題求解時，總是做出在當前看起來最好的選擇，所以此種演算法在解問題時，不是所有題型都能得到 global optimization (全域最佳解)，但對於相當多問題能產生整體最佳解或者是近似整體最佳解。

總之貪婪演算法的精神就是 : 短視近利、今朝有酒今朝醉，每一步面臨選擇時，都做眼前最有利的選擇，不考慮對將來是否有不良的影響，與 dynamic programming 不同，不會保留計算結果。

假設現在有個金額 M，有 1、5、10、20、50 元這些幣值種類，要盡可能用最少的錢幣湊到金額 M。根據貪婪演算法，能用 50 的就盡量用 50 的，否則盡量用 20 的...以此類推；在這種策略下，M 若是 15 則等於 10 * 1 + 5 * 1，共使用了 2 種錢幣。

但是如果我們換一組錢幣的種類如 1、5、11，貪婪演算法可能就不是最佳解。

或是我們有一個最多能背重量為 W 的背包，現在有 N 件物品，每件物品只能用一次且價值不相等，求解將哪些物品裝入背包裡物品價值總和最大，這時候因為要同時考慮重量和價值，也沒辦法用貪婪就取得最佳解。

這在下一篇 Dynamic Programming (動態規劃) 會講解到。

簡單輕鬆十分鐘學會 Graph (圖) 刷 LeetCode

一、Graph

1.1 基本觀念介紹

此處談及的 Graph 並不是指圖片或者圖形，而是由數個 vertex (點) 及數條 edgs (邊) 所構成；點與點之間以邊相連，表示這兩點有關聯性。

而一個頂點的 degree (度) 指與該頂點相連的邊的條數。

兩點之間也可以有很多條邊，代表這兩點有很多項關聯；一個點有連到自己的邊，稱之為self-loop (自環)，表示自己和自己有關聯。

1.1.1 Isomorphism / Isomorphic

(https://web.ntnu.edu.tw/~algo/Graph.html)

如果兩張圖的連接方式一模一樣時，則稱作同構圖。圖上的點可以任意移動位置，不論點的位置如何，都不會改變點與點之間的關聯。

簡單輕鬆十分鐘學會 Heap (堆疊) 刷 LeetCode

一、Heap

1.1 基本觀念介紹

Heap 有兩種分為資料結構和記憶體，都是取累積傾向的意思，而這邊要講的是資料結構的 Heap。

(https://www.geeksforgeeks.org/binary-heap/)

Heap 常見的實作為 Binary Heap，它的樹為 complete binary tree (完全二元樹) 如上圖。一棵依序節點可以從上到下、從左到右的表示為 1, 3, 6, 5, 9, 8。如果刪掉 node 9 那麼這便不是棵完全二元樹；如果拿掉 node 8 仍然是棵完全二元樹，因為整棵樹仍然可以從上到下、從左到右的表示成 1, 3, 6, 5, 9。

• 新增節點時優先從左到右填滿階層後才往下一層
• 概念基於 binary Tree，每個 node 下面最多只會有兩個 child，也有可能是一個或沒有
• 常使用 array 來實作，由左至右、由上到下表示出一個完全二元樹
• 若目前的 node 的 index 是 i，left child node 的 index 就是 i * 2 + 1，right child node 的 index 是 i * 2 + 2

簡單輕鬆十分鐘學會 Tree & Binary tree & Binary search tree 刷 LeetCode

一秒理解資料結構裡的樹

一、Tree & Binary tree & Binary search tree

1.1 基本觀念介紹

1.1.1 Tree

是一種模擬現實生活中樹幹和樹枝的資料結構，分為 :

Root (根節點)：沒有父節點的節點，所以每棵樹只有一個 root，如 A；在根節點之下是樹的樹枝，擁有 0 到 n 個子節點。

Node (節點)：一個個連結點，如 A、B、C ... M 都是結點。

Parent (父節點) : 節點 B 是 I 和 J 的父節點。

Child (子節點) : 節點 I 和 J 是 B 的子節點。

Siblings (兄弟節點) : 擁有共同父節點，如 I 和 J、K 和 L 和 M。

Leaf (葉節點)：節點沒有子節點的節點稱為葉節點，如 I、J、K、L、M、F、G、H。

Ancenstors (祖先節點) : 指某節點到根節點之間所經過的所有節點，都是此節點的祖先節點。

Level (階層) : 如果樹根是階層 1，其子節點即是階層 2，依序可以計算出樹的階層數；如節點A 階層是1，B、C 到 H 是階層 2，I、 J 到 M 是階層 3。

Height (樹高) : 又稱為 Depth (樹深)，指樹的最大階層數，如此圖的樹高是 3。

Dregree (分支度)：指每個節點擁有的子節點數，如節點 B 的分支度是 2，節點 E 的分支度是 3。

--
最廣義的樹對於 node 之 child 數目沒有限制，因此每個 node 可以有多個 child。

Linked list 也可以視作是樹只是每個 node 都只有一個 child。

簡單輕鬆十分鐘學會 Stack & Queue (堆疊 & 佇列) 刷 LeetCode

一、Stack & Queue

1.1 基本觀念介紹

這裡講的 stack 和 queue，就是和 event loop 裡會用到的 call stack 和 callback queue 的基礎資料結構。

如果不是很清楚 event loop 是什麼，可以看這篇。

Stack 和 Queue 常常用 array 或 linked list，但沒有限定，只要能實作出該資料結構即可。

1.1.1 Stack

Last in, First out (LIFO)

最後一個進去，第一個出來。

比如書籍堆疊起來，最後一本堆上去的會第一本先被拿走；

最下面 bottom 是第一個被放入的 frame，然後 frame 被一個一個堆起來 (push)，

如果要把 frame 抽走，只能從最上方開始拿 (pop)。

(https://open4tech.com/stacks-vs-queues/)

在英國當面試官面試其他 Junior 工程師之經驗

1. 關於面試者

目前我在英國面試到的都是 Junior 的工程師，

有幾個遇到面試者常常會有的問題 : 

1.1 太緊張到沒辦法好好打招呼或是回答問題

總結要點其實就是平常心，講是這樣講但就是很難做到，

我剛開始是連回訊息或是接電話都緊張，甚至還逃避不回不接，

也是慢慢的去克服這件事。

這篇 瘋了才會在疫情的時候跑到英國找工程師工作有當時的心路歷程和實踐的方式可以參考看看。

還有多練習、多參加面試，不管這公司你有沒有興趣，都可以當作練習去參加，

練到你對面試無感，可以前五分鐘邀約後五分鐘你就能面試；

平常也可以找人幫忙 mock interview。

--

被問到的問題不知道答案沒關係，可以花點時間好好想想，
急著馬上給答案，可能會沒有思考清楚、也會容易讓人質疑你的處事態度。

想要看答題技巧，可以看看這篇 國外找工作 :: 技術和面試題的蒐集、歸納與準備與約定面試時間等

--
把面試官當朋友，而不是一個在評估你的評審，
面試起來會比較放鬆、自然微笑，這樣也會給人比較有好感。

如果你有餘力，也可以試試加點 small talk 進去。