Data Structures interview revision notes

Interview-focused Data Structures revision. Written for developers preparing for an interview who want to refresh their Data Structures fast. Free, no sign-up.

What are data structures?

Simple real-life example (Understand first — very important for understanding)

Think of data structures as different ways to organize and store data so that certain operations (finding, adding, sorting) are easy or fast.
Like choosing the right container: a list for order, a stack for undo, a queue for waiting in line, a tree for hierarchy.
Picking the right structure makes your program simpler and faster.

Real-world idea: the right organization for the job. Data structures are how we arrange data so we can work with it efficiently.

Technical definition

Data structures are ways to organize and store data so that operations (insert, search, delete, traverse) can be done efficiently.
Choice of structure affects time (how fast) and space (how much memory). Different problems need different structures (e.g. hash for O(1) lookup, tree for ordered data).
Common categories: linear (array, list, stack, queue), tree (binary tree, BST, heap), graph, hash-based. Plus techniques: recursion, two pointers, binary search, DP, greedy.

Simple practical example

Choice of structure affects time (how fast) and space (how much memory).

Code example

// Need fast lookup by key? → Hash table
// Need order / range queries? → BST or sorted array + binary search
// Need LIFO (undo)? → Stack

Why it matters

Coding interviews focus on picking the right structure and justifying time/space complexity. "Which data structure would you use?" is very common.

Interview tip

"Pick structure by operations you need: array for index access, hash for lookup, stack/queue for order, tree for sorted/ hierarchical."

Big O notation

Simple real-life example (Understand first — very important for understanding)

Like describing how long a task takes as the amount of data grows: "double the list, double the time" vs "double the list, same time."
Big O gives a simple way to compare algorithms: O(1) constant, O(n) linear, O(n²) quadratic, etc. It ignores constants and focuses on growth.
You use it to choose the right algorithm and data structure when data can get large.

Real-world idea: how does effort grow with size? Big O helps you compare and choose algorithms.

Technical definition

Big O describes upper bound on growth (worst case): O(1) constant, O(n) linear, O(n²) quadratic, O(log n) logarithmic, O(n log n) for efficient sorts.
Drop constants and lower terms: 3n + 2 → O(n). Space complexity = extra memory used (e.g. O(n) for copying array).
Common: array access O(1); linear scan O(n); binary search O(log n); two nested loops over n O(n²); merge sort O(n log n).

Simple practical example

Drop constants and lower terms: 3n + 2 → O(n).

Code example

// Single loop → O(n)
for (let i = 0; i < n; i++) ...

// Two nested loops over n → O(n²)
for (let i = 0; i < n; i++)
  for (let j = 0; j < n; j++) ...

Why it matters

You must state time and space complexity and compare solutions. "What's the time complexity?" is asked in almost every problem.

Interview tip

"Big O = worst-case growth. State time and space. Know O(1), O(n), O(log n), O(n²), O(n log n) and when they appear."

Array

Simple real-life example (Understand first — very important for understanding)

Like a row of boxes numbered 0, 1, 2… You can jump to any box by index, add at the end, or walk through the whole row.
Arrays are good when you need order and fast access by position; inserting or deleting in the middle can be costly (you may shift elements).
The basic structure behind lists and vectors in most languages.

Real-world idea: ordered, indexable list. Arrays give fast access by index and are the foundation of many other structures.

Technical definition

Contiguous memory; index access O(1). Insert/delete at end O(1) amortized; in middle O(n) (shift). Size fixed (static) or dynamic (e.g. JS array, ArrayList).
Use for: random access, iteration, when order matters. Two pointers (start/end) for pair sum, palindrome; prefix sum for range sum.
Sorting in place: O(n log n) with quicksort/mergesort. Binary search on sorted array: O(log n).

Simple practical example

Use for: random access, iteration, when order matters.

Code example

// Two sum: use hash map for O(n)
// Or sort + two pointers if need to avoid duplicates
const twoSum = (arr, target) => {
  const seen = new Map();
  for (let i = 0; i < arr.length; i++) {
    if (seen.has(target - arr[i])) return [seen.get(target - arr[i]), i];
    seen.set(arr[i], i);
  }
};

Why it matters

Arrays are the most common input. Many problems are "array + two pointers" or "array + hash map". Know index vs value and in-place tricks.

Interview tip

"Array: O(1) access; insert middle O(n). Use two pointers, hash map, or sort + binary search depending on problem."

