Chương 12. Live Coding và giải thuật

Ở mức 2–4 năm, vòng live coding hiếm khi là LeetCode Hard. Đề thường ở mức easy/medium, gắn với việc thật: đếm, gom nhóm, xử lý chuỗi, viết cache, viết một đoạn SQL hay một đoạn đa luồng nhỏ. Thứ tôi chấm không phải là bạn có ra đáp án hay không, mà là cách bạn đi tới đáp án: có hỏi lại đề không, có nghĩ tới trường hợp biên không, có nói được độ phức tạp và có tự kiểm tra code của mình không. Rất nhiều ứng viên ra đáp án đúng vẫn trượt vì code trong im lặng 20 phút rồi nói "xong rồi anh".

Người phỏng vấn muốn kiểm tra

• Làm rõ đề và nêu giả định trước khi gõ code
• Chọn đúng cấu trúc dữ liệu và giải thích được vì sao (HashMap, ArrayDeque, TreeMap, PriorityQueue...)
• Nói được độ phức tạp thời gian/bộ nhớ và cách tối ưu từ lời giải brute-force
• Code sạch, đặt tên rõ, xử lý edge case, tự chạy thử bằng tay với ví dụ
• Viết được Stream API, SQL cơ bản và một bài đồng bộ đa luồng nhỏ mà không cần IDE nhắc

12.1 Người phỏng vấn thực sự chấm gì

Tôi dùng một phiếu chấm gần như cố định cho vòng live coding. Đáp án đúng chỉ chiếm khoảng một phần ba số điểm. Phần còn lại là những thứ phản ánh bạn sẽ làm việc thế nào trong team: bạn có hỏi khi yêu cầu mơ hồ không, có nghĩ tới dữ liệu xấu không, có biết code mình chậm ở đâu không.

Tiêu chí	Tín hiệu tốt	Tín hiệu xấu
Giao tiếp	Nói to suy nghĩ, giải thích lựa chọn	Im lặng gõ, hỏi gì cũng "chờ em chút"
Làm rõ đề	Hỏi input rỗng, null, trùng, kích thước	Lao vào code ngay giây thứ 10
Edge case	Tự liệt kê trước khi code	Chỉ chạy đúng ví dụ mẫu
Độ phức tạp	Nêu Big-O, biết điểm nghẽn	"Chắc là nhanh ạ"
Code sạch	Tên biến có nghĩa, tách hàm nhỏ	Biến a, b, tmp2, một hàm 60 dòng
Tự test	Chạy tay với 2–3 input, tự tìm bug	Chờ người phỏng vấn chỉ lỗi

Mẹo từ người phỏng vấn

Một ứng viên nói rõ "em làm brute-force O(n^2) trước cho chắc, sau đó tối ưu bằng HashMap xuống O(n)" và làm xong bản O(n) thường được điểm cao hơn người im lặng viết thẳng bản tối ưu nhưng không giải thích được. Người phỏng vấn cần nhìn thấy quá trình tư duy, vì đó là thứ họ sẽ phải làm việc cùng hằng ngày.

Với ứng viên 2–4 năm, tôi còn để ý thêm hai điều mà Fresher được châm chước: bạn có dùng đúng API của Java hiện đại không (ArrayDeque thay Stack, Map.merge, record, switch dạng mũi tên), và bạn có tự nhắc tới khía cạnh production không, ví dụ "nếu dữ liệu vài chục triệu bản ghi thì em sẽ không load hết vào memory mà xử lý theo batch".

12.2 Quy trình 6 bước nói to khi code

Hãy luyện quy trình này đến mức thành phản xạ. Mỗi bước đều nói ra thành lời, kể cả khi bạn đã biết đáp án.

1. Nhắc lại đề bằng lời của mình. "Em hiểu là: cho mảng số nguyên và target, trả về chỉ số hai phần tử có tổng bằng target, đúng không anh?" Bước này bắt được rất nhiều hiểu lầm.
2. Hỏi ràng buộc và nêu giả định. Input có thể rỗng hay null không? Có số âm, có phần tử trùng không? Kích thước cỡ nào (1 nghìn hay 10 triệu)? Chuỗi chỉ có ASCII hay có Unicode tiếng Việt? Không có đáp án thì trả gì, ném exception hay trả mảng rỗng?
3. Lấy ví dụ và liệt kê edge case. Tự viết 2–3 ví dụ nhỏ ra comment, gồm một ca bình thường và một ca biên.
4. Nêu hướng giải và độ phức tạp trước khi code. Bắt đầu từ brute-force, nói Big-O, rồi đề xuất cách tối ưu. Hỏi "anh có muốn em code luôn bản tối ưu không?".
5. Code và bình luận trong lúc gõ. Đặt tên rõ, tách hàm phụ nếu dài. Chỗ nào chưa chắc API thì nói thẳng: "em không nhớ chính xác tên method, em giả sử là X".
6. Tự test bằng tay và tổng kết. Chạy từng dòng với ví dụ đã viết ở bước 3, đặc biệt ca biên. Cuối cùng nhắc lại độ phức tạp và nêu hướng cải tiến nếu có thêm thời gian.

Bẫy thường gặp

Cái bẫy lớn nhất là ngại hỏi vì sợ bị đánh giá "không hiểu đề". Thực tế ngược lại: nhiều đề được cố tình viết thiếu để xem bạn có hỏi không. Trong công việc thật, yêu cầu từ BA hay khách hàng cũng luôn thiếu như vậy.

Mẹo từ người phỏng vấn

Khi bị kẹt, đừng im lặng. Hãy nói "em đang nghĩ tới hướng A nhưng vướng chỗ B". Người phỏng vấn thường sẽ gợi ý, và biết nhận gợi ý để đi tiếp cũng là một điểm cộng.

12.3 Big-O cần nhớ của Java Collections

Nhắc lại kiến thức

Bảng dưới dựa trên cách các collection được cài đặt bên trong: ArrayList là một mảng tự giãn, LinkedList là chuỗi node nối nhau, HashMap chia key vào các "ngăn" (bucket) theo hashCode, TreeMap là cây đỏ đen luôn giữ thứ tự. Nếu chưa chắc phần này, hãy đọc lại tổng quan Collections ở N1.11 và phần HashMap từ bên trong ở mục 1.5 trước.

Bạn không cần thuộc lòng lý thuyết độ phức tạp, nhưng phải nói ngay được chi phí của những thao tác mình dùng hằng ngày. Khi tôi hỏi "list.contains() trong vòng for thì độ phức tạp bao nhiêu?", câu trả lời phải bật ra ngay: O(n^2).

Cấu trúc	Thao tác	Độ phức tạp	Ghi chú
ArrayList	get(i), set(i)	O(1)	Truy cập ngẫu nhiên nhanh
ArrayList	add cuối	O(1) khấu hao	Thỉnh thoảng phải copy mảng khi đầy
ArrayList	add/remove giữa, contains	O(n)	Dịch phần tử, quét tuyến tính
LinkedList	thêm/xóa đầu, cuối	O(1)	get(i) là O(n), ít khi đáng dùng
ArrayDeque	push/pop/offer/poll	O(1)	Dùng làm stack và queue
HashMap, HashSet	get/put/contains	O(1) trung bình	Xấu nhất khoảng O(log n) khi bucket đã treeify (Java 8+, key nên implement Comparable)
LinkedHashMap	get/put	O(1) trung bình	Giữ thứ tự chèn hoặc thứ tự truy cập
TreeMap, TreeSet	get/put/remove, floorKey	O(log n)	Có thứ tự, tìm khoảng
PriorityQueue	offer/poll	O(log n)	peek O(1), remove(Object) O(n)
Arrays.sort, List.sort	sắp xếp	O(n log n)	Object dùng TimSort, ổn định

Ghi chú

Nhiều tài liệu cũ nói HashMap xấu nhất là O(n). Từ Java 8, khi một bucket vượt 8 phần tử và table đủ lớn (từ 64 bucket), danh sách liên kết được chuyển thành cây đỏ đen, nên xấu nhất khoảng O(log n) (đầy đủ khi key implement Comparable; nếu không, cây vẫn phải duyệt nhiều nhánh). Cũng có tài liệu ghi new StringBuilder(s).reverse() là "O(n/2)": thực chất vẫn là O(n), và method này còn xử lý đúng cặp surrogate (emoji, ký tự ngoài BMP), điều mà vòng lặp đảo char thủ công làm sai.

Hai điều hay bị hỏi thêm: nối chuỗi bằng + trong vòng lặp là O(n^2) vì mỗi lần tạo String mới, nên dùng StringBuilder; và Collections.sort với object là stable, tức phần tử bằng nhau giữ nguyên thứ tự ban đầu, điều quan trọng khi sort nhiều tiêu chí.

Big-O bằng lời thường

Big-O trả lời một câu hỏi rất đời thường: khi dữ liệu tăng lên, số bước chương trình phải làm tăng nhanh cỡ nào? Nó không đo số giây, vì số giây phụ thuộc máy nhanh hay chậm. Nó chỉ nói "hình dạng" của sự tăng trưởng. Ví dụ tìm tên một người trong danh sách lớp không sắp xếp: lớp 10 người thì xem tối đa 10 tên, lớp 1.000 người thì tối đa 1.000 tên, tức số bước tăng đúng bằng số người, đó là O(n). Còn tra từ trong từ điển đã xếp theo vần: mở giữa cuốn, biết từ cần tìm nằm nửa trước hay nửa sau, bỏ đi một nửa và lặp lại, đó là O(log n). Ký hiệu n là kích thước đầu vào (số phần tử mảng, số ký tự chuỗi, số dòng bảng).

Hai quy ước khi tính Big-O: bỏ hằng số (2n bước và n bước đều là O(n), vì khi n lớn, hệ số 2 không đổi được "hình dạng"), và chỉ giữ số hạng lớn nhất (n^2 + n là O(n^2), vì khi n = 1.000.000 thì phần n chỉ là một phần triệu của n^2).

Bảng dưới đây đếm số bước xấp xỉ khi n = 10, 1.000 và 1.000.000. Một máy chủ bình thường làm được cỡ vài trăm triệu đến một tỷ phép tính đơn giản mỗi giây, bạn dùng con số này để đổi ra thời gian.

Độ phức tạp	n = 10	n = 1.000	n = 1.000.000
O(1): tra HashMap, get(i) của ArrayList	1	1	1
O(log n): binary search, TreeMap	khoảng 3	khoảng 10	khoảng 20
O(n): duyệt mảng một lượt	10	1.000	1.000.000 (vài mili giây)
O(n log n): sort	khoảng 33	khoảng 10.000	khoảng 20 triệu (vài chục mili giây)
O(n^2): hai vòng for lồng nhau	100	1.000.000	10^12 (cỡ vài chục phút)

Điều cần rút ra: với n = 10, mọi thuật toán đều "nhanh", nên chạy thử với ví dụ nhỏ không bao giờ lộ ra vấn đề. Với n = 1.000.000, O(n^2) biến một API vài mili giây thành một request treo hàng chục phút. Đó là lý do người phỏng vấn luôn hỏi "nếu dữ liệu lên 1 triệu thì sao?".

Đoạn code dưới đây đếm số bước thật của tìm tuyến tính và binary search trên mảng 0, 1, ..., n-1, tìm phần tử cuối cùng (trường hợp xấu nhất cho tìm tuyến tính).

public class StepCounter {
    static long linearSteps(int[] a, int target) {
        long steps = 0;
        for (int x : a) { steps++; if (x == target) break; } // one step per element checked
        return steps;
    }

    static long binarySteps(int[] a, int target) {
        long steps = 0;
        int lo = 0, hi = a.length;
        while (lo < hi) { // each iteration halves the range
            steps++;
            int mid = lo + (hi - lo) / 2;
            if (a[mid] < target) lo = mid + 1; else hi = mid;
        }
        return steps;
    }

    public static void main(String[] args) {
        for (int n : new int[]{10, 1_000, 1_000_000}) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = i;
            System.out.println("n=" + n + " linear=" + linearSteps(a, n - 1)
                + " binary=" + binarySteps(a, n - 1) + " nested=" + (long) n * n);
        }
        // prints: n=10 linear=10 binary=3 nested=100
        // prints: n=1000 linear=1000 binary=10 nested=1000000
        // prints: n=1000000 linear=1000000 binary=20 nested=1000000000000
    }
}

Giải thích: chạy chương trình, bạn thấy tìm tuyến tính cần đúng n bước, còn binary search chỉ cần 3, 10 rồi 20 bước dù n tăng gấp trăm nghìn lần. Cột nested không chạy thật hai vòng lặp mà chỉ tính n * n, vì chạy thật 10^12 bước sẽ mất rất lâu; đó chính là chi phí của hai vòng for lồng nhau.

• log n (cơ số 2) là số lần phải chia đôi n cho tới khi còn 1: 1.000 chia đôi khoảng 10 lần, 1.000.000 khoảng 20 lần. Mỗi lần n tăng gấp 1.000, binary search chỉ thêm khoảng 10 bước.
• "O(1) khấu hao" (amortized) của ArrayList.add nghĩa là: đa số lần thêm tốn 1 bước, thỉnh thoảng mảng đầy phải copy sang mảng lớn gấp rưỡi tốn n bước, nhưng chia đều ra thì trung bình mỗi lần vẫn là hằng số.
• Độ phức tạp bộ nhớ đọc tương tự: thuật toán dùng thêm một HashMap chứa n phần tử là O(n) bộ nhớ, chỉ dùng vài biến đếm là O(1).

12.4 Nhóm HashMap: đếm tần suất và tra cứu O(1)

Đây là dạng gặp nhiều nhất ở vòng live coding tại Việt Nam. Mẫu tư duy: khi thấy "tìm cặp", "đếm", "đã gặp chưa", "phần tử trùng", hãy nghĩ ngay tới việc đánh đổi bộ nhớ lấy thời gian bằng HashMap hoặc HashSet để đưa O(n^2) xuống O(n).

Nhắc lại kiến thức

HashMap tra cứu O(1) trung bình vì nó tính hashCode của key để nhảy thẳng tới đúng "ngăn" chứa key, thay vì quét từ đầu. Điều này chỉ đúng khi key cài đặt equals và hashCode nhất quán (xem N1.9 và mục 1.2); các kiểu có sẵn như Integer, String, Character đã làm sẵn. Cơ chế bên trong xem N1.11 và mục 1.5.

Two Sum

Ý tưởng bằng lời thường: hãy tưởng tượng bạn đi dọc một hàng người, mỗi người cầm một số, và cần tìm hai người có tổng bằng 10. Cách chậm là với mỗi người, đi hỏi lại tất cả những người khác. Cách nhanh là mang theo một cuốn sổ: tới mỗi người, bạn tự hỏi "mình cần số bao nhiêu để cộng với số này ra 10?", lật sổ xem đã gặp số đó chưa; nếu chưa, ghi số của người này vào sổ rồi đi tiếp. Cuốn sổ chính là HashMap, và lật sổ tốn O(1).

