Jack's Space

前言每年的面試分享文，似乎已經默默的成為我的某種習慣了（還沒看過我之前文章的，可以參考 2023 跟 2024 的分享）。但今年比較不同的是，我要碩士畢業了！因此本篇分享會從以往的實習轉成正職，職位的部分我大多都是找 ML 相關為主。 面試紀錄 投遞履歷：7 家公司 面試邀請：6 家公司 Offer Get：2 家公司 TSMC應徵職位：沒分，統一丟備註：有研替時程： 8/30 EPO interview invitation 9/12 EPO interview 10/1 EPO Thank you 9/16? 收到 IT 副理電話聊天詢問面試意願 9/23? 沒收到後續，打電話回去問，他好像說他忘記，當天就收到面試邀請 10/15 收到 IT 另一個處約時間，想約同天但卡到 10/18 IT interview (AAPD) 10/25 IT interview (MLAD) 11/1 收到資歷查核 11/5 資歷查核送出，有問是否需要廠測，對方說去年有紀錄不用 11&#x...

HackMD 完整版請點我 最大子數列問題 (Maximum Subarray Problem)最大子陣列問題是指在一個整數數列中，找出一段連續子陣列，使其元素總和最大。這是經典的動態規劃問題之一，常用於資料分析，如股價變動趨勢。 例子：給定一個陣列 [-2, -3, 4, -1, -2, 1, 5, -3]，找出總和最大的子陣列。 解答：最大子陣列為 [4, -1, -2, 1, 5]，其總和為 7。 Kadane’s AlgorithmKadane’s Algorithm 是一種專門用來解決此問題的演算法，可在線性時間內計算完成。要了解 Kadane’s Algorithm，讓我們從暴力法一步一步來看。 滴滴面试手撕算法题-kadane算法 暴力法：遍歷全部連續子陣列最簡單的方式，就是窮舉所有可能的連續子陣列，並計算每一個子陣列的總和，再從中找出最大值。 12345678def maxSubArrayBF(nums): max_sum = nums[0] n = len(nums) for i in range(n): for j i...

HackMD 完整版請點我 差分陣列（Difference Array） 差分陣列是一種快速處理區間更新的技巧，特別適用於頻繁對陣列特定區間進行加減的情境，其基於前綴和（Prefix Sum）的概念來輔助實現。 其核心概念是透過維護一個輔助陣列 diff，來記錄原陣列的數值變化，使得區間的加減可以在 O(1) 時間內完成，而最終結果則可透過前綴和的技巧來計算。 輔助陣列的建立輔助陣列 diff 的計算方法為：diff[0] = nums[0]diff[i] = nums[i] - nums[i-1] (i > 0) 以上圖來看，原陣列 nums 是 [8, 2, 6, 3, 1]：diff[0] = 8diff[1] = nums[1] - nums[0] = 8 - 2 = -6diff[2] = nums[2] - nums[1] = 6 - 2 = 4…diff = [8, -6, 4, -3, -2] 有注意到嗎？每個 diff 記錄的是「這個位置與上個位置的差異...

HackMD 完整版請點我 圖的進階議題（Advanced Topic on Graph）最短路徑（Shortest Path）最短路徑問題（Shortest Path Problem）是圖論中的一個重要課題，目的是尋找從一個起始節點到其他節點的最短路徑。相關的應用像是地圖中的導航系統、網路路由選擇等等，背後都是使用最短路徑的演算法。 path - 演算法筆記 戴克斯特拉演算法（Dijkstra’s Algorithm） 戴克斯特拉演算法是一種廣泛使用的方法，特別適用於權重非負的有向圖和無向圖，通過不斷選擇當前距離最小的未訪問節點，並更新其所有相鄰節點的最短距離，來尋找從起始節點到其他所有節點的最短路徑。 特別要注意的是，若存在負權重的邊，則戴克斯特拉演算法就不再適用。為什麼？讓我們看看以下的圖：你想到原因了嗎？在這張圖中，使用戴克斯特拉演算法會發生什麼事情？ 基礎演算法系列 — Graph 資料結構與 Dijkstra’s Algorithm Visualization of Above Example Bellman–Ford Algorithm相較於戴克斯特拉演算法...

HackMD 完整版請點我 字串比對（String Matching）KMP 演算法 KMP 演算法是一種用於字串搜尋的高效方法。透過建立部分配對表（最長的相同前後綴），可以快速定位搜尋字串中的可能配對位置，減少不必要的重複比較，從而加速搜尋過程。 KMP 演算法其實相對複雜且較難實作，我個人認為有大概理解概念就好，實際上也很少遇到需要直接實作該演算法的情境。 初學者學 KMP 演算法 補充：KMP algorithm，從自學到放棄 (1)補充：KMP algorithm，從自學到放棄 (2)補充：演算法筆記：substring補充：KMP Visualization Leetcode 28. Find the Index of the First Occurrence in a String 位元運算（Bit Manipulation） Bit manipulation 是在電腦中用「位元」（bit）來進行操作的技巧，這種技巧常在程式設計競賽或像 Leetcode 這樣的題目中出現。位元是電腦中最基本的單位，由 0 或 1 組成，這跟開關一樣，只有開或關的狀態。這些 ...

