Hai TổngTwo Sum

Dùng Hash Map khi cần tra cứu / đếm / kiểm tra tồn tại với O(1) trung bình thay vì O(n) của brute force.

Dấu hiệu:
- Đề có "tồn tại không", "đếm số lần", "tìm cặp tổng = X"
- Brute force O(n²) — có thể giảm xuống O(n) nếu nhớ trước những gì đã thấy
- Mảng KHÔNG sorted (sorted thì xét Two-Pointer trước)

Trade-off: đổi O(n) space để giảm time.

Code mẫu (Two Sum):

function twoSum(nums: number[], target: number) {
  const seen = new Map<number, number>()
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i]
    if (seen.has(need)) return [seen.get(need)!, i]
    seen.set(nums[i], i)
  }
  return null
}

Top edge case dễ miss:

1. Input rỗng: [] hoặc "" — return null/empty hay throw?
2. Single element: [1] — nhiều thuật toán giả định ≥ 2
3. Toàn bộ trùng: [5, 5, 5, 5] — duplicate handling
4. Đã sorted vs reverse sorted: worst case của quick sort
5. Negative numbers: quên handle khi đề chỉ ví dụ dương
6. Max int / overflow: sum của large numbers
7. Pointer null/undefined: trong linked list / tree
8. Off-by-one: < vs <=, length vs length-1
9. Cycle trong graph: infinite loop nếu không có visited set
10. Concurrent modification: thay đổi mảng đang duyệt

Cách hỏi clarify trong phỏng vấn:
- "Mảng có thể rỗng không?"
- "Có duplicate không?"
- "Có negative không?"
- "Range của giá trị?" (để check overflow)
- "Cần return [] hay null khi không có?"

Mẹo: trình bày edge case xong viết test ngay — chứng minh handle đúng.

Flow chuẩn 8 bước:

1. Nhắc lại đề bằng lời mình. Confirm hiểu đúng.
2. Hỏi constraints: size input, sorted chưa, có duplicate, edge case range.
3. Brute force trước. Đưa ra cách thô O(n²) chứng minh logic đúng.
4. Chỉ ra bottleneck. "Vòng for lồng nhau làm O(n²)".
5. Suggest pattern tối ưu. Hash Map / Two-Pointer / Sliding Window / Binary Search...
6. Code rõ ràng, vừa viết vừa giải thích. Identifier có nghĩa (leftPointer, seen, không phải x, tmp).
7. Dry-run với ví dụ. Chạy code bằng tay trên 1-2 input.
8. Test edge cases + chốt Big-O. Time O(?) Space O(?).

Anti-patterns:
- Im lặng quá 30s
- Code ngay khi chưa hiểu đề
- Optimize sớm khi chưa có baseline
- Bỏ qua edge case rồi mới handle khi interviewer hỏi

Vàng: "Em chưa từng gặp pattern này, nhưng nhìn cấu trúc input em nghĩ có thể thử X..." — interviewer thích thấy bạn reason, không phải trả bài học thuộc.