GĐ00 — Data Structures, Algorithms & Complexity cho Software Engineer

Mục tiêu của giai đoạn này không phải biến bạn thành competitive programmer. Bạn cần đủ nền để chọn cấu trúc dữ liệu đúng, đọc được độ phức tạp của code, giải thích quyết định trong phỏng vấn, và nhận ra khi một đoạn code sẽ gãy khi dữ liệu tăng.

Học song song được với GĐ02–05. Không cần hoàn thành mọi bài thuật toán rồi mới viết backend.

Kiểm chứng ngày 2026-10-05: các đoạn mã ngắn ở mục 2, 5, 6, 7, 8, 9, 10, mục 10a, benchmark ở bài tập mục 1 và bản LRU danh sách liên kết đôi đều đã chạy trên Node 24.21 (macOS, type stripping) và qua tsc --noEmit TypeScript 6.0.3 với strict, noUncheckedIndexedAccess, erasableSyntaxOnly. Số ms của benchmark tuỳ máy; điều cần so là tỉ lệ. Chưa kiểm: hành vi trên các engine ngoài V8.

1. Complexity — đo trước khi tối ưu#

Big-O mô tả tốc độ tăng của thời gian hoặc bộ nhớ khi kích thước input n tăng.

Luôn xét cả:

• Time complexity: CPU tăng thế nào.
• Space complexity: bộ nhớ bổ sung tăng thế nào.
• Average vs worst case: hash map thường O(1), nhưng không phải lời hứa tuyệt đối.
• Input thực tế: thuật toán tốt hơn về Big-O chưa chắc nhanh hơn với dữ liệu rất nhỏ.

Bài tập#

1. Phân tích time/space complexity của năm hàm bạn từng viết.

   Lời giải và cách kiểm tra

   Tự làm trước, rồi mới mở. Code tham chiếu, chưa chạy riêng (các hàm ở mục 11 thì đã chạy, xem cuối mục đó).

   Cách làm: đếm vòng lặp lồng nhau, xem mỗi bước bên trong có tự lặp qua n không (includes, indexOf, slice, spread đều là O(n) ẩn), rồi đếm bộ nhớ tạo thêm.

   typescriptReady

   // A: O(n) time, O(1) spaceconst total = (xs: number[]) => xs.reduce((a, b) => a + b, 0)// B: O(n^2) time, O(1) space: indexOf() là vòng lặp ẩnconst hasDup = (xs: number[]) => xs.some((x, i) => xs.indexOf(x) !== i)// C: O(n) time, O(n) space: đổi bộ nhớ lấy thời gianconst hasDupFast = (xs: number[]) => new Set(xs).size !== xs.length// D: O(n log n) time, O(n) space: [...xs] copy + sortconst sortedCopy = (xs: number[]) => [...xs].sort((a, b) => a - b)// E: O(n^2) time, O(n^2) space: spread trong vòng lặp copy lại cả mảngconst prefixes = (xs: number[]) => xs.map((_, i) => [...xs.slice(0, i + 1)])

   Sai thường gặp: quên chi phí ẩn của indexOf/includes/slice nên tưởng B và E là O(n).

