1Biểu diễn đồ thị
Đồ thị gần như luôn lưu bằng danh sách kề. Lưới 2D là đồ thị ngầm: mỗi ô nối 4 ô kề, không cần dựng đồ thị.
| Cách lưu | Bộ nhớ | Dùng khi |
|---|---|---|
| Danh sách kề | O(V + E) | Đồ thị thưa: hầu hết bài |
| Ma trận kề | O(V²) | Đồ thị dày, V nhỏ |
Cấu trúc dữ liệu & Thuật toánMid34 phút đọc
Cả bài trong một trang: ý chính, sơ đồ, điểm phỏng vấn.
Đồ thị gần như luôn lưu bằng danh sách kề. Lưới 2D là đồ thị ngầm: mỗi ô nối 4 ô kề, không cần dựng đồ thị.
| Cách lưu | Bộ nhớ | Dùng khi |
|---|---|---|
| Danh sách kề | O(V + E) | Đồ thị thưa: hầu hết bài |
| Ma trận kề | O(V²) | Đồ thị dày, V nhỏ |
BFS dùng queue, cho đường ngắn nhất theo số cạnh. Cạnh có trọng số không âm thì Dijkstra với PriorityQueue, O(E log V).
flowchart TD
A{"Đường ngắn nhất?"} -->|không trọng số| B["BFS theo tầng, O(V + E)"]
A -->|trọng số không âm| C["Dijkstra + heap, O(E log V)"]
A -->|có cạnh âm| D["Bellman-Ford, O(V·E)"]
Topological sort (Kahn) xếp thứ tự có phụ thuộc; không xếp hết đỉnh là có chu trình. Union-find trả lời "cùng nhóm không" khi cạnh thêm dần, gần O(1).
Dùng khi đề hỏi số cách, min/max, và bài con lặp lại. Định nghĩa dp[...] bằng một câu trước, rồi mới viết công thức.
| Bài | dp nghĩa là |
Chuyển |
|---|---|---|
| Leo cầu thang | Số cách tới bậc i | ways[i-1] + ways[i-2] |
| Đổi tiền | Ít đồng nhất ra a | min(dp[a-c] + 1) |
| Knapsack 0/1 | Giá trị lớn nhất, sức chứa c | c giảm dần |
Duyệt sức chứa từ lớn về nhỏ để dp[c - w] vẫn là giá trị trước khi xét món này. Duyệt xuôi thành dùng một món nhiều lần.
for (int i = 0; i < weight.length; i++)
for (int c = cap; c >= weight[i]; c--)
dp[c] = Math.max(dp[c],
dp[c - weight[i]] + value[i]);
💡 Ghi nhớ
Nói tín hiệu, kỹ thuật, độ phức tạp trước khi code.
Memo top-down dễ viết; bảng bottom-up không tràn stack.
Đổi tiền: "vô cực" là amount + 1 để khỏi tràn số.
Knapsack O(n·C) là pseudo-polynomial, C lớn thì không dùng.
⭐ Điểm phỏng vấn
Tự trả lời trước, rồi bấm từng câu để xem đáp án.
BFS hay Dijkstra?
Không trọng số: BFS; trọng số không âm: Dijkstra.
Phát hiện chu trình có hướng?
Kahn không xếp được hết đỉnh.
Vì sao đổi tiền không tham lam?
{1, 3, 4} ra 6: tham lam 3 đồng, đúng 2.
Xong phần tự kiểm tra, bài này đã được đánh dấu đã học ✓
⚠️ Lỗi thường gặp
Đánh dấu visited khi lấy ra khỏi queue thay vì khi cho vào.
DFS đệ quy trên lưới 300×300 toàn đất: StackOverflowError.
Dùng Dijkstra khi có cạnh âm: kết quả sai.
Cụm bài Luyện phỏng vấn thuật toán: 1. Cây và heap · 2. Đồ thị và quy hoạch động
Mười một bài phỏng vấn hay gặp về đồ thị và quy hoạch động, mỗi bài có đề diễn đạt lại, ý tưởng, lời giải Java 21 đã chạy thử, độ phức tạp và edge case. Cuối bài có bảng “tín hiệu trong đề → kỹ thuật” để ôn nhanh. Nên đọc trước cây và heap (BFS, PriorityQueue) và memoization và tabulation.
Sơ đồ tóm tắt:
flowchart TD
Q{"Tín hiệu trong đề"} -->|"Lưới, vùng liền nhau"| G["BFS/DFS trên lưới"]
Q -->|"Ngắn nhất, không trọng số"| B["BFS theo tầng"]
Q -->|"Ngắn nhất, trọng số không âm"| D["Dijkstra + PriorityQueue"]
Q -->|"Thứ tự có phụ thuộc"| T["Topological sort, Kahn"]
Q -->|"Cùng nhóm, cạnh thêm dần"| U["Union-find"]
Q -->|"Số cách, min, max, bài con lặp"| P["Quy hoạch động"]
P --> P1["Memo top-down"]
P --> P2["Bảng bottom-up"]
Ý chính: đồ thị thường lưu bằng danh sách kề List<List<Integer>>. BFS dùng queue, cho đường ngắn nhất theo số cạnh; DFS dùng stack hoặc đệ quy, hợp với tìm vùng, chu trình.
| Cách lưu | Bộ nhớ | Hỏi “u nối v?” | Dùng khi |
|---|---|---|---|
| Danh sách kề | O(V + E) | O(bậc của u) | đồ thị thưa: hầu hết bài |
| Ma trận kề | O(V²) | O(1) | đồ thị dày, V nhỏ |
Lưới 2D không cần dựng đồ thị: hàng xóm của ô (r, c) là (r ± 1, c), (r, c ± 1) còn trong lưới.
Đề: lưới '1' (đất) và '0' (nước); đếm số đảo, mỗi đảo là các ô đất nối nhau theo chiều ngang hoặc dọc.
Ý tưởng: duyệt từng ô; gặp ô đất thì tăng bộ đếm và loang (BFS) để xoá cả đảo về '0'.
import java.util.*;
public class Main {
static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
static int numIslands(char[][] grid) {
if (grid.length == 0) return 0;
int rows = grid.length, cols = grid[0].length, count = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] != '1') continue;
count++;
Deque<int[]> queue = new ArrayDeque<>();
queue.offer(new int[]{r, c});
grid[r][c] = '0'; // mark when enqueued, not when polled
while (!queue.isEmpty()) {
int[] cell = queue.poll();
for (int[] d : DIRS) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '1') {
grid[nr][nc] = '0';
queue.offer(new int[]{nr, nc});
}
}
}
}
}
return count;
}
static char[][] grid(String... rows) {
char[][] g = new char[rows.length][];
for (int i = 0; i < rows.length; i++) g[i] = rows[i].toCharArray();
return g;
}
static void check(Object expected, Object actual) {
String e = String.valueOf(expected), a = String.valueOf(actual);
System.out.println((e.equals(a) ? "OK " : "FAIL ") + "expected " + e + ", got " + a);
}
public static void main(String[] args) {
check(1, numIslands(grid("11110", "11010", "11000", "00000")));
check(3, numIslands(grid("11000", "11000", "00100", "00011")));
check(2, numIslands(grid("10", "01"))); // diagonal cells are two islands
check(0, numIslands(grid("000")));
}
}
Lời giải sửa thẳng vào grid. Nếu đề không cho sửa đầu vào thì dùng boolean[][] visited, và nói rõ với người phỏng vấn.
Độ phức tạp: O(R·C) thời gian và bộ nhớ.
Edge case: lưới rỗng; toàn nước; hai ô chéo nhau là hai đảo.
Đề: lưới n×n gồm 0 (đi được) và 1 (chặn). Tìm số ô trên đường ngắn nhất từ góc trên trái tới góc dưới phải, đi 8 hướng; không có thì trả -1.
Ý tưởng: mọi bước có giá như nhau, nên BFS theo tầng: lần đầu chạm đích là đường ngắn nhất.
import java.util.*;
public class Main {
static int shortestPathBinaryMatrix(int[][] grid) {
int n = grid.length;
if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) return -1;
Deque<int[]> queue = new ArrayDeque<>();
queue.offer(new int[]{0, 0});
grid[0][0] = 1; // visited
for (int dist = 1; !queue.isEmpty(); dist++) {
for (int size = queue.size(); size > 0; size--) {
int[] cell = queue.poll();
if (cell[0] == n - 1 && cell[1] == n - 1) return dist;
for (int dr = -1; dr <= 1; dr++) {
for (int dc = -1; dc <= 1; dc++) {
int r = cell[0] + dr, c = cell[1] + dc;
if (r >= 0 && r < n && c >= 0 && c < n && grid[r][c] == 0) {
grid[r][c] = 1;
queue.offer(new int[]{r, c});
}
}
}
}
}
return -1;
}
static void check(Object expected, Object actual) {
String e = String.valueOf(expected), a = String.valueOf(actual);
System.out.println((e.equals(a) ? "OK " : "FAIL ") + "expected " + e + ", got " + a);
}
public static void main(String[] args) {
check(2, shortestPathBinaryMatrix(new int[][]{{0, 1}, {1, 0}}));
check(4, shortestPathBinaryMatrix(new int[][]{{0, 0, 0}, {1, 1, 0}, {1, 1, 0}}));
check(-1, shortestPathBinaryMatrix(new int[][]{{1, 0, 0}, {1, 1, 0}, {1, 1, 0}}));
check(1, shortestPathBinaryMatrix(new int[][]{{0}}));
}
}
Độ phức tạp: O(n²) thời gian và bộ nhớ.
Edge case: ô đầu hoặc cuối bị chặn; lưới 1×1 (đáp án 1).
Ý chính: topological sort xếp các đỉnh của đồ thị có hướng sao cho mọi cạnh u → v có u đứng trước v. Chỉ làm được khi không có chu trình (DAG), nên nó cũng dùng để phát hiện chu trình.
Thuật toán Kahn: đếm số cạnh đi vào (in-degree) mỗi đỉnh, cho các đỉnh in-degree 0 vào queue, lấy từng đỉnh ra và giảm in-degree các đỉnh nó trỏ tới.
Đề: n môn, cặp {a, b} nghĩa là học b trước a. Trả về một thứ tự học hết các môn, hoặc mảng rỗng nếu không thể.
import java.util.*;
public class Main {
static int[] findOrder(int numCourses, int[][] prerequisites) {
List<List<Integer>> next = new ArrayList<>();
for (int i = 0; i < numCourses; i++) next.add(new ArrayList<>());
int[] indegree = new int[numCourses];
for (int[] p : prerequisites) { // p = {course, prerequisite}
next.get(p[1]).add(p[0]);
indegree[p[0]]++;
}
Deque<Integer> ready = new ArrayDeque<>();
for (int i = 0; i < numCourses; i++) if (indegree[i] == 0) ready.offer(i);
int[] order = new int[numCourses];
int taken = 0;
while (!ready.isEmpty()) {
int course = ready.poll();
order[taken++] = course;
for (int after : next.get(course)) {
if (--indegree[after] == 0) ready.offer(after);
}
}
return taken == numCourses ? order : new int[0]; // fewer => there is a cycle
}
static void check(Object expected, Object actual) {
String e = String.valueOf(expected), a = String.valueOf(actual);
System.out.println((e.equals(a) ? "OK " : "FAIL ") + "expected " + e + ", got " + a);
}
public static void main(String[] args) {
check("[0, 1, 2, 3]", Arrays.toString(findOrder(4, new int[][]{{1, 0}, {2, 0}, {3, 1}, {3, 2}})));
check("[]", Arrays.toString(findOrder(2, new int[][]{{1, 0}, {0, 1}}))); // cycle
check("[]", Arrays.toString(findOrder(1, new int[][]{{0, 0}}))); // self-dependency
}
}
Độ phức tạp: O(V + E) thời gian và bộ nhớ.
Edge case: không có điều kiện nào; chu trình hai môn; môn tự phụ thuộc {0, 0}.
Ý chính: cạnh có trọng số không âm thì Dijkstra luôn mở rộng đỉnh có khoảng cách tạm nhỏ nhất, lấy bằng min-heap. PriorityQueue không “giảm khoá” được, nên ta đẩy bản ghi mới và bỏ qua bản ghi cũ khi lấy ra.
Đề: mạng n nút (1..n), cạnh có hướng {u, v, w}: tín hiệu từ u tới v mất w. Phát từ nút k; trả về thời gian để mọi nút nhận được, hoặc -1 nếu có nút không nhận được.
Ý tưởng: Dijkstra từ k, đáp án là khoảng cách lớn nhất.
import java.util.*;
public class Main {
static int networkDelayTime(int[][] times, int n, int k) {
List<List<int[]>> adj = new ArrayList<>();
for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
for (int[] t : times) adj.get(t[0]).add(new int[]{t[1], t[2]}); // u -> (v, w)
int[] dist = new int[n + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[k] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1])); // (node, dist)
pq.offer(new int[]{k, 0});
while (!pq.isEmpty()) {
int[] top = pq.poll();
int u = top[0], d = top[1];
if (d > dist[u]) continue; // stale entry, a shorter path was found
for (int[] edge : adj.get(u)) {
int v = edge[0], nd = d + edge[1];
if (nd < dist[v]) {
dist[v] = nd;
pq.offer(new int[]{v, nd});
}
}
}
int worst = 0;
for (int i = 1; i <= n; i++) {
if (dist[i] == Integer.MAX_VALUE) return -1;
worst = Math.max(worst, dist[i]);
}
return worst;
}
static void check(Object expected, Object actual) {
String e = String.valueOf(expected), a = String.valueOf(actual);
System.out.println((e.equals(a) ? "OK " : "FAIL ") + "expected " + e + ", got " + a);
}
public static void main(String[] args) {
check(2, networkDelayTime(new int[][]{{2, 1, 1}, {2, 3, 1}, {3, 4, 1}}, 4, 2));
check(-1, networkDelayTime(new int[][]{{1, 2, 1}}, 2, 2));
// the detour 1->3->4->2 (cost 3) beats the direct edge 1->2 (cost 10)
check(3, networkDelayTime(new int[][]{{1, 2, 10}, {1, 3, 1}, {3, 4, 1}, {4, 2, 1}}, 4, 1));
}
}
Test có một trường hợp đi đường vòng ba cạnh (tổng 3) rẻ hơn cạnh thẳng (10): đó là chỗ BFS thường sẽ sai.
Độ phức tạp: O(E log V) thời gian, O(V + E) bộ nhớ.
Edge case: nút không tới được; chỉ một nút.
Ý chính: union-find (disjoint set union) giữ các nhóm rời nhau, mỗi nhóm là một cây có gốc đại diện; find tìm gốc, union nối hai gốc. Có nén đường đi và gộp theo hạng thì mỗi thao tác gần như O(1) (chính xác là O(α(n)), α tăng cực chậm).
Đề: một cây n đỉnh bị thêm đúng một cạnh nên có chu trình. Cho danh sách cạnh, trả về cạnh mà bỏ đi thì còn lại một cây (nếu nhiều, lấy cạnh xuất hiện sau cùng).
Ý tưởng: thêm từng cạnh vào union-find; cạnh đầu tiên có hai đầu đã cùng nhóm là cạnh khép chu trình.
import java.util.*;
public class Main {
static class UnionFind {
private final int[] parent, rank;
UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]]; // path halving
x = parent[x];
}
return x;
}
boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false; // already connected
if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
parent[rb] = ra; // attach the shorter tree under the taller
if (rank[ra] == rank[rb]) rank[ra]++;
return true;
}
}
static int[] findRedundantConnection(int[][] edges) {
UnionFind uf = new UnionFind(edges.length + 1);
for (int[] e : edges) if (!uf.union(e[0], e[1])) return e;
return new int[0];
}
static void check(Object expected, Object actual) {
String e = String.valueOf(expected), a = String.valueOf(actual);
System.out.println((e.equals(a) ? "OK " : "FAIL ") + "expected " + e + ", got " + a);
}
public static void main(String[] args) {
check("[2, 3]", Arrays.toString(findRedundantConnection(new int[][]{{1, 2}, {1, 3}, {2, 3}})));
check("[1, 4]", Arrays.toString(findRedundantConnection(new int[][]{{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 5}})));
}
}
find ở đây dùng “path halving” (trỏ mỗi nút lên ông của nó), một dạng nén đường đi không cần đệ quy.
Độ phức tạp: O(E·α(V)), coi như O(E).
Edge case: đỉnh đánh số từ 1 nên mảng cần n + 1 ô.
Ý chính: dùng quy hoạch động (DP) khi đề hỏi số cách, min/max hoặc có làm được không, và mỗi lựa chọn chỉ phụ thuộc kết quả của các bài con nhỏ hơn. Quy trình: định nghĩa dp[...] bằng một câu, viết công thức chuyển, chọn base case, chọn thứ tự điền.
Memo top-down (đệ quy, nhớ kết quả) dễ viết; bảng bottom-up (vòng lặp) không tràn stack, hay rút gọn được bộ nhớ. So sánh chi tiết ở bài thực hành đệ quy.
| Bài | Trạng thái dp |
Công thức chuyển |
|---|---|---|
| Leo cầu thang | ways[i]: số cách tới bậc i |
ways[i-1] + ways[i-2] |
| Đổi tiền | dp[a]: ít đồng nhất để ra a |
min(dp[a - c] + 1) |
| LIS | dp[i]: dãy tăng dài nhất kết thúc ở i |
max(dp[j] + 1) với nums[j] < nums[i] |
| LCS | dp[i][j]: LCS của a[0..i), b[0..j) |
khớp: chéo + 1; không: max hai ô |
| Knapsack 0/1 | dp[c]: giá trị lớn nhất, sức chứa c |
max(dp[c], dp[c - w] + v), c giảm dần |
| Edit distance | dp[i][j]: số phép sửa a[0..i) thành b[0..j) |
khớp: chéo; không: 1 + min ba ô |
Đề: mỗi bước leo 1 hoặc 2 bậc; có bao nhiêu cách leo tới bậc n?
Ý tưởng: bước cuối là 1 bậc (từ n-1) hoặc 2 bậc (từ n-2), nên đây là Fibonacci; chỉ giữ hai số gần nhất.
import java.util.*;
public class Main {
static int climbStairs(int n) {
int prev = 1, cur = 1; // ways(0), ways(1)
for (int i = 2; i <= n; i++) {
int next = prev + cur;
prev = cur;
cur = next;
}
return cur;
}
static void check(Object expected, Object actual) {
String e = String.valueOf(expected), a = String.valueOf(actual);
System.out.println((e.equals(a) ? "OK " : "FAIL ") + "expected " + e + ", got " + a);
}
public static void main(String[] args) {
check(1, climbStairs(1));
check(8, climbStairs(5));
check(1836311903, climbStairs(45));
}
}
Độ phức tạp: O(n), O(1) bộ nhớ. Edge case: n = 1; n = 45 vừa int (1.836.311.903), lớn hơn cần long.
Đề: cho các mệnh giá (dùng không giới hạn) và số tiền amount, tìm số đồng ít nhất để ra đúng số tiền, hoặc -1.
Ý tưởng: đồng cuối là một mệnh giá c, phần còn lại a - c phải dùng ít đồng nhất. “Vô cực” là amount + 1 để +1 không tràn số.
import java.util.*;
public class Main {
static int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1]; // dp[a] = fewest coins for amount a
Arrays.fill(dp, amount + 1); // "infinity" that cannot overflow
dp[0] = 0;
for (int a = 1; a <= amount; a++) {
for (int c : coins) {
if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
static void check(Object expected, Object actual) {
String e = String.valueOf(expected), a = String.valueOf(actual);
System.out.println((e.equals(a) ? "OK " : "FAIL ") + "expected " + e + ", got " + a);
}
public static void main(String[] args) {
check(3, coinChange(new int[]{1, 2, 5}, 11));
check(-1, coinChange(new int[]{2}, 3));
check(0, coinChange(new int[]{1}, 0));
check(2, coinChange(new int[]{1, 3, 4}, 6)); // greedy would give 3
}
}
import java.util.*;
public class Main {
static int coinChangeMemo(int[] coins, int amount) {
int[] memo = new int[amount + 1];
Arrays.fill(memo, -2); // -2 = not computed yet
return minCoins(coins, amount, memo);
}
private static int minCoins(int[] coins, int rest, int[] memo) {
if (rest == 0) return 0;
if (memo[rest] != -2) return memo[rest];
int best = Integer.MAX_VALUE;
for (int c : coins) {
if (c > rest) continue;
int sub = minCoins(coins, rest - c, memo);
if (sub >= 0) best = Math.min(best, sub + 1);
}
return memo[rest] = (best == Integer.MAX_VALUE ? -1 : best);
}
static void check(Object expected, Object actual) {
String e = String.valueOf(expected), a = String.valueOf(actual);
System.out.println((e.equals(a) ? "OK " : "FAIL ") + "expected " + e + ", got " + a);
}
public static void main(String[] args) {
check(3, coinChangeMemo(new int[]{1, 2, 5}, 11));
check(-1, coinChangeMemo(new int[]{2}, 3));
check(2, coinChangeMemo(new int[]{1, 3, 4}, 6));
}
}
Phải phân biệt “chưa tính” (-2) với “không thể” (-1), nếu không các trạng thái không thể sẽ bị tính lại mãi. Với amount lớn (cỡ 10⁵ với đồng 1), độ sâu đệ quy bằng amount và dễ tràn stack: lý do bản bottom-up là lựa chọn mặc định.
Độ phức tạp: O(amount · k) với k loại tiền, O(amount) bộ nhớ. Edge case: amount = 0 trả 0; [2] với 3 trả -1.
Đề: tìm độ dài dãy con tăng ngặt dài nhất của một mảng (dãy con giữ thứ tự, không cần liền nhau).
Ý tưởng: bản O(n²) theo bảng trên. Bản O(n log n): tails[len - 1] = phần tử cuối nhỏ nhất của dãy tăng dài len; số mới tìm nhị phân chỗ thay.
import java.util.*;
public class Main {
static int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length]; // tails[len-1] = smallest tail of an increasing run of length len
int size = 0;
for (int x : nums) {
int lo = 0, hi = size;
while (lo < hi) { // first tail >= x
int mid = (lo + hi) >>> 1;
if (tails[mid] < x) lo = mid + 1; else hi = mid;
}
tails[lo] = x;
if (lo == size) size++;
}
return size;
}
static void check(Object expected, Object actual) {
String e = String.valueOf(expected), a = String.valueOf(actual);
System.out.println((e.equals(a) ? "OK " : "FAIL ") + "expected " + e + ", got " + a);
}
public static void main(String[] args) {
check(4, lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18}));
check(1, lengthOfLIS(new int[]{7, 7, 7, 7}));
check(0, lengthOfLIS(new int[]{}));
}
}
import java.util.*;
public class Main {
static int lisQuadratic(int[] nums) {
int[] dp = new int[nums.length]; // dp[i] = LIS ending at i
int best = 0;
for (int i = 0; i < nums.length; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
best = Math.max(best, dp[i]);
}
return best;
}
static void check(Object expected, Object actual) {
String e = String.valueOf(expected), a = String.valueOf(actual);
System.out.println((e.equals(a) ? "OK " : "FAIL ") + "expected " + e + ", got " + a);
}
public static void main(String[] args) {
check(4, lisQuadratic(new int[]{0, 1, 0, 3, 2, 3}));
check(4, lisQuadratic(new int[]{10, 9, 2, 5, 3, 7, 101, 18}));
check(1, lisQuadratic(new int[]{7, 7, 7, 7}));
}
}
Mình chạy cả hai bản trên 500 mảng ngẫu nhiên (độ dài 0 tới 29, giá trị -20 tới 19, có nhiều số trùng): kết quả khớp hết. Lưu ý tails không phải là một dãy tăng thật trong mảng, chỉ có độ dài là đúng. Tìm nhị phân “phần tử đầu tiên ≥ x” là biến thể lower bound ở bài tìm kiếm nhị phân.
Độ phức tạp: O(n log n) thời gian, O(n) bộ nhớ. Edge case: mảng rỗng (0); toàn số bằng nhau (1, vì phải tăng ngặt).
Đề: cho hai chuỗi, tìm độ dài dãy con chung dài nhất (LCS).
Ý tưởng: xét ký tự cuối của hai tiền tố: khớp thì cùng góp vào LCS, không khớp thì bỏ ký tự cuối của một trong hai chuỗi.
import java.util.*;
public class Main {
static int longestCommonSubsequence(String a, String b) {
int m = a.length(), n = b.length();
int[][] dp = new int[m + 1][n + 1]; // dp[i][j] = LCS of a[0..i) and b[0..j)
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = a.charAt(i - 1) == b.charAt(j - 1)
? dp[i - 1][j - 1] + 1
: Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[m][n];
}
static void check(Object expected, Object actual) {
String e = String.valueOf(expected), a = String.valueOf(actual);
System.out.println((e.equals(a) ? "OK " : "FAIL ") + "expected " + e + ", got " + a);
}
public static void main(String[] args) {
check(3, longestCommonSubsequence("abcde", "ace"));
check(0, longestCommonSubsequence("abc", "def"));
check(0, longestCommonSubsequence("", "abc"));
}
}
Độ phức tạp: O(m·n); chỉ cần độ dài thì giữ hai hàng, bộ nhớ O(n). Edge case: chuỗi rỗng; không có ký tự chung.
Đề: (a) knapsack 0/1: mỗi món có khối lượng, giá trị, lấy tối đa một lần; tìm giá trị lớn nhất với sức chứa C. (b) mảng số dương có chia được thành hai phần tổng bằng nhau không.
Ý tưởng: với mỗi món, duyệt c từ lớn về nhỏ để dp[c - w] vẫn là giá trị trước khi xét món này. Bài (b) là knapsack hỏi “có đạt đúng tổng/2 không”.
import java.util.*;
public class Main {
static int knapsack(int[] weight, int[] value, int capacity) {
int[] dp = new int[capacity + 1]; // dp[c] = best value with capacity c
for (int i = 0; i < weight.length; i++) {
for (int c = capacity; c >= weight[i]; c--) { // backwards: each item used at most once
dp[c] = Math.max(dp[c], dp[c - weight[i]] + value[i]);
}
}
return dp[capacity];
}
static void check(Object expected, Object actual) {
String e = String.valueOf(expected), a = String.valueOf(actual);
System.out.println((e.equals(a) ? "OK " : "FAIL ") + "expected " + e + ", got " + a);
}
public static void main(String[] args) {
check(9, knapsack(new int[]{1, 3, 4, 5}, new int[]{1, 4, 5, 7}, 7));
check(0, knapsack(new int[]{5}, new int[]{10}, 4));
check(10, knapsack(new int[]{2}, new int[]{10}, 4)); // the item is taken once, not twice
}
}
import java.util.*;
public class Main {
static boolean canPartition(int[] nums) {
int sum = Arrays.stream(nums).sum();
if (sum % 2 == 1) return false;
int target = sum / 2;
boolean[] reach = new boolean[target + 1];
reach[0] = true;
for (int x : nums) {
for (int s = target; s >= x; s--) reach[s] |= reach[s - x];
}
return reach[target];
}
static void check(Object expected, Object actual) {
String e = String.valueOf(expected), a = String.valueOf(actual);
System.out.println((e.equals(a) ? "OK " : "FAIL ") + "expected " + e + ", got " + a);
}
public static void main(String[] args) {
check(true, canPartition(new int[]{1, 5, 11, 5}));
check(false, canPartition(new int[]{1, 2, 3, 5}));
}
}
reach[s] = có chọn được một tập con tổng đúng bằng s không. Tổng lẻ thì trả false ngay.
Độ phức tạp: O(n·C) thời gian, O(C) bộ nhớ: “pseudo-polynomial”, C cỡ 10⁹ thì không dùng được. Edge case: không món nào vừa.
Đề: cho hai chuỗi, tìm số phép tối thiểu (chèn, xoá, thay một ký tự) để biến chuỗi thứ nhất thành chuỗi thứ hai.
Ý tưởng: ký tự cuối khớp thì không tốn gì; không khớp thì 1 + nhỏ nhất của thay (chéo), xoá (trên), chèn (trái). Base case: tiền tố dài i thành chuỗi rỗng tốn i phép xoá.
import java.util.*;
public class Main {
static int minDistance(String a, String b) {
int m = a.length(), n = b.length();
int[][] dp = new int[m + 1][n + 1]; // dp[i][j] = edits to turn a[0..i) into b[0..j)
for (int i = 0; i <= m; i++) dp[i][0] = i; // delete everything
for (int j = 0; j <= n; j++) dp[0][j] = j; // insert everything
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], // replace
Math.min(dp[i - 1][j], dp[i][j - 1])); // delete, insert
}
}
return dp[m][n];
}
static void check(Object expected, Object actual) {
String e = String.valueOf(expected), a = String.valueOf(actual);
System.out.println((e.equals(a) ? "OK " : "FAIL ") + "expected " + e + ", got " + a);
}
public static void main(String[] args) {
check(3, minDistance("horse", "ros"));
check(5, minDistance("intention", "execution"));
check(3, minDistance("", "abc"));
check(0, minDistance("abc", "abc"));
}
}
Kết quả test: horse → ros = 3, intention → execution = 5, "" → abc = 3, hai chuỗi giống nhau = 0.
Độ phức tạp: O(m·n) thời gian, bộ nhớ rút được về O(n). Dùng trong gợi ý sửa chính tả, tìm kiếm mờ.
Ý chính: tìm tín hiệu, chọn kỹ thuật, nói độ phức tạp trước khi code.
| Tín hiệu trong đề | Kỹ thuật | Độ phức tạp điển hình |
|---|---|---|
| Thông tin cả cây (cao, đường kính, LCA) | đệ quy “hỏi hai con” | O(n) |
| Theo tầng; ngắn nhất, không trọng số | BFS | O(V + E) |
| Lưới, đếm vùng, loang | BFS/DFS trên lưới | O(R·C) |
| Thứ tự có phụ thuộc; chu trình có hướng | topological sort | O(V + E) |
| Ngắn nhất, trọng số không âm | Dijkstra + heap | O(E log V) |
| “Cùng nhóm không”, cạnh thêm dần | union-find | gần O(1) |
| K lớn nhất, gộp K dãy | heap cỡ K | O(n log K) |
| Median của luồng | hai heap | O(log n) |
| Lân cận ≤ x, ≥ x, tập thay đổi | TreeMap |
O(log n) |
| Số cách, min/max, bài con lặp | quy hoạch động | số trạng thái × chi phí |
| Hai chuỗi, so khớp tiền tố | DP hai chiều | O(m·n) |
| Chọn hoặc bỏ món, giới hạn tổng | knapsack | O(n · C) |
Đề: lưới 0 (trống), 1 (cam tươi), 2 (cam thối). Mỗi phút, cam thối làm thối cam tươi kề cạnh. Trả về số phút tới khi hết cam tươi, hoặc -1.
Cho tất cả cam thối vào queue ngay từ đầu (BFS nhiều nguồn), mỗi tầng BFS là một phút. Đếm số cam tươi để biết khi nào xong và phát hiện cam không bao giờ bị lan tới.
import java.util.*;
public class Main {
static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
static int orangesRotting(int[][] grid) {
int rows = grid.length, cols = grid[0].length, fresh = 0;
Deque<int[]> queue = new ArrayDeque<>();
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++) {
if (grid[r][c] == 2) queue.offer(new int[]{r, c}); // every rotten orange is a source
else if (grid[r][c] == 1) fresh++;
}
int minutes = 0;
while (fresh > 0 && !queue.isEmpty()) {
for (int size = queue.size(); size > 0; size--) {
int[] cell = queue.poll();
for (int[] d : DIRS) {
int r = cell[0] + d[0], c = cell[1] + d[1];
if (r >= 0 && r < rows && c >= 0 && c < cols && grid[r][c] == 1) {
grid[r][c] = 2;
fresh--;
queue.offer(new int[]{r, c});
}
}
}
minutes++;
}
return fresh == 0 ? minutes : -1;
}
static void check(Object expected, Object actual) {
String e = String.valueOf(expected), a = String.valueOf(actual);
System.out.println((e.equals(a) ? "OK " : "FAIL ") + "expected " + e + ", got " + a);
}
public static void main(String[] args) {
check(4, orangesRotting(new int[][]{{2, 1, 1}, {1, 1, 0}, {0, 1, 1}}));
check(-1, orangesRotting(new int[][]{{2, 1, 1}, {0, 1, 1}, {1, 0, 1}}));
check(0, orangesRotting(new int[][]{{0, 2}}));
}
}
O(R·C). Edge case: không có cam tươi (0 phút), có cam tươi nhưng không có cam thối (-1).
Đề: mỗi nhà trên dãy phố có một số tiền; không được lấy hai nhà kề nhau. Tìm tổng lớn nhất.
Ở mỗi nhà chỉ có hai trạng thái: lấy hoặc bỏ. Lấy nhà này thì nhà trước phải bỏ; bỏ nhà này thì lấy tốt nhất của hai trạng thái trước.
import java.util.*;
public class Main {
static int rob(int[] nums) {
int skip = 0, take = 0; // best so far if we skipped / took the previous house
for (int x : nums) {
int newTake = skip + x;
skip = Math.max(skip, take);
take = newTake;
}
return Math.max(skip, take);
}
static void check(Object expected, Object actual) {
String e = String.valueOf(expected), a = String.valueOf(actual);
System.out.println((e.equals(a) ? "OK " : "FAIL ") + "expected " + e + ", got " + a);
}
public static void main(String[] args) {
check(4, rob(new int[]{1, 2, 3, 1}));
check(12, rob(new int[]{2, 7, 9, 3, 1}));
check(0, rob(new int[]{}));
}
}
O(n) thời gian, O(1) bộ nhớ. [1, 2, 3, 1] ra 4, [2, 7, 9, 3, 1] ra 12, mảng rỗng ra 0.
Mọi lời giải nằm trong một file GraphsDp.java có hàm main tự kiểm tra, chạy bằng java GraphsDp.java trên JDK 21. Kết quả: passed=55 failed=0.
{1, 3, 4} → 6 (phản ví dụ tham lam); LIS hai bản khớp trên 500 mảng ngẫu nhiên; LCS; knapsack và bài chia mảng; edit distance bốn ca.StackOverflowError, 1000×1000 chạy với -Xss64m.dp[...] bằng một câu cho cả sáu bài DP.Vì BFS thăm đỉnh theo đúng thứ tự khoảng cách: hết các đỉnh cách 1 cạnh, rồi tới 2 cạnh, nên lần đầu gặp đích là qua ít cạnh nhất.
DFS đi sâu theo một nhánh, có thể tới đích bằng đường vòng rất dài trước khi thử đường ngắn. Muốn DFS ra đường ngắn nhất thì phải thử mọi đường, tốn hàm mũ.
Hầu hết dùng danh sách kề: bộ nhớ O(V + E) và duyệt hàng xóm đúng bằng số hàng xóm. Ma trận kề chỉ đáng khi đồ thị dày và V nhỏ.
Ma trận tốn O(V²): một triệu đỉnh là 10¹² ô, không thể. Đổi lại, nó trả lời “u nối v không” trong O(1).
Chạy Kahn: nếu số đỉnh lấy ra ít hơn V thì có chu trình. Hoặc DFS ba màu: gặp lại một đỉnh đang “xám” (đang nằm trên đường đi hiện tại) là có chu trình.
Với đồ thị vô hướng thì đơn giản hơn: union-find, hoặc DFS gặp một đỉnh đã thăm mà không phải cha trực tiếp.
Hai dấu hiệu: đề hỏi số cách, min/max hoặc có làm được không; và lời giải ngây thơ bằng đệ quy gọi lại cùng một bài con nhiều lần.
Cách làm: viết đệ quy vét cạn trước, xem tham số nào xác định một bài con (đó là trạng thái), thêm memo. Sau đó, nếu cần, chuyển sang bảng bottom-up và rút gọn bộ nhớ. Nếu một lựa chọn cục bộ luôn đúng (có chứng minh) thì đó là tham lam, không cần DP.
O(E log V). PriorityQueue không cập nhật được khoá của phần tử đã có, nên ta đẩy bản ghi mới mỗi khi tìm được đường ngắn hơn, và khi lấy ra một bản ghi có khoảng cách lớn hơn dist hiện tại thì bỏ qua.
Không có dòng đó, kết quả vẫn đúng nhưng mỗi bản ghi cũ lại duyệt hết hàng xóm một lần nữa, tốn thêm thời gian. Gọi remove(o) để xoá bản ghi cũ thì O(n) mỗi lần, còn tệ hơn.
Hai tối ưu: nén đường đi (khi find, trỏ các nút thẳng lên gốc) và gộp theo hạng hoặc kích thước (nối cây thấp vào cây cao). Cùng nhau cho O(α(n)) mỗi thao tác, coi như hằng số.
Chỉ một trong hai cũng đã cho O(log n) mỗi thao tác. Ứng dụng thật: Kruskal tìm cây khung nhỏ nhất, gom nhóm tài khoản trùng nhau theo email hoặc số điện thoại, phát hiện vòng khi thêm cạnh.
Ở mọi chỗ có “việc này phải chạy sau việc kia”: thứ tự build module (Maven reactor), thứ tự khởi tạo bean trong Spring, các DAG trong scheduler như Airflow, thứ tự tạo bảng có khoá ngoại.
Điều quan trọng khi thiết kế: phát hiện chu trình và báo lỗi rõ ràng (Spring báo vòng phụ thuộc khi khởi động), và tận dụng các đỉnh in-degree 0 cùng lúc để chạy song song.
Bảng 10¹⁰ ô không thể vừa bộ nhớ, và 10¹⁰ phép tính mất cỡ 100 giây (ước lượng 10⁸ phép mỗi giây). Chỉ cần độ dài thì giữ hai hàng, bộ nhớ O(n); cần cả lời giải thì dùng chia để trị (Hirschberg).
Trong thực tế, công cụ diff dùng thuật toán Myers, O((m + n)·D) với D là số khác biệt, rất nhanh khi hai file giống nhau nhiều. Cũng có thể chặn trước: chỉ tính trong dải quanh đường chéo khi chỉ quan tâm khoảng cách ≤ k.
| Term | Phát âm | Nghĩa | Ví dụ câu tiếng Anh dùng trong phỏng vấn |
|---|---|---|---|
| adjacency list | /əˈdʒeɪ.sən.si lɪst/ | danh sách kề | “I’d store the graph as an adjacency list since it’s sparse.” |
| breadth-first search | /bredθ fɝːst sɝːtʃ/ | tìm kiếm theo chiều rộng | “Breadth-first search gives the shortest path in an unweighted graph.” |
| in-degree | /ˈɪn dɪˌɡriː/ | số cạnh đi vào | “Nodes with in-degree zero can start right away.” |
| topological order | /ˌtɑː.pəˈlɑː.dʒɪ.kəl ˈɔːr.dɚ/ | thứ tự tô-pô | “If I can’t place every node in topological order, there’s a cycle.” |
| disjoint set | /dɪsˈdʒɔɪnt set/ | tập rời nhau | “A disjoint set union answers connectivity queries almost in constant time.” |
| path compression | /pæθ kəmˈpreʃ.ən/ | nén đường đi | “Path compression flattens the tree during find.” |
| stale entry | /steɪl ˈen.tri/ | bản ghi cũ | “I skip stale entries instead of decreasing keys.” |
| overlapping subproblems | /ˌoʊ.vɚˈlæp.ɪŋ ˈsʌbˌprɑː.bləmz/ | bài con lặp lại | “Overlapping subproblems are the signal for dynamic programming.” |
Ghi chép tự tổng hợp từ tài liệu chính thức và kinh nghiệm thực tế.