Interview Patterns

📋 At a Glance

Aspect	Details
Time to Read	40 minutes
Prerequisites	Parts 1-21 (Full series)
Key Concepts	Two Pointers, Sliding Window, Monotonic Stack, Pattern Recognition
Difficulty	⭐⭐⭐ (Interview-Focused)

┌─────────────────────────────────────────────────────────────────┐
│              INTERVIEW ALGORITHM PATTERNS                       │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  ┌─────────────────┐    ┌─────────────────┐                     │
│  │ TWO POINTERS    │    │ SLIDING WINDOW  │                     │
│  │ ─────────────── │    │ ─────────────── │                     │
│  │ [→    ...    ←] │    │ [═══════►     ] │                     │
│  │ Start from ends │    │ Fixed/variable  │                     │
│  │ or same side    │    │ window size     │                     │
│  └─────────────────┘    └─────────────────┘                     │
│                                                                 │
│  ┌─────────────────┐    ┌─────────────────┐                     │
│  │ FAST & SLOW     │    │ MONOTONIC STACK │                     │
│  │ ─────────────── │    │ ─────────────── │                     │
│  │ 🐢───→ 🐇───→   │    │ [▁▂▃▄▅] always  │                     │
│  │ Cycle detection │    │ increasing or   │                     │
│  │ middle finding  │    │ decreasing      │                     │
│  └─────────────────┘    └─────────────────┘                     │
│                                                                 │
│  ┌─────────────────┐    ┌─────────────────┐                     │
│  │ BINARY SEARCH   │    │ PREFIX SUMS     │                     │
│  │ ON ANSWER       │    │ ─────────────── │                     │
│  │ ─────────────── │    │ [a,a+b,a+b+c]   │                     │
│  │ If f(x) works,  │    │ Range queries   │                     │
│  │ does f(x+1)?    │    │ in O(1)         │                     │
│  └─────────────────┘    └─────────────────┘                     │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

🎯 What You'll Learn

After completing this article, you will be able to:

Recognize patterns: Map problems to known techniques
Apply two pointers: Solve array/string problems efficiently
Master sliding window: Handle substring/subarray problems
Use monotonic structures: Next greater/smaller element problems
Ace interviews: Systematic problem-solving approach

🔥 The Interview Approach

The 5-Step Framework

┌─────────────────────────────────────────────────────────────────┐
│                  INTERVIEW PROBLEM-SOLVING                      │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  1. UNDERSTAND (2-3 min)                                        │
│     ┌─────────────────────────────────────────────────────┐     │
│     │ • Restate the problem                               │     │
│     │ • Ask clarifying questions                          │     │
│     │ • Identify input/output format                      │     │
│     │ • Work through example by hand                      │     │
│     └─────────────────────────────────────────────────────┘     │
│                                                                 │
│  2. MATCH (1-2 min)                                             │
│     ┌─────────────────────────────────────────────────────┐     │
│     │ • What pattern does this look like?                 │     │
│     │ • What data structures might help?                  │     │
│     │ • Have I seen a similar problem?                    │     │
│     └─────────────────────────────────────────────────────┘     │
│                                                                 │
│  3. PLAN (3-5 min)                                              │
│     ┌─────────────────────────────────────────────────────┐     │
│     │ • Describe approach in plain English                │     │
│     │ • Walk through example with approach                │     │
│     │ • Discuss time/space complexity                     │     │
│     │ • Get buy-in before coding                          │     │
│     └─────────────────────────────────────────────────────┘     │
│                                                                 │
│  4. IMPLEMENT (15-20 min)                                       │
│     ┌─────────────────────────────────────────────────────┐     │
│     │ • Write clean, readable code                        │     │
│     │ • Use meaningful variable names                     │     │
│     │ • Talk through your code                            │     │
│     │ • Handle edge cases explicitly                      │     │
│     └─────────────────────────────────────────────────────┘     │
│                                                                 │
│  5. VERIFY (5 min)                                              │
│     ┌─────────────────────────────────────────────────────┐     │
│     │ • Trace through with example                        │     │
│     │ • Test edge cases                                   │     │
│     │ • Discuss optimizations                             │     │
│     └─────────────────────────────────────────────────────┘     │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

🔬 Deep Dive: Two Pointers

Pattern 1: Opposite Direction

JAVA(98 lines)
Code
Loading syntax highlighter...

Pattern 2: Same Direction (Fast & Slow)

