DSA Pattern

---

🧭 1. Nhóm cơ bản — Foundation Patterns

Pattern	Tư duy chính	Ví dụ bài toán	Ứng dụng backend
Sliding Window	Cửa sổ di động trên mảng / chuỗi	Longest Substring Without Repeating Characters, Max Sum Subarray	Rate Limiter, Time-window Metrics, Moving Average
Two Pointers	Hai con trỏ quét ngược chiều hoặc cùng chiều	Container With Most Water, 3Sum, Merge Sorted Arrays	Stream merge, Event timeline comparison
Fast & Slow Pointers (Floyd’s Cycle)	Một con trỏ chạy nhanh, một chạy chậm	Linked List Cycle Detection	Deadlock detection, Event loop validation
Prefix Sum / Difference Array	Tính tổng nhanh O(1) bằng mảng tích lũy	Range Sum Query, Subarray Sum Equals K	Reporting system, metric aggregator
Binary Search	Tìm vị trí, giá trị, hoặc ranh giới	Search Insert Position, Peak Element, Min in Rotated Array	Search optimization, Pagination offset, Range queries

---

🧩 2. Nhóm Hash / Set / Map — Lookup & Counting Patterns

Pattern	Ý tưởng	Ví dụ	Ứng dụng backend
Hash Map Counting	Dùng map để đếm, check tồn tại	Two Sum, Anagram, Subarray Sum = K	Deduplication, Frequency tracking, Cache map
Grouping by Key	Gom nhóm dữ liệu theo khóa	Group Anagrams	Analytics by company_id, user_id
Set Membership	Kiểm tra nhanh tồn tại	Longest Consecutive Sequence	Bloom Filter, Redis Set cache
LRU / LFU Cache	Kết hợp HashMap + LinkedList / Heap	LRU Cache	Caching Layer, In-memory store

---

⚙️ 3. Nhóm Sorting & Searching — Ordering & Selection Patterns

Pattern	Ý tưởng	Ví dụ	Ứng dụng backend
Custom Sorting	Sắp xếp dựa trên nhiều tiêu chí	Sort Colors, Meeting Rooms	Rank product, Sort logs, Leaderboard
Top K Elements	Dùng Heap để chọn top-k	Kth Largest Element, Top K Frequent Words	Analytics Ranking, Trending Detection
Binary Search on Answer	Search trên miền kết quả	Allocate Books, Koko Eating Bananas	Optimize batch size, load balancing
Merge Intervals	Gộp các khoảng giao nhau	Merge Intervals, Meeting Scheduler	Job scheduling, Reservation system

---

🔢 4. Nhóm Recursion / Backtracking — Explore All Possibilities

Pattern	Ý tưởng	Ví dụ	Ứng dụng backend
Subsets / Permutations	Sinh tất cả tổ hợp / hoán vị	Subsets, Permutations, Combination Sum	Testing combinations, Feature toggling
DFS (Depth First Search)	Khám phá sâu, dùng stack / recursion	Path Sum, Word Search	Graph traversal, Service dependency analysis
BFS (Breadth First Search)	Khám phá theo tầng	Shortest Path in Binary Matrix	Queue processing, Graph topology

---

🧮 5. Nhóm Dynamic Programming (DP) — State + Transition

Pattern	Ý tưởng	Ví dụ	Ứng dụng backend
1D DP (Linear)	dp[i] phụ thuộc dp[i-1]	Climbing Stairs, House Robber	Cache computation, Cost minimization
2D DP (Grid)	dp[i][j] phụ thuộc hàng/cột	Unique Paths, Edit Distance	Routing, Diff algorithms
Knapsack	Chọn tối ưu trong giới hạn	0/1 Knapsack, Partition Equal Subset	Resource allocation, Cost optimization
Interval DP	Tối ưu đoạn liên tục	Burst Balloons, Matrix Chain Multiplication	Scheduling, Split optimization

---

🧠 6. Nhóm Greedy — Local Optimal → Global Optimal

Pattern	Ý tưởng	Ví dụ	Ứng dụng backend
Interval Scheduling	Chọn job không trùng	Activity Selection, Non-overlapping Intervals	Task scheduling, Job queue
Minimize Cost	Luôn chọn nhỏ nhất hiện tại	Huffman Encoding, Connect Sticks	Data compression, Cost-effective resource allocation
Coin Change (Greedy)	Dùng đồng lớn nhất có thể	Coin Change (greedy version)	Change making, Credit balance rounding

---

🌐 7. Nhóm Graph / Tree — Network Structure & Dependency Patterns

Pattern	Ý tưởng	Ví dụ	Ứng dụng backend
DFS/BFS on Graph	Traverse graph	Clone Graph, Word Ladder	Dependency resolution, Cluster discovery
Topological Sort	Sắp xếp thứ tự phụ thuộc	Course Schedule	Service boot order, DAG job scheduler
Union-Find (DSU)	Gom nhóm, detect cycle	Number of Connected Components	Service grouping, Cluster merge
Shortest Path (Dijkstra/BFS)	Tìm đường ngắn nhất	Dijkstra, Bellman-Ford	Network routing, Message propagation

---

⚡ 8. Nhóm Bit Manipulation — Low-level Optimization

Pattern	Ý tưởng	Ví dụ	Ứng dụng backend
Bitmask Enumeration	Duyệt tập hợp qua bit	Subsets using bitmask	Permission mask, Role management
Check bit / set bit / unset bit	x & (1<<i), x	(1<<i), x &~(1<<i)	Feature toggles, ID encoding
Count bits	Popcount, Brian Kernighan’s algorithm	Count 1 bits	Compression, HashID, Snowflake ID
(1<<k)-1 Pattern	Toàn bộ bit 1	Smallest Number with All Set Bits	Mask generation, Cache region mask

---

💬 9. Nhóm Concurrency / Parallelism (backend-oriented)

Pattern	Ý tưởng	Ứng dụng thực tế
Worker Pool	Giới hạn goroutine, xử lý batch song song	Job processing, Kafka consumer
Fan-in / Fan-out	Kết hợp hoặc tách luồng dữ liệu	ETL pipeline, Log aggregator
Pipeline Pattern	Chuỗi stage xử lý qua channel	Data stream processing
Rate Limiter	Sliding window hoặc Token bucket	API throttling
MapReduce / Shard-Reduce	Phân tán xử lý song song	Analytics computation

---

🧩 10. Meta Pattern — Cách suy nghĩ để nhận ra pattern

Khi gặp bài mới, hãy tự hỏi 4 câu:

1. Input có dạng gì? → Array, Graph, String, Tree → định hướng pattern.

2. Output có phải tối ưu / đếm / true-false / thứ tự không? → DP / Greedy / Sort / BFS.

3. Có ràng buộc thời gian hay bộ nhớ không? → Tìm O(n log n) hoặc O(1) space.

4. Có tính chất lặp / con giống cha không? → Có thể dùng recursion hoặc DP.

---

🧠 11. Gợi ý luyện pattern như senior backend dev

Mục tiêu	Lộ trình luyện
Nắm vững pattern	Làm 1–2 bài / pattern (Neetcode.io có list)
Hiểu khi nào dùng	Viết note riêng cho từng pattern: “Khi nào dùng – Khi nào fail”
Ứng dụng vào backend	Xây mini project thực tế: rate limiter, LRU, job scheduler, search service
Củng cố tư duy	Giải thích pattern bằng lời cho người khác (hoặc viết blog)