Brute-force là hai vòng for, O(n^2). Cách tối ưu: duyệt một lượt, với mỗi phần tử kiểm tra "phần bù" target - x đã từng gặp chưa.

import java.util.*;

public class TwoSum {
    // O(n) time, O(n) memory
    static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>(); // value -> index
        for (int i = 0; i < nums.length; i++) {
            Integer j = seen.get(target - nums[i]); // has the complement appeared on the left?
            if (j != null) return new int[]{j, i};
            seen.put(nums[i], i); // put AFTER the check so an element never pairs with itself
        }
        return new int[0]; // no answer: ask the interviewer what to return
    }
}

Giải thích: ý tưởng là thay vòng for thứ hai (tìm phần bù bằng cách quét) bằng một lần tra HashMap O(1). Map seen luôn chứa các phần tử bên trái vị trí hiện tại, nên khi tìm thấy phần bù thì chắc chắn đó là một phần tử khác.

• Chạy tay nums = [2, 7, 11, 15], target = 9: i = 0, x = 2, cần 7, map rỗng nên put {2:0}; i = 1, x = 7, cần 2, map có 2 -> 0 nên trả [0, 1].
• Độ phức tạp: O(n) thời gian vì mỗi phần tử được tra và put một lần; O(n) bộ nhớ cho map trong trường hợp xấu nhất (không có đáp án).
• Edge case: mảng rỗng hoặc một phần tử trả []; null sẽ ném NullPointerException (hỏi đề có cần kiểm tra không); số âm vẫn đúng; nhiều đáp án thì trả cặp đầu tiên tìm được. Lưu ý thứ tự: kiểm tra trước rồi mới put, nhờ vậy ca [3, 3] với target 6 vẫn đúng (i = 1 tìm thấy 3 -> 0) và không tự ghép một phần tử với chính nó.

Bảng chạy tay với nums = [3, 5, 2, 8], target = 10. Mỗi dòng là một vòng lặp; cột "seen" là nội dung map trước khi xét phần tử đó.

i, nums[i]	Cần tìm (target - x)	seen trước bước này	Hành động
0, 3	7	{}	không có 7, put 3 -> 0
1, 5	5	{3:0}	không có 5, put 5 -> 1
2, 2	8	{3:0, 5:1}	không có 8, put 2 -> 2
3, 8	2	{3:0, 5:1, 2:2}	có 2 -> 2, trả [2, 3]

Dòng i = 1 cho thấy vì sao phải kiểm tra trước rồi mới put: 5 + 5 = 10, nếu put 5 vào map trước khi tra thì code sẽ trả [1, 1], tức ghép phần tử với chính nó.

Câu hỏi đào sâu

"Nếu mảng đã được sắp xếp thì sao?" Dùng two pointers từ hai đầu: tổng nhỏ hơn target thì tăng con trỏ trái, lớn hơn thì giảm con trỏ phải. O(n) thời gian nhưng O(1) bộ nhớ. Nếu mảng chưa sort và đề cho phép, sort trước tốn O(n log n) nhưng mất chỉ số gốc, cần hỏi lại đề có cần index không.

Ký tự đầu tiên không lặp và Anagram

Ý tưởng bằng lời thường: giống kiểm phiếu bầu. Lượt đầu, đọc từng phiếu và gạch một vạch vào bảng đếm của tên đó. Sau khi đếm xong mới trả lời được câu hỏi "ai chỉ có đúng một phiếu" hay "hai thùng phiếu có số phiếu từng tên bằng nhau không".

Hai bài này cùng một mẫu: đếm tần suất rồi duyệt lại. Nếu tập ký tự nhỏ và biết trước (a-z), mảng int[26] nhanh hơn và gọn hơn HashMap.

// First unique character: O(n) time, O(k) memory (k = distinct characters)
static int firstUniqueIndex(String s) {
    Map<Character, Integer> freq = new HashMap<>();
    for (char c : s.toCharArray()) freq.merge(c, 1, Integer::sum); // pass 1: count
    for (int i = 0; i < s.length(); i++) {                         // pass 2: scan in original order
        if (freq.get(s.charAt(i)) == 1) return i;
    }
    return -1;
}

// Anagram, assuming lowercase a-z only: O(n) time, O(1) memory
static boolean isAnagram(String a, String b) {
    if (a.length() != b.length()) return false; // different lengths can never be anagrams
    int[] count = new int[26];
    for (int i = 0; i < a.length(); i++) {
        count[a.charAt(i) - 'a']++; // characters of a: increment
        count[b.charAt(i) - 'a']--; // characters of b: decrement
    }
    for (int c : count) if (c != 0) return false; // any non-zero cell means counts differ
    return true;
}

Giải thích: firstUniqueIndex phải đi hai lượt vì khi mới gặp một ký tự, ta chưa biết phía sau nó có lặp lại hay không. Lượt 1 đếm, lượt 2 duyệt lại theo thứ tự trong chuỗi (không duyệt map, vì HashMap không giữ thứ tự) và trả vị trí đầu tiên có tần suất 1.

• Chạy tay "leetcode": sau lượt 1, l=1, e=3, t=1, c=1, o=1, d=1; lượt 2 xét i = 0 là l có tần suất 1 nên trả 0. Với "aabb", mọi ký tự có tần suất 2 nên trả -1.
• isAnagram dùng một mảng đếm chung: ký tự của a cộng, ký tự của b trừ. Hai chuỗi là anagram khi và chỉ khi mọi ô về 0. Chạy tay "rat" và "car": r +1 rồi -1, a +1 rồi -1, t +1, c -1, còn hai ô khác 0 nên trả false. Với "listen" và "silent", mọi ô về 0 nên trả true.
• Độ phức tạp: cả hai O(n) thời gian. Bộ nhớ O(k) với HashMap (k là số ký tự khác nhau) và O(1) với mảng 26 phần tử cố định.
• Edge case: chuỗi rỗng (firstUniqueIndex trả -1, hai chuỗi rỗng là anagram của nhau); chữ hoa hoặc có dấu làm int[26] ném lỗi (xem bẫy bên dưới); ký tự ngoài BMP như emoji chiếm hai char nên nếu đề có emoji phải duyệt theo codePoints().

Bảng chạy tay isAnagram("aab", "aba"), chỉ ghi hai ô a và b của mảng count (các ô khác luôn bằng 0):

i	a.charAt(i), b.charAt(i)	count[a], count[b] sau bước	Ghi chú
0	a, a	0, 0	cộng rồi trừ cùng ô, triệt tiêu
1	a, b	1, -1	a thừa một, b thiếu một
2	b, a	0, 0	bù lại đúng phần lệch
hết		0, 0	mọi ô bằng 0, trả true

Ở giữa chừng mảng đếm có thể lệch (i = 1), nhưng chỉ kết quả cuối mới quan trọng. Nếu đổi thành "aab" và "abb", bước cuối cộng b và trừ b nên mảng còn a = 1, b = -1, trả false.

Bẫy thường gặp

Dùng int[26] mà không nói giả định "chỉ chữ thường a-z". Nếu chuỗi có chữ hoa hoặc tiếng Việt có dấu, code sẽ ném ArrayIndexOutOfBoundsException. Hãy nói giả định ra, hoặc dùng HashMap cho trường hợp tổng quát. Các bài họ hàng: tìm phần tử chung của hai list (retainAll trên HashSet, O(n + m)), xóa phần tử trùng giữ thứ tự (new LinkedHashSet<>(list)), gom nhóm anagram (key là chuỗi đã sort).

12.5 Two pointers và Sliding window

Mẫu tư duy: khi đề hỏi về "đoạn con liên tiếp" (substring, subarray) thỏa điều kiện nào đó, hãy nghĩ tới cửa sổ trượt với hai con trỏ left, right. Con trỏ phải luôn tiến, con trỏ trái chỉ tiến khi cửa sổ vi phạm điều kiện. Mỗi phần tử vào và ra cửa sổ tối đa một lần nên tổng là O(n) chứ không phải O(n^2).

Ý tưởng bằng lời thường: "con trỏ" ở đây chỉ là một biến int lưu vị trí trong mảng hoặc chuỗi, không liên quan tới con trỏ của C. Hãy hình dung một khung cửa sổ đặt trên dải ký tự: mép phải kéo dần sang phải để nhận thêm ký tự; khi trong khung xuất hiện thứ vi phạm điều kiện (ví dụ ký tự lặp), mép trái kéo sang phải cho tới khi khung hợp lệ trở lại. Hai mép chỉ đi về một hướng, nên tổng quãng đường của cả hai tối đa là 2n bước, tức O(n).

Bài kinh điển: độ dài chuỗi con dài nhất không có ký tự lặp.

// Sliding window: O(n) time, O(k) memory
static int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> lastIndex = new HashMap<>();
    int best = 0, left = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        Integer prev = lastIndex.get(c); // where c was last seen
        if (prev != null && prev >= left) left = prev + 1; // shrink the window past the duplicate
        lastIndex.put(c, right);
        best = Math.max(best, right - left + 1); // length of current window [left, right]
    }
    return best;
}

Giải thích: cửa sổ [left, right] luôn là một đoạn không có ký tự lặp. Mỗi bước mở rộng right thêm một ký tự; nếu ký tự đó đã xuất hiện bên trong cửa sổ thì nhảy left tới ngay sau lần xuất hiện cũ, thay vì lùi từng bước. Map lastIndex giúp biết vị trí cũ trong O(1).

• Chạy tay "abcabcbb": right = 0..2 cửa sổ "abc", best = 3; right = 3 gặp a (prev = 0 ≥ left = 0) nên left = 1, cửa sổ "bca"; tiếp tục tương tự, cửa sổ không bao giờ dài quá 3, kết quả 3.
• Điều kiện prev >= left là chỗ hay sai nhất. Chạy tay với "abba": right = 2 gặp b thứ hai nên left = 2; right = 3 gặp a có prev = 0, nhưng index 0 đã nằm ngoài cửa sổ (left = 2) nên giữ nguyên left, cửa sổ "ba", kết quả 2. Nếu thiếu điều kiện này, left sẽ bị kéo lùi về 1, cửa sổ "bba" chứa ký tự lặp và kết quả sai thành 3. Đây chính là lý do bước tự test bằng ca biên quan trọng.
• Độ phức tạp: O(n) thời gian vì right đi một lượt và left chỉ tiến, không lùi; O(k) bộ nhớ với k là số ký tự khác nhau.
• Edge case: chuỗi rỗng trả 0; chuỗi toàn một ký tự "bbbb" trả 1; chuỗi không có ký tự lặp trả đúng độ dài chuỗi.

Bảng chạy tay đầy đủ với "abcabcbb". Cột prev là giá trị lastIndex.get(c) trước khi cập nhật.

right, c	prev	left sau bước	Cửa sổ, best
0, a	null	0	a, 1
1, b	null	0	ab, 2
2, c	null	0	abc, 3
3, a	0 (≥ left 0)	1	bca, 3
4, b	1 (≥ left 1)	2	cab, 3
5, c	2 (≥ left 2)	3	abc, 3
6, b	4 (≥ left 3)	5	cb, 3
7, b	6 (≥ left 5)	7	b, 3

Để ý ở right = 6, left nhảy thẳng từ 3 lên 5 chứ không lùi hay nhích từng bước; đó là lý do tổng số bước vẫn là O(n).

Two pointers trên mảng đã sắp xếp

Ý tưởng bằng lời thường: một dạng khác của hai con trỏ là đặt chúng ở hai đầu mảng đã sort rồi tiến dần vào giữa. Với bài "tìm hai số có tổng bằng target": nếu tổng hai đầu nhỏ quá, số bên trái là số nhỏ nhất còn lại, ghép với số lớn nhất mà vẫn chưa đủ, nên nó không thể thuộc đáp án nào, bỏ nó bằng cách tăng left. Ngược lại, tổng lớn quá thì số bên phải chắc chắn thừa, giảm right. Mỗi bước loại được một phần tử, nên tối đa n bước.

import java.util.Arrays;

public class TwoPointers {
    // Sorted input: O(n) time, O(1) memory
    static int[] pairSum(int[] sorted, int target) {
        int left = 0, right = sorted.length - 1;
        while (left < right) {
            int sum = sorted[left] + sorted[right];
            if (sum == target) return new int[]{left, right};
            if (sum < target) left++; // sum too small: drop the smallest value
            else right--;             // sum too big: drop the largest value
        }
        return new int[0];
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 4, 6, 9};
        System.out.println(Arrays.toString(pairSum(nums, 13))); // prints: [2, 4]
        System.out.println(Arrays.toString(pairSum(nums, 2)));  // prints: []
    }
}

Giải thích: với target 13, code trả [2, 4] (hai số 4 và 9); với target 2 không có cặp nào nên trả mảng rỗng. So với Two Sum dùng HashMap ở mục 12.4, cách này không tốn bộ nhớ phụ, nhưng bắt buộc mảng đã sort; nếu phải tự sort thì tốn thêm O(n log n) và mất chỉ số gốc.

left, right	sorted[left] + sorted[right]	So với 13	Hành động
0, 4	1 + 9 = 10	nhỏ hơn	left = 1
1, 4	3 + 9 = 12	nhỏ hơn	left = 2
2, 4	4 + 9 = 13	bằng	trả [2, 4]

Với target 2: các tổng lần lượt là 10, 7, 5, 4, luôn lớn hơn 2 nên right giảm từ 4 xuống 0; khi left == right vòng lặp dừng và trả []. Điều kiện left < right (không phải <=) đảm bảo không ghép một phần tử với chính nó.

12.6 Stack: ngoặc hợp lệ

Nhắc lại kiến thức

Stack là cấu trúc "vào sau ra trước" (LIFO): phần tử đẩy vào cuối cùng được lấy ra đầu tiên, như chồng đĩa. ArrayDeque cài đặt interface Deque nên dùng được cả làm stack (push/pop/peek) lẫn queue (offer/poll), mọi thao tác O(1). Xem lại N1.11 và mục 1.5.

Ý tưởng bằng lời thường: hãy nghĩ tới chồng đĩa. Mỗi lần gặp ngoặc mở, bạn đặt lên chồng một tờ ghi chú "đang chờ ngoặc đóng loại này". Gặp ngoặc đóng thì chỉ được nhìn tờ trên cùng: đúng loại thì bỏ tờ đó đi, sai loại hoặc chồng trống thì chuỗi sai. Cuối chuỗi, chồng phải trống.

Mẫu tư duy: bài nào có tính "lồng nhau" hoặc "phần tử gần nhất chưa được xử lý" (ngoặc, biểu thức, undo, phần tử lớn hơn kế tiếp) thì nghĩ tới stack. Trong Java hiện đại, dùng ArrayDeque làm stack, không dùng lớp Stack cũ (kế thừa Vector, mọi method đều synchronized, không cần thiết).

