DOCS · v1.0 · 12 chương

Giáo trình DSA
Cấu trúc dữ liệu & Giải thuật

Tài liệu này mô tả chi tiết toàn bộ nội dung của 12 chương, kèm mục tiêu học tập, kiến thức cốt lõi, ví dụ tiêu biểu và bài toán phỏng vấn kinh điển. Đọc trước để có cái nhìn tổng quan, sau đó vào từng chương để học sâu.

📐 Triết lý học DSA của giáo trình này
  1. Hiểu trước, thuộc sau. Mỗi cấu trúc/giải thuật phải hiểu được tại sao nó tồn tại, giải quyết bài toán gì, đánh đổi cái gì.
  2. Code tay, không copy. Mỗi giải thuật bạn phải tự gõ ít nhất 1 lần bằng JavaScript/TypeScript trên môi trường thật.
  3. Phân tích Big-O ngay khi viết code. Không có thói quen này thì sẽ không bao giờ nhanh được trong phỏng vấn.
  4. Pattern hơn bài toán. Học pattern (sliding window, two pointers, BFS, DP states…) thay vì học thuộc bài.
  5. Visualize. Dùng visualizer trong trang web này để thấy giải thuật chạy, không chỉ đọc text.

📚 Mục lục — 12 chương

CH.01

Big-O & Phân tích độ phức tạp

Foundation

Nền tảng của mọi thứ khác. Không hiểu Big-O thì không thể đánh giá đoạn code mình viết là nhanh hay chậm.

🎯 Mục tiêu học tập

  • Định nghĩa Big-O, Big-Θ, Big-Ω và ý nghĩa trực quan của từng cái
  • Phân tích được độ phức tạp time/space của bất kỳ đoạn code nào
  • Hiểu khái niệm amortized analysis qua ví dụ dynamic array
  • So sánh trực quan tốc độ tăng giữa O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), O(n!)

📖 Nội dung chi tiết

  • 1.1 Tại sao cần Big-O? — câu chuyện n=1000 vs n=1,000,000
  • 1.2 Định nghĩa toán học của Big-O (đơn giản hoá cho lập trình viên)
  • 1.3 Quy tắc đếm: bỏ hằng số, giữ bậc cao nhất, nested loop
  • 1.4 Big-Θ và Big-Ω — khi nào thực sự cần phân biệt
  • 1.5 Space complexity — stack từ đệ quy, output space
  • 1.6 Amortized analysis qua dynamic array (push() trung bình O(1))
  • 1.7 Best case / Worst case / Average case
  • 1.8 Big-O của các thao tác phổ biến (Array, Object, Map, Set trong JS)

💡 Câu hỏi phỏng vấn kinh điển

  • Big-O của hai vòng for lồng nhau nhưng chạy trên hai mảng khác nhau là gì? (đáp án: O(n·m), không phải O(n²))
  • Tại sao Array.prototype.push trong JS được coi là O(1) dù thực ra có lúc phải resize?
  • Phân biệt O(log n) và O(√n)?
CH.02

Array & String

Linear DS

Cấu trúc dữ liệu phổ biến nhất. 40% bài phỏng vấn xoay quanh array/string + 2 pattern: two pointers và sliding window.

🎯 Mục tiêu học tập

  • Hiểu sự khác biệt giữa array trong C (cố định, contiguous memory) và Array trong JS (dynamic, có thể chứa kiểu khác nhau)
  • Thành thạo 2 pattern: Two Pointers và Sliding Window
  • Xử lý string trong JS: immutable, các phương thức quan trọng, khi nào convert sang array
  • Prefix sum & Difference array — kỹ thuật giảm O(n²) xuống O(n)

