顯示具有 Coding interview 標籤的文章。顯示所有文章

2022/11/04

面試國外工程師超詳細超過 100 道題目蒐集、分類歸納與準備

要面試工程師的流程真的超級複雜，所以我就詳細蒐集了

Technical, behavior questions 蒐集與分類
Coding, online assessment, assignment, system design interview 的準備

最後也有題庫供大家參考。

一、面試題目蒐集、分類歸納與準備

1.1 面試流程

在蒐集面試題前要先知道歐美軟體工程師的面試流程 :

Initial phone call：recruiter 或 head hunter 會和求職者約時間 phone call，通常會問位置、簽證狀態、薪資期望、自我介紹。有的公司在這步就會問技術相關問題或是需要解題。
Technical interview : 沒有 coding，直接問技術相關問題
Coding interview : 面試官出題，你講解思路和解題
Online assessment / Online test : 給你一個線上連結，限制時間內要寫完
Assignment : 線上測試或是帶回家的作業，通常也有限制時間
System design : 通常 senior engineer 才會遇到，考對於系統的規劃和設計
Behavior questions : 問各種情況下面試者會怎麼處理，主要想知道面試者的處事態度和個性

那工程師面試時可能會遇到這些關卡交錯，但不一定每關都會遇到；有公司沒有 technical interview，或是有兩次 coding interview。

1.2 蒐集面試題

首先先蒐集變化度夠豐富的題目，包括 technical questions (依照你要應徵的職缺而定) 和 behavior questions。

不比中文面試，因為英文面試是使用自己不熟的語言；

我自己的個性是 : 如果能事先做好足夠的準備，面試時就比較不容易緊張，

就算遇到沒準備的問題，也會比較有自信也是能答得出來。

我用特定 skills + interview questions, behavior questions 等關鍵字 google 搜尋後大約翻 15 ~ 20 幾頁，還有上 youtube 看影片搜集問題，還能順便練聽力。

需不需要做到這樣，就看個人的個性和時間安排，但至少遇到 common questions 要可以回答得很熟練。

相關面試題目我整理成了題庫，可以下滑到 第三大點面試題庫資源參考。

簡單輕鬆十分鐘學會 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 種錢幣。

	let normalCoins = [1, 5, 10, 20, 50];

	let moneyForGreedy = function (coins, amount) {
	let coinsLeng = coins.length;

	let number = [];

	for (let i = coinsLeng - 1; i >= 0; i--) {
	number[i] = Math.floor(amount / coins[i]);

	amount = amount - number[i] * coins[i];
	}

	return number.reduce((a, b) => a + b);
	};

	console.log(moneyForGreedy(normalCoins, 15)); // 2

view raw Greedy Algorithm - example 1 hosted with ❤ by GitHub

但是如果我們換一組錢幣的種類如 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。

Coding Interview 就是刷好刷滿刷爆 LeetCode 就會上?

我家可愛貓貓鎮樓，最後她一個都沒選；

畢竟她靠可愛就可以過活了，還是由奴才來好好工作賺罐罐錢吧。

之前在台灣面試時一直都沒怎麼遇過需要 coding interview，

而且我也一直對於在別人面前寫程式感到害羞，

還以為自己可以就這樣逃過 coding interview 的關卡。

殊不知在英國面試時就常常遇到 coding interview，雖然有時候會是 online test, assignment，

但果要進比較大的公司，coding interview 幾乎是必備。

還記得我第一次 coding interview 時，

面試開始時我想說我會寫我會寫欸然後我就直接寫完了，

還以為自己表現不錯題目有解出來 : )

結果得到 feedback 是 "感覺面試者沒有想跟面試官溝通"。

起先覺得困惑，後來才知道原來 coding interview 不是只是解題就好，

部分也是因為我自己這部份沒做好資料查詢。

所以痛定思定後，上網詳盡搜尋了相關資訊包括如何準備、面試時需要從哪些方面下手，並運用範例寫下 coding interview 過程，同時也請 MANGA 經過面試官訓練的朋友幫忙檢查內容。

我試圖把 coding interview 的流程寫成可以以較有結構式的方式執行；

這篇會分為平時練習時、面試前和面試過程中去解釋。

簡單輕鬆十分鐘學會 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/)

簡單輕鬆十分鐘學會 Recursion (遞迴) 刷 LeetCode

一、Recursion

1.1 基本觀念介紹

遞迴就是在函式之中呼叫函式自己本身，本質上是將複雜的問題，拆分成具有相同性質的子問題，進而解決問題的方法。

一個基本的遞迴函式一定要有：

終止條件 (基本條件)
遞迴條件 (呼叫自己的條件)

如果沒有終止條件，就會無限循環直到當掉。

