14 dạng bài LeetCode hay gặp trong phỏng vấn

Pattern là công cụ nén kinh nghiệm

Một pattern gom nhiều bài có cùng cấu trúc quyết định. Nó giúp bạn không bắt đầu từ số 0, nhưng không tự giải đề. Từ “đoạn liên tiếp” có thể dẫn tới sliding window, prefix sum, Kadane hoặc binary search trên đáp án. Muốn chọn, phải hỏi số âm, tính đơn điệu, cần giá trị hay chỉ số, dữ liệu tĩnh hay cập nhật.

Học pattern hiệu quả bằng bốn mảnh: tín hiệu; bất biến; độ phức tạp; phản ví dụ. Nếu chỉ giữ template code, bạn dễ dùng window cho điều kiện không co được hoặc dùng greedy khi lựa chọn cục bộ phá tương lai.

1. Bảng băm

Dùng khi cần tra cứu “đã thấy chưa”, tần suất hoặc phần bù. Two Sum là mẫu điển hình. Cần hỏi có giữ chỉ số đầu tiên, có trùng, có yêu cầu thứ tự. Hash map trung bình O(1) nhưng tốn bộ nhớ và không mặc định giữ thứ tự.

2. Hai con trỏ

Phù hợp mảng đã sắp, cặp từ hai đầu hoặc thao tác in-place. Bất biến thường là vùng ngoài hai con trỏ đã được xử lý. Nếu dữ liệu chưa sắp mà cần chỉ số gốc, sort có thể làm mất thông tin hoặc thêm O(n log n).

3. Cửa sổ trượt

Tín hiệu là đoạn liên tiếp và điều kiện có thể cập nhật khi thêm/bỏ biên. Window cố định dùng một tổng hoặc tần suất; window biến đổi cần biết khi nào co. Nếu số âm làm tổng không đơn điệu, kỹ thuật hai biên cho “tổng ít nhất S” có thể sai.

4. Prefix sum

Dùng cho nhiều truy vấn tổng đoạn hoặc biến điều kiện đoạn thành hiệu hai tiền tố. Kết hợp hash map để đếm đoạn có tổng k, kể cả số âm. Nếu có cập nhật, prefix tĩnh không đủ; cân nhắc Fenwick hoặc Segment Tree.

5. Fast–slow pointers

Rùa–thỏ phát hiện chu trình và tìm điểm giữa linked list với O(1) bộ nhớ. Bất biến liên quan tốc độ tương đối. Đừng áp dụng trên cấu trúc không có phép “bước tiếp theo” xác định.

6. Stack và monotonic stack

Stack xử lý ngoặc, undo, nearest unmatched. Monotonic stack xử lý phần tử lớn/nhỏ gần nhất và histogram. Phải nói stack tăng hay giảm, và khi bằng nhau thì pop hay giữ; lựa chọn đó ảnh hưởng trùng.

7. Binary search

Không chỉ tìm trong mảng. Binary search cần một predicate đơn điệu: sai rồi đúng hoặc đúng rồi sai. Viết rõ biên nửa mở, ý nghĩa l/r và kiểm nghiệm có tồn tại. Tìm trên đáp án còn cần dựng hàm feasible(x) đúng.

8. Interval và sweep

Sort theo đầu trái để merge, chèn, chọn không giao; sweep biến đầu mút thành sự kiện. Quy tắc sự kiện cùng tọa độ phụ thuộc đoạn đóng/nửa mở. Đây là nơi một dấu < gây sai dù ý tưởng đúng.

9. Heap / Top-K

Heap hữu ích khi chỉ cần phần tốt nhất đang biến đổi: kth largest, merge k lists, lịch công việc. Nếu cần toàn bộ thứ tự một lần, sort thường đơn giản. Xác định min-heap hay max-heap và kích thước k.

10. Tree DFS/BFS

State thường gồm node và thông tin cha. DFS tự nhiên cho tổng hợp từ con; BFS cho lớp. Trên đồ thị tổng quát cần visited, trên cây có thể truyền parent. Đệ quy sâu có nguy cơ tràn stack.

11. Graph traversal và topo

BFS cho đường ngắn không trọng số; Dijkstra cho trọng số không âm; topo cho phụ thuộc DAG. Nếu đồ thị có chu trình, topo không đủ. Hỏi directed/undirected, nhiều thành phần, self-loop và multiple edges.

12. Backtracking

Sinh tổ hợp, hoán vị, phân hoạch khi không gian nhỏ và có thể cắt nhánh. Hợp đồng quan trọng là chọn–đệ quy–hoàn tác. Dữ liệu trùng cần sort/skip đúng tầng để tránh đáp án trùng.

