Data Structures & Algorithms

Complete Interview Preparation & Reference Guide

1. Big-O Complexity Cheat Sheet

Big-O notation describes the upper bound of an algorithm's time or space complexity as input
size (n) grows. Understanding complexity is critical for writing efficient code.

Complexity Name Example Algorithm n=10 n=1000

O(1) Constant Hash table lookup 1 1
O(log n) Logarithmic Binary search 3 10
O(n) Linear Linear search 10 1,000
O(n log n) Linearithmic Merge sort, Heap sort 33 10,000
O(n²) Quadratic Bubble sort, Insertion sort 100 1,000,000
O(2ⁿ) Exponential Recursive Fibonacci 1,024 Astronomical
O(n!) Factorial Brute-force permutations 3,628,8 Impossible
00

2. Core Data Structures

2.1 Arrays & Strings
Operation Array (unsorted) Array (sorted) Notes
Access by index O(1) O(1) Direct memory address
calculation
Search O(n) O(log n) Binary search on sorted array
Insert (end) O(1) amortized O(n) Sorted needs shifting
Insert (middle) O(n) O(n) Elements must shift right
Delete O(n) O(n) Elements must shift left

2.2 Linked Lists

• Singly Linked — each node holds data and pointer to next; O(1) insert at head, O(n)
search
• Doubly Linked — each node holds pointers to both next and previous; O(1) delete with
node reference
• Circular Linked — last node points back to first; useful for round-robin scheduling
2.3 Stacks & Queues
Structure Push/ Pop/ Peek Use Cases
Enqueue Dequeue
Stack (LIFO) O(1) O(1) O(1) Undo/redo, call stack, DFS, balanced
brackets
Queue (FIFO) O(1) O(1) O(1) BFS, task scheduling, print spooler
Deque O(1) O(1) O(1) Sliding window problems, palindrome
check
Priority Queue O(log n) O(log n) O(1) Dijkstra's, task scheduling by priority

3. Trees & Graphs

3.1 Binary Search Tree (BST) Properties
• Left subtree contains only nodes with keys less than the parent node
• Right subtree contains only nodes with keys greater than the parent node
• Both left and right subtrees are also BSTs (recursive property)
• Average case: O(log n) for search, insert, delete | Worst case (skewed): O(n)
• Balanced BST variants: AVL Tree, Red-Black Tree — guarantee O(log n) worst case

3.2 Tree Traversals

Traversal Order Use Case Output for BST
In-order (LNR) Left → Node → Right Sorted output from BST Ascending sorted
sequence
Pre-order (NLR) Node → Left → Right Copy/serialize tree Root always first
Post-order (LRN) Left → Right → Node Delete tree, evaluate Root always last
expressions
Level-order (BFS) Level by level Shortest path, find height Top-down, left-right

3.3 Graph Representations

Representation Space Add Edge Check Best For
Edge
Adjacency Matrix O(V²) O(1) O(1) Dense graphs, frequent edge lookups
Adjacency List O(V+E) O(1) O(degree) Sparse graphs, traversals
Edge List O(E) O(1) O(E) Kruskal's MST algorithm
4. Sorting Algorithms
Algorithm Best Average Worst Space Stable Notes
?
Bubble Sort O(n) O(n²) O(n²) O(1) Yes Simple; only for teaching
Selection O(n²) O(n²) O(n²) O(1) No Always n² comparisons
Sort
Insertion O(n) O(n²) O(n²) O(1) Yes Good for small/nearly
Sort sorted
Merge Sort O(n log n) O(n log n) O(n log n) O(n) Yes Guaranteed O(n log n)
Quick Sort O(n log n) O(n log n) O(n²) O(log No Fastest in practice
n)
Heap Sort O(n log n) O(n log n) O(n log n) O(1) No In-place, not cache-
friendly
Counting O(n+k) O(n+k) O(n+k) O(k) Yes Only for integers in range
Sort k
Radix Sort O(nk) O(nk) O(nk) O(n+k) Yes Fast for fixed-length
integers

5. Graph Algorithms
5.1 Shortest Path Algorithms
Algorithm Graph Type Time Complexity Handles Negative Weights?
BFS Unweighted O(V + E) N/A (equal weights only)
Dijkstra's Weighted, non- O((V+E) log V) No
negative
Bellman-Ford Weighted O(V × E) Yes (detects negative cycles)
Floyd-Warshall All-pairs O(V³) Yes
A* Search Weighted + heuristic O(E log V) No (but very fast in practice)

5.2 Minimum Spanning Tree

• Kruskal's Algorithm — sort edges by weight, add edge if no cycle (uses Union-Find); O(E
log E)
• Prim's Algorithm — grow MST one vertex at a time using min-heap; O(E log V)
• Both produce the same MST weight but may differ in edge selection for equal weights
6. Dynamic Programming Patterns
Dynamic Programming (DP) solves problems by breaking them into overlapping subproblems
and storing results (memoization/tabulation) to avoid redundant computation.

6.1 Classic DP Problems

Problem DP Pattern Time Space
Fibonacci 1D DP / simple recurrence O(n) O(1)
optimize
d
0/1 Knapsack 2D DP (weight × items) O(n × W) O(n ×
W)
Longest Common 2D DP (two strings) O(m × n) O(m ×
Subsequence n)
Coin Change (min coins) 1D DP (bottom-up) O(amount × O(amou
coins) nt)
Longest Increasing 1D DP or Binary Search O(n log n) O(n)
Subsequence
Edit Distance 2D DP (two strings) O(m × n) O(m ×
n)
Matrix Chain Multiplication Interval DP O(n³) O(n²)

6.2 Memoization Template (Python)

from functools import lru_cache

@lru_cache(maxsize=None)
def dp(state):
# Base case
if is_base_case(state):
return base_value
# Recurrence relation
return min/max/sum(dp(next_state) for next_state in transitions(state))

7. Common Interview Problem Patterns

Pattern Trigger Keywords Data Structure / Technique
Two Pointers Sorted array, pair sum, Array with left/right pointers
palindrome
Sliding Window Subarray, substring, max/min Deque or two pointers + hashmap
window
Fast & Slow Pointers Cycle detection, middle of list Two pointers at different speeds
Binary Search Sorted, search, find min/max lo/hi/mid on answer space
BFS / Level-order Shortest path, min steps, tree Queue + visited set
levels
DFS / Backtracking Permutations, combinations, Recursion + pruning
paths
Heap / Top-K K largest, K smallest, median Min-heap or Max-heap
stream
Union-Find Connected components, cycle Disjoint Set Union (DSU)
detect
Monotonic Stack Next greater/smaller element Stack maintaining order
Trie Prefix search, autocomplete, word Tree of characters
dict

© 2024 | Data Structures & Algorithms Reference | For Interview Preparation