Đề bài: cho chuỗi chỉ gồm các ký tự ()[]{}, kiểm tra các ngoặc có được mở và đóng đúng cặp, đúng thứ tự hay không.

// Stack: O(n) time, O(n) memory
static boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        switch (c) {
            case '(' -> stack.push(')'); // push the closing bracket we expect
            case '[' -> stack.push(']');
            case '{' -> stack.push('}');
            default -> { // closing bracket: must match the expected one on top
                if (stack.isEmpty() || stack.pop() != c) return false;
            }
        }
    }
    return stack.isEmpty(); // unclosed brackets left -> invalid
}

Giải thích: mỗi ngoặc đóng phải khớp với ngoặc mở gần nhất chưa được đóng, đúng thứ tự "vào sau ra trước" của stack. Mẹo ở đây là khi gặp ngoặc mở, ta đẩy luôn ngoặc đóng tương ứng; khi gặp ngoặc đóng chỉ cần so sánh với phần tử lấy ra, không cần bảng tra cặp ngoặc.

• Chạy tay "([]{})": ( đẩy ); [ đẩy ], stack là ] ); ] lấy ra ] khớp; { đẩy }; } lấy ra } khớp; ) lấy ra ) khớp; stack rỗng nên trả true. Với "(]": ( đẩy ), gặp ] lấy ra ) không khớp nên trả false ngay.
• Độ phức tạp: O(n) thời gian, O(n) bộ nhớ trong trường hợp xấu nhất (toàn ngoặc mở).
• Edge case cần tự nói: chuỗi rỗng (hợp lệ), chỉ có ngoặc đóng ")" (kiểm tra isEmpty trước khi pop, nếu không sẽ ném NoSuchElementException), chỉ có ngoặc mở "((" (dòng return cuối). Chuỗi có ký tự khác ngoặc như "a(b)" sẽ rơi vào nhánh default và bị coi là sai, nên hỏi lại đề có cần bỏ qua ký tự thường không.

Bảng chạy tay "([]{})" và "([)]". Cột stack ghi đỉnh ở bên trái.

Chuỗi, bước	c	Hành động	Stack sau bước
([]{}), 1	(	push )	)
([]{}), 2	[	push ]	] )
([]{}), 3	]	pop ], khớp	)
([]{}), 4	{	push }	} )
([]{}), 5	}	pop }, khớp	)
([]{}), 6	)	pop ), khớp	rỗng, trả true
([)], 1–2	(, [	push ), push ]	] )
([)], 3	)	pop ], khác )	trả false ngay

Ca "([)]" là ca nhiều người quên: số ngoặc mở và đóng của từng loại đều bằng nhau, nên cách "đếm số ngoặc" cho kết quả sai là hợp lệ. Chỉ stack mới phát hiện được thứ tự lồng nhau sai.

12.7 Sort + merge interval và Binary search

Merge interval rất hay gặp vì nó gắn với nghiệp vụ thật: gộp các khung giờ đặt lịch, gộp khoảng thời gian khuyến mãi. Mẫu tư duy: sort theo điểm bắt đầu, sau đó chỉ cần so khoảng hiện tại với khoảng cuối cùng đã gộp.

Ý tưởng bằng lời thường: bạn có một chồng giấy đặt phòng họp lộn xộn. Việc đầu tiên là xếp chúng theo giờ bắt đầu. Sau đó cầm tờ đầu tiên trên tay; lấy tờ tiếp theo, nếu nó bắt đầu trước khi tờ trên tay kết thúc thì hai cuộc họp chồng nhau, gộp thành một tờ kéo dài tới giờ kết thúc muộn hơn. Nếu không chồng, đặt tờ trên tay vào chồng "đã xong" và cầm tờ mới.

Đề bài: cho mảng các khoảng [start, end] chưa sắp xếp, gộp mọi khoảng chồng lấn và trả về danh sách khoảng đã gộp.

// Sort + merge: O(n log n) time, O(n) memory for the result
static int[][] merge(int[][] intervals) {
    if (intervals.length == 0) return intervals;
    int[][] sorted = intervals.clone(); // do not mutate the caller's array
    Arrays.sort(sorted, Comparator.comparingInt(a -> a[0]));
    List<int[]> result = new ArrayList<>();
    int[] cur = sorted[0].clone();
    for (int i = 1; i < sorted.length; i++) {
        if (sorted[i][0] <= cur[1]) {
            cur[1] = Math.max(cur[1], sorted[i][1]); // overlap: extend the end
        } else {
            result.add(cur);
            cur = sorted[i].clone();
        }
    }
    result.add(cur); // do not forget the last pending interval
    return result.toArray(new int[0][]);
}

Giải thích: sau khi sort theo điểm bắt đầu, mọi khoảng có thể gộp với nhau sẽ nằm liền kề, nên chỉ cần so khoảng đang xét với khoảng cur đang gộp dở: bắt đầu trước khi cur kết thúc thì nới cur, ngược lại thì chốt cur vào kết quả và mở khoảng mới.

• Chạy tay [[1,3],[8,10],[2,6],[15,18]]: sau sort là [[1,3],[2,6],[8,10],[15,18]]; cur = [1,3]; [2,6] có 2 ≤ 3 nên cur = [1,6]; [8,10] có 8 > 6 nên chốt [1,6], cur = [8,10]; [15,18] chốt [8,10], cur = [15,18]; hết vòng chốt nốt. Kết quả [[1,6],[8,10],[15,18]].
• Độ phức tạp: O(n log n) thời gian do sort, phần gộp chỉ O(n); O(n) bộ nhớ cho bản sao và kết quả.
• Edge case: mảng rỗng trả rỗng; một khoảng trả chính nó; khoảng lồng nhau. Hỏi lại đề: hai khoảng [1,3] và [3,5] chạm nhau có tính là chồng lấn không? Dấu <= hay < phụ thuộc câu trả lời. Và Math.max là bắt buộc, vì [1,10] gộp với [2,3] vẫn phải là [1,10]; nếu viết cur[1] = sorted[i][1] thì kết quả sai thành [1,3]. Các lệnh clone() để không sửa mảng người gọi truyền vào, một điểm cộng nhỏ về tính cẩn thận.

Bảng chạy tay cùng input trên, sau khi sort thành [[1,3],[2,6],[8,10],[15,18]], bắt đầu với cur = [1,3], result rỗng:

i, sorted[i]	So sánh start với cur[1]	cur sau bước	result sau bước
1, [2,6]	2 ≤ 3, chồng lấn	[1,6]	[]
2, [8,10]	8 > 6, tách rời	[8,10]	[[1,6]]
3, [15,18]	15 > 10, tách rời	[15,18]	[[1,6],[8,10]]
sau vòng lặp	chốt cur		[[1,6],[8,10],[15,18]]

Dòng cuối là lý do phải có result.add(cur) sau vòng for: khoảng đang cầm trên tay chưa bao giờ được chốt trong vòng lặp.

Binary search cũng cần giải thích bằng lời thường trước khi đi vào khuôn. Ý tưởng: trò chơi đoán số từ 1 đến 100, mỗi lần đoán được trả lời "lớn hơn" hoặc "nhỏ hơn". Người chơi khôn luôn đoán số ở giữa khoảng còn lại, nên sau mỗi lần đoán loại được một nửa: 100, 50, 25, 13, 7, 4, 2, 1, tức tối đa 7 lần. Điều kiện bắt buộc là dữ liệu phải có thứ tự; trên mảng chưa sort, biết nums[mid] nhỏ hơn target không cho ta biết gì về nửa bên trái.

Binary search nghe đơn giản nhưng rất dễ sai ở biên. Tôi khuyên học thuộc một khuôn duy nhất là lower bound trên nửa khoảng [lo, hi), rồi biến đổi cho các bài khác.

// First index with nums[i] >= target (lower bound). Sorted array. O(log n)
static int lowerBound(int[] nums, int target) {
    int lo = 0, hi = nums.length; // search in the half-open range [lo, hi)
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2; // avoids overflow of (lo + hi) / 2
        if (nums[mid] < target) lo = mid + 1; // answer is definitely right of mid
        else hi = mid;                         // mid may be the answer, keep it in range
    }
    return lo; // = nums.length if every element < target
}

Giải thích: vòng lặp giữ một bất biến: mọi vị trí bên trái lo đều có giá trị nhỏ hơn target, mọi vị trí từ hi trở đi đều lớn hơn hoặc bằng target. Mỗi bước thu hẹp khoảng [lo, hi) đi một nửa, và khi lo == hi thì đó chính là vị trí đầu tiên có giá trị lớn hơn hoặc bằng target.

• Chạy tay nums = [1, 3, 3, 5], target = 3: lo = 0, hi = 4, mid = 2, nums[2] = 3 không nhỏ hơn 3 nên hi = 2; mid = 1, nums[1] = 3 nên hi = 1; mid = 0, nums[0] = 1 < 3 nên lo = 1; lo == hi, trả 1 (vị trí của số 3 đầu tiên). Với target = 6, lo tiến dần tới 4 và trả 4 (không có phần tử nào ≥ 6).
• Độ phức tạp: O(log n) thời gian, O(1) bộ nhớ.
• Edge case: mảng rỗng trả 0 mà không vào vòng lặp; mọi phần tử ≥ target trả 0. Muốn biết target có tồn tại không thì kiểm tra thêm lo < nums.length && nums[lo] == target. Đổi < thành <= ở điều kiện là được upper bound (vị trí đầu tiên lớn hơn hẳn target).

Bảng chạy tay nums = [1, 3, 3, 5, 8, 9], target = 5:

lo, hi trước bước	mid, nums[mid]	So với 5	lo, hi sau bước
0, 6	3, 5	không nhỏ hơn, giữ mid	0, 3
0, 3	1, 3	nhỏ hơn, bỏ mid	2, 3
2, 3	2, 3	nhỏ hơn, bỏ mid	3, 3
3, 3		lo == hi, dừng	trả 3

Chỉ sau 3 vòng, kết quả là index 3, đúng vị trí của số 5. Ở vòng đầu, dù nums[3] đã bằng target, code vẫn không dừng mà thu hi về 3 để chắc chắn không còn số 5 nào nằm bên trái; đó là cách lower bound luôn trả về lần xuất hiện đầu tiên.

Câu hỏi đào sâu

"Binary search dùng ở đâu ngoài tìm phần tử trong mảng?" Tìm trên không gian đáp án: tìm sức chứa nhỏ nhất để giao hết hàng trong D ngày, tìm phiên bản đầu tiên bị lỗi (First Bad Version). Chỉ cần điều kiện có tính đơn điệu (sai sai sai đúng đúng) là áp dụng được. Trong thực tế, git bisect chính là binary search trên lịch sử commit.

12.8 BFS/DFS cơ bản

Ở mức 2–4 năm, đồ thị thường xuất hiện dưới dạng lưới 2D hoặc cây: đếm số đảo, tìm đường đi ngắn nhất trong mê cung, duyệt cây danh mục sản phẩm. Mẫu tư duy: cần đường đi ngắn nhất trên đồ thị không trọng số thì dùng BFS (queue); cần duyệt hết/đếm vùng liên thông thì DFS hay BFS đều được.

Ý tưởng bằng lời thường: "đồ thị" chỉ là tập các điểm (ở đây là ô lưới) và các đường nối giữa chúng (hai ô kề nhau). BFS (Breadth-First Search, duyệt theo chiều rộng) giống như nhỏ một giọt mực vào ô xuất phát: mực loang ra tất cả các ô cách 1 bước, rồi mới tới các ô cách 2 bước, cứ thế từng vòng. Queue (hàng đợi, vào trước ra trước) là thứ giữ đúng thứ tự "vòng trong trước, vòng ngoài sau". DFS (Depth-First Search, duyệt theo chiều sâu) thì ngược lại, đi một mạch thật sâu theo một hướng, cụt đường mới quay lại, giống người đi mê cung luôn bám tay vào tường.

Đề bài: cho lưới 0/1, mỗi bước đi lên, xuống, trái hoặc phải sang ô 0; tìm số bước ít nhất để đi từ góc trên trái tới góc dưới phải, không có đường thì trả -1.

// BFS shortest path on a grid (0 = open, 1 = wall). O(m*n)
static int shortestPath(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    if (grid[0][0] == 1 || grid[m - 1][n - 1] == 1) return -1;
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    boolean[][] visited = new boolean[m][n];
    Deque<int[]> queue = new ArrayDeque<>();
    queue.offer(new int[]{0, 0, 0}); // row, col, steps
    visited[0][0] = true;
    while (!queue.isEmpty()) {
        int[] cur = queue.poll();
        if (cur[0] == m - 1 && cur[1] == n - 1) return cur[2]; // first time we reach the target = shortest
        for (int[] d : dirs) {
            int r = cur[0] + d[0], c = cur[1] + d[1];
            if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c] || grid[r][c] == 1) continue;
            visited[r][c] = true; // mark when enqueued, not when dequeued
            queue.offer(new int[]{r, c, cur[2] + 1});
        }
    }
    return -1; // queue exhausted without reaching target: no path
}

Giải thích: BFS lấy ô ra khỏi queue theo đúng thứ tự khoảng cách tăng dần: mọi ô cách 1 bước được xử lý xong mới tới các ô cách 2 bước. Vì vậy lần đầu tiên ô đích được lấy ra, số bước đi kèm chắc chắn là nhỏ nhất. DFS không có tính chất này, nó có thể tới đích bằng một đường vòng trước.

• Chạy tay lưới 3 x 3 [[0,0,0],[1,1,0],[0,0,0]] (hàng giữa có hai ô tường): từ (0,0) bước 0 chỉ đi được sang (0,1) bước 1, rồi (0,2) bước 2, xuống (1,2) bước 3, xuống (2,2) bước 4; khi lấy (2,2) ra thì trả 4.
• Độ phức tạp: O(m·n) thời gian vì mỗi ô vào queue tối đa một lần và xét 4 hướng; O(m·n) bộ nhớ cho visited và queue.
• Edge case: ô xuất phát hoặc ô đích là tường trả -1 ngay; lưới 1 x 1 [[0]] trả 0; không có đường trả -1; lưới rỗng thì grid[0] ném lỗi, nên hỏi đề trước. Cũng hỏi lại đề đếm "số bước di chuyển" hay "số ô trên đường đi" (khi đó cộng thêm 1).

Bảng chạy tay trên lưới có nhiều nhánh hơn, [[0,0,0],[0,1,0],[0,0,0]] (chỉ ô giữa là tường), nên có hai đường cùng dài 4 bước vòng quanh ô giữa. Thứ tự xét hướng theo mảng dirs: xuống, lên, phải, trái. Mỗi phần tử queue ghi dạng (hàng, cột, số bước).