JAVA(80 lines)
Code
Loading syntax highlighter...

🔬 Deep Dive: Sliding Window

Fixed Size Window

JAVA(73 lines)
Code
Loading syntax highlighter...

Variable Size Window

JAVA(110 lines)
Code
Loading syntax highlighter...

🔬 Deep Dive: Monotonic Stack/Queue

Next Greater Element

JAVA(77 lines)
Code
Loading syntax highlighter...

Monotonic Queue

JAVA(32 lines)
Code
Loading syntax highlighter...

🔬 Deep Dive: Binary Search on Answer

The Pattern

JAVA(97 lines)
Code
Loading syntax highlighter...

🔬 Deep Dive: Prefix Sum

JAVA(78 lines)
Code
Loading syntax highlighter...

🔬 Deep Dive: Meet in the Middle

JAVA(70 lines)
Code
Loading syntax highlighter...

📊 Pattern Recognition Guide

Problem → Pattern Mapping

┌──────────────────────────────────────────────────────────────────┐
│                  PATTERN RECOGNITION GUIDE                       │
├──────────────────────────────────────────────────────────────────┤
│                                                                  │
│  "Find pair/triplet with sum..."           → Two Pointers        │
│  "Longest/shortest substring/subarray..."  → Sliding Window      │
│  "Next greater/smaller element..."         → Monotonic Stack     │
│  "Find cycle in linked list..."            → Fast & Slow         │
│  "Minimum/maximum possible value..."       → Binary Search       │
│  "Count subarrays with sum..."             → Prefix Sum + HashMap│
│  "All permutations/combinations..."        → Backtracking        │
│  "Shortest path with constraints..."       → BFS/Dijkstra        │
│  "Count ways to reach target..."           → DP                  │
│  "Merge sorted structures..."              → Two Pointers/Heap   │
│  "Top K elements..."                       → Heap                │
│  "Valid parentheses/matching..."           → Stack               │
│  "Design LRU/LFU cache..."                 → HashMap + DLL       │
│                                                                  │
└──────────────────────────────────────────────────────────────────┘

Data Structure → Use Case

┌─────────────────────────────────────────────────────────────────┐
│               DATA STRUCTURE SELECTION                          │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Array:      • Fixed size, random access                        │
│              • Prefix sums, sliding window                      │
│                                                                 │
│  HashMap:    • O(1) lookup/insert                               │
│              • Counting, grouping, caching                      │
│                                                                 │
│  HashSet:    • O(1) membership test                             │
│              • Deduplication, cycle detection                   │
│                                                                 │
│  Stack:      • LIFO operations                                  │
│              • Parsing, backtracking, monotonic problems        │
│                                                                 │
│  Queue:      • FIFO operations                                  │
│              • BFS, level-order traversal                       │
│                                                                 │
│  Deque:      • Both ends operations                             │
│              • Sliding window max/min                           │
│                                                                 │
│  Heap:       • O(log n) insert, O(1) min/max                    │
│              • Top K, merge sorted, Dijkstra                    │
│                                                                 │
│  TreeMap:    • O(log n) sorted operations                       │
│              • Range queries, ceiling/floor                     │
│                                                                 │
│  Union-Find: • Near O(1) union/find                             │
│              • Connected components, Kruskal                    │
│                                                                 │
│  Trie:       • Prefix operations                                │
│              • Autocomplete, word search                        │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

🐛 Debug This: Sliding Window Bug

This sliding window solution for "longest substring with at most 2 distinct characters" has a bug. Can you find it?

JAVA(23 lines)
Code
Loading syntax highlighter...

🔍 Click to reveal the bug

Actually, this code is correct! The bug hunt was a trick question.

However, a common bug in similar code is forgetting to remove the key when count reaches 0:

JAVA(9 lines)
Code
Loading syntax highlighter...

Another common bug is updating maxLen inside the while loop instead of after:

JAVA(11 lines)
Code
Loading syntax highlighter...

💻 Exercises

Exercise 1: Longest Repeating Character Replacement ⭐⭐

Given string s and integer k, find longest substring where you can replace at most k characters to make all same.

JAVA(3 lines)
Code
Loading syntax highlighter...

Exercise 2: Product of Array Except Self ⭐⭐

Return array where result[i] is product of all elements except nums[i]. No division!

JAVA(3 lines)
Code
Loading syntax highlighter...

Exercise 3: Longest Valid Parentheses ⭐⭐⭐