範例 1 : 假設輸入一個正整數 n，求 1 + 2 + … + n 的總和

我們可以很直覺的使用迭代 (迴圈) 的方式，將所有數字累加在一起。

	function sum(n) {

	let result = 0;
	for (let i = 1; i <= n; i++) {
	result += i;
	}
	return result;

	}

view raw Recursion - example 1 hosted with ❤ by GitHub

但因為這個問題能拆成有規律的數個小問題，

如輸入正整數 2 → 1 + 2 = 3

輸入正整數 3 → 1 + 2 + 3 = 6

…

所以這時候就可以使用遞迴來計算。

	function sum(n) {

	if (n === 1) {
	return 1;
	}

	return n + sum(n - 1);

	}

view raw Recursion - example 2 hosted with ❤ by GitHub

Time complexity 是 O(n)，Space complexity 是 O(1)。

簡單輕鬆十分鐘 Linked List (鍊表) 刷 LeetCode

一、Linked List

1.1 基本觀念介紹

Linked list 是一種常見的資料結構，會包含 head 和 tail 的資訊，以 null 來代表 Linked list 的終點，使用 node 來記錄、表示、儲存資料。

1.1.1 Singly linked list

(https://www.geeksforgeeks.org/types-of-linked-list/)

單向鏈結串列 (單鏈結串列、線性鏈結串列、普通鏈結串列) 是最基本的鏈結串列，其特點是鏈結串列的鏈結方向是單向的，對鏈結串列的存取要通過從頭部開始，依序往下讀取。

每個 node 則會包含 value 和 next (Pointer，指向下一個 node 的位置) 的資訊。

簡單輕鬆十分鐘學會 Hash Map (雜湊表) 刷 LeetCode

先來個地獄梗 emtional damage!

一、Hash Map

1.1 基本觀念介紹

Hash map 是儲存 (key, value) 這種 mapping 關係的一種資料結構 (當數據儲存在記憶體中時，決定數據的順序和位置的稱之為資料結構)
各語言 / library 基本上有其 hash function，如有需要也可以自行建置
語言不同名稱也會不同，但基本上 Hash map == Hash table == Hash object == Hash dictionary

(https://vhanda.in/blog/2012/07/shared-memory-hash-table/)

舉例來說，如果我們有 n 個數字要儲存時，通常會用 array 來存。存好後如果我們拿到另一個數字 37，要判斷這個數字有沒有在 array 裡面，那我們就得跟 array 裡的元素一個個比較，這時 time complexcity 就會是 O(n)；下次再換查另一個數字時， time complexcity 又就會是 O(n)。但如果已經先建立好 hash table，之後如果要查數字 37 時，建立 hash map 時雖然 time complexcity 會是 O(n)，但查詢的 time complexcity 就只會是 O(1)。不過 O(1) 還是理論值，insert、search、lookup、delete 都有可能造成 time complexcity 是 O(n) (請看 example 3) 。

簡單輕鬆十分鐘看懂 Time complexity & Space complexity 分析刷 LeetCode

一、前導知識

1.1 演算法評估標準

當同一個問題可以用不同演算法去解決時，需要一個評量的標準去評估哪個演算法比較好，通常會用兩個指標去評量演算法的好壞 :

Time complexity (時間複雜度)
Space complexity (空間複雜度)

當然理論上所花費的時間和占用的記憶體是越小越好。

1.2 Time complexity

Time complexity 是電腦執行演算法所需要耗費的時間成本，通常會用 O (Big O notation) 去計算。

Big O notation 是解決一個規模為 n 的問題所花費的時間，或者所需步驟之數目；而演算法多快通常不是以秒而是步驟次數來衡量，因為每個人電腦效能會影響執行速度，若用秒數來衡量會顯得不夠客觀。

訂閱：文章 (Atom)

2022/11/04

一、面試題目蒐集、分類歸納與準備

1.1 面試流程

1.2 蒐集面試題

2022/06/16

一、Greedy Algorithm

1.1 基本觀念介紹

2022/06/14

一、Graph

1.1 基本觀念介紹

1.1.1 Isomorphism / Isomorphic

一、Heap

1.1 基本觀念介紹

2022/06/13

一、Tree & Binary tree & Binary search tree

1.1 基本觀念介紹

1.1.1 Tree

2022/05/09

一、Stack & Queue

1.1 基本觀念介紹

1.1.1 Stack

2022/04/14

一、Recursion

1.1 基本觀念介紹

一、Linked List

1.1 基本觀念介紹

1.1.1 Singly linked list

2022/03/22

一、Hash Map

1.1 基本觀念介紹

一、前導知識

1.1 演算法評估標準

1.2 Time complexity