Framework giải bài thuật toán — 5 bước biến brute force thành tối ưu

Bạn được hỏi: "Two Sum trên array 1 triệu phần tử, target = 100. Viết solution tối ưu." Đầu óc trống rỗng. Không biết bắt đầu từ đâu. Không nhớ "trick" nào phù hợp.

Cảm giác đó không phải vì bạn kém — mà vì không ai dạy quy trình tiếp cận bài mới. Hầu hết tài liệu chỉ cho xem solution, không cho xem cách suy nghĩ ra solution đó.

Bài này giải thích cách suy nghĩ về bài toán mới — quy trình thay vì "thiên tài hoặc may mắn". Framework 5 bước này cho phép bạn bắt đầu từ bất kỳ bài toán nào, tìm được approach có thể code được, và biết complexity của mình là bao nhiêu trước khi gõ dòng code đầu tiên.

1. Analogy — Bác sĩ chẩn đoán

Bệnh nhân bước vào phòng khám. Không bác sĩ nào giỏi mấy cũng đoán được bệnh ngay từ cái nhìn đầu tiên — dù đã khám hàng nghìn ca. Họ có quy trình:

Hỏi triệu chứng → xét nghiệm cơ bản → đặt giả thuyết → xét nghiệm chuyên sâu → kết luận điều trị.

Mỗi bước dựa trên kết quả bước trước. Bỏ qua bước nào cũng làm tăng nguy cơ chẩn đoán sai.

Giải bài thuật toán cũng vậy. Không có "thiên tài nhìn vào là biết" — chỉ có người đã nội hóa quy trình đến mức chạy tự động.

2. Bước 1 — Hiểu input/output rõ ràng

Sai lầm phổ biến nhất: nhảy vào code khi chưa hiểu đề bài đủ kỹ. Kết quả là giải xong một bài toán khác, hoặc đúng 80% test case và không biết tại sao sai 20% còn lại.

Những câu hỏi cần trả lời trước khi code bất kỳ dòng nào:

Về input:

• n cỡ bao nhiêu? 100? 10.000? 1 triệu? (quyết định complexity target)
• Có thể âm không? Có duplicate không? Đã sorted chưa?
• Kiểu dữ liệu là gì? int hay long? Có overflow không?

Về output:

• Trả về index hay value? Một kết quả hay tất cả?
• Nếu không có kết quả, trả về gì? -1, null, hay empty array?
• Có yêu cầu thứ tự không?

Về edge case:

• Array rỗng?
• Chỉ có 1 phần tử?
• Tất cả phần tử giống nhau?
• Giá trị Integer.MAX_VALUE hay Integer.MIN_VALUE?

// BEFORE writing any logic, document your understanding:
// Input:  int[] nums (1 <= nums.length <= 10^4, non-null)
//         int target (can be negative)
// Output: int[] of length 2, indices [i, j] where i != j
//         and nums[i] + nums[j] == target
// Guaranteed: exactly one solution exists
// Edge:   nums.length == 2 -> must return those two indices

3. Bước 2 — Brute force trước

Sau khi hiểu đề bài, đừng nghĩ tới "tối ưu" ngay. Viết solution đơn giản nhất có thể — solution mà bất kỳ ai cũng nghĩ ra.

Lý do:

Thứ nhất: brute force cho bạn code chạy được để so sánh kết quả. Khi tối ưu xong, bạn có ground truth để verify.

Thứ hai: đo Big-O của brute force cho bạn biết "ceiling" — bạn đang cải thiện từ điểm nào và cần cải thiện bao nhiêu.

Thứ ba: nếu n đủ nhỏ và brute force đủ nhanh với constraint đã cho, bạn không cần tối ưu. YAGNI (You Aren't Gonna Need It) — đừng optimize trước khi biết có cần không.

// Brute force Two Sum: try every pair (i, j) where i != j
// Time: O(n^2) -- two nested loops
// Space: O(1) -- no extra memory
public int[] twoSumBrute(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return new int[]{i, j};
            }
        }
    }
    return new int[]{-1, -1}; // should not reach here per problem guarantee
}