Find length of longest valid parentheses substring.

JAVA(3 lines)
Code
Loading syntax highlighter...

Exercise 4: Median from Data Stream ⭐⭐⭐

Design a data structure that supports addNum() and findMedian() efficiently.

JAVA(3 lines)
Code
Loading syntax highlighter...

Exercise 5: Sliding Window Median ⭐⭐⭐⭐

Find median of each window of size k.

JAVA(3 lines)
Code
Loading syntax highlighter...

🎤 Mock Interview Questions

Question 1: String Processing

Problem: Given a string with parentheses, remove minimum parentheses to make it valid.

Example: "()())()" → "()()()" or "(())()"; "(((" → ""

Solution approach:

JAVA(5 lines)
Code
Loading syntax highlighter...

Question 2: Array/Two Pointers

Problem: Given sorted array, find number of pairs with difference exactly k.

Example: [1, 3, 5, 7], k=2 → 3 pairs: (1,3), (3,5), (5,7)

Follow-up: What if array isn't sorted?

Question 3: Graph

Problem: Clone a graph where nodes have random neighbors.

Key points:

Use HashMap to track original → clone mapping
DFS or BFS traversal
Handle cycles (check if already cloned)

Question 4: Design

Problem: Design a time-based key-value store that supports set(key, value, timestamp) and get(key, timestamp).

Key points:

HashMap<String, List<Pair<Integer, String>>>
Binary search for get() with timestamp
Handle case when no value exists before timestamp

Question 5: DP

Problem: Given coin denominations and amount, find number of combinations (not permutations) to make the amount.

Key insight: Process coins in outer loop to avoid counting same combination multiple times.

JAVA(5 lines)
Code
Loading syntax highlighter...

📋 Quick Reference

Time Complexity Cheatsheet

Pattern	Typical Time	When to Use
Two Pointers	O(n)	Sorted arrays, pair finding
Sliding Window	O(n)	Contiguous subarray/substring
Binary Search	O(log n)	Sorted data, monotonic function
BFS/DFS	O(V + E)	Graph traversal
DP	O(n²) or O(n×m)	Optimization, counting
Heap	O(n log k)	Top K problems
Monotonic Stack	O(n)	Next greater/smaller

Interview Checklist

Before coding:
□ Understand problem completely
□ Ask about edge cases
□ Discuss approach and complexity
□ Get confirmation to proceed

While coding:
□ Write clean, readable code
□ Use meaningful names
□ Handle edge cases
□ Think out loud

After coding:
□ Trace through example
□ Test edge cases
□ Discuss optimizations
□ Ask if any questions

🎯 Final Summary

The Complete Algorithms Compendium Journey

Part 0-1:   Foundations          → Understanding complexity, recursion
Part 2-3:   Theory              → Recursion, Divide & Conquer
Part 4-7:   Sorting             → QuickSort to advanced techniques
Part 8-10:  Searching           → Binary search, string matching
Part 11-15: Graphs              → Traversal, shortest path, MST, applications
Part 16-18: Dynamic Programming → Foundations to advanced DP
Part 19-20: Greedy & Backtracking → When each works
Part 21:    Probabilistic       → Bloom filters, HyperLogLog
Part 22:    Interview Patterns  → Putting it all together

Key Takeaways

Pattern recognition is the most valuable skill
Practice implementation, not just understanding
Analyze complexity before coding
Communicate clearly in interviews
Test edge cases systematically

📅 Review Schedule

Day	Focus	Time
0	Full read + practice problems	90 min
1	Pattern recognition guide	15 min
3	Two pointers + sliding window	30 min
7	Mock interview practice	45 min
14	All patterns review	30 min
30	Full mock interview	60 min

🎉 Congratulations!

You've completed the Algorithms Compendium: From Theory to Production.

What's Next?

Practice: Solve problems on LeetCode, HackerRank, CodeSignal
Review: Use the spaced repetition schedule
Teach: Explaining concepts solidifies understanding
Apply: Use these patterns in real projects

Recommended Practice Order

Easy problems to build confidence
Medium problems for pattern recognition
Hard problems for interview readiness
Mock interviews for real pressure

Start: Part 0: How to Use This Series →

Full Series: 23 parts covering algorithms from theory to production

Total Investment: ~35 hours for complete mastery

Your Investment: Countless opportunities ahead

"The best time to learn algorithms was 10 years ago. The second best time is now."