HackMD 完整版請點我 分治法（Divide-and-Conquer） Divide-and-Conquer又稱為分治法。其中 Divide 指的是將一個較大的問題不斷切割成小問題。而 Conquer 是當最後切割成的小問題簡單到可以直接解決，就可以組合成大問題的答案。在程式語言中時常都會用到分治法的觀念，並結合遞迴的概念求解。 Source: 分而治之法與遞迴關係 還記得之前教過的 Merge Sort 嗎？（合併排序法：將陣列不斷細分，再將細分後的結果兩兩合併。）其實 Merge Sort 的精神本質上就是 Divide-and-Conquer！ 【舌尖上的演算法】Day15 – Divide and Conquer - Merge Sort Leetcode 108. Convert Sorted Array to Binary Search Tree 148. Sort List 動態規劃（Dynamic Programming） Dynamic Programming = Divide-and-Conquer + Memoization 動態規...

HackMD 完整版請點我 其他演算法與常見解題技巧演算法（Algorithm）是在有限的步驟之內，提供明確的法則，求出問題正確答案的程序。它可以是一種方法、法則或者程序，讓資料可按照預先設計的方式處理。 認識演算法 推薦補充閱讀：演算法筆記 Algorithm Design 暴力法（Brute Force）暴力法（Brute Force）是一種基本的解題策略，透過系統地嘗試所有可能的解決方案來找出答案。它的原理很簡單：列舉所有可能性，不斷嘗試，直到找到符合要求的解。 這種方法的優點是實現簡單，且保證能找到存在的解。但它的效率通常較低，特別是在處理大規模問題時，因此暴力法常用於簡單問題或作為其他算法的比較基準。 以下補充幾個以前教過，但其實都跟暴力法有關的演算法。 補充：【舌尖上的演算法】Day6 – Brute Force - Selection Sort補充：【舌尖上的演算法】Day7 – Brute Force - Bubble Sort補充：【舌尖上的演算法】Day8 – Brute Force - Knapsack補充：【舌尖上的演算法】Day9 – Brut...

HackMD 完整版請點我 雜湊表（Hash Table） 雜湊函數的性質雜湊函式是一種把輸入數據轉換成固定長度的字符串（雜湊值）的工具。它有以下特點： 固定長度輸出：無論輸入數據有多長，輸出都是固定長度。 無法回推：從雜湊值無法反推出原始輸入（即單向性），保證了數據的不可逆性。 抗碰撞性：難以找到兩個不同的輸入有相同的雜湊值。 快速計算：能快速生成雜湊值。 [資料結構] 雜湊 (Hash) Images are from 什麼是Hash Function? 有什麼特性及用途? 雜湊函數的應用 資料完整性驗證：確保收到的資料是完整的，或確保文件未被篡改。 密碼儲存：儲存密碼的雜湊值，而不是明文密碼，提高安全性。常見的加密方式如 MD5、SHA-256 等等，若有興趣可以再研究密碼學。 資料結構：用於實現雜湊表，能夠快速存取資料。使用雜湊函數的常見資料結構包含集合（Set）、字典（Dictionary）等等。 數位簽章：保護資料完整性和驗證身份。 補充：雜湊函數 - 維基百科 Leetcode 49. Group Anagrams 387. First Uni...

HackMD 完整版請點我 矩陣（Matrix） 在介紹 Graph 的表示方法時，我們提到了兩種不同的表示方式，分別是鄰接串列（Adjacency List）與鄰接矩陣（Adjacency Matrix）。不過其實，矩陣本身也可以被當作一種資料結構來使用，舉凡像是迷宮、地圖等等具有 2D 性質的資料型態，都可以使用矩陣來表示。 Matrix 的相關操作其實都與 Graph 差不多，不外乎就是在 Matrix 中進行搜尋或遍歷，但因為我們可以以 $O(1)$ 的複雜度，直接取用 Matrix 內部中的任一元素（matrix[row][col]），所以 Matrix 在某些應用上具有較為快速的優勢。那接著就讓我們直接實戰演練吧！ Leetcode 200. Number of Islands 994. Rotting Oranges 1351. Count Negative Numbers in a Sorted Matrix 堆積（Heap）一種具有特殊性質（Parent Node 大於或小於 Child Node）的 Complete Binary Tree。 堆積排序法(H...

HackMD 完整版請點我 樹（Tree）基本單位為 Node，且只有一個 Node 是 Root（無人指向的 Node），且不存在任何 Cycle。每個 Node 可以指向多個 Child。 Tree(樹): Intro(簡介) 二元樹（Binary Tree）當樹中的每個 Node 都只有兩個 Child，即為 Binary Tree。 Binary Tree: Intro(簡介) Binary Tree: Traversal(尋訪) 以上面的 Binary Tree 為例： Pre-Order Traversal: ABDECFG In-Order Traversal: DBEAFCG Post-Order Traversal: DEBFGCA 延伸閱讀：Binary Tree: 建立一棵Binary Tree 二元搜尋樹（Binary Search Tree）若一個二元樹中，所有 Node 都滿足 Node.left.value < Node.value < Node.right.value，就稱為二元搜尋樹。二元搜尋樹有良好的排序特質，...