Với n = 1 triệu: n² = 1 nghìn tỷ phép tính. Máy thực hiện khoảng 10⁸–10⁹ phép đơn giản/giây → mất 1.000 đến 10.000 giây. Không chấp nhận được. Cần tối ưu.

Với n = 1.000: n² = 1 triệu. Chạy trong vài ms. Nếu bài yêu cầu n tối đa 1.000, brute force là đủ — không cần thêm complexity.

4. Bước 3 — Identify bottleneck

Nhìn vào brute force, tìm phần nào tốn thời gian nhất. Thường là:

Loop lồng nhau: inner loop lặp lại việc đã làm ở outer loop. Có cách dùng memory để tránh lặp không?

Tính lại kết quả đã biết: tính lại cùng giá trị nhiều lần (overlapping subproblem → dấu hiệu của DP).

Tìm kiếm linear trong dữ liệu có thể sort: nếu array đã sorted, binary search thay thế linear scan.

Tìm kiếm linear trong tập đã có: nếu bạn đang hỏi "có X trong tập này không?" bằng loop → HashSet trả lời trong O(1).

Với Two Sum brute force:

Outer loop: i từ 0 đến n-1                -- O(n)
  Inner loop: j từ i+1 đến n-1            -- O(n)
    Check: nums[i] + nums[j] == target    -- O(1)

Bottleneck = inner loop: với mỗi i,
ta đang tim kiem "target - nums[i]"
trong phan con lai cua array bang linear scan.

Câu hỏi đúng: "Có cách nào tìm target - nums[i] nhanh hơn O(n) không?"

Nếu lưu các giá trị đã thấy vào HashMap, lookup từ O(n) xuống O(1). Đây là trade space for time: dùng thêm O(n) memory để tiết kiệm O(n) mỗi vòng lặp → tổng từ O(n²) xuống O(n).

5. Bước 4 — Áp kỹ thuật phù hợp

Bốn kỹ thuật phổ biến nhất, đủ để giải phần lớn bài interview cấp mid/senior:

Hashing — đổi linear search thành O(1) lookup

Khi bottleneck là "kiểm tra xem X có tồn tại không" hoặc "tìm phần tử có property Y", HashMap/HashSet cắt từ O(n) xuống O(1). Trade: O(n) space.

Sort — mở ra 2-pointer và binary search

Khi bài liên quan đến pair/triplet/nearest neighbor, sort trước rồi dùng 2 pointer từ 2 đầu thường giải được. O(n log n) time, O(1) space sau sort. Dùng được khi không cần giữ index gốc — hoặc khi index không quan trọng.

Two-pointer / Sliding window — khai thác tính đơn điệu

Khi array đã sorted hoặc constraint có tính monotonic (tăng/giảm dần), 2 pointer đi từ 2 đầu hoặc sliding window expand/shrink dựa trên điều kiện. O(n) time.

Divide & conquer / DP — chia bài thành bài nhỏ hơn

Khi bài có subproblem trùng lặp (bài con giống bài lớn, chỉ nhỏ hơn), hoặc optimal solution của bài lớn xây từ optimal solution bài con. DP thêm memoization để không tính lại.

Bảng mapping input pattern → kỹ thuật:

6. Bước 5 — Verify bằng test case

Solution đẹp về lý thuyết vẫn sai trên edge case. Bước này không phải "chạy thử cho chắc" — mà là kiểm tra có chủ đích:

Verify trên input nhỏ so với brute force: nếu có brute force từ Bước 2, chạy cả hai trên cùng input n = 5–20 và so sánh output. Nếu khác nhau, tìm ngay lý do.

Test edge case đã xác định ở Bước 1: array rỗng, 1 phần tử, tất cả giống nhau, Integer.MAX_VALUE.

Test max constraint: với n = 10⁶, solution có chạy trong thời gian chấp nhận không? Nếu có thể đo thực tế thì đo.

Trace qua tay 1 ví dụ cụ thể: đừng chỉ đọc code bằng mắt — trace từng bước với input [2, 7, 11, 15], target = 9 và kiểm tra output đúng là [0, 1].

7. Framework áp dụng vào Two Sum — từ O(n²) xuống O(n)

Đây là toàn bộ 5 bước trên một bài cụ thể:

