Giao diện
Mẫu tối ưu — Optimization Patterns ⚙️
Trong production, hai yếu tố luôn kéo ngược nhau: tốc độ và ổn định. Tối ưu vòng lặp mà bỏ qua race condition thì hệ thống nhanh nhưng sai. Khóa mọi thứ cho an toàn thì đúng nhưng chậm. Module này trang bị bốn mẫu thiết kế để cân bằng cả hai — mỗi pattern giải quyết một lớp bài toán cụ thể mà kỹ sư gặp lại nhiều lần trong sự nghiệp.
Bốn pattern chia thành hai nhóm rõ ràng: hiệu năng thuật toán (Sliding Window, Floyd's Cycle) giúp giảm độ phức tạp tính toán, và an toàn đồng thời (Token Bucket, CAS) giúp hệ thống chịu tải mà không sụp.
Lộ trình học
Khuyến nghị thứ tự: bắt đầu từ Sliding Window (trực quan nhất) → Floyd's Cycle (cùng nhóm two-pointer) → Token Bucket (chuyển sang concurrency) → CAS (khó nhất, cần hiểu multi-threading).
Nội dung
⚡ Hiệu năng thuật toán
Nhóm pattern biến thuật toán chậm thành nhanh, giảm bộ nhớ từ
| Bài học | Độ khó | Thời gian | Mô tả |
|---|---|---|---|
| Sliding Window | Intermediate | 25-35 phút | Two-pointer, fixed/variable window, streaming analytics |
| Floyd's Cycle Detection | Intermediate | 20-30 phút | Tortoise and Hare, phát hiện vòng lặp, tìm phần tử trùng |
🔒 An toàn đồng thời
Nhóm pattern bảo vệ hệ thống khi có nhiều request/thread đồng thời.
| Bài học | Độ khó | Thời gian | Mô tả |
|---|---|---|---|
| Token Bucket | Intermediate | 20-30 phút | Rate limiting, burst control, API gateway protection |
| Compare-And-Swap (CAS) | Advanced | 30-40 phút | Lock-free programming, atomic operations, ABA problem |
Khi nào dùng pattern nào?
| Tín hiệu từ đề bài / requirements | Pattern |
|---|---|
| "Contiguous subarray", "substring", "maximum/minimum of K elements" | Sliding Window |
| "Detect cycle", "find duplicate", "infinite loop" | Floyd's Cycle |
| "Max N requests per second", "rate limit", "throttle" | Token Bucket |
| "Concurrent writes", "lock-free", "atomic update" | CAS |
Tiên quyết
Trước khi bắt đầu module này, bạn cần nắm vững:
- Phân tích độ phức tạp — Big O — hiểu O(N), O(1), amortized analysis
- Kiến thức cơ bản về linked list, array, hash map
- Với nhóm concurrency: hiểu thread, mutex, race condition ở mức cơ bản
🧠 Quiz
Câu 1: Sliding Window phù hợp nhất với dạng dữ liệu nào?
- [ ] A) Đồ thị (graph)
- [x] B) Mảng hoặc chuỗi — bài toán liên quan đến dãy con liên tiếp (contiguous subarray/substring)
- [ ] C) Cây nhị phân
- [ ] D) Ma trận thưa (sparse matrix)
💡 Giải thích: Sliding Window duy trì một "cửa sổ" [left, right] trên mảng/chuỗi. Right mở rộng để thêm phần tử, left thu hẹp khi vi phạm ràng buộc. Mỗi phần tử vào/ra window tối đa 1 lần → O(n). Không áp dụng cho dữ liệu phi tuyến tính.
Câu 2: Compare-And-Swap (CAS) thuộc lĩnh vực nào?
- [ ] A) Thuật toán sắp xếp
- [ ] B) Nén dữ liệu
- [x] C) Concurrent programming — đảm bảo atomicity không dùng lock
- [ ] D) Machine learning optimization
💡 Giải thích: CAS là hardware instruction: so sánh giá trị hiện tại với expected, nếu khớp thì swap sang new value — tất cả atomic. Đây là nền tảng của lock-free data structures, Java AtomicInteger, và concurrent hash maps.