2. Thay một đoạn tìm kiếm lặp lại trên array bằng Map và đo trước/sau.

   Lời giải và cách kiểm tra

   Tự làm trước, rồi mới mở. Benchmark dưới đây đã chạy trên Node 24.21 (máy 12 core, ba lần chạy cho kết quả cùng cỡ).

   Cách làm: dựng n bản ghi, tra n lần; bản chậm dùng find, bản nhanh dựng Map một lần (chi phí dựng Map tính vào bản nhanh). Phải có warm-up: vài lượt đầu V8 chưa tối ưu code nóng nên chậm và dao động; bỏ chúng ra, rồi lấy trung vị nhiều lượt thay vì một lần console.time.

   typescriptReady

   const n = Number(process.argv[2] ?? 20_000)const users = Array.from({ length: n }, (_, i) => ({ id: i, name: `u${i}` }))const ids = Array.from({ length: n }, (_, i) => (i * 7919) % n)function viaFind(): number {  let hits = 0  for (const id of ids) if (users.find((u) => u.id === id)) hits++  return hits}function viaMap(): number {  const byId = new Map(users.map((u) => [u.id, u]))  let hits = 0  for (const id of ids) if (byId.get(id)) hits++  return hits}function bench(name: string, fn: () => number, warmup = 3, runs = 7): void {  for (let i = 0; i < warmup; i++) fn() // lượt nóng máy, bỏ kết quả  const times: number[] = []  for (let i = 0; i < runs; i++) {    const t = performance.now()    fn()    times.push(performance.now() - t)  }  times.sort((a, b) => a - b)  console.log(`${name} median ${times[runs >> 1]!.toFixed(2)} ms`)}bench('find', viaFind)bench('map', viaMap)

   Số đo (median, node bench.ts N):

   n	find	Map	find / Map
   2 000	1,04 ms	0,14 ms	cỡ 7 lần
   20 000	113 đến 120 ms	1,3 đến 1,5 ms	cỡ 80 lần

   Cách đọc: n tăng 10 lần thì find chậm khoảng 110 lần (O(n²)), Map chậm khoảng 10 lần (O(n)); với n = 2 000 chênh lệch còn nhỏ nên tối ưu sớm ở đó chưa đáng. Sai thường gặp: đo với n = 10, thấy find không chậm hơn, rồi kết luận Big-O vô nghĩa (với n nhỏ, hằng số che mất tốc độ tăng); đo một lần duy nhất bằng console.time rồi tin con số đó.

3. Giải thích vì sao tối ưu O(n²) đáng ưu tiên hơn micro-optimize một vòng O(n).

   Lời giải và cách kiểm tra

   Tự làm trước, rồi mới mở. Code tham chiếu, chưa chạy riêng (các hàm ở mục 11 thì đã chạy, xem cuối mục đó).

   Micro-optimize chỉ đổi hằng số (thường 1,5–3 lần); đổi lớp độ phức tạp đổi cả hệ số theo n. Ví dụ: n = 10⁵ thì n² = 10¹⁰ phép tính (hàng chục giây) còn n = 10⁵ (dưới 1 ms): bỏ vòng O(n²) được lợi cỡ 10⁵ lần, tối ưu hằng số một vòng O(n) được lợi vài lần trên một phần nhỏ thời gian. Điều kiện: đo trước (profile) để chắc đoạn O(n²) nằm trên đường nóng với n thật.

2. Array và String#

Array lưu một dãy phần tử theo thứ tự. Đây là cấu trúc bạn dùng nhiều nhất trong application code.

Cần nắm:

• Truy cập theo index thường là O(1).
• Tìm theo giá trị là O(n) nếu chưa có index phụ.
• Thêm/xoá ở cuối thường rẻ; thêm/xoá ở đầu hoặc giữa phải dịch chuyển phần tử.
• slice, spread và nhiều hàm immutable tạo array mới, vì vậy có chi phí bộ nhớ.
• String thường immutable; nối chuỗi lớn trong loop có thể tạo nhiều allocation.

Pattern cần luyện:

• Two pointers.
• Sliding window.
• Prefix sum.
• Sort rồi scan.

// two pointers trên mảng đã sort: có cặp cộng ra target không? O(n) time, O(1) spacefunction hasPairWithSum(sorted: number[], target: number): boolean {  let left = 0  let right = sorted.length - 1  while (left < right) {    const sum = sorted[left]! + sorted[right]!    if (sum === target) return true    if (sum < target) left++    else right--  }  return false}// nối chuỗi lớn: gom vào mảng rồi join một lầnconst lines = Array.from({ length: 5 }, (_, i) => `row ${i}`)console.log(hasPairWithSum([1, 3, 5, 8, 11], 13), hasPairWithSum([1, 3, 5], 100))console.log(lines.join('\n').split('\n').length)

Liên hệ backend: pagination trong bộ nhớ, xử lý batch, rolling metrics, rate limiting theo cửa sổ thời gian.

3. Hash Map và Set#

Trong TypeScript, hai công cụ chính là Map và Set.

Dùng khi cần:

• Lookup theo key.
• Đếm tần suất.
• Deduplicate.
• Group dữ liệu.
• Join hai tập dữ liệu nhỏ trong application memory.

function countByStatus(items: { status: string }[]) {  const counts = new Map<string, number>()  for (const item of items) {    counts.set(item.status, (counts.get(item.status) ?? 0) + 1)  }  return counts}countByStatus([{ status: 'ok' }, { status: 'fail' }, { status: 'ok' }])// Map(2) { 'ok' => 2, 'fail' => 1 }   (đã chạy trên Node 24.21)

Pitfall: biến toàn bộ bảng database thành Map trong RAM không thay thế cho index hoặc query đúng.

4. Stack và Queue#

Stack — LIFO#

Phần tử vào sau ra trước.

Ứng dụng:

• Call stack.
• Undo.
• Parse expression.
• DFS không dùng recursion.
• Kiểm tra ngoặc hợp lệ.

Queue — FIFO#

Phần tử vào trước ra trước.

Ứng dụng:

• Background jobs.
• Buffer.
• Request scheduling.
• BFS.

Trong JavaScript, gọi shift() liên tục trên array lớn có thể tốn O(n). Khi cần queue hiệu quả, dùng con trỏ head hoặc cấu trúc queue chuyên dụng.

5. Linked List#

Linked list cho phép thêm/xoá tại vị trí đã biết mà không dịch chuyển toàn bộ phần tử, đổi lại:

• Không truy cập index O(1) như array.
• Tốn thêm bộ nhớ cho pointer.
• Cache locality kém hơn array.

Bạn cần hiểu để phỏng vấn và đọc implementation của LRU cache; trong product code TypeScript, ít khi cần tự viết linked list.

type ListNode<T> = { value: T; next: ListNode<T> | null }// đảo danh sách liên kết đơn tại chỗ: O(n) time, O(1) spacefunction reverse<T>(head: ListNode<T> | null): ListNode<T> | null {  let prev: ListNode<T> | null = null  while (head) {    const next = head.next // nhớ node kế trước khi đổi con trỏ    head.next = prev    prev = head    head = next  }  return prev}const list: ListNode<number> = { value: 1, next: { value: 2, next: { value: 3, next: null } } }let node = reverse(list)const out: number[] = []while (node) { out.push(node.value); node = node.next }console.log(out) // [ 3, 2, 1 ]

Bản LRU dùng danh sách liên kết đôi kèm Map nằm ở mini utility số 1 (phần Thực hành bên dưới).

6. Tree, Binary Search Tree và B-tree#

Tree mô hình hoá dữ liệu phân cấp: DOM, filesystem, category tree, AST.

Cần nắm:

• Root, parent, child, leaf, depth, height.
• DFS: preorder, inorder, postorder.
• BFS theo từng level.
• Binary Search Tree và điều kiện trái < node < phải.
• Tree cân bằng giữ lookup gần O(log n).

type TreeNode = { key: number; left: TreeNode | null; right: TreeNode | null }// BST: trái < node < phải. Insert O(h), h ~ log n nếu cây cân bằng, n nếu bị lệchfunction insert(root: TreeNode | null, key: number): TreeNode {  if (!root) return { key, left: null, right: null }  if (key < root.key) root.left = insert(root.left, key)  else if (key > root.key) root.right = insert(root.right, key)  return root}// DFS inorder trên BST cho ra dãy tăng dầnfunction inorder(root: TreeNode | null, out: number[] = []): number[] {  if (root) { inorder(root.left, out); out.push(root.key); inorder(root.right, out) }  return out}let root: TreeNode | null = nullfor (const key of [50, 30, 70, 20, 40, 60, 80]) root = insert(root, key)console.log(inorder(root)) // 20, 30, 40, 50, 60, 70, 80 (tăng dần)

Chèn khoá đã sắp xếp sẵn (1, 2, 3, ...) vào BST không cân bằng cho ra cây lệch thành một đường thẳng, lookup lùi về O(n); đó là lý do cần tree tự cân bằng và B-tree.

Liên hệ backend: PostgreSQL thường dùng B-tree index, được thiết kế cho block storage và cho phép mỗi node chứa nhiều key. Không đồng nhất B-tree với binary tree.

7. Heap và Priority Queue#

Heap trả phần tử nhỏ nhất hoặc lớn nhất hiệu quả mà không cần sort lại toàn bộ collection.

Ứng dụng:

• Job priority.
• Top-K.
• Scheduler.
• Merge nhiều stream đã sắp xếp.

Cần biết:

• Peek: O(1).
• Push/pop: O(log n).
• Build heap có thể đạt O(n).

Không cần tự thuộc implementation; cần giải thích được vì sao priority queue phù hợp hơn việc sort array sau mỗi lần thêm.

const heap = new MinHeap() // lớp MinHeap lấy từ Bài 11for (const priority of [5, 1, 4, 2]) heap.push(priority)console.log(heap.peek(), heap.pop(), heap.pop(), heap.size) // 1 1 2 2

8. Graph#

Graph gồm vertex và edge, có thể có hướng hoặc vô hướng, có trọng số hoặc không.

Ứng dụng:

• Dependency graph.
• Social connection.
• Workflow/state transition.
• Service dependency.
• Route planning.

Hai cách biểu diễn chính:

• Adjacency list: phù hợp graph thưa, thường dùng nhất.
• Adjacency matrix: lookup edge nhanh nhưng tốn O(V²) bộ nhớ.

Cần luyện:

• BFS cho đường đi ngắn nhất trên graph không trọng số.
• DFS cho traversal và cycle detection.
• Topological sort cho dependency có hướng không chu trình.

// adjacency list từ danh sách cạnh có hướng: from phụ thuộc vào toconst edges: [string, string][] = [['api', 'db'], ['api', 'cache'], ['cache', 'db']]const graph = new Map<string, string[]>()for (const [from, to] of edges) {  graph.set(from, [...(graph.get(from) ?? []), to])  if (!graph.has(to)) graph.set(to, []) // node chỉ có cạnh vào vẫn phải có mặt}console.log(graph)// Map(3) { 'api' => [ 'db', 'cache' ], 'db' => [], 'cache' => [ 'db' ] }

Ngoài phạm vi của stage này: đường đi ngắn nhất có trọng số (Dijkstra), Trie, Union-Find. Gặp trong thực tế thì dùng thư viện hoặc tìm bài giải khi cần; BFS, DFS và topological sort ở trên là đủ cho nền backend.

9. Search và Sort#

Search#

• Linear search: O(n).
• Binary search: O(log n), chỉ đúng khi dữ liệu có thứ tự và invariant được giữ.

Binary search không chỉ dùng để tìm một giá trị. Nó còn dùng để tìm biên đầu/cuối hoặc “giá trị nhỏ nhất thoả điều kiện”.

Sort#

Cần hiểu trade-off, không cần tự viết mọi thuật toán:

• Stable vs unstable.
• In-place vs cần bộ nhớ phụ.
• Average vs worst case.
• Comparator phải nhất quán.

Trong application code, ưu tiên built-in sort. Tự triển khai chỉ để học cơ chế.

console.log([10, 9, 1].sort()) // [ 1, 10, 9 ]: mặc định so sánh như chuỗiconsole.log([10, 9, 1].sort((a, b) => a - b)) // [ 1, 9, 10 ]const rows = [{ n: 'b', p: 1 }, { n: 'a', p: 1 }, { n: 'c', p: 0 }]// sort ổn định (Node 11+): hai phần tử bằng nhau giữ thứ tự cũ; toSorted không đổi mảng gốcconsole.log(rows.toSorted((x, y) => x.p - y.p).map((r) => r.n).join('')) // cbaconsole.log(rows.map((r) => r.n).join('')) // bac

10. Recursion và Dynamic Programming cơ bản#

Recursion phù hợp cấu trúc tự lặp như tree, nhưng recursion quá sâu có thể làm tràn call stack.

Dynamic Programming dùng khi bài toán có:

• Subproblem lặp lại.
• Optimal substructure.

Hai cách:

• Memoization: top-down.
• Tabulation: bottom-up.

Cho mục tiêu full-stack, chỉ cần nhận diện và giải các bài DP một chiều/two-dimensional cơ bản. Không để DP chiếm thời gian đáng ra dùng để build sản phẩm.

// memoization top-down: fib(n) từ O(2^n) xuống O(n)function fib(n: number, memo = new Map<number, number>()): number {  if (n < 2) return n  const hit = memo.get(n)  if (hit !== undefined) return hit  const value = fib(n - 1, memo) + fib(n - 2, memo)  memo.set(n, value)  return value}console.log(fib(50)) // 12586269025 (bản không memo mất hàng chục giây)// recursion quá sâu làm tràn call stackconst depth = (n: number): number => (n === 0 ? 0 : 1 + depth(n - 1))try { depth(1_000_000) } catch (e) { console.log((e as Error).name, (e as Error).message) }

10a. Bẫy JavaScript có chứng minh bằng lệnh chạy được#

Sáu lệnh trong bảng dưới đây đều chạy xong mà không ném exception (lỗi nằm ở kết quả sai, không phải ở lỗi chạy; phần ghi chú của bẫy 6 nhắc thêm rằng JSON.stringify với BigInt thì có ném TypeError, nhưng lệnh trong bảng không chứa BigInt). Mỗi bẫy có một lệnh để tự chạy, kết quả thật trên Node 24.21 và cách tránh.

Bẫy 4 còn có mặt nguy hiểm hơn: Object.assign({}, JSON.parse('{"__proto__":{"admin":true}}')).admin trả true (đã chạy), vì Object.assign gán qua setter __proto__ nên prototype của object đích bị thay bằng dữ liệu của người dùng; spread { ...input } không dính. Đừng trộn input thô vào object cấu hình bằng Object.assign, hãy validate bằng schema (Zod) rồi mới dùng.

11. Bài tập có đáp án TypeScript#

Cách học phần này#

Với mỗi bài:

1. Tự làm tối thiểu 20 phút.
2. Viết brute-force trước nếu chưa thấy lời giải tối ưu.
3. Chạy test bằng tay.
4. Ghi time/space complexity.
5. Sau đó mới mở đáp án và tự viết lại không nhìn.

Các snippet giả định TypeScript strict: true. Có thể đặt vào một project Vitest hoặc chạy bằng tsx.

Bài 1 — Two Sum bằng Hash Map#

Đề. Cho array số nguyên và target, trả về index của hai phần tử có tổng bằng target. Mỗi input có tối đa một đáp án; không dùng lại cùng một phần tử.

twoSum([2, 7, 11, 15], 9) // [0, 1]

Hướng nghĩ. Brute-force thử mọi cặp mất O(n²). Khi đang đứng ở value, ta cần biết target - value đã xuất hiện chưa. Map trả lời lookup đó trung bình O(1).

Đáp án.

function twoSum(values: number[], target: number): [number, number] | null {  const indexByValue = new Map<number, number>()  for (let index = 0; index < values.length; index++) {    const value = values[index]!    const complement = target - value    const complementIndex = indexByValue.get(complement)    if (complementIndex !== undefined) {      return [complementIndex, index]    }    indexByValue.set(value, index)  }  return null}

Vì sao đúng. Trước khi lưu phần tử hiện tại, map chỉ chứa các phần tử đứng trước nó. Nếu complement tồn tại, hai index chắc chắn khác nhau. Lưu sau khi kiểm tra cũng xử lý đúng [3, 3], target 6.

• Time: O(n) trung bình.
• Space: O(n).
• Pitfall: dùng if (complementIndex) sẽ bỏ sót index 0; phải so với undefined.

Bài 2 — Deduplicate event, giữ bản mới nhất#

Đề. Một batch có thể chứa nhiều event cùng id. Giữ event có occurredAt mới nhất và trả theo thứ tự thời gian tăng dần.

type DomainEvent = { id: string; occurredAt: number; payload: string }

Đáp án.

function deduplicateLatest(events: DomainEvent[]): DomainEvent[] {  const latestById = new Map<string, DomainEvent>()  for (const event of events) {    const current = latestById.get(event.id)    if (!current || event.occurredAt > current.occurredAt) {      latestById.set(event.id, event)    }  }  return [...latestById.values()].sort(    (left, right) => left.occurredAt - right.occurredAt,  )}

Giải thích. Map loại vòng lặp tìm event cũ cho từng event mới. Sau deduplicate còn k event duy nhất, nên bước sort là O(k log k).

• Time: O(n + k log k).
• Space: O(k).
• Production note: deduplicate trong RAM chỉ có hiệu lực trong một process/batch; idempotency phân tán cần unique constraint hoặc shared store.

Bài 3 — Sliding window rate limit#

Đề. Cho danh sách timestamp đã tăng dần, tìm số request lớn nhất xuất hiện trong bất kỳ cửa sổ windowMs nào.

maxRequestsInWindow([100, 200, 900, 1_099, 1_200], 1_000) // 4

Đáp án.

function maxRequestsInWindow(timestamps: number[], windowMs: number): number {  let left = 0  let maximum = 0  for (let right = 0; right < timestamps.length; right++) {    while (timestamps[right]! - timestamps[left]! >= windowMs) {      left++    }    maximum = Math.max(maximum, right - left + 1)  }  return maximum}

Vì sao là O(n). right đi từ trái sang phải một lần. left cũng chỉ tăng, tổng cộng tối đa n lần; while lồng bên trong không biến toàn bộ thuật toán thành O(n²).

• Time: O(n).
• Space: O(1) ngoài input.
• Boundary: code dùng cửa sổ nửa mở [now - windowMs, now); timestamp cách nhau đúng windowMs không cùng cửa sổ.

Bài 4 — Prefix Sum cho số liệu theo khoảng#

Đề. Cho số request mỗi phút. Trả tổng request từ phút start đến end, bao gồm cả hai đầu. Hàm sẽ được gọi nhiều lần trên cùng dữ liệu.

Đáp án.

class RangeSum {  private readonly prefix: number[]  constructor(values: number[]) {    this.prefix = new Array(values.length + 1).fill(0)    for (let index = 0; index < values.length; index++) {      this.prefix[index + 1] = this.prefix[index]! + values[index]!    }  }  query(start: number, end: number): number {    if (start < 0 || end < start || end >= this.prefix.length - 1) {      throw new RangeError('Invalid range')    }    return this.prefix[end + 1]! - this.prefix[start]!  }}

Giải thích. prefix[i] lưu tổng của các phần tử trước index i. Tổng [start, end] bằng tổng trước end + 1 trừ tổng trước start.

• Build: time O(n), space O(n).
• Mỗi query: O(1) thay vì O(n).
• Trade-off: phù hợp dữ liệu ít thay đổi, nhiều query; update liên tục cần cấu trúc khác như Fenwick tree hoặc xử lý ở database.

Bài 5 — Stack kiểm tra dấu ngoặc#

Đề. Chuỗi chỉ chứa ()[]{}. Trả true nếu mọi dấu ngoặc đóng đúng loại và đúng thứ tự.

Đáp án.

function hasValidBrackets(input: string): boolean {  const expectedOpening: Record<string, string> = {    ')': '(',    ']': '[',    '}': '{',  }  const stack: string[] = []  for (const character of input) {    const opening = expectedOpening[character]    if (opening) {      if (stack.pop() !== opening) return false    } else {      stack.push(character)    }  }  return stack.length === 0}

Giải thích. Dấu đóng phải khớp dấu mở gần nhất chưa được đóng — đúng định nghĩa LIFO của stack.

• Time: O(n).
• Space: O(n) worst case khi toàn dấu mở.
• Pitfall: chỉ đếm số lượng từng loại không phát hiện sai thứ tự như ([)].

Bài 6 — Queue không dùng shift()#

Đề. Cài queue generic với enqueue, dequeue, peek và size, tránh dịch chuyển array sau mỗi lần lấy phần tử.

Đáp án.

class Queue<T> {  private readonly items: T[] = []  private head = 0  get size(): number {    return this.items.length - this.head  }  enqueue(value: T): void {    this.items.push(value)  }  dequeue(): T | undefined {    const value = this.items[this.head]    if (value === undefined) return undefined    this.head++    if (this.head > 1_000 && this.head * 2 > this.items.length) {      this.items.splice(0, this.head)      this.head = 0    }    return value  }  peek(): T | undefined {    return this.items[this.head]  }}

Giải thích. head tăng mà không dịch chuyển phần còn lại. Thỉnh thoảng compact array để phần tử đã dequeue không bị giữ mãi; chi phí được phân bổ qua nhiều operation.

• enqueue: amortized O(1).
• dequeue: amortized O(1).
• Space: O(n) với số phần tử đang chờ cộng phần chưa compact.

Bài 7 — Binary Search tìm lower bound#

Đề. Array đã sắp xếp tăng dần. Tìm index đầu tiên có giá trị >= target; nếu mọi giá trị nhỏ hơn target, trả values.length.

lowerBound([1, 2, 2, 4], 2) // 1lowerBound([1, 2, 2, 4], 3) // 3

Đáp án.

function lowerBound(values: number[], target: number): number {  let left = 0  let right = values.length  while (left < right) {    const middle = left + Math.floor((right - left) / 2)    if (values[middle]! < target) {      left = middle + 1    } else {      right = middle    }  }  return left}

Invariant. Đáp án luôn nằm trong đoạn nửa mở [left, right]. Khi values[middle] < target, middle chắc chắn không phải đáp án. Ngược lại, middle vẫn có thể là phần tử đầu tiên nên giữ lại bằng right = middle.

• Time: O(log n).
• Space: O(1).
• Pitfall: dùng right = middle - 1 trong template nửa mở này làm mất candidate.

Bài 8 — BFS theo level trên cây#

Đề. Trả danh sách value theo từng depth của binary tree.

type TreeNode<T> = {  value: T  left?: TreeNode<T>  right?: TreeNode<T>}

Đáp án.

function levelOrder<T>(root?: TreeNode<T>): T[][] {  if (!root) return []  const queue: TreeNode<T>[] = [root]  const levels: T[][] = []  let head = 0  while (head < queue.length) {    const levelSize = queue.length - head    const level: T[] = []    for (let count = 0; count < levelSize; count++) {      const node = queue[head++]!      level.push(node.value)      if (node.left) queue.push(node.left)      if (node.right) queue.push(node.right)    }    levels.push(level)  }  return levels}

Giải thích. Tại đầu mỗi vòng while, queue chứa đúng các node chưa xử lý; levelSize chụp số node của level hiện tại trước khi child được thêm vào.

• Time: O(n).
• Space: O(w), với w là chiều rộng lớn nhất của cây; array backing có thể giữ tới O(n) nếu không compact.

Bài 9 — DFS phát hiện cycle trong dependency graph#

Đề. Graph có hướng biểu diễn service -> dependencies. Trả true nếu có cycle.

Đáp án.

function hasDependencyCycle(graph: Map<string, string[]>): boolean {  const visiting = new Set<string>()  const visited = new Set<string>()  const visit = (node: string): boolean => {    if (visiting.has(node)) return true    if (visited.has(node)) return false    visiting.add(node)    for (const dependency of graph.get(node) ?? []) {      if (visit(dependency)) return true    }    visiting.delete(node)    visited.add(node)    return false  }  for (const node of graph.keys()) {    if (visit(node)) return true  }  return false}

Giải thích. visiting là các node trên recursion path hiện tại. Gặp lại node trong tập này tạo back-edge, tức cycle. visited chứa node đã kiểm tra xong và giúp mỗi node chỉ xử lý một lần.

• Time: O(V + E).
• Space: O(V).
• Pitfall: chỉ dùng một visited set không phân biệt “đang thăm” và “đã xong”, nên không phát hiện đúng cycle có hướng.

Bài 10 — Topological Sort cho thứ tự deploy#

Đề. Trả thứ tự sao cho dependency được deploy trước service phụ thuộc nó. Nếu có cycle, ném lỗi.

Đáp án — Kahn's algorithm.

function deploymentOrder(graph: Map<string, string[]>): string[] {  const dependents = new Map<string, string[]>()  const remainingDependencies = new Map<string, number>()  for (const [service, dependencies] of graph) {    remainingDependencies.set(service, dependencies.length)    for (const dependency of dependencies) {      if (!remainingDependencies.has(dependency)) {        remainingDependencies.set(dependency, 0)      }      const list = dependents.get(dependency) ?? []      list.push(service)      dependents.set(dependency, list)    }  }  const queue = [...remainingDependencies]    .filter(([, count]) => count === 0)    .map(([service]) => service)  const order: string[] = []  let head = 0  while (head < queue.length) {    const deployed = queue[head++]!    order.push(deployed)    for (const dependent of dependents.get(deployed) ?? []) {      const nextCount = remainingDependencies.get(dependent)! - 1      remainingDependencies.set(dependent, nextCount)      if (nextCount === 0) queue.push(dependent)    }  }  if (order.length !== remainingDependencies.size) {    throw new Error('Dependency cycle detected')  }  return order}

Giải thích. Bắt đầu từ service không còn dependency. Mỗi khi deploy một service, giảm dependency count của các service phụ thuộc nó. Nếu không thể xử lý hết node, phần còn lại nằm trong cycle.

• Time: O(V + E).
• Space: O(V + E).

Bài 11 — Min Heap và Top-K latency#

Đề. Trả k latency lớn nhất nhưng không sort toàn bộ input. Dùng min heap kích thước tối đa k.

Đáp án.

class MinHeap {  private readonly values: number[] = []  get size(): number {    return this.values.length  }  peek(): number | undefined {    return this.values[0]  }  push(value: number): void {    this.values.push(value)    let index = this.values.length - 1    while (index > 0) {      const parent = Math.floor((index - 1) / 2)      if (this.values[parent]! <= this.values[index]!) break      ;[this.values[parent], this.values[index]] = [        this.values[index]!,        this.values[parent]!,      ]      index = parent    }  }  pop(): number | undefined {    if (this.values.length === 0) return undefined    const minimum = this.values[0]!    const last = this.values.pop()!    if (this.values.length === 0) return minimum    this.values[0] = last    let index = 0    while (true) {      const left = index * 2 + 1      const right = left + 1      let smallest = index      if (left < this.values.length && this.values[left]! < this.values[smallest]!) smallest = left      if (right < this.values.length && this.values[right]! < this.values[smallest]!) smallest = right      if (smallest === index) break      ;[this.values[index], this.values[smallest]] = [        this.values[smallest]!,        this.values[index]!,      ]      index = smallest    }    return minimum  }}function topKLatencies(latencies: number[], k: number): number[] {  if (k <= 0) return []  const heap = new MinHeap()  for (const latency of latencies) {    heap.push(latency)    if (heap.size > k) heap.pop()  }  const result: number[] = []  while (heap.size > 0) result.push(heap.pop()!)  return result.reverse()}

Giải thích. Heap chỉ giữ k phần tử lớn nhất đã thấy. Phần tử nhỏ nhất trong nhóm nằm ở root và bị loại khi heap vượt kích thước.

• Time: O(n log k) thay vì sort toàn bộ O(n log n).
• Space: O(k).
• Production note: percentile như p95 không nên tính bằng top-K trên toàn bộ traffic; dùng histogram hoặc streaming quantile phù hợp.

Bài 12 — Dynamic Programming: minimum cost#

Đề. Có chi phí tại mỗi bước. Từ vị trí 0 hoặc 1, mỗi lần đi 1 hoặc 2 bước. Tính chi phí nhỏ nhất để đi qua cuối array.

minCost([10, 15, 20]) // 15

Đáp án tối ưu bộ nhớ.

function minCost(costs: number[]): number {  let costBeforeTwo = 0  let costBeforeOne = 0  for (const currentCost of costs) {    const next = currentCost + Math.min(costBeforeOne, costBeforeTwo)    costBeforeTwo = costBeforeOne    costBeforeOne = next  }  return Math.min(costBeforeOne, costBeforeTwo)}

Giải thích. Chi phí tối ưu để đến bước hiện tại chỉ phụ thuộc hai bước trước. Không cần giữ cả bảng DP; hai biến đủ duy trì state transition.

• Time: O(n).
• Space: O(1).
• Cách nhận diện DP: cùng subproblem “chi phí tốt nhất tới index i” được dùng lại, và đáp án hiện tại được xây từ đáp án tối ưu nhỏ hơn.

Test nhanh cho các đáp án#

import assert from 'node:assert/strict'assert.deepEqual(twoSum([2, 7, 11, 15], 9), [0, 1])assert.equal(maxRequestsInWindow([100, 200, 900, 1_099, 1_200], 1_000), 4)assert.equal(hasValidBrackets('([]{})'), true)assert.equal(hasValidBrackets('([)]'), false)assert.equal(lowerBound([1, 2, 2, 4], 2), 1)assert.equal(lowerBound([1, 2, 2, 4], 3), 3)assert.deepEqual(topKLatencies([120, 10, 900, 340, 50], 3), [900, 340, 120])assert.equal(minCost([10, 15, 20]), 15)

Các test trên là smoke test, chưa đủ edge case. Tự bổ sung input rỗng, một phần tử, duplicate, số âm, boundary và input lớn.

levelOrder [[1],[2,3],[4]]          # cây: 1 -> (2 -> 4), 3cycle? false | order db -> cache -> api   # api cần db, cache; cache cần dbcycle? true                          # a -> b -> atopK [ 900, 340, 120 ]minCost 15

values: [1, 2, 2, 4]    target = 2     left=0 right=4 vòng 1: middle=2  values[2]=2 >= 2  -> right=2   (giữ middle làm ứng viên) vòng 2: middle=1  values[1]=2 >= 2  -> right=1 vòng 3: middle=0  values[0]=1 <  2  -> left=1 left == right == 1  -> trả 1

remaining: api=2  cache=1  db=0           queue=[db] deploy db    -> api=1, cache=0           queue=[cache] deploy cache -> api=0                    queue=[api] deploy api                               order = db, cache, api (đủ 3 node)Có cycle: một số node không bao giờ về 0, order.length < tổng node -> throw.

Thực hành — mini backend utilities#

Viết và test:

1. LRU cache giới hạn số phần tử.

   Lời giải và cách kiểm tra

   Tự làm trước. Cả hai bản dưới đây đã chạy trên Node 24.21 với test, và qua tsc --noEmit (TypeScript 6.0.3, strict, erasableSyntaxOnly).

   Hướng làm: Map giữ thứ tự chèn, nên key đầu tiên là key lâu chưa dùng nhất; mỗi lần get xoá rồi chèn lại để đẩy xuống cuối. get và set đều O(1).

   typescriptReady

   export class LruCache<K, V> {  private readonly map = new Map<K, V>()  private readonly capacity: number  constructor(capacity: number) {    if (capacity < 1) throw new RangeError('capacity must be >= 1')    this.capacity = capacity  }  get(key: K): V | undefined {    if (!this.map.has(key)) return undefined    const value = this.map.get(key) as V    this.map.delete(key)    this.map.set(key, value) // mới dùng -> cuối    return value  }  set(key: K, value: V): void {    if (this.map.has(key)) this.map.delete(key)    else if (this.map.size >= this.capacity) {      const oldest = this.map.keys().next().value as K      this.map.delete(oldest)    }    this.map.set(key, value)  }}

   Kết quả mong đợi: với capacity = 2, chuỗi set a, set b, get a, set c loại b (không phải a): get b trả undefined, get a và get c trả giá trị. Test cần có: ghi đè key cũ không làm tăng size, get key không tồn tại không đổi thứ tự. Lỗi hay gặp: dùng if (value) để kiểm tồn tại (bỏ sót giá trị 0, ''); không refresh thứ tự khi get, thành FIFO chứ không phải LRU.

   Bản danh sách liên kết đôi + Map (đúng cơ chế mà bản trên dựa vào ngầm; phỏng vấn thường yêu cầu bản này). Map cho lookup O(1) tới node; danh sách giữ thứ tự dùng, node có prev và next nên gỡ ra khỏi giữa danh sách cũng O(1):

   typescriptReady

   type Entry<K, V> = { key: K; value: V; prev: Entry<K, V> | null; next: Entry<K, V> | null }// Map cho lookup O(1); danh sách liên kết đôi giữ thứ tự dùng gần đây (đầu = mới nhất)export class LruCache<K, V> {  private readonly index = new Map<K, Entry<K, V>>()  private head: Entry<K, V> | null = null  private tail: Entry<K, V> | null = null  private readonly capacity: number  constructor(capacity: number) {    if (capacity < 1) throw new RangeError('capacity must be >= 1')    this.capacity = capacity  }  get(key: K): V | undefined {    const entry = this.index.get(key)    if (!entry) return undefined    this.unlink(entry)    this.pushFront(entry) // vừa dùng -> về đầu, O(1) vì có prev/next    return entry.value  }  set(key: K, value: V): void {    const existing = this.index.get(key)    if (existing) {      existing.value = value      this.unlink(existing)      this.pushFront(existing)      return    }    if (this.index.size >= this.capacity && this.tail) {      this.index.delete(this.tail.key) // loại node cuối = lâu chưa dùng nhất      this.unlink(this.tail)    }    const entry: Entry<K, V> = { key, value, prev: null, next: null }    this.index.set(key, entry)    this.pushFront(entry)  }  private unlink(entry: Entry<K, V>): void {    if (entry.prev) entry.prev.next = entry.next    else this.head = entry.next    if (entry.next) entry.next.prev = entry.prev    else this.tail = entry.prev    entry.prev = entry.next = null  }  private pushFront(entry: Entry<K, V>): void {    entry.next = this.head    if (this.head) this.head.prev = entry    this.head = entry    this.tail ??= entry  }}

   Test đã chạy: capacity = 2 với set a, set b, get a, set c loại b; ghi đè key cũ không tăng size và refresh thứ tự; giá trị 0 vẫn là hit; capacity = 0 ném RangeError; cuối cùng 20 000 thao tác ngẫu nhiên (seed cố định, 12 key, capacity = 5) cho kết quả get giống hệt bản Map. Output: lru ok. Lỗi hay gặp: quên cập nhật head/tail khi gỡ node ở hai đầu; quên index.delete khi loại node cuối; để prev/next cũ còn trỏ sau khi gỡ (rò node).

2. Rate limiter sliding window chạy trong memory.

   Lời giải và cách kiểm tra

   Tự làm trước. Code tham chiếu, chưa chạy: chỉ kiểm tĩnh bằng tsc --noEmit (TypeScript 6.0.3, strict, erasableSyntaxOnly); kết quả mong đợi suy ra từ code.

   Hướng làm: mỗi key giữ timestamp của các request được chấp nhận trong cửa sổ; bỏ timestamp đã ra khỏi cửa sổ rồi so với giới hạn. Đây là bài 3 áp vào từng key.

   typescriptReady

   export class SlidingWindowLimiter {  private readonly hits = new Map<string, number[]>()  private readonly limit: number  private readonly windowMs: number  constructor(limit: number, windowMs: number) {    this.limit = limit    this.windowMs = windowMs  }  allow(key: string, now = Date.now()): boolean {    const list = this.hits.get(key) ?? []    let start = 0    while (start < list.length && now - list[start]! >= this.windowMs) start++    const recent = start === 0 ? list : list.slice(start)    if (recent.length >= this.limit) {      this.hits.set(key, recent)      return false    }    recent.push(now)    this.hits.set(key, recent)    return true  }}

   Kết quả mong đợi: limit = 3, windowMs = 1000: gọi tại 0, 100, 200 đều true, tại 300 là false, tại 1000 là true (request ở 0 đã ra khỏi cửa sổ nửa mở, khớp quy ước bài 3). Truyền now vào để test không cần sleep. Giới hạn: nằm trong RAM một process, Map không tự dọn key không còn truy cập (cần job dọn hoặc TTL), nhiều instance mỗi bên đếm riêng nên cần Redis (GĐ09 nói về rate limit thật).

3. Job scheduler nhỏ dùng priority queue.

   Lời giải và cách kiểm tra

   Tự làm trước. Code tham chiếu, chưa chạy: chỉ kiểm tĩnh bằng tsc --noEmit (TypeScript 6.0.3, strict, erasableSyntaxOnly); kết quả mong đợi suy ra từ code.

   Hướng làm: tổng quát hoá MinHeap ở bài 11 bằng comparator; khoá so sánh là (runAt, seq) để job cùng giờ chạy theo thứ tự thêm (tính ổn định).

   typescriptReady

   type Job = { runAt: number; seq: number; run: () => void }const before = (a: Job, b: Job) => a.runAt < b.runAt || (a.runAt === b.runAt && a.seq < b.seq)class JobHeap {  private readonly items: Job[] = []  get size() { return this.items.length }  peek(): Job | undefined { return this.items[0] }  push(job: Job): void {    const a = this.items    a.push(job)    for (let i = a.length - 1; i > 0; ) {      const p = (i - 1) >> 1      if (!before(a[i]!, a[p]!)) break      ;[a[i], a[p]] = [a[p]!, a[i]!]      i = p    }  }  pop(): Job | undefined {    const a = this.items    const top = a[0]    const last = a.pop()    if (a.length > 0 && last) {      a[0] = last      for (let i = 0; ; ) {        let m = i        for (const c of [2 * i + 1, 2 * i + 2]) if (c < a.length && before(a[c]!, a[m]!)) m = c        if (m === i) break        ;[a[i], a[m]] = [a[m]!, a[i]!]        i = m      }    }    return top  }}export class Scheduler {  private readonly heap = new JobHeap()  private seq = 0  schedule(runAt: number, run: () => void): void {    this.heap.push({ runAt, seq: this.seq++, run })  }  /** Chạy mọi job đến hạn tại thời điểm `now`; trả số job đã chạy. */  tick(now: number): number {    let ran = 0    while (this.heap.peek() && this.heap.peek()!.runAt <= now) {      this.heap.pop()!.run()      ran++    }    return ran  }}

   Kết quả mong đợi: thêm job ở t=30, 10, 20, 10; tick(15) chạy 2 job t=10 (theo thứ tự thêm), tick(100) chạy hai job còn lại theo thứ tự 20, 30. Lấy job tiếp theo là O(log n) thay vì sort lại cả danh sách mỗi lần thêm. Với process thật, tick được gọi từ một setTimeout đặt theo peek().runAt - Date.now(). Giới hạn: mất hết khi process chết, nên production dùng queue có lưu trữ (GĐ10).

4. Dependency resolver có cycle detection và topological sort.

   Lời giải và cách kiểm tra

   Tự làm trước. Code tham chiếu, chưa chạy: chỉ kiểm tĩnh bằng tsc --noEmit (TypeScript 6.0.3, strict, erasableSyntaxOnly); kết quả mong đợi suy ra từ code.

   Hướng làm: gộp bài 9 (phát hiện cycle) và bài 10 (thứ tự), nhưng báo cả đường đi của cycle để lỗi đọc được.

   typescriptReady

   export function findCycle(graph: Map<string, string[]>): string[] | null {  const path: string[] = []  const onPath = new Set<string>()  const done = new Set<string>()  const visit = (node: string): string[] | null => {    if (onPath.has(node)) return [...path.slice(path.indexOf(node)), node]    if (done.has(node)) return null    onPath.add(node)    path.push(node)    for (const dep of graph.get(node) ?? []) {      const found = visit(dep)      if (found) return found    }    path.pop()    onPath.delete(node)    done.add(node)    return null  }  for (const node of graph.keys()) {    const found = visit(node)    if (found) return found  }  return null}export function resolve(graph: Map<string, string[]>): string[] {  const cycle = findCycle(graph)  if (cycle) throw new Error(`Dependency cycle: ${cycle.join(' -> ')}`)  return deploymentOrder(graph) // bài 10}

   Kết quả mong đợi: a -> b -> c -> a ném Dependency cycle: a -> b -> c -> a; đồ thị api -> [db, cache], cache -> [db] cho db, cache, api (đã chạy deploymentOrder với đồ thị này). Test cần có: node chỉ xuất hiện như dependency (không có key), self-loop a -> a, hai thành phần rời nhau.

5. Hàm group/deduplicate một batch event bằng Map/Set.

   Lời giải và cách kiểm tra

   Tự làm trước. Code tham chiếu, chưa chạy: chỉ kiểm tĩnh bằng tsc --noEmit (TypeScript 6.0.3, strict, erasableSyntaxOnly); kết quả mong đợi suy ra từ code.

   Hướng làm: Map<key, mảng> để group, Set để loại trùng; dedupe có chọn bản mới nhất đã có ở bài 2.

   typescriptReady

   export function groupBy<T, K>(items: T[], keyOf: (item: T) => K): Map<K, T[]> {  const groups = new Map<K, T[]>()  for (const item of items) {    const key = keyOf(item)    const list = groups.get(key)    if (list) list.push(item)    else groups.set(key, [item])  }  return groups}export function uniqueBy<T, K>(items: T[], keyOf: (item: T) => K): T[] {  const seen = new Set<K>()  return items.filter((item) => {    const key = keyOf(item)    if (seen.has(key)) return false    seen.add(key)    return true  })}

   Kết quả mong đợi: groupBy(events, e => e.type) cho Map có số phần tử bằng số type, tổng độ dài các nhóm bằng events.length; uniqueBy giữ bản đầu tiên của mỗi key và giữ thứ tự gốc. Time O(n), space O(n). Lỗi hay gặp: dùng object {} làm map với key do người dùng gửi (__proto__), nên dùng Map.

Không dùng các utility này thay Redis hoặc queue thật trong production. Mục tiêu là hiểu cơ chế mà công cụ production đang cung cấp.

Done khi#

• Tự phân tích được time và space complexity của code có một hoặc hai vòng lặp.

  Đáp án

  Quy trình: đếm vòng lặp lồng nhau, tìm chi phí ẩn (includes, indexOf, slice, spread, sort), rồi đếm bộ nhớ thêm. Ví dụ: hai vòng song song là O(n), hai vòng lồng nhau là O(n²), vòng lặp có Set.has bên trong vẫn O(n). Cách tự kiểm: làm lại bài tập mục 1, đối chiếu với bài 1, 3, 4 ở mục 11. Sai thường gặp: bỏ qua space của [...xs]/slice. Xem GĐ00 mục 1.

• Chọn được Array, Map, Set, Stack, Queue, Heap, Tree hoặc Graph và giải thích vì sao.

  Đáp án

  Cần lookup/đếm/dedupe: Map/Set. Thứ tự vào/ra: Queue (FIFO), Stack (LIFO). Lấy nhỏ/lớn nhất liên tục: heap. Phân cấp: tree. Quan hệ n-n: graph. Mẫu trả lời: "cần X thao tác, cấu trúc này làm X trong O(...), đánh đổi là ...". Ví dụ: job ưu tiên dùng heap vì pop là O(log n) còn sort lại mỗi lần thêm là O(n log n). Xem GĐ00 mục 3 đến 8.

• Viết được BFS và DFS mà không nhìn tài liệu.

  Đáp án

  BFS: queue + head + chụp levelSize (bài 8). DFS: đệ quy hoặc stack, với đồ thị có hướng cần tập "đang thăm" và "đã xong" (bài 9). Cách tự kiểm: viết lại cả hai trên cùng đồ thị, kết quả BFS phải theo level, DFS phát hiện được a -> b -> a. Sai thường gặp: quên đánh dấu visited khi push vào queue nên node bị thêm nhiều lần.

• Dùng binary search đúng điều kiện.

  Đáp án

  Điều kiện: dữ liệu có thứ tự theo đúng vị từ đang tìm, và giữ nguyên một invariant (đáp án luôn nằm trong [left, right] nửa mở). Mẫu lowerBound ở bài 7 giải được cả "tìm biên đầu", "chèn vào đâu", "giá trị nhỏ nhất thoả điều kiện". Cách tự kiểm: chạy trên mảng rỗng, một phần tử, target nhỏ hơn hết và lớn hơn hết. Sai thường gặp: right = middle - 1 trong template nửa mở.

• Giải được khoảng 40–60 bài theo pattern, không học thuộc lời giải.

  Đáp án

  Đây là việc luyện tập, tự kiểm bằng sổ ghi: mỗi bài ghi pattern (two pointers, sliding window, prefix sum, hash map, heap, BFS/DFS, binary search, DP), độ phức tạp, và một lỗi đã mắc. Đạt khi gặp bài mới trong 5 phút gọi được tên pattern. Sai thường gặp: học thuộc lời giải; kiểm bằng cách giải lại sau một tuần không nhìn.

• Hoàn thành năm mini utilities và có test.

  Đáp án

  Năm cái là LRU, rate limiter, scheduler, dependency resolver, group/dedupe; mỗi cái có test (ít nhất: bình thường, rỗng, biên, lỗi). Xem khối lời giải dưới từng mục 1–5. Cách tự kiểm: các test chạy không cần sleep (truyền thời gian vào).

• Nêu được sáu bẫy JavaScript ở mục 10a và cách tránh từng bẫy.

  Đáp án

  Số thực (0.1 + 0.2): tiền lưu số nguyên cent. sort() mặc định so như chuỗi và đổi mảng gốc: truyền comparator, dùng toSorted. Số nguyên quá MAX_SAFE_INTEGER mất độ chính xác: ID lớn dạng string/BigInt. Object thường có prototype: dùng Map cho từ điển. Array(n).fill([]) dùng chung một tham chiếu: Array.from. JSON.stringify bỏ undefined, làm phẳng Map, ném với BigInt. Cách tự kiểm: chạy lại sáu lệnh ở bảng và đoán kết quả trước khi chạy. Xem GĐ00 mục 10a.

• Liên hệ được ít nhất năm cấu trúc dữ liệu với backend production.

  Đáp án

  Ví dụ: B-tree (index PostgreSQL), hash map (cache, đếm rate limit), heap/sorted set (hàng đợi job có độ ưu tiên, delayed job của BullMQ dùng sorted set của Redis), queue (background job, buffer), graph (dependency giữa service, thứ tự migration), linked list + hash map (LRU), tree (filesystem, category). Cách tự kiểm: với mỗi cái chỉ ra một nơi trong dự án của bạn đang dùng nó. Xem GĐ00 mục 6 về B-tree.

Câu hỏi mở / chưa giải quyết#

• Ngôn ngữ phỏng vấn chính sẽ là TypeScript hay ngôn ngữ khác?

  Hướng trả lời hiện tại

  Chưa chốt, suy ra từ mục tiêu của stage: người học chuyển Fullstack/AI SaaS đã dùng TypeScript hằng ngày, nên luyện bằng TypeScript là hợp lý; nếu công ty yêu cầu ngôn ngữ khác, các pattern vẫn giữ nguyên và chỉ đổi cú pháp.

• Công ty mục tiêu yêu cầu DSA ở mức thực dụng hay competitive programming?

  Hướng trả lời hiện tại

  Chưa chốt: với mục tiêu "thực dụng" ở đầu file, ưu tiên các pattern ở mục 11 trước competitive programming; chỉ mở rộng (đồ thị có trọng số, DP khó) khi biết cụ thể vòng phỏng vấn của công ty mục tiêu.