📖 Nội dung chi tiết

  • 2.1 Array internals: cách JS engine (V8) lưu array, dense vs sparse
  • 2.2 Các thao tác và Big-O: access, search, insert, delete
  • 2.3 Two Pointers: opposite direction, same direction — vd Two Sum sorted, Reverse string
  • 2.4 Sliding Window: fixed window vs variable window — vd Longest Substring Without Repeating
  • 2.5 Prefix Sum: subarray sum trong O(1) sau O(n) preprocessing
  • 2.6 Difference Array: range update O(1)
  • 2.7 String trong JS: immutability, template literals, encoding (UTF-16)
  • 2.8 Pattern matching cơ bản (KMP để dành chương String nâng cao)

💡 Bài toán LeetCode tiêu biểu

  • Two Sum, 3Sum, Container With Most Water (two pointers)
  • Longest Substring Without Repeating Characters, Minimum Window Substring (sliding window)
  • Subarray Sum Equals K (prefix sum + hash map)
  • Product of Array Except Self
CH.03

Linked List

Linear DS

Cấu trúc dạy bạn về con trỏ và tham chiếu. Phỏng vấn cực hay hỏi vì test khả năng thao tác pointer cẩn thận.

🎯 Mục tiêu học tập

  • Tự cài đặt singly linked list và doubly linked list bằng class JS
  • Thành thạo kỹ thuật dummy node và fast/slow pointer
  • Đảo ngược linked list bằng cả iterative và recursive
  • Phát hiện và tìm điểm bắt đầu vòng lặp (Floyd's cycle detection)

📖 Nội dung chi tiết

  • 3.1 Linked list là gì? So sánh với Array — đánh đổi memory layout vs flexibility
  • 3.2 Singly LL: cài đặt Node + List, các thao tác cơ bản
  • 3.3 Doubly LL: thêm prev pointer, ưu/nhược
  • 3.4 Circular LL: ứng dụng (round-robin scheduler)
  • 3.5 Dummy node pattern: tránh edge case khi xử lý head
  • 3.6 Fast & Slow pointer: tìm middle, phát hiện cycle, tìm node thứ k từ cuối
  • 3.7 Reverse linked list: 3 cách (iterative, recursive, stack)
  • 3.8 Merge & Sort linked list (merge sort vì quick sort không tốt cho LL)

💡 Bài toán LeetCode tiêu biểu

  • Reverse Linked List, Merge Two Sorted Lists, Merge K Sorted Lists
  • Linked List Cycle I & II (Floyd's algorithm)
  • Remove Nth Node From End
  • Reorder List, Copy List with Random Pointer
CH.04

Stack & Queue

Linear DS

Hai cấu trúc đơn giản nhưng là nền móng cho rất nhiều giải thuật cao cấp hơn (DFS, BFS, undo/redo, expression parsing).

🎯 Mục tiêu học tập

  • Phân biệt LIFO (stack) và FIFO (queue), khi nào dùng cái nào
  • Cài đặt stack/queue bằng array và linked list
  • Hiểu Deque (double-ended queue) — vừa stack vừa queue
  • Pattern Monotonic Stack — giải bài "next greater element" trong O(n)

📖 Nội dung chi tiết

  • 4.1 Stack: push/pop/peek, ứng dụng (function call stack, undo, parenthesis matching)
  • 4.2 Queue: enqueue/dequeue, ứng dụng (BFS, scheduling, message queue thực tế)
  • 4.3 Cài đặt Queue bằng 2 stacks (câu hỏi phỏng vấn kinh điển)
  • 4.4 Cài đặt Stack bằng 2 queues
  • 4.5 Deque trong JS: dùng array với push/pop/shift/unshift hoặc tự cài
  • 4.6 Monotonic Stack: increasing vs decreasing, bài Next Greater Element
  • 4.7 Monotonic Deque: bài Sliding Window Maximum
  • 4.8 Expression evaluation: infix → postfix (Shunting Yard algorithm)

💡 Bài toán LeetCode tiêu biểu

  • Valid Parentheses, Min Stack, Largest Rectangle in Histogram
  • Daily Temperatures, Next Greater Element II
  • Implement Queue using Stacks, Sliding Window Maximum
CH.05

Hash Table

Lookup DS

"Vũ khí bí mật" giảm độ phức tạp từ O(n²) xuống O(n) trong cực nhiều bài toán. Hiểu sâu cơ chế bên trong là điểm cộng lớn khi phỏng vấn.

🎯 Mục tiêu học tập

  • Hiểu cách hash function biến key thành index
  • Phân biệt 2 cách xử lý collision: chaining và open addressing
  • Hiểu khái niệm load factor và khi nào hash table cần rehashing
  • Tự cài đặt một hash map đơn giản bằng JS
  • Phân biệt Object vs Map vs Set trong JS — khi nào dùng cái nào

📖 Nội dung chi tiết

  • 5.1 Bài toán: tìm kiếm O(1) — tại sao cần hash table?
  • 5.2 Hash function: tính chất tốt (deterministic, uniform distribution, fast)
  • 5.3 Collision và 2 cách xử lý: Separate Chaining (linked list) vs Open Addressing (linear/quadratic probing, double hashing)
  • 5.4 Load factor & Rehashing: khi nào resize, cost amortized
  • 5.5 Big-O: O(1) trung bình, O(n) worst case (khi tất cả collide)
  • 5.6 JS specific: Object (key chỉ là string/symbol), Map (key kiểu gì cũng được, giữ thứ tự insert), Set (chỉ value)
  • 5.7 Hash Set: ứng dụng (kiểm tra duplicate, intersection, union)
  • 5.8 Bài toán "đếm tần suất" + bài "two-sum-like"

💡 Bài toán LeetCode tiêu biểu

  • Two Sum, Group Anagrams, Top K Frequent Elements
  • Longest Consecutive Sequence (cực kinh điển)
  • Subarray Sum Equals K (kết hợp prefix sum + hash map)
  • LRU Cache (kết hợp hash map + doubly linked list)
CH.06

Recursion & Backtracking

Technique

Tư duy đệ quy là kỹ năng nền tảng cho cây, đồ thị, divide & conquer, dynamic programming. Backtracking là "anh em song sinh" — đệ quy có rollback.

🎯 Mục tiêu học tập

  • Viết được hàm đệ quy đúng: định nghĩa base case + recursive case rõ ràng
  • Vẽ được recursion tree, tính được Big-O từ tree
  • Hiểu call stack — tại sao đệ quy sâu gây stack overflow
  • Phân biệt đệ quy và backtracking: backtracking = đệ quy + thử-sai-quay-lui
  • Áp dụng template backtracking cho permutations, combinations, subsets, N-Queens, Sudoku

📖 Nội dung chi tiết

  • 6.1 Đệ quy là gì? Tại sao đệ quy = "định nghĩa cái lớn dựa trên cái nhỏ hơn cùng loại"
  • 6.2 Cách viết hàm đệ quy 3 bước: base case → giả định đúng cho n-1 → ráp lại cho n
  • 6.3 Recursion tree và cách tính Big-O từ tree
  • 6.4 Tail recursion và tail call optimization (TCO trong JS hiện tại)
  • 6.5 Memoization: cache kết quả để tránh tính lại
  • 6.6 Backtracking template: choose → explore → un-choose
  • 6.7 Phân biệt Permutations vs Combinations vs Subsets
  • 6.8 Bài kinh điển: N-Queens, Sudoku Solver, Word Search

💡 Bài toán LeetCode tiêu biểu

  • Subsets, Permutations, Combinations, Combination Sum
  • Word Search, N-Queens, Sudoku Solver
  • Generate Parentheses, Letter Combinations of a Phone Number
  • Restore IP Addresses, Palindrome Partitioning
CH.07

Sorting Algorithms

Algorithm

Phỏng vấn ít hỏi cài đặt từ đầu, nhưng RẤT hay hỏi: "Sort này hoạt động thế nào? Big-O? Stable không? In-place không?"

🎯 Mục tiêu học tập

  • Cài đặt được 7 thuật toán sort: Bubble, Selection, Insertion, Merge, Quick, Heap, Counting
  • Phân tích Big-O time/space cho từng cái
  • Hiểu khái niệm stable sort và in-place sort
  • Biết V8 dùng gì cho Array.prototype.sort (TimSort)
  • Pick đúng sort cho bài toán: nearly sorted? small n? memory limited? need stable?

📖 Nội dung chi tiết

  • 7.1 Tiêu chí so sánh sort: time (best/avg/worst), space, stability, in-place, comparison-based hay không
  • 7.2 Bubble Sort: O(n²), demo tốt cho người mới
  • 7.3 Selection Sort: O(n²), ít swap nhất
  • 7.4 Insertion Sort: O(n²) nhưng O(n) khi nearly-sorted, dùng cho mảng nhỏ
  • 7.5 Merge Sort: O(n log n), stable, không in-place
  • 7.6 Quick Sort: O(n log n) avg, O(n²) worst, in-place, không stable. Pivot strategies
  • 7.7 Heap Sort: O(n log n), in-place, không stable
  • 7.8 Counting Sort & Radix Sort: O(n+k) — khi nào dùng được
  • 7.9 TimSort: hybrid Merge + Insertion, dùng trong V8/Python

💡 Bài toán LeetCode tiêu biểu

  • Sort Colors (Dutch National Flag — 3-way partition)
  • Merge Intervals, Insert Interval
  • Kth Largest Element (Quickselect)
  • Largest Number (custom comparator)
CH.08

Searching & Binary Search

Algorithm

Binary search nghe đơn giản nhưng cài đặt đúng thì cực khó (off-by-one bug). Pattern "binary search trên đáp án" là vũ khí cho bài toán tối ưu.

🎯 Mục tiêu học tập

  • Cài đặt 3 dạng binary search: tìm chính xác, tìm leftmost, tìm rightmost
  • Tránh được bug off-by-one và overflow (mid = lo + (hi-lo)/2)
  • Áp dụng binary search trên không gian đáp án (binary search the answer)
  • Binary search trên array đã sort xoay vòng (rotated sorted array)

📖 Nội dung chi tiết

  • 8.1 Linear search và khi nào nó đủ tốt
  • 8.2 Binary search cơ bản — invariants & template
  • 8.3 Lower bound (leftmost) & Upper bound (rightmost)
  • 8.4 Binary search trên rotated sorted array
  • 8.5 Binary search trên không gian đáp án — bài Capacity to Ship Packages
  • 8.6 Ternary search (cho hàm unimodal)
  • 8.7 Exponential search (khi không biết kích thước)
  • 8.8 Tìm kiếm trong ma trận sorted

💡 Bài toán LeetCode tiêu biểu

  • Binary Search, Search in Rotated Sorted Array
  • Find First and Last Position, Median of Two Sorted Arrays
  • Capacity To Ship Packages Within D Days, Koko Eating Bananas
  • Search a 2D Matrix I & II
CH.09

Tree (Binary Tree, BST, Trie)

Hierarchical DS

Tree là cây cấu trúc dữ liệu xuất hiện khắp nơi: file system, DOM, JSON, database index. Phỏng vấn rất hay hỏi traversal và BST.

🎯 Mục tiêu học tập

  • Phân biệt: tree, binary tree, BST, balanced BST (AVL, Red-Black), complete tree, full tree
  • Cài đặt 4 loại traversal: pre-order, in-order, post-order, level-order — cả recursive và iterative
  • Hiểu tại sao in-order traversal của BST cho ra mảng sorted
  • Cài đặt Trie (prefix tree) — ứng dụng autocomplete, spell check
  • Hiểu nguyên lý balance tree (không cần cài AVL/RB chi tiết)

📖 Nội dung chi tiết

  • 9.1 Terminology: root, leaf, parent/child, depth, height, level
  • 9.2 Binary Tree: cài đặt Node, các loại (full, complete, perfect, balanced)
  • 9.3 Traversal: pre/in/post-order — recursive (dễ) và iterative bằng stack (khó)
  • 9.4 Level-order traversal (BFS) bằng queue
  • 9.5 BST: invariants, insert, search, delete (3 cases khi delete)
  • 9.6 In-order traversal cho ra sorted output — invariant quan trọng nhất của BST
  • 9.7 Balanced BST: tại sao cần (BST suy biến thành linked list), giới thiệu AVL & Red-Black
  • 9.8 Trie: cấu trúc, insert/search/startsWith, ứng dụng autocomplete
  • 9.9 Lowest Common Ancestor (LCA), Diameter của tree

💡 Bài toán LeetCode tiêu biểu

  • Maximum Depth of Binary Tree, Same Tree, Symmetric Tree
  • Binary Tree Level Order Traversal, Zigzag Level Order
  • Validate BST, Lowest Common Ancestor
  • Serialize and Deserialize Binary Tree
  • Implement Trie, Word Search II
CH.10

Heap & Priority Queue

Tree-based DS

Heap là binary tree đặc biệt được lưu trong array. Priority Queue (bản thực dụng) dùng heap. Đây là vũ khí cho bài "Top K", "K-th largest", scheduling.

🎯 Mục tiêu học tập

  • Hiểu heap property: min-heap vs max-heap
  • Cài đặt heap bằng array (parent/child indexing: 2i+1, 2i+2, (i-1)/2)
  • Cài đặt insert (sift-up) và extract (sift-down) — cả hai O(log n)
  • Hiểu heapify O(n) (không phải O(n log n)!)
  • Pattern Top-K bằng min-heap kích thước K
  • JS không có built-in PriorityQueue — biết cách dùng thư viện hoặc tự cài

📖 Nội dung chi tiết

  • 10.1 Heap property và biểu diễn dạng array
  • 10.2 Min-heap vs Max-heap
  • 10.3 Insert + sift-up (bubble-up)
  • 10.4 Extract-min/max + sift-down (bubble-down)
  • 10.5 Build-heap (heapify) trong O(n)
  • 10.6 Heap Sort (đã giới thiệu ở chương 7, đào sâu hơn)
  • 10.7 Priority Queue: API và sự khác biệt với Heap
  • 10.8 Pattern Top-K: dùng min-heap size K
  • 10.9 Two-heap technique: tìm median của data stream

💡 Bài toán LeetCode tiêu biểu

  • Kth Largest Element in an Array, Top K Frequent Elements
  • Merge K Sorted Lists, Find Median from Data Stream
  • Task Scheduler, Meeting Rooms II
  • K Closest Points to Origin
CH.11

Graph (BFS, DFS, Dijkstra, MST)

Graph DS

Đỉnh cao của DSA cơ bản. Graph mô hình hoá rất nhiều bài toán thực tế: bản đồ, mạng xã hội, dependency, network routing.

🎯 Mục tiêu học tập

  • Biểu diễn graph bằng adjacency list và adjacency matrix — đánh đổi giữa hai cách
  • Cài đặt BFS và DFS — cả recursive lẫn iterative
  • Phát hiện cycle trong directed và undirected graph
  • Topological sort (Kahn's algorithm + DFS-based)
  • Shortest path: BFS (unweighted), Dijkstra (non-negative weights), Bellman-Ford (negative weights)
  • Minimum Spanning Tree: Kruskal (Union-Find) và Prim
  • Union-Find (Disjoint Set Union) — cấu trúc kèm

📖 Nội dung chi tiết

  • 11.1 Graph terminology: vertex, edge, directed/undirected, weighted/unweighted, cycle, DAG, connected component
  • 11.2 Biểu diễn: adjacency list (sparse) vs adjacency matrix (dense)
  • 11.3 BFS: queue-based, dùng cho shortest path trên unweighted graph
  • 11.4 DFS: stack/recursive, dùng cho path-finding, cycle detection, topological sort
  • 11.5 Cycle detection: undirected (DFS + parent), directed (DFS + 3 màu)
  • 11.6 Topological sort: Kahn (BFS + indegree) vs DFS-based
  • 11.7 Dijkstra: greedy + priority queue, không chạy được với negative weight
  • 11.8 Bellman-Ford: O(V·E), phát hiện được negative cycle
  • 11.9 Floyd-Warshall: all-pairs shortest path, O(V³)
  • 11.10 Union-Find: path compression + union by rank, gần như O(1)
  • 11.11 MST: Kruskal (sort edges + Union-Find) vs Prim (giống Dijkstra)

💡 Bài toán LeetCode tiêu biểu

  • Number of Islands, Clone Graph, Course Schedule I & II
  • Network Delay Time (Dijkstra), Cheapest Flights Within K Stops (Bellman-Ford)
  • Word Ladder (BFS), Pacific Atlantic Water Flow (multi-source DFS)
  • Number of Connected Components (Union-Find)
CH.12

Dynamic Programming

Technique

Chương khó nhất nhưng cũng "tách giỏi" nhất trong phỏng vấn. DP không phải kỹ thuật bí ẩn — đó là đệ quy có cache + tư duy state.

🎯 Mục tiêu học tập

  • Phân biệt 2 cách viết DP: top-down (memoization) vs bottom-up (tabulation)
  • Định nghĩa được state của bài DP — đây là 80% công việc
  • Viết được state transition (recurrence relation)
  • Tối ưu space của DP từ O(n²) xuống O(n) hoặc O(1) khi có thể
  • Nhận diện 5 dạng DP phổ biến: 1D linear, 2D grid, knapsack, LIS/LCS, interval

📖 Nội dung chi tiết

  • 12.1 DP là gì? Tại sao đệ quy thường + cache → DP
  • 12.2 2 điều kiện để dùng DP: optimal substructure + overlapping subproblems
  • 12.3 Top-down (memoization) vs Bottom-up (tabulation) — đánh đổi
  • 12.4 Quy trình giải bài DP 5 bước: định nghĩa state → base case → transition → thứ tự duyệt → trả lời
  • 12.5 1D DP: Fibonacci, Climbing Stairs, House Robber
  • 12.6 2D Grid DP: Unique Paths, Min Path Sum
  • 12.7 Knapsack: 0/1 knapsack, unbounded knapsack, partition
  • 12.8 LIS (Longest Increasing Subsequence): O(n²) DP và O(n log n) với binary search
  • 12.9 LCS (Longest Common Subsequence) & Edit Distance
  • 12.10 Interval DP: Matrix Chain Multiplication, Burst Balloons
  • 12.11 Tối ưu space: rolling array
  • 12.12 DP trên cây và DP bitmask (giới thiệu)

💡 Bài toán LeetCode tiêu biểu

  • Climbing Stairs, House Robber I & II, Coin Change I & II
  • Longest Increasing Subsequence, Longest Common Subsequence, Edit Distance
  • Unique Paths, Minimum Path Sum, Word Break
  • Best Time to Buy and Sell Stock (4 biến thể), Partition Equal Subset Sum
  • Burst Balloons, Regular Expression Matching
⚠️ Lời khuyên cuối

DSA không học một lần là xong. Hãy đi qua giáo trình này theo chiều ngang trước (đọc tổng quan từng chương), rồi mới đi sâu chiều dọc (gõ code, làm bài tập). Sau khi xong toàn bộ, quay lại review và bắt đầu giải LeetCode pattern theo pattern.

Số lượng bài cần giải để cảm thấy "thoải mái": ~150-200 bài LeetCode (NeetCode 150 + một ít bonus). Đừng cố giải 500 bài — chất lượng tư duy cho mỗi bài quan trọng hơn.

← Quay lại Trang chủ DSA Bắt đầu học Chương 01: Big-O →