Đến nội dung chính
Sổ ôn Backend

Tìm kiếm

Cấu trúc dữ liệu & Thuật toánMid34 phút đọc

Luyện phỏng vấn: đồ thị và quy hoạch động trong Java

Ôn 14 thẻ
Trong bài này

Cả bài trong một trang: ý chính, sơ đồ, điểm phỏng vấn.

Luyện phỏng vấn: đồ thị và quy hoạch động trong Java

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ỏ

2BFS, DFS và Dijkstra

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)"]

3Topological sort và union-find

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).

  • Kahn: đỉnh in-degree 0 vào queue, giảm in-degree đỉnh kề
  • Union-find: nén đường đi + gộp theo hạng
  • Cạnh nối hai đỉnh đã cùng nhóm là cạnh khép chu trình

4Quy hoạch động

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

5Knapsack 0/1 cho đúng

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.

⚠️ 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"]

1. Biểu diễn đồ thị, BFS và DFS

Ý 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.

1.1. Đếm số đảo (tương tự LeetCode 200)

Đề: 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'.

Lời giải đếm số đảo bằng BFS
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.

1.2. Đường ngắn nhất trong ma trận nhị phân (tương tự LeetCode 1091)

Đề: 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.

Lời giải BFS trên lưới 8 hướng
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).

2. Topological sort: thứ tự có phụ thuộc

Ý 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.

2.1. Thứ tự học các môn (tương tự LeetCode 207, 210)

Đề: 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}.

3. Đường đi ngắn nhất có trọng số: Dijkstra

Ý 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.

3.1. Thời gian lan tín hiệu trong mạng (tương tự LeetCode 743)

Đề: 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.

Lời giải Dijkstra với PriorityQueue
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.

4. Union-find: gộp nhóm dần dần

Ý 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).

4.1. Cạnh thừa tạo chu trình (tương tự LeetCode 684)

Đề: 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.

Lời giải union-find với nén đường đi và gộp theo hạng
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 ô.

5. Quy hoạch động

Ý 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 ô

5.1. Leo cầu thang (tương tự LeetCode 70)

Đề: 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.

5.2. Đổi tiền ít đồng nhất (tương tự LeetCode 322)

Đề: 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
    }
}
Cùng bài, viết kiểu memo top-down
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.

5.3. Dãy con tăng dài nhất (tương tự LeetCode 300)

Đề: 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[]{}));
    }
}
Bản O(n²) và cách kiểm chứng hai bản khớp nhau
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).

5.4. Dãy con chung dài nhất (tương tự LeetCode 1143)

Đề: 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.

5.5. Knapsack 0/1 và chia mảng thành hai nửa bằng nhau (tương tự LeetCode 416)

Đề: (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
    }
}
Lời giải chia mảng thành hai nửa bằng nhau
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.

5.6. Khoảng cách chỉnh sửa (tương tự LeetCode 72)

Đề: 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á.

Lời giải edit distance
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ờ.

6. Bảng nhận dạng pattern

Ý 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)

Bài tập

Bài 1: Cam thối lan (tương tự LeetCode 994)

Đề: 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.

Lời giải Bài 1: BFS nhiều nguồn

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).

Bài 2: Trộm nhà dọc phố (tương tự LeetCode 198)

Đề: 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.

Lời giải Bài 2: DP hai trạng thái

Ở 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.

Cách mình chạy thử tất cả lời giải

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.

  • Đảo: ví dụ 1 đảo và 3 đảo, toàn nước, hai ô chéo (2 đảo), lưới 1000×1000 toàn đất (1 đảo, không tràn stack với BFS).
  • Môn học: kiểm tra thứ tự trả về thoả mọi điều kiện thay vì so mảng cố định; chu trình hai môn; không điều kiện; tự phụ thuộc.
  • BFS lưới: 2×2 chéo (2), đường vòng 3×3 (4), ô đầu bị chặn, 1×1, không có đường.
  • Dijkstra: ví dụ cơ bản (2), nút không tới được (-1), đường vòng ba cạnh rẻ hơn cạnh thẳng (3), một nút (0).
  • Union-find: chu trình tam giác, chu trình ở giữa danh sách.
  • DP: cầu thang 1, 2, 5, 45; đổi tiền cả hai bản với {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.
  • Đo riêng giới hạn stack của DFS đệ quy trên lưới toàn đất: 100×100 chạy, 300×300 StackOverflowError, 1000×1000 chạy với -Xss64m.

Ghi nhớ

  • Giải thích được vì sao BFS cho đường ngắn nhất khi không có trọng số, và khi nào phải đổi sang Dijkstra.
  • Viết được Kahn và biết dùng nó để phát hiện chu trình.
  • Viết được union-find có nén đường đi và gộp theo hạng.
  • Định nghĩa được dp[...] bằng một câu cho cả sáu bài DP.
  • Nói được kỹ thuật và độ phức tạp cho một đề mới nhờ bảng pattern.

Câu hỏi phỏng vấn

Junior

Vì sao BFS tìm được đường ngắn nhất trên đồ thị không trọng số còn DFS thì không?

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ũ.

Lưu đồ thị bằng danh sách kề hay ma trận kề?

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).

Mid

Phát hiện chu trình trong đồ thị có hướng thế nào?

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.

Làm sao nhận ra một bài là quy hoạch động?

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.

Dijkstra với PriorityQueue của Java: độ phức tạp, và vì sao cần dòng “bỏ qua bản ghi cũ”?

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.

Senior

Union-find tối ưu thế nào và độ phức tạp là bao nhiêu?

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.

Topological sort xuất hiện ở đâu trong hệ thống backend?

Ở 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.

LCS hay edit distance với hai chuỗi dài 100.000 ký tự: bảng m×n có vấn đề gì và xử lý ra sao?

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.

Từ vựng tiếng Anh

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ế.