DSA Pattern Library (Interview-Optimized)

This document lists the core algorithmic patterns that cover 90–95% of FAANG-level coding interview problems.
Mastering these patterns to procedural fluency enables solving medium problems in 2–5 minutes.

---

1. Linked List Patterns (5 Core Templates)

Core

1. Reverse Linked List (iterative)
2. Merge Two Lists (dummy head pattern)
3. Partition Into Two Lists (small/big dummy heads)
4. Fast/Slow Pointers
   • middle of list
   • cycle detection (Floyd)
   • reorder list
5. Remove/Skip Nodes With Dummy
   • remove Nth from end
   • skip duplicates
   • delete specific node pattern

---

2. Two-Pointer & Sliding Window Patterns

Core

6. Two-Pointer Convergence (sorted arrays)
7. Opposing Pointers for Optimization (max/min problems)
8. Sliding Window – Fixed Size
9. Sliding Window – Variable Size
10. Sliding Window – Longest Substring With Constraints
11. Sliding Window – Shortest Substring With Constraints

Core (Prefix/Hash)

12. Prefix Sums + Hashmap
13. Subarray Sum = K Pattern

Secondary

14. Dutch National Flag (3-Way Partition)

---

3. Stack Patterns

Core

15. Monotonic Increasing Stack
    • next greater element
    • stock span
16. Monotonic Decreasing Stack
    • largest rectangle in histogram
    • max rectangle in matrix
17. Parentheses Stack Patterns
    • valid parentheses
    • minimum removals
    • longest valid parentheses

---

4. Queue / Deque Patterns

Core

18. Sliding Window Max/Min Using Deque
19. BFS Level-Order Traversal
20. BFS Shortest Path in Grid Graph

---

5. Binary Search Patterns

Core

21. Standard Binary Search Template
22. Binary Search on Answer (parametric search)
23. Lower-Bound / Upper-Bound
24. Search in Rotated Sorted Array

---

6. Tree Patterns

Core

25. DFS Recursion Patterns
    • preorder
    • inorder
    • postorder
26. BFS Tree Traversal
27. Lowest Common Ancestor
    • binary tree
    • binary search tree
28. Diameter / Depth Patterns
    • max depth
    • diameter of binary tree
29. Binary Tree Serialization / Deserialization (BFS-based)

Secondary

30. BST Insert / Delete / Search (conceptual + implementation)

---

7. Graph Patterns

Core

31. DFS Graph Template
32. BFS Graph Template
33. Topological Sort (Kahn’s Algorithm)
34. Cycle Detection in Directed Graph
    • DFS recursion stack
    • Kahn’s indegree method
35. Connected Components (BFS or DFS)
36. Union-Find (Disjoint Set Union)
    • path compression
    • union by rank
37. Dijkstra’s Algorithm (Min-Heap Pattern)

---

8. Dynamic Programming Patterns

Core

38. Fibonacci / Linear DP Template
39. Knapsack DP
    • classic 2D
    • optimized 1D rolling array
40. Subsequence DP
    • LCS
    • edit distance
    • LIS
41. Palindrome DP
    • palindromic substrings
    • longest palindromic substring
42. Partition DP
    • subset sum
    • equal partition
43. Interval DP
    • burst balloons
    • matrix chain multiplication

Secondary

44. Bitmask DP (rare, niche)

---

9. Intervals / Greedy Patterns

Core

45. Sort + Merge Intervals
46. Insert Interval
47. Select Maximum Non-Overlapping Intervals (classic greedy)
48. Gas Station / Circular Tour
49. Meeting Rooms Scheduling (heap-based)

---

10. Heap & Misc Patterns

Core

50. Kth Largest Element
    • min-heap of size k
    • quickselect
51. Top-K Frequency (heap or bucket sort)
52. Heap-Select Patterns
53. Prefix Product / Postfix Product (product of array except self)

Optional

54. Sweep Line
55. Reservoir Sampling
56. Randomized Quickselect

---

Summary

Core patterns to master: 51
These are sufficient to solve nearly all FAANG-level technical interview questions with speed and confidence.

---

Recommended Usage

• Treat these as templates, not problems.
• Drill 3 patterns per day for 10–15 minutes.
• Aim for procedural fluency: solutions should be reflexive, fast, automatic.
• Build a repo with one directory per pattern containing:
  • Python template
  • Example problems
  • Practice implementations
  • Notes + pitfalls

Master these → Mediums become trivial, hards become mechanical.

Repository Index

• patterns/01-linked-list-reverse/: core iterative reverse template with notes.
• patterns/01_linked_list_patterns.py: full linked list pattern implementations (reverse, merge, partition, fast/slow, remove with dummy).
• patterns/02_two_pointers_and_windows.py: two-pointer + sliding window patterns (fixed, variable, prefix-sum/hash) ready to use.
• shared/: reusable structures such as ListNode plus build/print helpers.