Lượt	Lấy ra	Đưa thêm vào queue	Queue sau lượt
1	(0,0,0)	(1,0,1), (0,1,1)	(1,0,1) (0,1,1)
2	(1,0,1)	(2,0,2)	(0,1,1) (2,0,2)
3	(0,1,1)	(0,2,2)	(2,0,2) (0,2,2)
4	(2,0,2)	(2,1,3)	(0,2,2) (2,1,3)
5	(0,2,2)	(1,2,3)	(2,1,3) (1,2,3)
6	(2,1,3)	(2,2,4)	(1,2,3) (2,2,4)
7	(1,2,3)	không có: (2,2) đã visited	(2,2,4)
8	(2,2,4)	là ô đích	trả 4

Bảng cho thấy hai điều. Thứ nhất, số bước của các phần tử lấy ra luôn không giảm (0, 1, 1, 2, 2, 3, 3, 4), đúng tính chất "loang theo vòng". Thứ hai, ở lượt 7, ô (2,2) đã được đánh dấu visited từ lượt 6 nên không bị đưa vào queue lần nữa; nếu đợi tới lúc lấy ra mới đánh dấu, (2,2) sẽ nằm trong queue hai lần.

Bẫy thường gặp

DFS đệ quy trên lưới lớn (ví dụ 2000 x 2000) có thể gây StackOverflowError vì độ sâu đệ quy tới hàng triệu. Nói được điều này và đề xuất BFS hoặc DFS dùng stack tường minh là dấu hiệu của người có kinh nghiệm. Lỗi phổ biến khác là đánh dấu visited lúc lấy ra khỏi queue, khiến một ô bị đưa vào queue nhiều lần.

12.9 LRU Cache

Đây là bài "thiết kế nhỏ" yêu thích của tôi với ứng viên middle, vì nó nối giải thuật với thực tế (cache cục bộ, Caffeine, Redis eviction policy). Yêu cầu: get và put đều O(1), vượt sức chứa thì bỏ phần tử lâu nhất chưa được dùng.

Nhắc lại kiến thức

LinkedHashMap là HashMap có thêm một danh sách liên kết đôi nối các entry, nên vừa tra cứu O(1) vừa nhớ được thứ tự (thứ tự chèn, hoặc thứ tự truy cập nếu bật accessOrder). Xem N1.11 và mục 1.5.

Ý tưởng bằng lời thường: LRU (Least Recently Used) nghĩa là "lâu nhất chưa được dùng". Hãy nghĩ tới một bàn làm việc chỉ để vừa 2 cuốn sách. Cuốn nào vừa đọc thì đặt lên trên cùng chồng sách. Khi cần đặt cuốn thứ 3 lên bàn mà bàn đã đầy, bạn cất cuốn nằm dưới đáy chồng, vì đó là cuốn lâu nhất chưa đụng tới. Cache cũng vậy: bộ nhớ có hạn, giữ lại những thứ vừa được dùng vì chúng có khả năng được dùng lại cao nhất.

Cách 1, nếu người phỏng vấn cho phép dùng thư viện chuẩn: LinkedHashMap với accessOrder = true.

import java.util.*;

public class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LruCache(int capacity) {
        super(16, 0.75f, true); // accessOrder = true: get/put moves the entry to the tail
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity; // over capacity -> evict least recently used (head)
    }
}

Giải thích: LinkedHashMap là HashMap cộng thêm một danh sách liên kết đôi nối các entry. Với accessOrder = true, mỗi lần get hoặc put một key, entry đó được chuyển về cuối danh sách, nên đầu danh sách luôn là entry lâu chưa dùng nhất. Sau mỗi lần put, LinkedHashMap tự gọi removeEldestEntry; trả true thì entry đầu danh sách bị xóa.

• Chạy tay với capacity = 2: put(1), put(2) cho thứ tự 1, 2; get(1) chuyển 1 về cuối thành 2, 1; put(3) làm size = 3 > 2 nên xóa entry đầu là 2, còn 1, 3; get(2) trả null.
• Độ phức tạp: get và put O(1) trung bình; bộ nhớ O(capacity).
• Edge case: capacity ≤ 0 khiến mọi entry bị xóa ngay sau khi thêm, nên kiểm tra tham số trong constructor. Kế thừa LinkedHashMap cũng làm lộ mọi method của Map ra ngoài (ai đó gọi putAll, entrySet vẫn được); nếu người phỏng vấn để ý tính đóng gói, hãy chuyển sang composition: class bọc một LinkedHashMap private và chỉ lộ get/put.

Đoạn code dưới đây chạy thật một chuỗi thao tác trên cache sức chứa 2 và in thứ tự key sau mỗi bước (đầu danh sách là entry lâu chưa dùng nhất), để bạn đối chiếu với bảng chạy tay.

import java.util.*;

public class LruDemo {
    public static void main(String[] args) {
        Map<Integer, String> lru = new LinkedHashMap<>(16, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {
                return size() > 2; // capacity = 2
            }
        };
        lru.put(1, "A"); lru.put(2, "B");
        System.out.println(lru.keySet()); // prints: [1, 2]
        lru.get(1);
        System.out.println(lru.keySet()); // prints: [2, 1]
        lru.put(3, "C");                  // evicts 2
        System.out.println(lru.keySet()); // prints: [1, 3]
        System.out.println(lru.get(2));   // prints: null
        lru.put(1, "A2");                 // update also counts as access
        lru.put(4, "D");                  // evicts 3
        System.out.println(lru.keySet()); // prints: [1, 4]
    }
}

Giải thích: chương trình in [1, 2], [2, 1], [1, 3], null, [1, 4]. Bảng dưới đây đi qua từng thao tác:

Thao tác	Kết quả trả về	Thứ tự sau thao tác (cũ → mới)	Ghi chú
put(1), put(2)		1, 2	chưa vượt sức chứa
get(1)	A	2, 1	1 vừa được dùng, chuyển về cuối
put(3)		1, 3	size = 3 > 2, xóa đầu danh sách là 2
get(2)	null	1, 3	2 đã bị loại
put(1, A2)		3, 1	cập nhật cũng tính là truy cập
put(4)		1, 4	xóa 3, lâu chưa dùng nhất

Nếu tạo LinkedHashMap với accessOrder = false (mặc định), get(1) không đổi thứ tự và put(3) sẽ xóa 1 thay vì 2; khi đó cache thành FIFO (vào trước ra trước), không còn là LRU.

Cách 2, thường được yêu cầu ngay sau đó: tự cài bằng HashMap (tra cứu O(1)) cộng danh sách liên kết đôi (di chuyển, xóa node O(1)). Khung lời giải bạn cần nói ra trước khi code:

• Mỗi Node giữ key, value, prev, next. Node phải lưu cả key để khi evict còn biết xóa entry nào khỏi map.
• Dùng hai node canh head và tail (sentinel) để thao tác chèn/xóa không phải kiểm tra null ở biên.
• get: không có thì trả -1; có thì tách node ra và chèn lại ngay sau head.
• put: key đã có thì cập nhật value và đưa lên đầu; nếu map đã đầy thì xóa node sát tail (lâu chưa dùng nhất) khỏi cả list lẫn map, rồi chèn node mới sau head.
• Hai hàm phụ unlink(node) và addFirst(node) mỗi hàm chỉ 2–4 dòng gán con trỏ. Tách chúng ra thì get/put gần như đọc được bằng tiếng Việt.

Câu hỏi đào sâu

"Cache này có thread-safe không?" Không. Cách đơn giản nhất là bọc get/put bằng synchronized hoặc ReentrantLock, chấp nhận nghẽn khi tải cao. Lưu ý với LinkedHashMap accessOrder, ngay cả get cũng sửa cấu trúc danh sách nên không thể dùng ReadWriteLock cho phép nhiều reader. Trong production, tôi muốn nghe bạn nói "em sẽ dùng Caffeine chứ không tự viết", và biết cách đo hit rate trước khi quyết định kích thước cache.

12.10 Bài Stream API

Nhắc lại kiến thức

Stream là một "dây chuyền" xử lý dữ liệu: nguồn (list, mảng) đi qua các bước trung gian như filter, map, sorted và kết thúc bằng một bước cuối như collect, count. Các bước trung gian chỉ chạy khi có bước cuối. Cú pháp lambda và method reference (Order::amount) xem N1.15 và mục 1.8.

Với 2–4 năm, gần như chắc chắn bạn sẽ được yêu cầu viết Stream trên giấy hoặc trong editor không có gợi ý code. Dạng hay gặp: gom nhóm và tính tổng, top N, đếm tần suất, chia hai nhóm. Biến thể "phần tử lớn nhất mỗi nhóm" dùng Collectors.maxBy làm downstream collector.

Hai đoạn dưới đây dùng chung một record Order và một danh sách orders; đề thường cho sẵn dữ liệu kiểu này và yêu cầu viết từng câu truy vấn.

import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;

public class StreamQueries {
    record Order(String customer, String category, long amount) {}

    public static void main(String[] args) {
        // Sample data: the same orders as the worked example below
        List<Order> orders = List.of(
            new Order("An", "sách", 100), new Order("Bình", "sách", 300), new Order("An", "đồ ăn", 250),
            new Order("Chi", "đồ ăn", 50), new Order("Dũng", "sách", 80));

        // 1. Total amount per category
        Map<String, Long> totalByCategory = orders.stream()
            .collect(Collectors.groupingBy(Order::category, Collectors.summingLong(Order::amount))); // key -> sum of amount

        // 2. Top 3 customers by spending
        List<String> top3 = orders.stream()
            .collect(Collectors.groupingBy(Order::customer, Collectors.summingLong(Order::amount))) // customer -> total spent
            .entrySet().stream()
            .sorted(Map.Entry.<String, Long>comparingByValue().reversed()) // explicit type witness required, see explanation
            .limit(3)
            .map(Map.Entry::getKey)
            .toList();

        System.out.println(totalByCategory.get("sách") + " " + totalByCategory.get("đồ ăn")); // prints: 480 300
        System.out.println(top3);                                                              // prints: [An, Bình, Dũng]
    }
}

Giải thích: groupingBy gom các phần tử có cùng key vào một nhóm, còn collector thứ hai (downstream) quyết định mỗi nhóm được thu gọn thành gì, ở đây là tổng amount. Câu 2 làm hai bước: gom thành map "khách hàng → tổng chi", rồi stream lại các entry của map để sort giảm dần và lấy 3 phần tử đầu.

• Chạy tay với các đơn (An, sách, 100), (Bình, sách, 300), (An, đồ ăn, 250), (Chi, đồ ăn, 50), (Dũng, sách, 80): câu 1 cho {sách=480, đồ ăn=300}; câu 2 gom được {An=350, Bình=300, Chi=50, Dũng=80}, sort giảm dần và lấy 3 cho [An, Bình, Dũng].
• Vì sao phải viết Map.Entry.<String, Long>comparingByValue(): khi nối thêm .reversed(), Java không suy ra được kiểu generic từ ngữ cảnh nữa và báo lỗi biên dịch, nên phải chỉ rõ kiểu.
• Edge case: orders rỗng thì cả hai kết quả rỗng; ít hơn 3 khách thì limit(3) trả ít hơn 3; hai khách bằng tiền nhau thì thứ tự giữa họ không xác định (map gốc là HashMap), cần thêm thenComparing(Map.Entry::getKey) nếu đề yêu cầu ổn định.

Hai câu tiếp theo cũng rất hay gặp: đếm số lần xuất hiện của mỗi từ trong một đoạn văn bản text, và chia danh sách đơn thành hai nhóm theo giá trị.

import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;

public class StreamQueries2 {
    record Order(String customer, String category, long amount) {}

    public static void main(String[] args) {
        // Sample input (the same shape as in the previous block)
        String text = "  to be or not to be ";
        List<Order> orders = List.of(
            new Order("An", "book", 1200), new Order("Binh", "toy", 300), new Order("An", "toy", 800));

        // 3. Word frequency
        Map<String, Long> wordCount = Arrays.stream(text.trim().split("\\s+")) // trim first to avoid a leading empty token
            .collect(Collectors.groupingBy(Function.identity(), Collectors.counting())); // word -> count

        // 4. Split into 2 groups: orders >= 1000 and small orders
        Map<Boolean, List<Order>> bigOrSmall = orders.stream()
            .collect(Collectors.partitioningBy(o -> o.amount() >= 1000)); // always has both keys true/false

        System.out.println(wordCount.get("to") + " " + wordCount.get("or"));                      // prints: 2 1
        System.out.println(bigOrSmall.get(true).size() + " " + bigOrSmall.get(false).size());     // prints: 1 2
    }
}

Giải thích: câu 3 tách chuỗi theo một hoặc nhiều khoảng trắng, rồi gom theo chính từ đó (Function.identity()) và đếm số phần tử mỗi nhóm. Câu 4 là trường hợp đặc biệt của gom nhóm với key chỉ có hai giá trị.

• Chạy tay text = " to be or not to be ": sau trim và split được [to, be, or, not, to, be], kết quả {to=2, be=2, or=1, not=1}. Nếu bỏ trim, khoảng trắng ở đầu chuỗi sinh ra một phần tử rỗng "" và bị đếm như một từ.
• Edge case: text rỗng thì "".split("\\s+") trả về mảng một phần tử rỗng, kết quả là {""=1} chứ không phải map rỗng, nên kiểm tra isBlank() trước; "To" và "to" bị đếm là hai từ khác nhau nếu không chuẩn hóa về chữ thường. Với câu 4, khác groupingBy, partitioningBy luôn trả về đủ hai key true và false, kể cả khi một nhóm rỗng, nên đọc bigOrSmall.get(true) không bao giờ bị null.

Độ phức tạp: bước gom nhóm O(n), bước sort để lấy top N là O(k log k) với k là số khách hàng. Nếu k rất lớn mà N nhỏ, có thể dùng PriorityQueue kích thước N để còn O(k log N).

Bẫy thường gặp

Hai lỗi hay gặp: dùng Collectors.toMap khi key có thể trùng mà không truyền hàm merge (ném IllegalStateException), và tách từ bằng split("\\W+") với văn bản tiếng Việt, vì \W coi chữ có dấu là ký tự phân tách. Ngoài ra, .toList() (Java 16+) trả về list không sửa được, khác với Collectors.toList(); biết điểm này là cộng điểm.

12.11 Bài SQL trên giấy

Nhắc lại kiến thức

Thứ tự thực thi logic của một câu SELECT: FROM/JOIN, WHERE, GROUP BY, HAVING, window function, SELECT, ORDER BY, LIMIT. Vì vậy WHERE không nhìn thấy kết quả của window function hay alias đặt trong SELECT. GROUP BY, HAVING và các bài SQL kinh điển mức cơ bản xem N2.2, N2.3; window function và index xem mục 6.1, 6.2.