7.1 Bước 1: Hiểu input/output

Input: int[] nums (non-null, ít nhất 2 phần tử), int target. Output: int[] hai phần tử là index i và j sao cho nums[i] + nums[j] == target và i != j. Đảm bảo tồn tại đúng 1 solution.

7.2 Bước 2: Brute force

Nested loop — thử mọi cặp (i, j). O(n²) time, O(1) space. Code đã có ở trên.

Với n = 10⁶: không chấp nhận được. Cần tối ưu.

7.3 Bước 3: Identify bottleneck

Inner loop là linear scan để tìm target - nums[i]. Mỗi lookup O(n). Nếu lưu giá trị đã thấy vào HashMap, lookup xuống O(1).

7.4 Bước 4: Áp kỹ thuật — ba approach

Approach 1: HashMap (O(n) time, O(n) space)

// HashMap approach: one pass, store value -> index as we go
// Time: O(n) -- one loop, O(1) lookup per iteration
// Space: O(n) -- HashMap stores at most n entries
public int[] twoSumHash(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>(); // value -> index
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (seen.containsKey(complement)) {
            return new int[]{seen.get(complement), i};
        }
        seen.put(nums[i], i);
    }
    return new int[]{-1, -1}; // unreachable per problem guarantee
}

One pass: với mỗi phần tử, kiểm tra complement có trong map không; nếu không thì thêm vào. Không cần hai vòng lặp riêng.

Approach 2: Sort + 2-pointer (O(n log n) time, O(n) space nếu cần giữ index)

// Sort + two-pointer: sort a copy with original indices, then converge
// Time: O(n log n) for sort, O(n) for two-pointer scan
// Space: O(n) for the index copy
// Use when: index not needed (e.g. return values instead of indices)
public int[] twoSumTwoPointer(int[] nums, int target) {
    // Pair up value with original index to recover after sorting
    int[][] indexed = new int[nums.length][2];
    for (int i = 0; i < nums.length; i++) {
        indexed[i][0] = nums[i];
        indexed[i][1] = i;
    }
    Arrays.sort(indexed, (a, b) -> a[0] - b[0]);

    int left = 0, right = indexed.length - 1;
    while (left < right) {
        int sum = indexed[left][0] + indexed[right][0];
        if (sum == target) {
            // Return original indices in sorted order
            int i = Math.min(indexed[left][1], indexed[right][1]);
            int j = Math.max(indexed[left][1], indexed[right][1]);
            return new int[]{i, j};
        } else if (sum < target) {
            left++;  // need larger sum: move left pointer right
        } else {
            right--; // need smaller sum: move right pointer left
        }
    }
    return new int[]{-1, -1};
}

2-pointer hoạt động vì sau sort, nếu tổng nhỏ hơn target thì di chuyển left sang phải (tăng giá trị), nếu lớn hơn thì di chuyển right sang trái (giảm giá trị). Mỗi bước loại đi ít nhất 1 phần tử.

So sánh ba approach:

7.5 Bước 5: Verify

// Test cases to verify:
// Normal: [2,7,11,15], target=9  -> [0,1]
// Small:  [3,3], target=6        -> [0,1]  (duplicate values, different indices)
// Negative: [-1,-2,-3,-4,-5], target=-8 -> [2,4]
// Large complement: [0,4,3,0], target=0  -> [0,3]

Compare HashMap output vs brute force output for all 4 cases above — kết quả phải khớp.

8. Pitfall

Pitfall 1: Tối ưu sớm trước khi có brute force chạy được.

Nhảy vào HashMap solution mà chưa có brute force để compare là đặt cược vào solution đúng ngay lần đầu. Khi có bug, không có gì để debug bằng. Brute force là safety net — đừng bỏ nó.

Thêm nữa: đôi khi brute force đủ. Với n tối đa 100 và time limit 2 giây, O(n²) = 10.000 ops — chạy trong microseconds. Optimize thêm chỉ tốn thời gian mà không có lợi ích thực tế.

Pitfall 2: Nhận pattern sai — thấy mảng là nghĩ binary search, thấy pair là nghĩ HashMap.