String (common operations)

Simple real-life example (Understand first — very important for understanding)

Like a sequence of characters (letters, digits, symbols). Often treated as an array of characters or as an immutable value.
Common operations: length, concatenate, find substring, split, replace. Many problems (parsing, matching) are about processing strings.
Pattern matching and string algorithms (e.g. sliding window) show up often in interviews.

Real-world idea: text as a sequence of characters. String operations and patterns are fundamental in many problems.

Technical definition

String as array of characters (in many languages immutable — operations return new string). Length, index, slice, compare. Check anagram: sort both or count chars (array/hash).
Palindrome: two pointers from both ends, or reverse and compare. Substring: sliding window or two pointers for "longest substring with at most K distinct".
Pattern matching: brute force O(n*m); KMP for linear; or hash (rolling hash) for Rabin-Karp. For interviews, often hash or brute is enough.

Simple practical example

Palindrome: two pointers from both ends, or reverse and compare.

Code example

// Palindrome check
const isPal = (s) => {
  let i = 0, j = s.length - 1;
  while (i < j) { if (s[i++] !== s[j--]) return false; }
  return true;
};

Why it matters

String problems are frequent (palindrome, anagram, substring, parsing). Know immutability and when to use array of chars for in-place style.

Interview tip

"Strings often immutable; use two pointers for palindrome/substring. Anagram: sort or count array. Sliding window for longest substring."

Linked List

Simple real-life example (Understand first — very important for understanding)

Like a chain of beads: each bead points to the next (and maybe the previous); there is no "index"—you walk from the head to find a position.
Adding or removing at the head (or tail with a tail pointer) is cheap; access by index is slow because you have to traverse.
Use when you insert/delete often at the beginning or when you don't need random access.

Real-world idea: items chained one after another. Linked lists are good when you add or remove at the ends often.

Technical definition

Nodes with value and pointer(s) to next (singly) or next + prev (doubly). No random access — traverse from head: O(n). Insert/delete at head O(1); at known node O(1) if you have ref; middle O(n) to find.
Use for: when insert/delete at head or in middle (with ref) is frequent; queues (with tail pointer); LRU cache (doubly + hash).
Classic: reverse list (iterative with prev/curr/next), detect cycle (slow/fast pointers), find middle (slow/fast), merge two sorted lists.

Simple practical example

Use for: when insert/delete at head or in middle (with ref) is frequent; queues (with tail pointer); LRU cache (doubly + hash).

Code example

// Reverse singly linked list
let prev = null, curr = head;
while (curr) {
  const next = curr.next;
  curr.next = prev;
  prev = curr;
  curr = next;
}
return prev;

Why it matters

"Reverse a linked list" and "detect cycle" are standard. Know dummy node trick and fast/slow pointers.

Interview tip

"No random access; insert at head O(1). Use dummy node for simpler edge cases. Fast/slow for cycle and middle."

Stack

Simple real-life example (Understand first — very important for understanding)

Like a stack of plates: you add on top (push) and take from the top (pop); last in, first out (LIFO).
Use for undo (push each state, pop to undo), matching brackets, or any "reverse order" or "last thing first" need.
No random access; you only see or remove the top.

Real-world idea: last in, first out. Stacks are for undo, parsing, and anything that needs "most recent first."

Technical definition

LIFO: push (add top), pop (remove top), peek (top without remove). All O(1) with array or linked list. Use for: undo, parentheses matching, DFS, expression evaluation (postfix).
Monotonic stack: keep stack in sorted order (e.g. strictly increasing). Use for "next greater element", "largest rectangle in histogram".
Implement with array (push/pop) or linked list. Call stack in recursion is a stack.

Simple practical example