Hầu hết vòng phỏng vấn backend tại Việt Nam có ít nhất một câu SQL viết tay. Ba bài kinh điển là lương cao thứ hai, top N mỗi nhóm và tìm/xóa bản ghi trùng. Ở mức 2–4 năm, tôi kỳ vọng bạn dùng được window function (MySQL 8+, PostgreSQL, Oracle, SQL Server đều hỗ trợ).

Ba câu đầu dưới đây làm việc trên bảng employee(id, name, department_id, salary).

-- 2nd highest salary: NULL if none, unaffected by ties at the top
SELECT MAX(salary) AS second_highest
FROM employee
WHERE salary < (SELECT MAX(salary) FROM employee);  -- drop every row equal to the max

-- General form for the Nth highest salary
SELECT DISTINCT salary
FROM (SELECT salary, DENSE_RANK() OVER (ORDER BY salary DESC) AS rnk FROM employee) t
WHERE rnk = 2;  -- replace 2 with N

-- Top 3 salary levels per department
SELECT department_id, name, salary
FROM (
  SELECT e.*, DENSE_RANK() OVER (PARTITION BY department_id ORDER BY salary DESC) AS rnk  -- rank restarts in each department
  FROM employee e
) t
WHERE rnk <= 3;

Giải thích: câu 1 loại toàn bộ những người có mức lương cao nhất rồi lấy MAX của phần còn lại. Câu 2 và 3 dùng window function: DENSE_RANK() gán hạng cho từng dòng mà không gom dòng lại như GROUP BY, còn PARTITION BY làm việc xếp hạng bắt đầu lại từ 1 ở mỗi phòng ban. Không lọc rnk trực tiếp trong WHERE được vì WHERE chạy trước window function, nên phải bọc trong subquery t.

• Chạy tay với dữ liệu: phòng 1 có A = 100, B = 100, C = 90; phòng 2 có D = 80. Câu 1: MAX là 100, còn lại 90 và 80, trả 90. Câu 2: hạng lần lượt 1, 1, 2, 3 nên rnk = 2 là 90; DISTINCT cần thiết khi nhiều người cùng mức lương đó. Câu 3: phòng 1 có A, B hạng 1, C hạng 2; phòng 2 có D hạng 1; cả 4 dòng đều thỏa rnk <= 3.
• Lưu ý "top 3 mức lương" với DENSE_RANK có thể trả nhiều hơn 3 người mỗi phòng khi có người bằng lương; nếu đề muốn đúng 3 người thì đổi sang ROW_NUMBER.
• Độ phức tạp: window function cần sort theo phân vùng, cỡ O(n log n); index (department_id, salary) giúp DB tránh bước sort.
• Edge case: bảng rỗng hoặc mọi người cùng lương thì câu 1 trả một dòng NULL, câu 2 trả rỗng. Cột salary có NULL: MAX bỏ qua NULL, nhưng PostgreSQL xếp NULL lên đầu khi ORDER BY ... DESC nên NULL sẽ chiếm hạng 1; thêm WHERE salary IS NOT NULL hoặc NULLS LAST.

Hai câu tiếp theo xử lý bảng users(id, email) bị trùng email do thiếu unique constraint.

-- Find duplicated emails and their counts
SELECT email, COUNT(*) AS cnt
FROM users
GROUP BY email
HAVING COUNT(*) > 1;  -- HAVING filters after grouping

-- Delete duplicates, keep the smallest id
DELETE FROM users
WHERE id IN (
  SELECT id FROM (
    SELECT id, ROW_NUMBER() OVER (PARTITION BY email ORDER BY id) AS rn FROM users  -- smallest id gets rn = 1
  ) t
  WHERE rn > 1  -- every other copy
);

Giải thích: câu tìm trùng gom theo email và chỉ giữ nhóm có hơn một dòng. Câu xóa đánh số các dòng trong cùng một email theo id tăng dần; dòng số 1 được giữ, các dòng số 2 trở đi bị xóa. ROW_NUMBER là lựa chọn đúng ở đây vì nó luôn đánh số liên tiếp, không bao giờ có hai dòng cùng số như RANK.

• Chạy tay: users có (1, a@x), (2, b@x), (3, a@x), (4, a@x). Câu tìm trùng trả a@x | 3. Trong câu xóa, a@x được đánh số id 1 là 1, id 3 là 2, id 4 là 3; b@x có id 2 là 1. Các id 3 và 4 bị xóa, bảng còn id 1 và 2.
• Subquery bọc hai lớp (SELECT id FROM (...) t) không thừa: MySQL không cho DELETE một bảng mà subquery lại đọc trực tiếp từ chính bảng đó (lỗi 1093), bọc thêm một lớp derived table là cách vượt qua. PostgreSQL không cần nhưng viết vậy vẫn chạy.
• Độ phức tạp: sort theo (email, id) cỡ O(n log n); có index trên email thì nhanh hơn nhiều.
• Edge case: email khác nhau chỉ ở chữ hoa, chữ thường (A@x và a@x) cần PARTITION BY LOWER(email) nếu nghiệp vụ coi là trùng; email NULL bị gom chung một nhóm trong cả GROUP BY lẫn PARTITION BY, nên câu xóa sẽ xóa hết các dòng email NULL trừ một dòng, cần thêm WHERE email IS NOT NULL trong subquery.

Hàm	Kết quả với lương 100, 100, 90	Khi nào dùng
ROW_NUMBER	1, 2, 3	Cần đúng N dòng, khử trùng
RANK	1, 1, 3	Xếp hạng có nhảy bậc
DENSE_RANK	1, 1, 2	"Mức lương cao thứ N"

Mẹo từ người phỏng vấn

Câu SELECT salary FROM employee ORDER BY salary DESC LIMIT 1 OFFSET 1 sai khi hai người cùng lương cao nhất. Hãy chủ động nói ra edge case này trước khi người phỏng vấn hỏi. Và khi viết DELETE, nói thêm "trên production em sẽ chạy câu SELECT trước để đếm số dòng, làm trong transaction, sau đó thêm unique constraint để trùng không quay lại". Đó là câu trả lời của người đã từng làm thật.

12.12 Bài concurrency nhỏ

Nhắc lại kiến thức

Mỗi object Java có một "monitor" (khóa ngầm): synchronized chiếm khóa đó, wait() nhả khóa và ngủ, notify/notifyAll đánh thức thread đang chờ trên cùng object (xem N1.13 và mục 3.4). BlockingQueue, Semaphore, CountDownLatch là các công cụ đồng bộ dựng sẵn trong java.util.concurrent, xem mục 3.8. Race condition và vì sao count++ không an toàn xem mục 3.3, 3.4.

Bài đa luồng trong live coding thường ngắn, nhưng lộ rất rõ bạn hiểu wait/notify, BlockingQueue và interrupt tới đâu. Hai bài phổ biến nhất là producer-consumer và in số chẵn lẻ bằng hai thread.

Producer-consumer: đừng tự viết bằng wait/notify trừ khi bị yêu cầu. BlockingQueue đã xử lý toàn bộ việc chờ và đánh thức.

import java.util.concurrent.*;

public class ProducerConsumer {
    private static final int POISON = -1; // "poison pill": end-of-data signal

    public static void main(String[] args) throws InterruptedException {
        BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(10); // bounded -> back-pressure
        Thread producer = new Thread(() -> {
            try {
                for (int i = 1; i <= 20; i++) queue.put(i); // put() blocks when full
                queue.put(POISON);
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt(); // restore the interrupt flag, do not swallow it
            }
        });
        Thread consumer = new Thread(() -> {
            try {
                while (true) {
                    int item = queue.take(); // take() blocks when empty
                    if (item == POISON) break;
                    System.out.println("Xử lý " + item);
                }
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        });
        producer.start(); consumer.start();
        producer.join(); consumer.join(); // main waits for both to finish
    }
}

Giải thích: hàng đợi có giới hạn là điểm hẹn giữa hai thread: producer nhanh hơn thì bị chặn ở put() khi đầy (back-pressure tự nhiên, không tràn bộ nhớ), consumer nhanh hơn thì bị chặn ở take() khi rỗng. Mọi việc khóa, chờ và đánh thức đã nằm trong ArrayBlockingQueue, nên code không có synchronized hay wait/notify nào.

• Chạy tay: producer đẩy 1..10 thì queue đầy và producer dừng ở put(11); consumer lấy 1 ra in "Xử lý 1", queue có chỗ trống nên producer đẩy tiếp 11. Cứ thế đến khi consumer in "Xử lý 20" rồi lấy được POISON, thoát vòng lặp; join() trả về và chương trình kết thúc. Thứ tự in luôn là 1 đến 20 vì queue là FIFO.
• Vì sao cần poison pill: nếu không có tín hiệu kết thúc, consumer sẽ nằm chờ mãi ở take() sau phần tử cuối và consumer.join() không bao giờ trả về.
• Độ phức tạp: O(n) với n là số phần tử; bộ nhớ O(capacity) = 10 dù sinh ra bao nhiêu phần tử.
• Edge case: có k consumer thì phải gửi k poison pill, mỗi consumer nhận một; giá trị -1 không được trùng dữ liệu thật; nếu producer chết giữa chừng mà chưa gửi POISON thì consumer treo, nên gửi poison pill trong finally hoặc dùng poll(timeout).

In chẵn lẻ luân phiên: bài này kiểm tra đúng kiến thức monitor. Hai thread cùng khóa trên một object, mỗi thread chờ tới lượt của mình.

public class OddEvenPrinter {
    private static final int MAX = 10;
    private int current = 1; // only accessed inside synchronized, so no volatile needed

