Final Revision

Arrays & Strings

Operation	Time Complexity
Access	O(1)
Search (unsorted)	O(n)
Search (sorted)	O(log n)
Insert (end)	O(1) amortized
Insert (beginning)	O(n)
Delete	O(n)

Key patterns: Two Pointers, Sliding Window, Prefix Sum, HashMap

Linked Lists

Operation	Time Complexity
Access	O(n)
Search	O(n)
Insert (head)	O(1)
Insert (tail)	O(1) with tail pointer
Delete	O(1) if node given

Key patterns: Fast/Slow Pointers, Reversal, Merge, Cycle Detection

Stacks & Queues

Structure	Push/Pop	Peek	Search
Stack	O(1)	O(1)	O(n)
Queue	O(1)	O(1)	O(n)
Deque	O(1)	O(1)	O(n)

Key patterns: Monotonic Stack, Next Greater Element, Parentheses Validation

Hash Maps

Operation	Average	Worst Case
Get	O(1)	O(n)
Put	O(1)	O(n)
Remove	O(1)	O(n)
ContainsKey	O(1)	O(n)

Key patterns: Two Sum, Anagram Grouping, Frequency Counting, Sliding Window with HashMap

Trees

Type	Height	Operations
Binary Tree	O(n)	O(n)
Balanced BST	O(log n)	O(log n)
BST (worst)	O(n)	O(n)

Key patterns: DFS (Preorder, Inorder, Postorder), BFS (Level Order), Path Sum, LCA

Heaps

Operation	Time Complexity
Insert	O(log n)
Extract Min/Max	O(log n)
Peek	O(1)
Build Heap	O(n)

Key patterns: Top K Elements, Median Finding, Priority Queue Problems

Graphs

Representation	Space	Edge Query
Adjacency Matrix	O(V²)	O(1)
Adjacency List	O(V+E)	O(degree)

Key patterns: DFS, BFS, Topological Sort, Union-Find, Dijkstra, MST (Prim/Kruskal)

Sorting Algorithms

Algorithm	Time (Avg)	Time (Worst)	Space	Stable
Bubble Sort	O(n²)	O(n²)	O(1)	Yes
Insertion Sort	O(n²)	O(n²)	O(1)	Yes
Merge Sort	O(n log n)	O(n log n)	O(n)	Yes
Quick Sort	O(n log n)	O(n²)	O(log n)	No
Heap Sort	O(n log n)	O(n log n)	O(1)	No
Tim Sort	O(n log n)	O(n log n)	O(n)	Yes

Binary Search

// Standard template
int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

Variants: First/Last occurrence, Search in rotated array, Search in matrix

Dynamic Programming

Key Decision Tree:

1. Can the problem be broken into subproblems? -> DP
2. Are subproblems overlapping? -> Memoization/Tabulation
3. Do we need all subproblems? -> Tabulation
4. Only optimal solution? -> Greedy might work

Common DP Patterns:

• 0/1 Knapsack
• Unbounded Knapsack
• Longest Common Subsequence
• Longest Increasing Subsequence
• Edit Distance
• Coin Change
• Matrix Chain Multiplication

Graph Algorithms

Algorithm	Time	Space	Use Case
DFS	O(V+E)	O(V)	Path finding, cycles
BFS	O(V+E)	O(V)	Shortest path (unweighted)
Dijkstra	O((V+E) log V)	O(V)	Shortest path (weighted)
Bellman-Ford	O(VE)	O(V)	Negative weights
Floyd-Warshall	O(V³)	O(V²)	All-pairs shortest path
Topological Sort	O(V+E)	O(V)	Task ordering
Union-Find	O(α(n))	O(V)	Connected components

Greedy Algorithms

When to use:

• Optimal substructure
• Local optimal leads to global optimal
• No overlapping subproblems

Common problems:

• Activity Selection
• Fractional Knapsack
• Huffman Coding
• Job Scheduling

Sliding Window

// Fixed window
int maxSum = 0;
for (int i = 0; i < k; i++) windowSum += arr[i];
maxSum = windowSum;
for (int i = k; i < n; i++) {
    windowSum += arr[i] - arr[i-k];
    maxSum = Math.max(maxSum, windowSum);
}

// Variable window
int left = 0;
for (int right = 0; right < n; right++) {
    // expand window
    while (window violates condition) {
        // shrink window
        left++;
    }
    // update answer
}

Backtracking Template

void backtrack(path, choices) {
    if (base case) {
        result.add(path);
        return;
    }
    for (choice : choices) {
        if (choice is invalid) continue;
        // make choice
        path.add(choice);
        // recurse
        backtrack(path, remainingChoices);
        // undo choice
        path.remove(path.size() - 1);
    }
}

System Design Framework

Step 1: Requirements Clarification

• Functional requirements
• Non-functional requirements (scale, latency, availability)
• Constraints and assumptions

Step 2: Back-of-Envelope Estimation

• Users, requests per second, storage, bandwidth

Step 3: High-Level Design

• Core components and data flow
• APIs and data models

Step 4: Detailed Design

• Database schema
• Caching strategy
• Load balancing
• Message queues

Step 5: Scaling

• Horizontal vs vertical scaling
• Sharding strategies
• CDN and edge caching

Key Numbers to Remember

Metric	Value
1 day	86,400 seconds
1 million seconds	~11.5 days
1 billion seconds	~31.7 years
SSD random read	~0.1ms
HDD random read	~10ms
Same datacenter round trip	~0.5ms
Cross-continent round trip	~150ms

Design Patterns for Interviews

URL Shortener

• Hash-based encoding
• Base62/Base64 conversion
• Database: key-value store
• Cache: Redis for hot URLs

Rate Limiter

• Token bucket algorithm
• Sliding window counter
• Distributed: Redis + Lua

Chat System

• WebSocket for real-time
• Message queue for persistence
• Presence service for online status

News Feed

• Fan-out on write vs fan-out on read
• Timeline: pull vs push model
• Cache: hot feeds in Redis