Monotonic stack: keep stack in sorted order (e.

Code example

// Valid parentheses
const valid = (s) => {
  const stack = [], map = { ')': '(', ']': '[', '}': '{' };
  for (const c of s) {
    if (c in map) { if (stack.pop() !== map[c]) return false; }
    else stack.push(c);
  }
  return stack.length === 0;
};

Why it matters

Parentheses, valid parentheses, next greater element, and DFS all use stack. Monotonic stack is a common advanced pattern.

Interview tip

"Stack: LIFO, push/pop O(1). Use for matching, DFS, undo. Monotonic stack for next greater / histogram problems."

Queue

Simple real-life example (Understand first — very important for understanding)

Like a line at a counter: first in, first out (FIFO); you add at the back (enqueue) and take from the front (dequeue).
Use for tasks in order (e.g. print queue), BFS in graphs, or any fair ordering where the first arrived is served first.
Often implemented with a linked list or a circular array.

Real-world idea: first in, first out. Queues are for fair ordering and breadth-first processing.

Technical definition

FIFO: enqueue (add back), dequeue (remove front). O(1) with doubly linked list or circular buffer; array dequeue is O(n) if shift. Use for: BFS, task scheduling, sliding window max (deque).
Priority queue (heap): dequeue returns min or max. Use for merge K sorted lists, top K, Dijkstra. Deque (double-ended): push/pop both ends — sliding window max.
BFS on graph/tree always uses a queue to process level by level.

Simple practical example

Priority queue (heap): dequeue returns min or max.

Code example

// BFS template
const q = [start];
while (q.length) {
  const node = q.shift();
  // process node
  for (const next of node.neighbors) q.push(next);
}

Why it matters

BFS = queue. "Level order traversal" and "shortest path in unweighted graph" need a queue. Know when to use deque or priority queue.

Interview tip

"Queue: FIFO; use for BFS. Deque for sliding window max; priority queue (heap) for top K or Dijkstra."

Hash Table

Simple real-life example (Understand first — very important for understanding)

Like a dictionary: you look up a word (key) and get the definition (value); you can add, find, and remove by key very fast on average.
Hash tables map keys to values using a hash function; average lookup/insert/delete is O(1); good for "do I have this?" or "what value goes with this key?"
Use when you need fast lookup by key, counting occurrences, or deduplication.

Real-world idea: look up by key quickly. Hash tables give fast lookup, insert, and delete by key.

Technical definition

Key–value store: average O(1) insert, lookup, delete. Implemented with array + hash function + collision handling (chaining or open addressing).
Use for: count frequency, "have we seen this?", two sum, grouping (group anagrams by sorted key), cache (LRU with hash + doubly linked list).
Trade-off: no order (use ordered map if you need sorted keys). Collisions can degrade to O(n) worst case; good hash + load factor matter.

Simple practical example

Use for: count frequency, "have we seen this?

Code example

// Count frequency
const freq = new Map();
for (const x of arr) freq.set(x, (freq.get(x) || 0) + 1);
// Group anagrams: key = sorted string, value = list of strings

Why it matters

Many problems are "one pass with hash map": two sum, subarray sum, first non-repeating. "Can we do it in O(n)?" often means hash.

Interview tip

"Hash: O(1) average lookup. Use for frequency, 'seen', two sum, grouping. No order; use Map for key-count or key-list."

Tree & Binary Tree

Simple real-life example (Understand first — very important for understanding)

Like a family tree or folder structure: each node has children (and one parent); you can have a root and walk down the branches.
Trees are used for hierarchies, sorting (binary search tree), and many algorithms (traversals, path finding).
Common: binary tree (at most two children), and balanced trees for efficient search and insert.

Real-world idea: hierarchy and branching. Trees organize data in levels and support efficient search and traversal.

Technical definition

Tree: nodes, one root, each node has children. Binary tree: at most two children (left, right). No order guarantee unless BST. Traversals: inorder (L root R), preorder (root L R), postorder (L R root), level order (BFS).
Recursive definition: empty or root + left subtree + right subtree. Many problems: max depth, same tree, invert, path sum — solve with recursion (or iterative with stack/queue).
DFS: stack (or recursion); BFS: queue. Inorder on BST gives sorted order.

Simple practical example

Recursive definition: empty or root + left subtree + right subtree.

Code example

// Max depth
const maxDepth = (root) => !root ? 0 : 1 + Math.max(maxDepth(root.left), maxDepth(root.right));

// Inorder (BST → sorted)
const inorder = (root) => {
  if (!root) return;
  inorder(root.left);
  console.log(root.val);
  inorder(root.right);
};

Why it matters

Tree problems are everywhere: depth, path sum, serialize, LCA. Know the four traversals and when to use recursion vs iterative.

Interview tip

"Tree: recursive or stack/queue. Inorder/pre/post/level order. Inorder on BST = sorted. Many problems are recursive on left/right."

Binary Search Tree (BST)

Simple real-life example (Understand first — very important for understanding)

Like a sorted list arranged as a tree: smaller values go left, larger go right, so finding, inserting, and checking membership is fast when the tree is balanced.
Binary search tree (BST) keeps an ordering; in-order traversal gives sorted order. Balance (e.g. AVL, red-black) keeps operations O(log n).
Use when you need ordered data with fast search, insert, and delete.

Real-world idea: a tree that keeps things sorted. BST gives ordered storage with efficient search and updates.

Technical definition

Binary tree with order: left < root < right (or equivalent). Inorder traversal = sorted. Search, insert, delete: O(h) where h = height (O(log n) if balanced).
Use for: search, range queries (inorder between L and R), successor/predecessor. Validate BST: pass [min, max] down and check each node.
Balanced BST (AVL, Red-Black): h = O(log n). Language libraries: TreeSet/TreeMap (Java), set/map with order (C++), or sorted structures.

Simple practical example

Use for: search, range queries (inorder between L and R), successor/predecessor.

Code example

// Search in BST
const search = (root, val) => {
  if (!root || root.val === val) return root;
  return val < root.val ? search(root.left, val) : search(root.right, val);
};

Why it matters

"Validate BST", "Kth smallest in BST" (inorder), "LCA in BST" (compare with root) are common. Know inorder = sorted.

Interview tip

"BST: left < root < right; inorder = sorted. Search/insert O(h). Validate by passing [min,max] range."

Heap

Simple real-life example (Understand first — very important for understanding)

Like a priority queue: the "most important" (e.g. largest or smallest) is always at the top; you add items and always take or peek at the top.
A heap is a tree (usually binary) where the parent is always ≥ or ≤ children; insert and remove-top are O(log n).
Use for priority queues, heapsort, or "always process the biggest/smallest first."

Real-world idea: always get the top priority item. Heaps give fast insert and remove-max (or min).

Technical definition

Min-heap: parent ≤ children; root = min. Max-heap: parent ≥ children; root = max. Stored as array: parent at i, children at 2i+1, 2i+2. Insert and extract-min/max: O(log n).
Use for: priority queue, top K elements (min-heap of size K), merge K sorted lists, heap sort. Get min/max: O(1).
No general search: heap is not sorted; only guarantee is root. For "top K", keep K elements in heap; if larger than min, pop min and push new.

Simple practical example

Use for: priority queue, top K elements (min-heap of size K), merge K sorted lists, heap sort.

Code example

// Top K largest: min-heap of size K
// For each x: if heap.size < K, push; else if x > heap.peek(), pop then push(x)
// JS: no built-in heap; use array + manual heapify or library

Why it matters

"Top K frequent", "merge K sorted lists", "find median" (two heaps) use heaps. Know array representation and O(log n) insert/extract.

Interview tip

"Heap: min/max at root; insert/extract O(log n). Use for top K, merge K lists, median. Array: children at 2i+1, 2i+2."

Graph (BFS, DFS)

Simple real-life example (Understand first — very important for understanding)

Like a map of cities and roads: nodes (cities) and edges (roads); you can have one-way or two-way links, and weights (e.g. distance).
Graphs model networks: social connections, routes, dependencies. You traverse with BFS or DFS and solve path and connectivity problems.
Representation: adjacency list (list of neighbors per node) or matrix; choice affects speed and memory.

Real-world idea: things connected by links. Graphs model relationships and networks; BFS/DFS are the basic tools.

Technical definition

Graph: vertices + edges. Directed/undirected; weighted/unweighted. Representation: adjacency list (list of neighbors per node) or matrix. List is usually better for sparse graphs.
BFS: queue; shortest path in unweighted graph; level by level. DFS: stack or recursion; cycle detection, topological sort, path finding. Visit set to avoid revisiting.
Topological sort: DFS with finish order (reverse) or Kahn (in-degree, queue). Shortest path weighted: Dijkstra (priority queue) or Bellman-Ford.

Simple practical example

BFS: queue; shortest path in unweighted graph; level by level.

Code example

// DFS template
const visit = (node, seen) => {
  if (seen.has(node)) return;
  seen.add(node);
  for (const next of node.neighbors) visit(next, seen);
};
// BFS: queue + seen; push neighbors

Why it matters

"Number of islands", "clone graph", "course schedule" = graph + BFS/DFS. Know adjacency list and when BFS vs DFS.

Interview tip

"Graph: adjacency list. BFS = queue (shortest unweighted); DFS = stack/recursion (cycles, topo). Use visited set."

Trie

Simple real-life example (Understand first — very important for understanding)

Like a tree of letters: each path spells a word or prefix; you can find all words that start with a prefix or check if a word exists.
Tries are used for autocomplete, spell check, and prefix search; they trade space for fast prefix and lookup.
Each node can have many children (one per possible next character).

Real-world idea: store and search by prefix. Tries are for words and prefix-based lookup.

Technical definition

Trie (prefix tree): tree where each node represents a character; path from root = prefix. Use for: autocomplete, prefix search, "word in dictionary", word search II.
Insert: follow path character by character; create nodes as needed. Search: follow path; check if node is end-of-word. Space: O(total chars); time per op O(length of word).
Can store count or end-of-word flag at nodes. Good when many strings share prefixes.

Simple practical example

Insert: follow path character by character; create nodes as needed.

Code example

// Trie node: { children: Map<char, Node>, isEnd: boolean }
// insert(word): for each char, go to or create child; mark isEnd at last
// search(word): follow path; return isEnd at last node

Why it matters

"Implement autocomplete", "prefix search", "word break" (trie or DP). Less common than array/hash/tree but good to know.

Interview tip

"Trie: prefix tree; each node = char. Insert/search O(word length). Use for prefix search, autocomplete, word break."

Recursion

Simple real-life example (Understand first — very important for understanding)

Like a task that breaks into smaller versions of the same task: "solve for n by solving for n-1 and combining."
You need a base case (when to stop) and a recursive case (call itself with a smaller input).
Use for trees, divide-and-conquer, and when the structure of the problem is self-similar.

Real-world idea: solve by breaking into smaller same-shaped problems. Recursion is natural for trees and divide-and-conquer.

Technical definition

Function calls itself; base case (termination) and recursive case. Call stack holds state. Tree/graph DFS, divide-and-conquer (merge sort), backtracking are recursive.
Tail recursion: last action is recursive call (some languages optimize to loop). Avoid stack overflow: ensure base case is reached; consider iterative if depth is large.
Memoization: cache results of (params) to avoid repeated work — turns recursive solution into DP.

Simple practical example

Tail recursion: last action is recursive call (some languages optimize to loop).

Code example

// Fibonacci with memo
const fib = (n, memo = {}) => {
  if (n <= 1) return n;
  if (memo[n] != null) return memo[n];
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
};

Why it matters

Many problems are naturally recursive (tree, backtracking). "Convert to iterative" or "add memoization" are common follow-ups.

Interview tip

"Base case + recursive case. Memoization to avoid repeated work (DP). Iterative or stack if depth too large."

Two pointers & sliding window

Simple real-life example (Understand first — very important for understanding)

Like two fingers on a list: one at the start, one at the end (or both at the start), moving in a rule-based way to find a pair or a range.
Often used on sorted arrays: move the left or right pointer depending on whether the current sum is too big or too small.
Saves time by avoiding nested loops when one pass with two pointers is enough.

Real-world idea: two positions moving through the data. Two pointers often give O(n) solutions for pair or range problems.

Technical definition

Two pointers: two indices (often start/end or slow/fast). Sorted array: move left or right by comparison (two sum, pair with sum). Linked list: slow/fast for cycle, middle.
Sliding window: subarray/substring with some invariant (e.g. sum ≤ K, at most K distinct chars). Expand end; if invalid, shrink start. O(n) for one pass.
Fixed-size window: just maintain window of size K and update result. Variable size: expand until invalid, then shrink.

Simple practical example

Sliding window: subarray/substring with some invariant (e.

Code example

// Two sum (sorted): left=0, right=n-1; if sum < target left++; else right--
// Sliding window: max subarray sum ≤ K: expand right, while sum > K subtract arr[start++]

Why it matters

"Two sum", "three sum", "longest substring with K distinct", "max subarray sum" — two pointers or sliding window are standard.

Interview tip

"Two pointers: sorted array or slow/fast. Sliding window: expand/shrink for subarray/substring; O(n) single pass."

Binary search

Simple real-life example (Understand first — very important for understanding)

Like guessing a number: "Is it higher or lower?" You keep narrowing the range until you find the answer.
Binary search works on sorted data: compare with the middle, then search the left or right half; O(log n) steps.
Use whenever the data is sorted and you need to find a value or the right position (e.g. insert, lower_bound).

Real-world idea: halve the search space each step. Binary search is for sorted data and gives fast find or position.

Technical definition

On sorted array (or range): mid = (lo + hi) / 2; compare with target; go left or right. O(log n). Loop: while lo ≤ hi; update lo = mid+1 or hi = mid-1.
Variants: first occurrence, last occurrence, insert position, search in rotated array (one half is always sorted). Use condition that splits range and keeps answer in one half.
Binary search on answer: when answer is in a range (e.g. "minimum capacity"), binary search the range and check feasibility. Very common.

Simple practical example

Variants: first occurrence, last occurrence, insert position, search in rotated array (one half is always sorted).

Code example

let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
  const mid = (lo + hi) >> 1;
  if (arr[mid] === target) return mid;
  if (arr[mid] < target) lo = mid + 1;
  else hi = mid - 1;
}
return -1;

Why it matters

"Search in rotated array", "find first/last position", "binary search on answer" are frequent. Avoid off-by-one: use lo ≤ hi and mid±1.

Interview tip

"Sorted array or range; mid, compare, narrow half. Watch bounds (lo <= hi, mid+1/mid-1). Binary search on value range for 'min/max feasible'."

Sorting (Quick, Merge)

Simple real-life example (Understand first — very important for understanding)

Like arranging cards in order: you compare and swap (or merge, or partition) until everything is in the right order.
Different algorithms (quick sort, merge sort, etc.) have different trade-offs: time, space, stability. You often use the language's built-in sort.
Understanding sorting helps with "find the kth largest" or "merge sorted lists" type problems.

Real-world idea: put items in order. Sorting is a building block for many other algorithms and interview problems.

Technical definition

Merge sort: divide into halves, sort each, merge. O(n log n) time, O(n) extra space. Stable. Good for linked list (no random access).
Quick sort: pick pivot (e.g. last); partition (smaller left, larger right); recurse on both. O(n log n) average, O(n²) worst; in-place. Not stable.
Use built-in sort (usually O(n log n)) unless asked to implement. Know one O(n log n) sort and when stability or in-place matters.

Simple practical example

Quick sort: pick pivot (e.

Code example

// Merge sort: merge(left, right) with two pointers
// Quick sort: partition(arr, lo, hi) returns pivot index; then sort(lo, p-1), sort(p+1, hi)

Why it matters

"Sort an array" or "merge two sorted" are building blocks. "Implement quicksort/mergesort" sometimes asked. Know time/space and stability.

Interview tip

"Merge: O(n log n), stable, O(n) space. Quick: O(n log n) avg, in-place, pivot + partition. Built-in sort unless implement required."

Dynamic programming

Simple real-life example (Understand first — very important for understanding)

Like solving a puzzle by filling a table: you break the problem into subproblems, solve each once, store the answer, and reuse it.
DP avoids recomputing the same subproblem (e.g. Fibonacci, shortest path); you need a recurrence and a base case, then iterate or recurse with memoization.
Use when the problem has overlapping subproblems and optimal substructure.

Real-world idea: solve subproblems once and reuse. Dynamic programming turns exponential work into polynomial by storing results.

Technical definition

Solve by breaking into overlapping subproblems; store results (memoization or table) to avoid recomputation. Often "optimal substructure": optimal solution uses optimal solutions of subproblems.
Steps: define state (e.g. dp[i] = best for prefix i), recurrence (how dp[i] depends on earlier dp), base case, order of fill (often left to right or by dependency).
Classic: Fibonacci, climb stairs, coin change, knapsack, LCS, LIS, edit distance, max subarray. 1D or 2D table; sometimes space-optimized (e.g. only previous row).

Simple practical example

Steps: define state (e.

Code example

// Climb stairs: dp[i] = dp[i-1] + dp[i-2], dp[0]=1, dp[1]=1
// Coin change: dp[amount] = min over coins of 1 + dp[amount - coin]

Why it matters

DP is a major interview topic. "Can you do it in O(n²)?" often means DP. Start with recursive + memo, then convert to table if asked.

Interview tip

"Define state and recurrence; base case; fill table (or memo). Start recursive + memo; optimize space if needed."

Greedy

Simple real-life example (Understand first — very important for understanding)

Like making the best local choice at each step: pick the largest coin, schedule the shortest job first, and hope the overall result is optimal.
Greedy doesn't always give the best global answer, but when it does (e.g. activity selection, Huffman), it's simple and fast.
You often prove that the greedy choice is safe (stays in an optimal solution) and that subproblems remain.

Real-world idea: take the best local step and hope for the best overall. Greedy works when local best leads to global best.

Technical definition

Greedy: make locally optimal choice at each step hoping for global optimum. Works when "greedy choice" is safe (e.g. sort by end time for interval scheduling).
No general rule — prove or intuition that greedy works. Common: sort then iterate (intervals, tasks), Huffman, activity selection, jump game, merge intervals.
When greedy fails: need to consider future (e.g. some knapsack). Then use DP or backtracking.

Simple practical example

No general rule — prove or intuition that greedy works.

Code example

// Merge intervals: sort by start, then if curr.start <= last.end, merge (last.end = max(last.end, curr.end)); else push new

Why it matters

"Merge intervals", "non-overlapping intervals", "jump game" are often greedy. Know when to try "sort + one pass" or "pick best local option."

Interview tip

"Greedy: local optimal choice. Often sort first (by end or start). Prove it works for the problem or give counterexample."

Common patterns

Simple real-life example (Understand first — very important for understanding)

Many problems reuse the same ideas: sliding window (contiguous subarray), fast/slow pointers (cycle detection), or merge intervals.
Recognizing the pattern (e.g. "this is a BFS," "this is two pointers") helps you pick the right structure and algorithm.
Practice common patterns so you can map a new problem to a known approach.

Real-world idea: reuse known patterns. Sliding window, two pointers, and other patterns show up again and again.

Technical definition

Prefix sum: precompute sum[0..i]; range sum [i,j] = sum[j] - sum[i-1]. O(1) range sum after O(n) precompute. Use for subarray sum, equilibrium.
Sliding window: see section 15. Two pointers: sorted array or slow/fast. Binary search on answer: range [lo, hi], check(mid) feasible.
Cycle detection: Floyd (slow/fast) in linked list or graph. Union Find: disjoint sets, merge and find parent; use for connectivity, cycle in undirected graph.

Simple practical example

Sliding window: see section 15.

Code example

// Prefix sum: sum[i] = sum[i-1] + arr[i]; rangeSum(i,j) = sum[j] - (sum[i-1] || 0)
// Union Find: find(x) with path compression; union(x,y) by rank or size

Why it matters

Many problems are a combination: "subarray sum" = prefix sum or sliding window; "connectivity" = Union Find or BFS/DFS.

Interview tip

"Prefix sum for range sum. Union Find for disjoint sets. Know sliding window, two pointers, binary search on answer; combine as needed."

Practise the questions

Read the top 50 Data Structures interview questions and answers to test yourself after revising.

20 topics in these notes

What are data structures?

Simple real-life example (Understand first — very important for understanding)

Technical definition

Simple practical example

Code example

Why it matters

Interview tip

Big O notation

Simple real-life example (Understand first — very important for understanding)

Technical definition

Simple practical example

Code example

Why it matters

Interview tip

Array

Simple real-life example (Understand first — very important for understanding)

Technical definition

Simple practical example

Code example

Why it matters

Interview tip

String (common operations)

Simple real-life example (Understand first — very important for understanding)

Technical definition

Simple practical example

Code example

Why it matters

Interview tip

Linked List

Simple real-life example (Understand first — very important for understanding)

Technical definition

Simple practical example

Code example

Why it matters

Interview tip

Stack

Simple real-life example (Understand first — very important for understanding)

Technical definition

Simple practical example

Code example

Why it matters

Interview tip

Queue

Simple real-life example (Understand first — very important for understanding)

Technical definition

Simple practical example

Code example

Why it matters

Interview tip

Hash Table

Simple real-life example (Understand first — very important for understanding)

Technical definition

Simple practical example

Code example

Why it matters

Interview tip

Tree & Binary Tree

Simple real-life example (Understand first — very important for understanding)

Technical definition

Simple practical example

Code example

Why it matters

Interview tip

Binary Search Tree (BST)

Simple real-life example (Understand first — very important for understanding)

Technical definition

Simple practical example

Code example

Why it matters

Interview tip

Heap

Simple real-life example (Understand first — very important for understanding)

Technical definition

Simple practical example

Code example

Why it matters

Interview tip

Graph (BFS, DFS)

Simple real-life example (Understand first — very important for understanding)

Practise the questions