    private synchronized void printTurns(boolean odd) {
        try {
            while (current <= MAX) {
                // while, not if: guards against spurious and wrong-turn wakeups
                while (current <= MAX && (current % 2 == 1) != odd) wait();
                if (current > MAX) break;
                System.out.println(Thread.currentThread().getName() + ": " + current++);
                notifyAll(); // wake the other thread
            }
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }

    public static void main(String[] args) throws InterruptedException {
        var printer = new OddEvenPrinter();
        Thread odd = new Thread(() -> printer.printTurns(true), "Odd");
        Thread even = new Thread(() -> printer.printTurns(false), "Even");
        odd.start(); even.start();
        odd.join(); even.join();
    }
}

Giải thích: hai thread dùng chung monitor của object printer. Thread nào chưa tới lượt thì gọi wait(): nhả khóa và ngủ cho tới khi được đánh thức. Thread tới lượt in một số, tăng current, rồi notifyAll() để thread kia dậy kiểm tra lại điều kiện.

• Chạy tay: giả sử thread Even giành được khóa trước; current = 1 là lẻ, chưa tới lượt nên Even wait() và nhả khóa. Odd vào, in "Odd: 1", current = 2, gọi notifyAll(), vòng lặp tiếp theo thấy 2 không phải lượt mình nên wait(). Even dậy, in "Even: 2", và cứ luân phiên như vậy. Sau khi Even in 10, current = 11; Odd dậy, điều kiện current <= MAX ở vòng while trong đã sai nên thoát, gặp break; Even cũng thoát vòng ngoài. Kết quả là Odd: 1, Even: 2, ..., Even: 10 theo đúng thứ tự, bất kể thread nào khởi động trước.
• Vì sao vòng while trong có thêm current <= MAX &&: đây là điều kiện phòng thủ để thread nào bị đánh thức sau khi số cuối đã in đều thoát ra, thay vì quay lại wait() mà không còn ai gọi notifyAll(). Với hai thread chẵn lẻ, thread còn lại luôn thấy "tới lượt mình" nên vẫn thoát được; nhưng khi mở rộng thành ba thread in luân phiên theo số dư khi chia 3, thiếu điều kiện này sẽ có một thread chờ mãi mãi và join() treo.
• Độ phức tạp: O(MAX) lần in, nhưng mỗi lần in kèm một lần chuyển ngữ cảnh giữa hai thread, nên cách làm này chỉ để minh họa cơ chế, không nhanh.
• Edge case: MAX = 0 thì không in gì và cả hai thread kết thúc ngay; bị interrupt thì khôi phục cờ interrupt và thoát.

Câu hỏi đào sâu

"Viết lại bằng cách khác được không?" Dùng hai Semaphore: oddTurn khởi tạo 1 permit, evenTurn khởi tạo 0; thread lẻ acquire oddTurn, in, rồi release evenTurn và ngược lại. Câu hỏi tiếp theo thường là "vì sao gọi wait() ngoài synchronized thì lỗi?": vì thread phải giữ monitor mới được chờ trên nó, nếu không sẽ ném IllegalMonitorStateException. Và "vì sao notifyAll chứ không phải notify?": với hai thread thì notify cũng chạy, nhưng khi có nhiều thread chờ các điều kiện khác nhau, notify có thể đánh thức nhầm thread và gây treo.

12.13 Kế hoạch luyện tập 4–6 tuần

Mục tiêu không phải là số bài thật nhiều, mà là nhận ra dạng trong 2–3 phút đầu và code sạch trong 20–25 phút. Khoảng 60–80 bài easy/medium chọn đúng chủ đề là đủ cho vị trí middle tại phần lớn công ty Việt Nam. Mỗi ngày 2–3 bài, mỗi bài đặt giờ, luôn nói to quy trình 6 bước như đang phỏng vấn thật.

Tuần	Chủ đề	Số bài	Bài gợi ý trên LeetCode
1	Array, String, HashMap	12–15	Two Sum, Valid Anagram, Group Anagrams, First Unique Character
2	Two pointers, Sliding window	10–12	Longest Substring Without Repeating, Container With Most Water
3	Stack, Queue, Sort, Interval	10–12	Valid Parentheses, Merge Intervals, Daily Temperatures
4	Binary search, Heap, Linked list	10–12	Search Insert Position, Top K Frequent, LRU Cache
5	Tree, BFS/DFS	10–12	Number of Islands, Binary Tree Level Order, Max Depth
6	SQL, Stream, Concurrency, ôn lại	10–15	Second Highest Salary, Department Top Three, Print FooBar Alternately

Một vài nguyên tắc để kế hoạch này hiệu quả:

• Kẹt quá 25 phút thì xem lời giải, hiểu rồi đóng lại, 2 ngày sau tự code lại từ đầu. Bài làm lại được mới là bài của bạn.
• Luyện trong editor không có auto-complete ít nhất một nửa số bài, vì nhiều công ty dùng công cụ chia sẻ code không có gợi ý.
• Ghi sổ tay mẫu tư duy: "đoạn con liên tiếp thì sliding window", "top K thì heap", "ngắn nhất không trọng số thì BFS". Trước buổi phỏng vấn chỉ cần đọc lại sổ này.
• Tuần cuối, nhờ bạn bè phỏng vấn thử 2–3 buổi, có người ngồi nghe bạn nói mới lộ ra những lúc bạn im lặng.
• Bài Stream và SQL tự đặt đề từ domain dự án của bạn (đơn hàng, giao dịch, người dùng) sẽ sát thực tế hơn nhiều so với đề mẫu.

12.14 Bài tập tự luyện

Sáu bài dưới đây mỗi bài ứng với một dạng đã học trong chương. Hãy tự làm trước theo quy trình 6 bước ở mục 12.2: nói lại đề, hỏi ràng buộc, chạy tay bằng bảng trạng thái, rồi mới mở đáp án. Mỗi bài nên xong trong 15–20 phút.

Câu hỏi (Thực chiến): Bài tập 1 (HashMap) – Tìm giá trị xuất hiện nhiều nhất trong mảng

Đề: cho mảng số nguyên khác rỗng, trả về giá trị xuất hiện nhiều lần nhất; nếu nhiều giá trị cùng số lần thì trả giá trị nhỏ nhất. Ví dụ [4, 1, 2, 2, 4, 3] trả 2 (2 và 4 cùng xuất hiện 2 lần, 2 nhỏ hơn).

Gợi ý: đếm tần suất bằng Map.merge, sau đó duyệt map một lượt để chọn; đừng quên luật hòa.

Đáp án:

Đếm tần suất một lượt O(n), rồi duyệt map một lượt O(k) để chọn giá trị tốt nhất theo hai tiêu chí: số lần giảm dần, giá trị tăng dần.

import java.util.*;

public class MostFrequent {
    static int mostFrequent(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : nums) freq.merge(x, 1, Integer::sum); // value -> count
        int best = nums[0];
        for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
            int value = e.getKey(), count = e.getValue(), bestCount = freq.get(best);
            if (count > bestCount || (count == bestCount && value < best)) best = value; // tie: smaller wins
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(mostFrequent(new int[]{4, 1, 2, 2, 4, 3})); // prints: 2
        System.out.println(mostFrequent(new int[]{7}));                // prints: 7
    }
}

Giải thích: sau lượt đếm, map là {1=1, 2=2, 3=1, 4=2}. Lượt chọn so từng entry với best: giá trị 2 và 4 cùng 2 lần, luật hòa giữ 2. Vì HashMap không có thứ tự, luật hòa phải nằm trong điều kiện so sánh chứ không được dựa vào "gặp trước". Độ phức tạp O(n) thời gian, O(k) bộ nhớ với k là số giá trị khác nhau. Mảng rỗng sẽ ném ArrayIndexOutOfBoundsException ở nums[0], nên hỏi đề và kiểm tra trước nếu cần.

Câu hỏi (Thực chiến): Bài tập 2 (Sliding window) – Tổng lớn nhất của k phần tử liên tiếp

Đề: cho mảng số nguyên và số k (1 ≤ k ≤ độ dài mảng), tìm tổng lớn nhất của một đoạn gồm đúng k phần tử liên tiếp. Ví dụ [2, 1, 5, 1, 3, 2], k = 3 trả 9 (đoạn 5, 1, 3).

Gợi ý: brute-force tính lại tổng mỗi đoạn tốn O(n·k). Khi cửa sổ trượt một ô, chỉ có một phần tử vào và một phần tử ra.

Đáp án:

Cửa sổ kích thước cố định: tính tổng k phần tử đầu, sau đó mỗi bước cộng phần tử mới vào và trừ phần tử rời cửa sổ, O(n) thời gian, O(1) bộ nhớ.

public class MaxWindowSum {
    static int maxWindowSum(int[] a, int k) {
        int sum = 0;
        for (int i = 0; i < k; i++) sum += a[i]; // first window
        int best = sum;
        for (int right = k; right < a.length; right++) {
            sum += a[right] - a[right - k]; // add the new element, drop the oldest
            best = Math.max(best, sum);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(maxWindowSum(new int[]{2, 1, 5, 1, 3, 2}, 3)); // prints: 9
    }
}

Giải thích: bảng chạy tay:

right	Vào, ra	sum sau bước	best
khởi tạo	2, 1, 5	8	8
3	vào 1, ra 2	7	8
4	vào 3, ra 1	9	9
5	vào 2, ra 5	6	9

Khác bài 12.5 ở chỗ cửa sổ luôn dài đúng k, nên left không cần biến riêng mà luôn là right - k + 1. Hỏi thêm đề: tổng có thể vượt int không (nếu có thì dùng long), mảng có số âm không (thuật toán vẫn đúng).

Câu hỏi (Thực chiến): Bài tập 3 (Stack) – Bao nhiêu ngày nữa thì ấm hơn

Đề: cho mảng nhiệt độ theo ngày, với mỗi ngày trả về số ngày phải chờ tới ngày đầu tiên ấm hơn; không có thì 0. Ví dụ [73, 74, 75, 71, 69, 72, 76, 73] trả [1, 1, 4, 2, 1, 1, 0, 0].

Gợi ý: đây là dạng "phần tử lớn hơn kế tiếp". Giữ một stack các ngày đang chờ ngày ấm hơn; một ngày mới ấm hơn sẽ "giải quyết" các ngày trên đỉnh stack.

Đáp án:

Monotonic stack: stack chứa chỉ số các ngày chưa tìm được ngày ấm hơn, nhiệt độ giảm dần từ đáy lên đỉnh; mỗi chỉ số vào và ra stack đúng một lần nên O(n).

import java.util.*;

public class DailyTemperatures {
    static int[] daysUntilWarmer(int[] t) {
        int[] ans = new int[t.length];
        Deque<Integer> stack = new ArrayDeque<>(); // indices still waiting for a warmer day
        for (int i = 0; i < t.length; i++) {
            while (!stack.isEmpty() && t[stack.peek()] < t[i]) {
                int j = stack.pop();
                ans[j] = i - j; // day i is the first warmer day after j
            }
            stack.push(i);
        }
        return ans; // indices left in the stack keep the default 0
    }

    public static void main(String[] args) {
        int[] t = {73, 74, 75, 71, 69, 72, 76, 73};
        System.out.println(Arrays.toString(daysUntilWarmer(t))); // prints: [1, 1, 4, 2, 1, 1, 0, 0]
    }
}

Giải thích: chạy tay vài bước: i = 2 (75) đẩy vào; i = 3 (71), i = 4 (69) lạnh hơn nên chỉ đẩy vào, stack (đỉnh bên trái) là 4 3 2; i = 5 (72) ấm hơn 69 và 71 nên pop 4 (ans = 1), pop 3 (ans = 2), dừng ở 75, đẩy 5; i = 6 (76) pop 5 (ans = 1) và pop 2 (ans = 4). Brute-force hai vòng for là O(n^2); vòng while bên trong trông như lồng nhau nhưng tổng số lần pop của cả chương trình không vượt quá n.

Câu hỏi (Thực chiến): Bài tập 4 (Sort + merge) – Tổng số phút phòng họp bị chiếm

Đề: cho danh sách cuộc họp [start, end) tính bằng phút, có thể chồng nhau, tính tổng số phút phòng có ít nhất một cuộc họp. Ví dụ [[10,30],[20,40],[50,60]] trả 40.

Gợi ý: đừng cộng thẳng độ dài từng cuộc họp (sẽ đếm trùng 10 phút từ 20 tới 30). Gộp các khoảng chồng lấn trước, như mục 12.7.

Đáp án:

Sort theo start, gộp khoảng chồng lấn, cộng độ dài các khoảng sau gộp; O(n log n) do bước sort.

import java.util.*;

public class BusyMinutes {
    static int busyMinutes(int[][] meetings) {
        if (meetings.length == 0) return 0;
        int[][] sorted = meetings.clone();
        Arrays.sort(sorted, Comparator.comparingInt(m -> m[0]));
        int total = 0, curStart = sorted[0][0], curEnd = sorted[0][1];
        for (int i = 1; i < sorted.length; i++) {
            if (sorted[i][0] < curEnd) {             // [start, end): touching is not overlapping
                curEnd = Math.max(curEnd, sorted[i][1]);
            } else {
                total += curEnd - curStart;          // close the merged block
                curStart = sorted[i][0];
                curEnd = sorted[i][1];
            }
        }
        return total + (curEnd - curStart);          // the last block
    }

    public static void main(String[] args) {
        System.out.println(busyMinutes(new int[][]{{10, 30}, {20, 40}, {50, 60}})); // prints: 40
    }
}

Giải thích: hai khoảng đầu gộp thành [10,40) dài 30 phút, khoảng [50,60) dài 10 phút, tổng 40. Vì đề dùng nửa khoảng [start, end), hai cuộc họp [10,20) và [20,30) chỉ chạm nhau, điều kiện dùng < thay vì <=; cả hai cách đều ra cùng tổng số phút, nhưng nói ra được lựa chọn này cho thấy bạn đọc đề kỹ. Không cần lưu danh sách khoảng đã gộp, chỉ cần cộng dồn, nên bộ nhớ phụ chỉ là bản sao mảng.

Câu hỏi (Thực chiến): Bài tập 5 (Binary search) – Căn bậc hai nguyên không dùng Math.sqrt

Đề: cho số nguyên x ≥ 0, trả về phần nguyên của căn bậc hai. Ví dụ x = 8 trả 2, x = 16 trả 4, x = 2147483647 trả 46340.

Gợi ý: binary search trên không gian đáp án (mục 12.7, callout DEEP). Điều kiện m * m > x có tính đơn điệu: sai, sai, ..., đúng, đúng. Cẩn thận tràn số khi nhân.

Đáp án:

Dùng khuôn lower bound tìm số m nhỏ nhất có m * m > x, đáp án là m - 1; tính bằng long để mid * mid không tràn int. O(log x).

public class IntSqrt {
    static int intSqrt(int x) {
        long lo = 0, hi = (long) x + 1; // first m with m*m > x lies in [lo, hi]
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (mid * mid <= x) lo = mid + 1; // mid is still small enough
            else hi = mid;
        }
        return (int) (lo - 1);
    }

    public static void main(String[] args) {
        System.out.println(intSqrt(8));                 // prints: 2
        System.out.println(intSqrt(16));                // prints: 4
        System.out.println(intSqrt(0));                 // prints: 0
        System.out.println(intSqrt(Integer.MAX_VALUE)); // prints: 46340
    }
}

Giải thích: với x = 8, các số 0, 1, 2 có bình phương ≤ 8, số 3 có bình phương 9 > 8, nên m = 3 và đáp án 2. Nếu dùng int cho mid, với x gần Integer.MAX_VALUE thì mid * mid tràn thành số âm, điều kiện <= x đúng sai lung tung và kết quả sai. hi là x + 1 cũng phải tính bằng long vì Integer.MAX_VALUE + 1 tràn. Đây là ca biên mà người phỏng vấn gần như chắc chắn sẽ hỏi.

Câu hỏi (Thực chiến): Bài tập 6 (BFS) – Đếm số đảo

Đề: cho lưới 0/1, 1 là đất, 0 là nước; các ô đất nối nhau theo 4 hướng tạo thành một đảo. Đếm số đảo. Ví dụ lưới dưới đây có 3 đảo.

1 1 0 0
1 0 0 1
0 0 1 1
1 0 0 0

Gợi ý: duyệt từng ô; gặp ô đất chưa thăm thì tăng đếm và chạy BFS "loang" đánh dấu cả đảo đó là đã thăm.

Đáp án:

Mỗi lần gặp ô đất chưa thăm là gặp một đảo mới; BFS từ ô đó đánh dấu toàn bộ đảo để không đếm lại. Mỗi ô được xử lý một lần nên O(m·n).

import java.util.*;

public class CountIslands {
    static int countIslands(int[][] grid) {
        int m = grid.length, n = grid[0].length, islands = 0;
        boolean[][] visited = new boolean[m][n];
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0 || visited[i][j]) continue;
                islands++; // new island found, flood it
                Deque<int[]> queue = new ArrayDeque<>();
                queue.offer(new int[]{i, j});
                visited[i][j] = true;
                while (!queue.isEmpty()) {
                    int[] cur = queue.poll();
                    for (int[] d : dirs) {
                        int r = cur[0] + d[0], c = cur[1] + d[1];
                        if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c] || grid[r][c] == 0) continue;
                        visited[r][c] = true;
                        queue.offer(new int[]{r, c});
                    }
                }
            }
        }
        return islands;
    }

    public static void main(String[] args) {
        int[][] grid = {{1, 1, 0, 0}, {1, 0, 0, 1}, {0, 0, 1, 1}, {1, 0, 0, 0}};
        System.out.println(countIslands(grid)); // prints: 3
    }
}

Giải thích: duyệt theo hàng: ô (0,0) là đất mới, đếm 1, BFS đánh dấu (0,0), (1,0), (0,1). Tiếp theo ô (1,3) là đất mới, đếm 2, BFS đánh dấu (1,3), (2,3), (2,2). Cuối cùng ô (3,0) đứng riêng, đếm 3. Ô (2,2) và (1,3) chỉ nối qua (2,3) nhưng vẫn cùng một đảo, đó là lý do phải loang chứ không chỉ nhìn ô kề trực tiếp. Dùng DFS đệ quy cũng được, nhưng với lưới lớn có rủi ro StackOverflowError như callout ở mục 12.8. Nếu được phép sửa input, có thể ghi đè ô đã thăm thành 0 thay cho mảng visited, nhưng phải hỏi trước.

12.15 Câu hỏi phỏng vấn thường gặp

Các câu dưới đây nhóm theo chủ đề: Big-O và quy trình, giải thuật, SQL, concurrency, và cách nói to khi code.

Câu hỏi (Cơ bản): Big-O là gì, vì sao khi tính lại được bỏ hằng số?

Big-O mô tả số bước (hoặc bộ nhớ) tăng nhanh cỡ nào khi kích thước đầu vào n tăng, không đo thời gian tuyệt đối.

• Bỏ hằng số vì khi n rất lớn, hình dạng tăng trưởng quyết định tất cả: thuật toán 5n bước với n = 1 triệu là 5 triệu bước, còn n^2 là 10^12 bước; hệ số 5 không làm thay đổi kết luận.
• Tuy vậy, hằng số vẫn có ý nghĩa thực tế khi n nhỏ hoặc khi hai thuật toán cùng Big-O: mảng int[26] và HashMap cùng O(1) cho mỗi lần tra nhưng mảng nhanh hơn nhiều vì không phải tính hash hay boxing.
• Nên nói kèm cả trường hợp: trung bình (HashMap O(1)) và xấu nhất (O(log n) khi bucket treeify).

Câu hỏi (Cơ bản): "O(1) khấu hao" của ArrayList.add nghĩa là gì?

Phần lớn các lần add tốn O(1), thỉnh thoảng một lần tốn O(n) để copy sang mảng lớn hơn, nhưng tính trung bình trên nhiều lần add thì mỗi lần vẫn là hằng số.

