Algorithm & Data Structure trong Java: Từ "Gà" Phỏng Vấn Đến "Cao Thủ" Thực Chiến
Algorithm & Data Structure trong Java: Từ “Gà” Phỏng Vấn Đến “Cao Thủ” Thực Chiến
Ai nên đọc: Senior Java Backend Developer đang chuẩn bị phỏng vấn, hoặc bất kỳ ai muốn hiểu sâu cách dùng algorithm/data structure trong production thay vì chỉ “cày leetcode thuộc lòng”.
Mục lục:
Chúng ta đều biết một sự thật: Phỏng vấn Senior ở VN không chỉ hỏi “Bạn đã dùng những framework nào?“. Họ sẽ cho bạn một bài toán, và trong lúc bạn code, họ lắng nghe cách bạn tư duy.
Điểm khác biệt giữa Mid-level và Senior không nằm ở việc bạn giải được bài Two Sum nhanh hơn 5 phút, mà là bạn chọn đúng cấu trúc dữ liệu và thuật toán cho bài toán thực tế, giải thích được cơ chế bên trong của nó, và dự đoán được edge case trong production.
Bài viết này sẽ dẫn dắt bạn qua một tình huống thực tế (Bottleneck Production), đào sâu vào cơ chế hoạt động của những cấu trúc dữ liệu quen thuộc như HashMap, Tree, Sliding Window, sau đó cung cấp code pattern chuẩn production và framework trả lời phỏng vấn “ăn điểm”.
1. Câu chuyện thực tế: Bottleneck Production
Hãy tưởng tượng bạn vừa join một dự án ngân hàng. Hệ thống notification của họ gửi push notification mỗi khi có giao dịch giá trị cao (> 1 triệu VNĐ). Giờ cao điểm: 10,000 giao dịch mỗi giây.
Team dev trước đó để lại cho bạn một “cục nợ” kỹ thuật với hàng loạt vấn đề:
Vấn đề 1: Query full table scan
-- Query hiện tại: Quét toàn bộ 50 triệu rows để lấy khách hàng giao dịch > 1 triệu
SELECT customer_id FROM transactions WHERE amount > 1000000; -- Tốn 5 giây!Root cause: Thiếu index. Database không có “mục lục” để tra nhanh, phải đọc hết cả bảng.
Giải pháp: Cần một B-tree index trên cột amount. B-tree là kiểu cấu trúc cây cân bằng, lưu dữ liệu theo thứ tự đã sắp xếp trên ổ đĩa, cho phép tìm kiếm range query (ví dụ: amount > 1000000) chỉ trong O(log n), thay vì O(n) như full scan.
Vấn đề 2: Kiểm tra trùng notification một cách chậm chạp
// Cần biết: "User X đã được gửi notification trong 5 phút qua chưa?"
// Code hiện tại: Duyệt toàn bộ list "recent notifications" -> O(n)
List<Notification> recents = getRecentNotifications();
boolean alreadySent = recents.stream().anyMatch(n -> n.getUserId().equals(userId));Giải pháp: Thay bằng HashSet (nếu data set nhỏ, trong bộ nhớ) hoặc Bloom Filter (nếu data set cực lớn, chấp nhận sai số nhỏ). Một Bloom filter dùng một bit array và vài hàm hash để trả lời “chắc chắn chưa có” hoặc “có thể đã có” với O(k) time (k là số hàm hash, hằng số rất nhỏ). Điều này giúp loại bỏ O(n) scan.
Vấn đề 3: Memory leak do lưu trữ không giới hạn
Cách làm cũ: Lưu tất cả notification_id đã gửi vào một ArrayList. Sau 1 tuần server hết RAM.
Giải pháp: Cần một Sliding Window với expiration. Lưu timestamps vào một Deque (hàng đợi hai đầu). Mỗi khi kiểm tra, tự động xóa những timestamp nằm ngoài 5 phút gần nhất. Cấu trúc này chỉ giữ lại dữ liệu trong khoảng thời gian trượt, memory usage ổn định bất kể hệ thống chạy bao lâu.
Tư duy Senior phân biệt Mid ở chỗ: Nhìn câu chuyện trên, bạn không cần thuộc lòng “implement B-tree như thế nào”. Bạn chỉ cần biết: Khi nào dùng B-tree index (range query), khi nào dùng HashSet (membership check), khi nào dùng Bloom Filter (membership check với big data, cost thấp), và khi nào dùng Sliding Window (deduplication theo khoảng thời gian).
2. Mental Model: Cơ chế bên trong
Hiểu rõ bản chất bên trong của cấu trúc dữ liệu giúp bạn tự tin khi đối mặt với câu hỏi “tại sao” và phòng tránh bug production.
HashMap Internals – “Trái tim” của Java Collection
HashMap trong Java lưu trữ các cặp Key-Value trong một mảng các Bucket. Nhưng điều kỳ diệu thực sự nằm ở cách nó xử lý va chạm (collision).
- Default: Mảng có 16 bucket, mỗi bucket là một Linked List.
- Load Factor = 0.75: Khi số phần tử vượt quá
16 * 0.75 = 12, HashMap sẽ tự động tăng kích thước mảng lên gấp đôi và rehash toàn bộ key vào bucket mới. Đây là lý do bạn không nên khởi tạonew HashMap()không tham số nếu đã biết trước khoảng 1 triệu phần tử – việc resize liên tục rất tốn CPU. Hãy dùngnew HashMap<>(expectedSize).
Quy trình PUT:
int hash = key.hashCode()(thực tế Java còn dùnghash ^ (hash >>> 16)để giảm va chạm).int bucketIndex = hash & (capacity - 1). Lưu ý: Dùng bitwise AND chứ không phải% capacityvì nó nhanh hơn rất nhiều, nhưng chỉ hoạt động khicapacitylà lũy thừa của 2 (16, 32, 64…).- Nếu bucket rỗng -> thêm node mới.
- Nếu bucket đã có node: So sánh
hashvàequals(). Nếu key giống -> update value. Nếu key khác -> Hash Collision (va chạm hash).
Xử lý Collision (Java 8+):
Thay vì chỉ dùng Linked List (worst-case O(n) khi tất cả key cùng rơi vào 1 bucket), từ Java 8, khi một bucket có hơn 8 node và tổng capacity >= 64, Linked List sẽ được chuyển thành Red-Black Tree (cây đỏ-đen - một dạng cây nhị phân tự cân bằng). Khi đó thời gian tìm kiếm giảm từ O(n) xuống O(log n). Điều này vô hiệu hóa các cuộc tấn công Hash Collision DoS, nơi attacker cố tình gửi các key được thiết kế để cùng rơi vào 1 bucket.
ConcurrentHashMap (Java 8+): Không dùng segment lock (lock một phần map) như Java 7 nữa, mà dùng CAS (Compare-And-Swap) kết hợp
synchronizedtrên mỗi bucket. Điều này cho phép nhiều thread ghi vào các bucket khác nhau mà không block nhau, cải thiện concurrency rất lớn. Chi tiết sẽ được bàn trong chủ đề Java Concurrency (#1).
Tree Traversal – Tư duy đệ quy “gốc rễ”
Khi gặp bài toán về cây, đừng hoảng. Hãy quy về một pattern duy nhất: “Nếu node hiện tại giao việc cho con trái và con phải (đệ quy), và giả sử chúng đều trả về kết quả đúng, thì tôi kết hợp chúng như thế nào?”
Cho cây nhị phân:
1
/ \
2 3
/ \ / \
4 5 6 7Có 4 cách duyệt chính:
- Inorder (Trái - Gốc - Phải):
4, 2, 5, 1, 6, 3, 7-> Ứng dụng: In ra cây tìm kiếm nhị phân (BST) theo thứ tự tăng dần. - Preorder (Gốc - Trái - Phải):
1, 2, 4, 5, 3, 6, 7-> Ứng dụng: Serialize (lưu cấu trúc cây ra file/network), copy cây. - Postorder (Trái - Phải - Gốc):
4, 5, 2, 6, 7, 3, 1-> Ứng dụng: Xóa cây (phải xóa các nút con trước khi xóa cha). - BFS (Level Order - theo tầng):
1, 2, 3, 4, 5, 6, 7-> Ứng dụng: Tìm đường đi ngắn nhất (trong đồ thị không trọng số), xử lý theo tầng.
Sliding Window – Pattern “cửa sổ trượt”
Đây là pattern kinh điển cho các bài toán về chuỗi con, mảng con với ràng buộc.
Tư duy chính: Dùng 2 con trỏ left và right để co giãn một “cửa sổ” trên mảng.
// Template bất biến cho Variable Size Sliding Window
int left = 0;
int result = 0;
for (int right = 0; right < n; right++) {
// 1. Mở rộng cửa sổ: Thêm arr[right] vào trạng thái
windowState.add(arr[right]);
// 2. Thu hẹp cửa sổ nếu vi phạm ràng buộc
while (windowState.violatesConstraint()) {
windowState.remove(arr[left]);
left++;
}
// 3. Cập nhật kết quả dựa trên cửa sổ hợp lệ hiện tại
result = Math.max(result, right - left + 1);
}Độ phức tạp luôn là O(n) vì mỗi phần tử được thêm vào và xóa khỏi windowState tối đa 1 lần. Dù có vòng lặp while bên trong, tổng số lần left++ không vượt quá n.
Complexity Analysis – “Vũ khí” phân tích thuật toán
Đừng chỉ nhớ thuộc lòng Big-O. Hãy hiểu bản chất:
- O(1): Tức thì, không phụ thuộc input size (Truy cập mảng
arr[i],HashMap.get). - O(log n): Mỗi lần thực thi, không gian tìm kiếm giảm một nửa (Binary Search,
TreeMap). - O(n): Thời gian tỉ lệ thuận với input (Duyệt mảng 1 lần).
- O(n²): Hai vòng lặp lồng nhau (Bubble sort).
- Space Complexity cũng quan trọng không kém: Ví dụ,
BFStrên cây dùng Queue, không gian bộ nhớ làO(w)vớiwlà chiều rộng tối đa của cây. - Space-Time Trade-off: Đây là câu hỏi tủ của Senior interviewer: “Dùng thêm bộ nhớ để giảm thời gian chạy có được không?” (Ví dụ: Dùng HashMap cho Two Sum: time
O(n), spaceO(n)).
3. Production-Grade Implementation
Lý thuyết là để hiểu, code mới là thực hành. Dưới đây là các pattern Java bạn có thể dùng ngay.
HashMap – Pattern Sử Dụng “xịn”
// Pattern 1: Đếm tần suất (Frequency counting)
// Dùng getOrDefault để tránh 2 lần lookup (containsKey rồi mới get)
Map<String, Integer> freq = new HashMap<>();
for (String item : items) {
freq.put(item, freq.getOrDefault(item, 0) + 1);
}
// Pattern 2: Gom nhóm (Grouping)
// computeIfAbsent: An toàn hơn putIfAbsent, tránh NPE, tạo List mới khi cần
Map<String, List<Transaction>> groups = new HashMap<>();
for (Transaction txn : txns) {
groups.computeIfAbsent(txn.getUserId(), k -> new ArrayList<>())
.add(txn);
}
// Pattern 3: Khử trùng (Deduplication) với Stream
// Set.add() trả về false nếu element đã tồn tại
Set<String> seen = new HashSet<>();
List<Transaction> unique = txns.stream()
.filter(t -> seen.add(t.getTransactionId()))
.collect(Collectors.toList());
// Pattern 4: LRU Cache "thần thánh" dùng LinkedHashMap
// accessOrder=true -> Tự động sắp xếp theo thứ tự truy cập.
// removeEldestEntry -> Tự động xóa phần tử cũ nhất khi đầy.
class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75f, true);
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
}Tree Problems – “Kinh điển” Validate BST & LCA
// Validate BST: Dùng range (min, max) để kiểm tra đệ quy
public boolean isValidBST(TreeNode root) {
return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean validate(TreeNode node, long min, long max) {
if (node == null) return true;
if (node.val <= min || node.val >= max) return false;
// Trái: max mới là node.val; Phải: min mới là node.val
return validate(node.left, min, node.val)
&& validate(node.right, node.val, max);
}
// Lowest Common Ancestor (LCA): Pattern đệ quy "chia để trị"
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// Nếu tìm thấy cả 2 phía -> root chính là LCA
if (left != null && right != null) return root;
return left != null ? left : right; // Nếu chỉ 1 phía thấy -> trả phía đó
}Sliding Window – Ứng dụng thực tế: Rate Limiter
Tình huống: Bạn cần giới hạn mỗi user chỉ được gọi API 100 lần trong 60 giây.
/**
* Simple Sliding Window Rate Limiter
* Cho phép maxRequests trong windowSizeMs.
*/
public class SlidingWindowRateLimiter {
private final int maxRequests;
private final long windowSizeMs;
private final Map<String, Deque<Long>> userWindows = new ConcurrentHashMap<>();
public boolean isAllowed(String userId) {
long now = System.currentTimeMillis();
long windowStart = now - windowSizeMs;
Deque<Long> timestamps = userWindows.computeIfAbsent(userId, k -> new ArrayDeque<>());
synchronized (timestamps) {
// Xóa timestamps cũ nằm ngoài cửa sổ
while (!timestamps.isEmpty() && timestamps.peekFirst() < windowStart) {
timestamps.pollFirst();
}
if (timestamps.size() < maxRequests) {
timestamps.addLast(now);
return true;
}
return false;
}
}
}4. Trade-offs & Anti-patterns
Những sai lầm “chết người” hoặc những lựa chọn đánh đổi bạn phải nắm rõ.
| Data Structure | Khi Nào Dùng | Trade-off |
|---|---|---|
| HashMap vs TreeMap | Cần lookup nhanh O(1) (không cần thứ tự). | TreeMap dùng Red-Black Tree, O(log n) nhưng duy trì thứ tự sắp xếp, hỗ trợ range query (subMap). |
| Fixed Window vs Sliding Window | Fixed window: Đơn giản, chỉ cần 1 counter. | Sliding window: Mượt hơn, ngăn burst traffic ở rìa cửa sổ, nhưng tốn bộ nhớ hơn để lưu timestamps. Token Bucket là lựa chọn production phổ biến khác cân bằng hơn. |
| DFS vs BFS | DFS dùng stack, thích hợp duyệt sâu. BFS dùng queue, tìm ngắn nhất. | DFS có thể gây StackOverflow với cây rất sâu. BFS tốn O(w) bộ nhớ, có thể rất lớn nếu cây rộng. |
Anti-patterns “Không Tha Thứ”
1. Quên override equals() và hashCode() cho custom key:
class UserId { String value; } // Ngây thơ không override
Map<UserId, User> map = new HashMap<>();
map.put(new UserId("123"), user);
map.get(new UserId("123")); // Trả về null! -> Logic sai.Nguyên tắc: Nếu 2 object bằng nhau theo business logic (cùng value), chúng phải có cùng hashCode. Java dùng hashCode để tìm bucket, equals để tìm đúng object trong bucket.
2. Dùng Mutable key trong HashMap:
List<String> key = new ArrayList<>(Arrays.asList("a"));
map.put(key, "val");
key.add("b"); // hashcode của key thay đổi!
map.get(key); // null - "ma" luôn.Luôn dùng Immutable Objects làm key: String, Integer, UUID, hoặc custom class final chỉ có getter.
3. Code ngay, không clarify (Anti-pattern phỏng vấn): Khi được hỏi “Two Sum”, nếu bạn im lặng lao vào code, bạn đã tự loại mình. Câu thần chú: “Clarify trước khi code.”
- Mảng đã sort chưa? (Sort rồi -> Dùng Two Pointers,
O(1)space) - Cần trả về index hay value? (Có hashmap không được nếu cần value gốc không sắp xếp).
- Có bao nhiêu cặp? Có duplicate không? Bộ nhớ có phải là vấn đề?
5. Interview Framework: Trả lời theo tầng
Cách bạn trả lời thể hiện bạn là ai.
Tầng 1 (Junior/Surface): Câu hỏi “Dùng gì?"
"HashMap và TreeMap khác gì nhau?”
Trả lời: “HashMap dùng hash table,
O(1)trung bình cho put/get nhưng không đảm bảo thứ tự. TreeMap dùng Red-Black Tree,O(log n)nhưng key luôn được sắp xếp. Em dùng HashMap khi cần lookup nhanh, TreeMap khi cần range queries như ‘lấy tất cả giao dịch từ ngày A đến B’.”
Tầng 2 (Mid/Deep Dive): Câu hỏi “Tại sao?"
"HashMap worst-case O(n) xảy ra khi nào? Java fix thế nào?”
Trả lời: “Khi nhiều key bị hash collision vào cùng 1 bucket, Hashmap thành LinkedList. Attacker có thể lợi dụng điều này để tấn công DoS. Từ Java 8, khi một bucket dài trên 8 node, nó sẽ được chuyển thành Red-Black Tree, giảm worst-case xuống
O(log n). Java 7 cũng đã thêmhash seedngẫu nhiên để chống collision attack ngay từ đầu. Trade-off: cây đỏ-đen dùng nhiều memory hơn linked list.”
Tầng 3 (Senior/Architecture): Câu hỏi “Thiết kế thế nào?"
"Thiết kế hệ thống tìm kiếm transaction cho hàng chục triệu bản ghi.”
Framework trả lời:
- Clarify: “Em thấy có 2 loại query chính: a) Tìm chính xác theo mã giao dịch, b) Lọc theo user + khoảng thời gian. Hệ thống có cần real-time không? Có cần full-text search trên description không?”
- Data Structure Selection: “Với query chính xác, dùng Hash Index. Với range query (theo ngày tháng), B-Tree index là lựa chọn tối ưu vì nó hỗ trợ range scan
O(log n + k)với k là kết quả.”- Caching: “Với user thường xuyên truy cập lịch sử gần đây, ta có thể dùng Redis Sorted Set (dùng timestamp làm score) để cache. ZRANGEBYSCORE cho range query trong
O(log n).”- Deep Dive: “Với phân trang (pagination), không nên dùng
OFFSET/LIMITvì database vẫn phải scan quaOFFSETdòng. Thay vào đó, dùng Cursor-based Pagination (Keyset pagination):WHERE id > lastSeenId LIMIT 10, tận dụng index đã có.”
6. Checklist Thành Thạo & Survival Guide
Bạn đã sẵn sàng? Hãy tự kiểm tra:
- Giải thích được HashMap collision: Cơ chế chaining, tree conversion, tại sao capacity là lũy thừa của 2, và load factor ảnh hưởng performance ra sao.
- Phân biệt rõ BFS/DFS: Không chỉ code, mà còn nói được khi nào dùng cái nào (BFS: đường đi ngắn nhất, theo tầng; DFS: backtracking, cycle detection).
- Implemented Sliding Window tổng quát: Code được cả hai loại fixed-size và variable-size. Giải thích tại sao độ phức tạp là
O(n). - Custom Key cho HashMap: Tự tin viết class
AccountIdvớiequals()vàhashCode()chuẩn, giải thích hậu quả nếu quên override. - Phân tích Complexity: Mỗi khi viết xong 1 hàm, tự hỏi Time/Space Complexity là gì, có thể cải thiện bằng Space-Time Trade-off không.
Survival Guide cho Senior Java Backend VN:
- Ít “cày leetcode hard” hơn bạn nghĩ. Các công ty tập trung vào: “Implement cái này trong ngữ cảnh hệ thống của chúng tôi.”
- Ví dụ phỏng vấn thực tế: “Chúng tôi có bài toán deduplicate payment notification trong 5 phút. Bạn hãy design và implement.”
- Điều họ quan sát: Bạn có hỏi rõ yêu cầu không? Code của bạn có clean không? Bạn có tự động nghĩ đến edge case (tiếng Việt: trường hợp biên) như null, empty, single element, concurrency không? Bạn có bàn luận về trade-off của giải pháp mình chọn không?
Hy vọng bài viết này sẽ là “bảo bối” giúp bạn tự tin hơn trong phỏng vấn và áp dụng thành công vào dự án thực tế. Chúc bạn sớm “cập bến” công ty mơ ước!