13. Dynamic Programming

Nhận ra bài toán con lặp và lựa chọn cuối. Viết state bằng câu, transition, base, order. Không phải bài tối ưu nào cũng là DP; nếu greedy có exchange argument hoặc graph có thuật toán chuẩn, state lớn là dấu hiệu cần nghĩ lại.

14. Union-Find

Quản lý các thành phần khi cạnh được thêm, kiểm chu trình vô hướng, Kruskal. Path compression và union by size cho thời gian gần hằng số. DSU cơ bản không hỗ trợ xóa cạnh hoặc đường đi chi tiết.

Bảng phân biệt các mẫu dễ nhầm

Chạy tay cửa sổ không lặp

Với pwwkew, giữ l và vị trí cuối của mỗi ký tự. r=0 (p) cho độ dài 1; r=1 (w) cho 2; r=2 gặp lại w nên l nhảy tới 2; sau đó wke đạt 3; w cuối làm l nhảy qua w cũ. Đáp án 3, nhưng chuỗi kết quả không nhất thiết là prefix.

Điểm tinh tế: l = max(l, last[c]+1). Không dùng max, một ký tự xuất hiện trước cửa sổ hiện tại có thể kéo l lùi. Với abba, lỗi này thường lộ ra.

#include <algorithm>
#include <array>
#include <iostream>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    getline(cin, s);
    array<int, 256> last;
    last.fill(-1);
    int l = 0, best = 0;
    for (int r = 0; r < (int)s.size(); r++) {
        unsigned char c = s[r];
        l = max(l, last[c] + 1);
        last[c] = r;
        best = max(best, r - l + 1);
    }
    cout << best << '\n';
    return 0;
}

import sys


def length_of_longest_substring(s: str) -> int:
    last: dict[str, int] = {}
    left = best = 0
    for right, ch in enumerate(s):
        left = max(left, last.get(ch, -1) + 1)
        last[ch] = right
        best = max(best, right - left + 1)
    return best


def main() -> None:
    s = sys.stdin.readline().rstrip("\n")
    print(length_of_longest_substring(s))


if __name__ == "__main__":
    main()

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        if (s == null) s = "";
        Map<Character, Integer> last = new HashMap<>();
        int l = 0, best = 0;
        for (int r = 0; r < s.length(); r++) {
            char c = s.charAt(r);
            l = Math.max(l, last.getOrDefault(c, -1) + 1);
            last.put(c, r);
            best = Math.max(best, r - l + 1);
        }
        System.out.println(best);
    }
}

Code C++ mẫu dùng bảng 256 byte, phù hợp input byte/ASCII. Python và Java làm việc theo ký tự của ngôn ngữ; với Unicode phức tạp như grapheme cluster, hợp đồng phải đổi. Đây là ví dụ một template không tự xử lý mọi định nghĩa “ký tự”.

Cách học 14 mẫu mà không thuộc vẹt

Mỗi mẫu chọn ba bài: bài cơ chế, bài biến thể, bài dễ nhầm với mẫu khác. Với mỗi bài viết một thẻ gồm tín hiệu, bất biến, chi phí và phản ví dụ. Sau một tuần, trộn tên bài và tự chọn phương án mà không nhìn chương.

Khi giải lại, không cần nhớ từng dòng. Hãy dựng code từ bất biến. Nếu không làm được, bạn chưa sở hữu pattern. Dùng lộ trình có thứ tự để bảo đảm độ phủ, nhưng định kỳ mock ngẫu nhiên để tránh gợi ý ngầm.

Các lỗi nhận dạng thường gặp

• Thấy “đoạn” là dùng window dù dữ liệu có số âm và điều kiện không đơn điệu.
• Thấy “đã sắp” là binary search dù chỉ cần quét một lần.
• Dùng heap cho toàn bộ sort rồi nhận cùng O(n log n) với code khó hơn.
• Gọi DFS có memo là DP mà không kiểm chu trình state.
• Dùng DSU khi bài hỏi đường đi hoặc cần xóa cạnh.
• Thuộc template nhưng không nói quy tắc hòa, chỉ số và kiểu số.

Luyện ngay trên Big-O Coding

Bắt đầu với cửa sổ không lặp rồi đi theo các chương của Coding Interview 150 để phủ đủ pattern.

Câu hỏi thường gặp

Nguồn tham khảo

• USACO Guide: Using this guide
• Tech Interview Handbook: Algorithms study cheatsheet
• CP-Algorithms