ArrayList giãn mảng lên khoảng 1,5 lần mỗi khi đầy. Với n lần add, tổng số phần tử phải copy qua mọi lần giãn chỉ cỡ vài lần n, chia cho n lần add thì mỗi lần tốn hằng số. Hệ quả thực tế: nếu biết trước kích thước (ví dụ map 10.000 dòng từ DB sang DTO), khởi tạo new ArrayList<>(10_000) để tránh giãn nhiều lần.

Câu hỏi đào sâu

"Vậy có lần add nào chậm bất thường không?" Có, lần add kích hoạt giãn mảng tốn O(n); với list rất lớn, lần đó có thể tạo một mảng mới hàng trăm MB và gây áp lực lên GC. Đây là lý do với hệ thống nhạy độ trễ, người ta cấp sẵn capacity.

Câu hỏi (Cơ bản): Trước khi code một bài live coding, bạn cần hỏi những gì?

Hỏi về dữ liệu vào, dữ liệu ra và kích thước: input có rỗng, null, trùng, âm không; không có đáp án thì trả gì; n cỡ bao nhiêu.

• Dữ liệu vào: mảng rỗng, null, phần tử trùng, số âm, chuỗi có chữ hoa hoặc Unicode không.
• Dữ liệu ra: trả index hay giá trị, nhiều đáp án thì trả cái nào, không có thì trả -1, mảng rỗng hay ném exception.
• Kích thước: n cỡ nghìn hay chục triệu, dữ liệu có vừa bộ nhớ không; điều này quyết định O(n^2) có chấp nhận được không.
• Nói to các giả định nếu người phỏng vấn bảo "em tự quyết": "Em giả định input không null và chỉ có chữ thường a-z".

Câu hỏi (Cơ bản): Khi nào dùng mảng int[26] thay cho HashMap để đếm ký tự?

Khi tập ký tự nhỏ, biết trước và liên tục (chữ thường a-z); ngoài ra thì dùng HashMap.

int[26] nhanh hơn (truy cập mảng trực tiếp, không boxing Character/Integer, không tính hash) và bộ nhớ cố định O(1). Nhưng nó ném ArrayIndexOutOfBoundsException ngay khi gặp chữ hoa, chữ số hay chữ có dấu tiếng Việt, vì 'A' - 'a' là số âm và 'ă' - 'a' vượt 25. Với ASCII mở rộng có thể dùng int[128] hoặc int[256]; với Unicode tổng quát thì dùng HashMap<Integer, Integer> theo code point.

Câu hỏi (Cơ bản): Vì sao không lọc được rnk của window function trong mệnh đề WHERE cùng cấp?

Vì WHERE được thực thi trước khi window function được tính, nên tại thời điểm lọc cột rnk chưa tồn tại; phải bọc trong subquery hoặc CTE rồi lọc ở tầng ngoài.

-- Fails: column "rnk" does not exist at WHERE time
SELECT name, DENSE_RANK() OVER (ORDER BY salary DESC) AS rnk
FROM employee
WHERE rnk = 2;

-- Works: compute in a CTE, filter outside
WITH ranked AS (
  SELECT name, salary, DENSE_RANK() OVER (ORDER BY salary DESC) AS rnk
  FROM employee
)
SELECT name, salary FROM ranked WHERE rnk = 2;

Giải thích: câu đầu báo lỗi cột không tồn tại (PostgreSQL: column "rnk" does not exist, MySQL: Unknown column 'rnk' in 'where clause'). Câu thứ hai tính hạng trong CTE ranked, sau đó truy vấn ngoài coi ranked như một bảng bình thường nên lọc rnk được. CTE và subquery trong FROM tương đương nhau ở đây, CTE dễ đọc hơn khi viết trên giấy. Một số hệ quản trị (Snowflake, BigQuery, DuckDB) có mệnh đề QUALIFY để lọc trực tiếp, nhưng MySQL và PostgreSQL chưa có, nên đừng dùng khi đề không nói rõ DB.

Câu hỏi (Hiểu sâu): Sliding window có vòng lặp của right và left cùng di chuyển, vì sao vẫn là O(n) chứ không phải O(n^2)?

Vì cả hai con trỏ chỉ đi về phía trước và không bao giờ vượt quá n, nên tổng số lần di chuyển của cả hai tối đa là 2n.

Cách đếm đúng là đếm tổng số bước của từng con trỏ trong cả chương trình, không phải nhân số vòng ngoài với số bước tối đa của vòng trong. right đi đúng n bước. left có thể có lúc nhảy nhiều ô trong một vòng (như ở bảng chạy tay mục 12.5), nhưng tổng quãng nó đi cũng không quá n. Cách lập luận này (amortized analysis) áp dụng cho cả monotonic stack ở bài tập 3: mỗi phần tử push một lần, pop tối đa một lần.

Bẫy thường gặp

Nếu mỗi lần co cửa sổ bạn lại tạo substring mới hoặc quét lại cả cửa sổ để kiểm tra điều kiện, độ phức tạp thật sẽ là O(n·k) hoặc O(n^2) dù code "trông như" sliding window. Trạng thái cửa sổ phải được cập nhật tăng dần bằng map hoặc biến đếm.

Câu hỏi (Hiểu sâu): Vì sao BFS tìm được đường ngắn nhất trên lưới còn DFS thì không?

Vì BFS xử lý các ô theo đúng thứ tự khoảng cách tăng dần, nên lần đầu gặp ô đích là qua đường ngắn nhất; DFS đi sâu theo một hướng nên có thể tới đích bằng đường vòng trước.

Queue của BFS luôn chứa các ô có khoảng cách d hoặc d + 1, không bao giờ lẫn xa hơn (xem cột "Queue sau lượt" ở bảng chạy tay mục 12.8). DFS muốn tìm đường ngắn nhất phải duyệt hết mọi đường và so sánh, tốn hàm mũ trong trường hợp xấu. Lưu ý điều này chỉ đúng khi mọi cạnh có cùng trọng số (mỗi bước tốn 1); nếu các bước có chi phí khác nhau (đường cao tốc và đường làng), phải dùng Dijkstra với PriorityQueue.

Câu hỏi (Hiểu sâu): Trong LRU tự cài, vì sao cần danh sách liên kết đôi và vì sao Node phải lưu cả key?

Liên kết đôi cho phép gỡ một node bất kỳ khỏi danh sách trong O(1) khi đã có tham chiếu tới nó (từ HashMap); lưu key để khi evict node cuối danh sách còn biết xóa entry nào khỏi HashMap.

• Với danh sách liên kết đơn, muốn gỡ node X phải biết node đứng trước X, mà tìm node đó tốn O(n). Liên kết đôi có sẵn prev, nên unlink chỉ là gán lại hai con trỏ.
• Khi cache đầy, ta lấy node sát tail; lúc đó ta chỉ có node, không có key, nên node phải mang key để gọi map.remove(node.key). Quên điều này là lỗi rất hay gặp khi code trên giấy.
• ArrayList không dùng được vì xóa ở giữa là O(n).

Câu hỏi (Hiểu sâu): Vì sao phải gọi wait() trong vòng while chứ không dùng if?

Vì thread có thể thức dậy khi điều kiện vẫn chưa đúng: spurious wakeup (JVM cho phép thức dậy không lý do), hoặc bị notifyAll đánh thức cùng lúc với thread khác và thread kia đã giành lượt trước.

Với if, thread thức dậy và làm tiếp mà không kiểm tra lại, dẫn tới in sai lượt hoặc lấy phần tử từ queue đã rỗng. Với while, sau mỗi lần thức dậy thread kiểm tra lại điều kiện, chưa tới lượt thì ngủ tiếp. Đây là quy tắc được ghi rõ trong Javadoc của Object.wait(). Trong bài in chẵn lẻ ở mục 12.12, hai thread dùng chung notifyAll, nên thread vừa in xong cũng có thể được đánh thức bởi chính lời gọi của thread kia ở vòng sau và cần kiểm tra lại lượt.

Câu hỏi (Hiểu sâu): Producer-consumer có 3 consumer thì poison pill cần thay đổi gì?

Producer phải gửi đúng 3 poison pill, mỗi consumer nhận một viên rồi thoát; nếu chỉ gửi một viên, một consumer thoát còn hai consumer kia treo mãi ở take().

• Cách khác: consumer nhận poison pill thì đặt lại nó vào queue trước khi thoát để consumer kế tiếp cũng nhận được; cách này không cần biết trước số consumer.
• Trong code thực tế với ExecutorService, thường dùng shutdown() cùng poll(timeout) kiểm tra cờ dừng, hoặc shutdownNow() để interrupt các consumer đang chờ.
• Giá trị poison pill phải không trùng dữ liệu thật; với object, dùng một hằng static final và so sánh bằng ==.

Câu hỏi (Hiểu sâu): Top 3 khách hàng từ một map có hàng triệu khách, sort toàn bộ hay dùng PriorityQueue?

Với N nhỏ (3, 10) và k rất lớn, PriorityQueue (min-heap) giữ N phần tử cho O(k log N), tốt hơn sort toàn bộ O(k log k) và không cần copy cả tập ra list.

Ý tưởng: duyệt từng khách, đưa vào heap; khi heap vượt N phần tử thì bỏ phần tử nhỏ nhất ở đỉnh. Cuối cùng heap chứa N khách lớn nhất (thứ tự trong heap chưa sort, cần sort lại N phần tử). Với k = 1 triệu, N = 3: sort cần khoảng 20 triệu phép so sánh, heap cần khoảng 1,6 triệu. Tuy vậy, khi k chỉ vài nghìn, cách Stream sorted().limit(3) ở mục 12.10 dễ đọc hơn và đủ nhanh; nói được trade-off này mới là điểm cộng. Trong production, top N trên dữ liệu lớn nên đẩy xuống DB bằng ORDER BY ... LIMIT có index.

Câu hỏi (Đọc code): Hàm khử trùng dưới đây có độ phức tạp bao nhiêu, sửa thế nào?

static List<Integer> dedupe(List<Integer> input) {
    List<Integer> result = new ArrayList<>();
    for (Integer x : input) {
        if (!result.contains(x)) result.add(x);
    }
    return result;
}

Đáp án:

O(n^2) trong trường hợp xấu nhất, vì result.contains(x) quét tuyến tính cả list kết quả cho mỗi phần tử; sửa bằng LinkedHashSet hoặc thêm một HashSet phụ để còn O(n).

• Với n = 1.000 phần tử khác nhau, số lần so sánh cỡ 500.000; với n = 1.000.000 là cỡ 5 × 10^11, tức hàm "chạy đúng" trên dữ liệu test nhưng treo trên production.
• Cách sửa giữ nguyên thứ tự xuất hiện: return new ArrayList<>(new LinkedHashSet<>(input));. Hoặc giữ vòng lặp nhưng thêm Set<Integer> seen = new HashSet<>() và kiểm tra seen.add(x) (trả false khi đã có).
• Code không có lỗi đúng đắn: contains dùng equals nên Integer so sánh đúng giá trị. Nếu phần tử là object tự định nghĩa, cả hai cách đều yêu cầu equals/hashCode đúng (xem N1.9).

Câu hỏi (Đọc code): Binary search dưới đây sai ở edge case nào?

static int lowerBound(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (nums[mid] < target) lo = mid;
        else hi = mid;
    }
    return lo;
}

Đáp án:

Có ba lỗi: lo = mid gây vòng lặp vô hạn khi khoảng còn hai phần tử, hi = nums.length - 1 khiến không bao giờ trả được nums.length khi mọi phần tử nhỏ hơn target, và mảng rỗng trả 0 như thể có đáp án.

• Vòng lặp vô hạn: nums = [1, 3], target = 3. lo = 0, hi = 1, mid = 0, nums[0] = 1 < 3 nên lo = mid = 0; trạng thái không đổi và lặp mãi. Quy tắc: nhánh nào loại mid thì phải là mid + 1 hoặc mid - 1, nếu không khoảng không thu hẹp.
• Biên phải: nums = [1, 2], target = 5 phải trả 2 (không có phần tử ≥ 5), nhưng code chỉ có thể trả tối đa 1. Nên dùng nửa khoảng [0, nums.length) như khuôn ở mục 12.7.
• (lo + hi) / 2 tràn số khi lo và hi gần Integer.MAX_VALUE; ít gặp với mảng nhưng gặp khi binary search trên không gian đáp án. Dùng lo + (hi - lo) / 2.

Câu hỏi (Đọc code): Đoạn sliding window dưới đây in ra gì với hai input, và sai ở đâu?

import java.util.*;

public class BuggyWindow {
    static int longest(String s) {
        Map<Character, Integer> lastIndex = new HashMap<>();
        int best = 0, left = 0;
        for (int right = 0; right < s.length(); right++) {
            Integer prev = lastIndex.get(s.charAt(right));
            if (prev != null) left = prev + 1;
            lastIndex.put(s.charAt(right), right);
            best = Math.max(best, right - left + 1);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(longest("abcabcbb")); // prints: 3
        System.out.println(longest("abba"));     // prints: 3
    }
}

Đáp án:

In 3 và 3. Với "abcabcbb" kết quả tình cờ đúng, nhưng với "abba" đáp án đúng là 2; lỗi là thiếu điều kiện prev >= left, nên left bị kéo lùi về một vị trí cũ nằm ngoài cửa sổ.

Chạy tay "abba": right = 2 gặp b có prev = 1 nên left = 2, cửa sổ "b". Right = 3 gặp a có prev = 0; code gán left = 1, tức lùi từ 2 về 1, cửa sổ thành "bba" dài 3 dù chứa hai chữ b. Bài học: chỉ chạy tay ví dụ mẫu của đề ("abcabcbb") không đủ; bạn phải tự nghĩ ca biên khiến ký tự lặp nằm ngoài cửa sổ. Sửa: if (prev != null && prev >= left), hoặc viết left = Math.max(left, prev + 1).

Câu hỏi (Đọc code): Hàm merge interval dưới đây in ra gì?

import java.util.*;

public class BuggyMerge {
    static int[][] merge(int[][] intervals) {
        int[][] sorted = intervals.clone();
        Arrays.sort(sorted, Comparator.comparingInt(a -> a[0]));
        List<int[]> result = new ArrayList<>();
        int[] cur = sorted[0].clone();
        for (int i = 1; i < sorted.length; i++) {
            if (sorted[i][0] <= cur[1]) cur[1] = sorted[i][1];
            else { result.add(cur); cur = sorted[i].clone(); }
        }
        result.add(cur);
        return result.toArray(new int[0][]);
    }