Pattern matching nông làm bạn áp sai kỹ thuật. Binary search yêu cầu array đã sorted và bài toán có dạng monotonic. HashMap phù hợp khi cần lookup complement — không phải mọi bài pair. Luôn đi qua Bước 3 (identify bottleneck) trước khi nhảy đến kỹ thuật.

Ví dụ: bài "tìm cặp (i, j) sao cho j - i lớn nhất với nums[i] < nums[j]" — pattern trông giống Two Sum nhưng không giải được bằng HashMap. Cần prefix min / suffix max.

Pitfall 3: Quên test edge case — solution đẹp nhưng sai trên input biên.

O(n) HashMap solution cho Two Sum sẽ trả về kết quả sai nếu bạn vô tình để i == j trong kết quả. Trường hợp [3, 3], target = 6 — phải trả về [0, 1], không phải [0, 0]. Bug này chỉ xuất hiện khi test duplicate value. Không test edge case → fail interview hay production incident dù algorithm đúng về lý thuyết.

9. Ứng dụng thực tế

Google interview rubric chấm theo 4 chiều: approach (tìm ra hướng giải), coding (code sạch, đúng), complexity (phân tích Big-O), testing (tự test edge case). Bỏ qua bất kỳ chiều nào đều bị trừ điểm đáng kể. Framework 5 bước này map trực tiếp: Bước 1–4 cover approach + complexity, Bước 2 cho code baseline, Bước 5 cover testing. Candidate nào chỉ code nhanh mà không giải thích approach thường fail ở "approach" và "complexity" dimension — dù code đúng.

Production debug dùng framework tương tự. Khi gặp slow query: input cỡ nào (bảng bao nhiêu row)? Brute force hiện tại đang làm gì (full table scan? N+1 query?)? Bottleneck ở đâu (CPU, I/O, hay network)? Optimize bằng gì (index, cache, batch)? Verify bằng explain plan và đo thực tế. Quy trình giống hệt — chỉ domain khác.

Code review: khi junior nộp solution không phân tích complexity, reviewer catch bằng cách hỏi đúng Bước 3 — "bottleneck của đoạn này là gì?" và "với n = 10⁶ thì chạy bao lâu?". Nếu không trả lời được, solution cần rework dù test pass. Framework này là ngôn ngữ chung giữa reviewer và author.

System design interview: bài system design cũng dùng 5 bước tương đương — load estimation (bước 1: n cỡ nào?), naive design (bước 2: monolith đơn giản), identify bottleneck (bước 3: single point of failure, hot partition), apply techniques (bước 4: sharding, caching, CDN, async queue), verify (bước 5: back-of-envelope capacity check). Người quen framework algorithm chuyển sang system design nhanh hơn đáng kể.

10. 📚 Deep Dive tài liệu gốc

11. Tóm tắt

• 5 bước: Hiểu input/output → Brute force → Identify bottleneck → Áp kỹ thuật → Verify. Không bỏ bước nào, kể cả khi bạn "biết answer rồi".
• Bước 1 là nền tảng: hiểu sai constraint (n cỡ nào, có duplicate không, output format gì) dẫn đến giải sai bài toán.
• Brute force luôn đi trước: cho bạn ground truth để verify, cho biết ceiling complexity, và đôi khi là đủ với constraint nhỏ.
• Identify bottleneck chính xác: đừng hỏi "tối ưu cái gì?" mà hỏi "operation nào tốn nhất, lặp lại nhiều nhất?".
• Bốn kỹ thuật phổ biến: Hashing (linear → O(1) lookup), Sort + 2-pointer (pair/nearest neighbor), Sliding window (monotonic constraint), DP (overlapping subproblem).
• Two Sum: từ O(n²) brute force → O(n) HashMap bằng cách nhận ra inner loop là linear search complement → trade O(n) space để cắt O(n) per iteration.
• Verify có chủ đích: compare với brute force trên input nhỏ, test edge case đã liệt kê ở Bước 1, trace tay một ví dụ đủ phức tạp.
• Framework này áp dụng ngoài interview: debug production, system design, code review đều dùng cùng quy trình — chỉ thay domain.

12. Tự kiểm tra

Bài tiếp theo: Mini-challenge: naive vs optimized benchmark