    public static void main(String[] args) {
        int[][] in = {{1, 10}, {2, 3}, {4, 5}};
        System.out.println(Arrays.deepToString(merge(in))); // prints: [[1, 3], [4, 5]]
    }
}

Đáp án:

In [[1, 3], [4, 5]] trong khi đáp án đúng là [[1, 10]]; lỗi là gán cur[1] = sorted[i][1] thay vì Math.max(cur[1], sorted[i][1]), nên khoảng nằm lồng bên trong làm co ngắn khoảng lớn.

Chạy tay: cur = [1,10]; [2,3] có 2 ≤ 10 nên cur[1] = 3, cur thành [1,3] (sai, đã mất đoạn 3 tới 10); [4,5] có 4 > 3 nên chốt [1,3] và mở [4,5]. Ví dụ mẫu [[1,3],[2,6],...] không lộ lỗi này vì các khoảng không lồng nhau, nên hãy luôn tự thêm một ca "khoảng lồng trong khoảng" khi tự test. Ngoài ra hàm ném ArrayIndexOutOfBoundsException với mảng rỗng vì thiếu dòng kiểm tra intervals.length == 0.

Câu hỏi (Đọc code): Chương trình dưới đây in ra gì, vì sao?

public class RaceCounter {
    private static int count = 0;

    public static void main(String[] args) throws InterruptedException {
        Runnable task = () -> { for (int i = 0; i < 100_000; i++) count++; };
        Thread t1 = new Thread(task), t2 = new Thread(task);
        t1.start(); t2.start();
        t1.join(); t2.join();
        System.out.println(count); // usually prints a number below 200000
    }
}

Đáp án:

Thường in một số nhỏ hơn 200.000 và khác nhau mỗi lần chạy, vì count++ không phải thao tác nguyên tử: nó gồm đọc, cộng 1 và ghi lại, hai thread có thể cùng đọc một giá trị cũ và ghi đè lên nhau (race condition).

• Ví dụ xen kẽ: t1 đọc 5, t2 đọc 5, t1 ghi 6, t2 ghi 6; hai lần tăng chỉ còn một.
• join() đảm bảo main thấy kết quả cuối của hai thread (happens-before), nên vấn đề không nằm ở việc in, mà ở các lần tăng bị mất.
• volatile không sửa được, vì nó chỉ đảm bảo nhìn thấy giá trị mới, không làm đọc-sửa-ghi thành nguyên tử. Sửa bằng AtomicInteger.incrementAndGet(), LongAdder khi tranh chấp cao, hoặc synchronized. Xem mục 3.3, 3.4.

Câu hỏi (Đọc code): Câu SQL lấy người lương cao nhất mỗi phòng dưới đây sai ở đâu?

SELECT department_id, name, MAX(salary) AS max_salary
FROM employee
GROUP BY department_id;

Đáp án:

Cột name không nằm trong GROUP BY và không phải hàm gộp, nên PostgreSQL và MySQL 5.7+ (chế độ ONLY_FULL_GROUP_BY mặc định) báo lỗi; các DB cho chạy thì trả một name bất kỳ trong nhóm, không đảm bảo là người có lương cao nhất.

• Lý do: sau GROUP BY mỗi phòng chỉ còn một dòng, nhưng phòng có nhiều name, DB không biết chọn tên nào. MAX(salary) không "kéo theo" tên của dòng chứa giá trị max.
• Cách đúng: window function như mục 12.11 (DENSE_RANK() OVER (PARTITION BY department_id ORDER BY salary DESC) rồi lọc rnk = 1, trả mọi người cùng lương cao nhất), hoặc JOIN lại với subquery (department_id, MAX(salary)).
• Ca biên nên nói ra: hai người cùng lương cao nhất thì trả cả hai hay một? Câu trả lời quyết định chọn DENSE_RANK hay ROW_NUMBER.

Câu hỏi (Thực chiến): Viết SQL tìm khách hàng chưa từng đặt đơn nào. Vì sao NOT IN nguy hiểm?

Dùng NOT EXISTS hoặc LEFT JOIN ... WHERE o.id IS NULL; tránh NOT IN (subquery) vì chỉ cần subquery trả một giá trị NULL là cả câu trả về rỗng.

-- Safe: NOT EXISTS ignores NULLs in orders.customer_id
SELECT c.id, c.name
FROM customer c
WHERE NOT EXISTS (SELECT 1 FROM orders o WHERE o.customer_id = c.id);

-- Dangerous: returns no rows if any orders.customer_id is NULL
SELECT id, name FROM customer
WHERE id NOT IN (SELECT customer_id FROM orders);

Giải thích: x NOT IN (1, 2, NULL) được hiểu là x <> 1 AND x <> 2 AND x <> NULL; so sánh với NULL cho kết quả UNKNOWN, nên cả biểu thức không bao giờ TRUE và mọi dòng bị loại. NOT EXISTS chỉ hỏi "có tồn tại dòng khớp không", không bị ảnh hưởng. Ví dụ: bảng orders có một đơn khách vãng lai với customer_id NULL; câu NOT IN bỗng trả rỗng dù có khách chưa mua gì. Về hiệu năng, PostgreSQL và MySQL 8 đều tối ưu NOT EXISTS và LEFT JOIN IS NULL thành anti-join; cần index trên orders.customer_id.

Câu hỏi (Thực chiến): Viết code gọi 3 service song song, chờ cả 3 xong mới cộng kết quả, có timeout.

Dùng CompletableFuture với executor riêng, allOf để chờ cả ba, orTimeout để không chờ vô hạn; không dùng new Thread và join thủ công.

import java.util.concurrent.*;

public class ParallelCalls {
    public static void main(String[] args) {
        ExecutorService pool = Executors.newFixedThreadPool(3); // dedicated pool, not the common pool
        try {
            CompletableFuture<Integer> price = CompletableFuture.supplyAsync(() -> 100, pool);
            CompletableFuture<Integer> tax = CompletableFuture.supplyAsync(() -> 10, pool);
            CompletableFuture<Integer> shipping = CompletableFuture.supplyAsync(() -> 25, pool);
            int total = CompletableFuture.allOf(price, tax, shipping)
                .thenApply(v -> price.join() + tax.join() + shipping.join()) // all done, join() won't block
                .orTimeout(2, TimeUnit.SECONDS)                               // fail instead of waiting forever
                .join();
            System.out.println("Total = " + total); // prints: Total = 135
        } finally {
            pool.shutdown();
        }
    }
}

Giải thích: ba lambda supplyAsync đại diện cho ba lời gọi service, chạy đồng thời trên pool 3 thread nên tổng thời gian xấp xỉ lời gọi chậm nhất, không phải tổng ba lời gọi. allOf hoàn thành khi cả ba xong; bên trong thenApply, gọi join() không còn chặn vì kết quả đã có. Nếu quá 2 giây, orTimeout làm future thất bại với TimeoutException (bọc trong CompletionException khi join). Trong phỏng vấn, nói thêm: xử lý lỗi từng lời gọi bằng exceptionally để trả giá trị mặc định nếu nghiệp vụ cho phép, và không dùng common ForkJoinPool cho I/O. Chi tiết xem mục 3.7. Cách khác cũng được chấp nhận: CountDownLatch(3) hoặc invokeAll của ExecutorService.

Câu hỏi (Thực chiến): Bạn bị kẹt 10 phút giữa bài, không nghĩ ra cách tối ưu. Bạn nói gì?

Nói to trạng thái hiện tại và phương án dự phòng: "Em chưa ra cách O(n), em sẽ code bản brute-force O(n^2) chạy đúng trước, rồi tìm chỗ tối ưu"; một lời giải đúng mà chậm luôn hơn trang giấy trắng.

• Mô tả chỗ vướng cụ thể: "Em đang cần biết phần tử lớn hơn kế tiếp mà không quét lại, em đang nghĩ tới stack nhưng chưa rõ lúc nào pop." Người phỏng vấn gợi ý đúng chỗ khi biết bạn kẹt ở đâu.
• Quay lại ví dụ nhỏ và chạy tay, thường sẽ thấy mẫu lặp lại.
• Điểm lại các mẫu tư duy: đếm/tìm cặp thì HashMap, đoạn liên tiếp thì sliding window, lồng nhau thì stack, có thứ tự thì binary search.
• Khi nhận gợi ý, xác nhận lại bằng lời và đi tiếp, đừng xin lỗi nhiều lần.

Bẫy thường gặp

Im lặng xóa đi viết lại nhiều lần, hoặc nói "em chịu" khi còn 20 phút. Với người phỏng vấn, cả hai đều cho thấy khi gặp bug khó trong dự án bạn cũng sẽ im lặng như vậy.

Câu hỏi (Thực chiến): Code của bạn chạy đúng, người phỏng vấn hỏi "nếu input là 10 triệu phần tử thì sao?". Bạn trả lời thế nào?

Trả lời theo ba tầng: độ phức tạp thời gian còn chấp nhận được không, bộ nhớ có đủ không, và dữ liệu có nên nằm trong một JVM không.

• Thời gian: O(n) với 10 triệu là vài chục mili giây, ổn; O(n log n) vẫn ổn; O(n^2) là 10^14 bước, bắt buộc tối ưu.
• Bộ nhớ: một HashMap<Integer, Integer> 10 triệu entry tốn cỡ vài trăm MB đến 1 GB do boxing và overhead mỗi entry; có thể chuyển sang mảng nguyên thủy, bitset, hoặc thư viện map chuyên cho primitive.
• Kiến trúc: nếu dữ liệu nằm trong DB, đẩy phép tính xuống SQL (GROUP BY, index); nếu là file lớn, đọc theo luồng/batch thay vì load hết; nếu vượt một máy, chia nhỏ và xử lý song song.
• Kết bằng câu hỏi ngược: "Dữ liệu này đến từ đâu, có cần kết quả real-time không?" cho thấy bạn nghĩ như người làm production.

Câu hỏi (Thực chiến): Trong lúc code, bạn nên nói gì để người phỏng vấn thấy được tư duy mà không làm chậm tốc độ?

Nói "vì sao" ở các quyết định chính, không đọc lại từng dòng code: chọn cấu trúc dữ liệu gì, bất biến của vòng lặp là gì, ca biên nào đang xử lý.

Ví dụ khi code Two Sum: "Em dùng HashMap từ giá trị sang index để tra phần bù O(1). Em kiểm tra trước rồi mới put, để không ghép phần tử với chính nó. Đoạn này em trả mảng rỗng khi không có đáp án, như mình đã thống nhất." Ba câu, mỗi câu gắn với một dòng quan trọng. Không cần nói "em khai báo biến i bằng 0". Khi viết xong, nói "giờ em chạy tay với ví dụ [3, 3], target 6" và đọc bảng trạng thái ra thành lời như các bảng chạy tay trong chương này.

12.16 Tóm tắt trọng tâm

• Đáp án đúng chỉ là khoảng một phần ba số điểm, vì người phỏng vấn cần nhìn thấy cách bạn làm rõ đề, xử lý ca biên và tự kiểm tra, đúng những việc bạn sẽ làm hằng ngày trong team.
• Luôn hỏi input rỗng/null/trùng, kích thước n và giá trị trả về khi không có đáp án trước khi gõ code, vì nhiều đề cố tình viết thiếu để xem bạn có hỏi không.
• Big-O đo tốc độ tăng số bước theo n chứ không đo giây; với n = 1 triệu, O(n) là 1 triệu bước còn O(n^2) là 10^12 bước, nên ví dụ nhỏ không bao giờ lộ ra lời giải chậm.
• Thấy "tìm cặp, đếm, đã gặp chưa" thì nghĩ tới HashMap, vì nó đổi O(n) bộ nhớ lấy tra cứu O(1) và kéo O(n^2) xuống O(n).
• Thấy "đoạn con liên tiếp" thì nghĩ tới sliding window; nó là O(n) vì hai con trỏ chỉ tiến, và điều kiện prev >= left là chỗ hay sai nhất.
• Thấy "lồng nhau" hoặc "phần tử gần nhất chưa xử lý" thì dùng stack bằng ArrayDeque, vì Stack cũ kế thừa Vector và đồng bộ không cần thiết.
• Merge interval bắt buộc sort theo start trước và dùng Math.max khi nới đầu cuối, vì khoảng lồng bên trong sẽ làm co ngắn khoảng lớn nếu gán thẳng.
• Học thuộc một khuôn binary search là lower bound trên nửa khoảng [lo, hi), vì mọi biến thể (upper bound, tìm trên không gian đáp án) đều suy ra từ nó và ít sai biên.
• BFS cho đường ngắn nhất trên đồ thị không trọng số vì nó xử lý theo vòng khoảng cách tăng dần; đánh dấu visited lúc đưa vào queue để không xử lý một ô nhiều lần.
• LRU cần HashMap cộng danh sách liên kết đôi để cả get và put đều O(1); trong production nên dùng Caffeine thay vì tự viết.
• Luôn chạy tay code bằng bảng trạng thái với ít nhất một ca biên do bạn tự nghĩ ra, vì các lỗi như left lùi hay khoảng lồng nhau không lộ ra với ví dụ mẫu của đề.
• Với SQL, dùng window function và bọc trong subquery/CTE để lọc hạng, vì WHERE chạy trước window function; tránh NOT IN với cột có thể NULL.
• Với concurrency, ưu tiên công cụ dựng sẵn (BlockingQueue, CompletableFuture, Atomic) thay vì tự viết wait/notify, và luôn khôi phục cờ interrupt khi bắt InterruptedException.

12.17 Checklist ôn tập

Thuộc quy trình 6 bước và luyện nói to khi code ít nhất 10 bài Luôn hỏi input rỗng/null, phần tử trùng, kích thước dữ liệu và giá trị trả về khi không có đáp án Nói ngay được Big-O của ArrayList, HashMap, TreeMap, ArrayDeque, PriorityQueue và giải thích treeify của HashMap Viết không cần IDE: Two Sum, Anagram, ký tự đầu tiên không lặp, chuỗi con dài nhất không lặp Dùng ArrayDeque thay Stack, giải thích vì sao Merge interval và lower bound viết đúng biên ngay lần đầu BFS trên lưới, biết đánh dấu visited đúng lúc và rủi ro StackOverflowError của DFS đệ quy LRU Cache bằng cả LinkedHashMap và HashMap + doubly linked list, nói được vấn đề thread-safety Stream: groupingBy + summingLong/counting/maxBy, top N, partitioningBy, lỗi key trùng của toMap SQL: lương cao thứ 2, top N mỗi nhóm bằng DENSE_RANK, tìm và xóa bản ghi trùng, phân biệt ROW_NUMBER/RANK/DENSE_RANK Producer-consumer bằng BlockingQueue, in chẵn lẻ bằng wait/notifyAll và bằng Semaphore Luôn khôi phục cờ interrupt khi bắt InterruptedException Hoàn thành 60–80 bài theo kế hoạch 4–6 tuần và 2–3 buổi phỏng vấn thử Nói được bằng lời thường Big-O nghĩa là gì và số bước của O(log n), O(n), O(n^2) khi n = 1.000.000 Chạy tay được mọi bài trong chương bằng bảng trạng thái và tự nghĩ ra ít nhất một ca biên cho mỗi bài Tự làm lại 6 bài tập ở mục 12.14 trong 20 phút mỗi bài mà không xem đáp án