Data Structures & Algorithms — Interview Reference

Data Structures & Algorithms

Lecturer Interview Reference Guide

Full-depth coverage: definitions, formulas, derivations, and every DSA question pattern that has
appeared across your past interview transcripts.

Page 1 of 43
Data Structures & Algorithms — Interview Reference

TOC \h \o "1-2"

Page 2 of 43
Data Structures & Algorithms — Interview Reference

1. Complexity Analysis — the language you'll use for everything else

1.1 Asymptotic notation, precisely defined
• Big-O (O) — upper bound: f(n) = O(g(n)) if there exist positive constants c and n₀ such that f(n) ≤
c·g(n) for all n ≥ n₀. Describes the worst case growth rate.
• Big-Omega (Ω) — lower bound: f(n) = Ω(g(n)) if there exist positive constants c and n₀ such that
f(n) ≥ c·g(n) for all n ≥ n₀. Describes the best case growth rate.
• Big-Theta (Θ) — tight bound: f(n) = Θ(g(n)) if f(n) is both O(g(n)) and Ω(g(n)) — the function is
sandwiched on both sides by the same growth rate. This is the strongest, most informative
statement, and the one to give whenever you actually know it.
Common confusion to avoid: “worst case” and “O” are not synonyms, even though people use them
that way casually. You can describe the best case using O too (it's just a looser, less useful bound).
Precisely: “worst-case time complexity is Θ(n²)” is a statement about which input produces the
slowest behavior, while O/Ω/Θ are statements about how tightly a bound describes growth. In
interviews, the panel usually accepts O for “worst case” colloquially, but knowing the precise
distinction is a strong signal of depth if asked directly.

1.2 Common growth rates, smallest to largest

Notation Name Example

O(1) Constant Array index access, hash table lookup (average case)
O(log n) Logarithmic Binary search, balanced BST operations
O(n) Linear Linear search, single pass through an array
O(n log n) Linearithmic Merge sort, heap sort, efficient comparison sorts
O(n²) Quadratic Bubble sort, insertion sort, selection sort (worst case)
Naive recursive Fibonacci, brute-force subset
O(2ⁿ) Exponential
enumeration
Brute-force traveling salesman, generating all
O(n!) Factorial
permutations

1.3 Master rules for deriving complexity

• Drop constants and lower-order terms: 3n² + 5n + 7 → O(n²).
• Nested loops multiply: a loop of n inside a loop of m is O(n·m); two nested loops both over the
same n is O(n²).
• Sequential (non-nested) blocks add, and you keep only the dominant term: an O(n) pass
followed by an O(n²) pass is O(n) + O(n²) = O(n²).

Page 3 of 43
Data Structures & Algorithms — Interview Reference

• Recursive complexity is found by solving the recurrence relation it satisfies (see Section 4 for
worked examples like the Master Theorem applied to merge sort).

2. Arrays and Searching

2.1 Array basics
A contiguous block of memory holding elements of the same type, enabling O(1) random access via
index arithmetic: address(arr[i]) = base_address + i × element_size. This direct address computation is
exactly why arrays give O(1) access while linked lists do not (see Section 3).

2.2 Linear Search

Scan every element until found (or the array ends).

Case Time complexity When it occurs

Best O(1) Target is the first element
Average O(n) Target is in a random position
Worst O(n) Target is the last element, or not present at all
Works on any array, sorted or unsorted, and on any sequential structure (including a linked list) — it
makes no assumptions about ordering.

2.3 Binary Search

Requires a sorted array. Repeatedly halve the search space by comparing the target to the middle
element.
lo = 0, hi = n - 1
while lo <= hi:
mid = lo + (hi - lo) / 2
if arr[mid] == target: return mid
elif arr[mid] < target: lo = mid + 1
else: hi = mid - 1
return -1 # not found

Why mid = lo + (hi - lo) / 2 and not (lo + hi) / 2: the second form can integer-overflow if lo and hi are
both large, in languages with fixed-width integers. This is exactly the same bug class as the Java
binary-search integer-overflow bug referenced in the Security guide — a great cross-topic callback if
you want to show range.

Case Time complexity

Best O(1) (target is the first middle checked)
Average / Worst O(log n)

Page 4 of 43
Data Structures & Algorithms — Interview Reference

• Derivation of O(log n): each comparison discards half the remaining elements. Starting from n
elements, after k halvings, n/2^k elements remain; the search ends when n/2^k = 1, i.e. k =
log₂(n). So at most log₂(n) comparisons are needed.

2.4 The “array list / Python list / linked list” ambiguity (Swakkhar sir's question,
worked in full)
This question rewards giving a structured, diplomatic answer that explicitly covers both interpretations
rather than guessing which one was meant.

Interpretation Best-case search Why

Only if the target happens to be at the very
Unsorted array / Python list O(1) first index checked — still requires linear
search overall
Sorted array (binary search Target happens to be exactly the middle
O(1)
applicable) element on the first check
Target happens to be the head node — but
binary search is NOT possible on a linked list
Linked list (singly or doubly) O(1)
even if sorted, because there's no O(1)
random access to jump to a “middle” node
The follow-up the panel pushed on — “what's the time complexity of binary search, and is there an
alternative?”: log n for binary search (sorted array only); the alternative offered was a hash map,
giving O(1) average-case lookup regardless of order.
• The follow-up after that — “what's the drawback of using a hash map?”: memory inefficiency.
A hash table typically over-allocates space (load factor kept below ~0.7–0.75 to keep collision
rates low) and stores extra metadata per bucket/entry, so it generally uses more memory than a
tightly packed sorted array for the same data. It also loses the ordering information a sorted
array has for free (so range queries, “find the next largest element,” etc. become harder), and
average-case O(1) is not worst-case O(1) — a poor hash function or adversarial input can
degrade it to O(n) (see Section 8.4).

3. Linked Lists
3.1 Why linked lists exist (contrast with arrays)

Array Linked List

Scattered (nodes linked via
Memory layout Contiguous
pointers)
Random access O(1) O(n) — must traverse from the head
Insert/delete at front O(n) (shift elements) O(1)

Page 5 of 43
Data Structures & Algorithms — Interview Reference

Array Linked List

Insert/delete at O(n) to find the position, O(1) once
O(n)
arbitrary position there
Memory overhead None beyond the data Extra pointer(s) per node
Cache locality Good (contiguous) Poor (pointer chasing)

3.2 Types of linked lists

• Singly linked list: each node holds data + a pointer to the next node. Traversal is one-directional.
• Doubly linked list: each node additionally holds a pointer to the previous node — enables O(1)
backward traversal and O(1) deletion given only a pointer to the node itself (no need to find its
predecessor first).
• Circular linked list: the last node points back to the first (in a singly circular list) or the list is
circular in both directions (doubly circular) — useful for round-robin scheduling, circular buffers.

3.3 Operation complexity table

Operation Singly linked list Doubly linked list

Access by index O(n) O(n)
Search O(n) O(n)
Insert at head O(1) O(1)
O(1) if a tail pointer is
Insert at tail (no tail pointer) O(n)
maintained
Delete at head O(1) O(1)
O(1) (predecessor is directly
Delete given a pointer to the node O(n) (must find predecessor)
known)

3.4 Classic linked-list interview patterns (good to have ready even if not explicitly in
your transcripts)
• Reversing a linked list: iteratively walk the list keeping prev, curr, next pointers, relinking
[Link] = prev at each step — O(n) time, O(1) extra space.
• Detecting a cycle (Floyd's cycle detection / “tortoise and hare”): two pointers, one advancing 1
step at a time, one advancing 2 steps at a time. If there's a cycle, the fast pointer eventually laps
the slow pointer and they meet; if there's no cycle, the fast pointer reaches the end first. O(n)
time, O(1) space — a frequently-cited example of a clever space-optimal solution.
• Finding the middle node: same two-pointer idea — when the fast pointer reaches the end, the
slow pointer is at the middle.

Page 6 of 43
Data Structures & Algorithms — Interview Reference

4. Stacks and Queues

4.1 Stack — LIFO (Last In, First Out)

Operation Description Time

push(x) Add x to the top O(1)
pop() Remove and return the top element O(1)
peek() / top() Return the top element without removing it O(1)
isEmpty() Check if the stack has no elements O(1)
• Applications: function call stacks / recursion (this is literally how the call stack itself works —
each call pushes a frame, each return pops it), undo functionality, expression evaluation and
syntax parsing (matching parentheses, infix-to-postfix conversion), DFS (can be implemented
either recursively, using the call stack implicitly, or iteratively with an explicit stack),
backtracking algorithms.
• Implementation: via a dynamic array (amortized O(1) push, with occasional O(n) resize) or via a
linked list (true O(1) push/pop, no resize needed, but extra pointer memory per element).

4.2 Queue — FIFO (First In, First Out)

Operation Description Time

enqueue(x) Add x to the back O(1)
dequeue() Remove and return the front element O(1)
front() / peek() Return the front element without removing it O(1)
isEmpty() Check if the queue has no elements O(1)
• Applications: BFS, task/job scheduling, buffering (I/O, printer queues), simulating real-world
waiting lines.
• Circular queue: a fixed-size array-backed queue where front/rear indices wrap around modulo
the array size, avoiding the wasted space a naive array-backed queue would accumulate at the
front as elements are dequeued.
• Deque (double-ended queue): supports O(1) insertion/removal at both ends — a strict
generalization of both stack and queue.
• Priority queue: not strictly FIFO — elements come out in priority order rather than insertion
order; almost always implemented with a heap (Section 7), giving O(log n) insert and O(log n)
extract-min/max.

Page 7 of 43
Data Structures & Algorithms — Interview Reference

5. Recursion
5.1 Anatomy of a recursive function
• Base case: the condition under which the function returns directly without recursing — without
this, recursion never terminates.
• Recursive case: the function calls itself on a smaller/simpler version of the problem, then
combines that result to solve the original problem.

5.2 GCD using recursion (asked directly)

Euclid's algorithm: gcd(a, b) = gcd(b, a mod b), with base case gcd(a, 0) = a.
function gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)

• Why this works: any common divisor of a and b also divides (a mod b), and vice versa, so
gcd(a,b) = gcd(b, a mod b) exactly — this identity is the entire correctness proof.
• Time complexity: O(log(min(a,b))) — each recursive step at least halves one of the two numbers
within roughly two steps (a consequence of properties of the Fibonacci-like worst case), giving
logarithmic rather than linear behavior. This is a notably better bound than students often guess
instinctively (many assume O(min(a,b)) by analogy with naive repeated subtraction).

5.3 Division without using / or % (asked directly: “find quotient and remainder
dividing a by b”)
Core idea: division is repeated subtraction. Naively subtracting b from a repeatedly until a < b gives the
quotient (count of subtractions) and remainder (final a) — but that's O(a/b) time, which is poor when a
is much larger than b.
A faster approach uses repeated doubling (binary/bit-shift long division), getting O(log a) time:
function divide(a, b): # a = dividend, b = divisor, both positive
quotient = 0
remainder = a
while remainder >= b:
temp = b
multiple = 1
while (temp << 1) <= remainder: # double temp while it still fits
temp = temp << 1
multiple = multiple << 1
remainder = remainder - temp
quotient = quotient + multiple
return quotient, remainder

• Why doubling is faster: instead of subtracting b one copy at a time (a/b iterations), we subtract
the largest power-of-two multiple of b that still fits, each outer iteration removing at least half
of what's left — giving O(log a) outer iterations rather than O(a/b).

Page 8 of 43
Data Structures & Algorithms — Interview Reference

If pressed for the simplest correct answer on paper (lower bar, still correct): the simple repeated-
subtraction version is perfectly acceptable as a first answer (“quotient = number of times you can
subtract b from a before it goes below b; remainder = what's left”) — know it cold, then offer the
doubling optimization if asked “can you do better?”

6. Trees
This is the single most heavily and repeatedly tested DSA topic in your transcripts — the BST
height/node-count question appeared in at least two separate interviews (Huda sir), and the complete
binary tree definition was explicitly called out as a question where “all previous candidates gave false
answers.” Treat every definition in this section as something you must be able to state with zero
hesitation and zero imprecision.

6.1 Core terminology (precise definitions — get these exactly right)

• Node: a single element of the tree, holding data and pointers/references to its children.
• Root: the single node with no parent; the topmost node.
• Leaf: a node with no children.
• Edge: the connection between a parent and a child node.
• Depth of a node: the number of edges from the root to that node. The root has depth 0.
• Height of a node: the number of edges on the longest path from that node down to a leaf. A leaf
has height 0.
• Height of a tree: the height of its root — equivalently, the number of edges on the longest root-
to-leaf path.
The exact trap from Huda sir's question: whether height is measured starting at 0 or 1 at the root is a
convention, and the panel explicitly tested whether the candidate could adapt their formula when
told to restart counting from h=0. Always clarify or state your convention explicitly before giving a
height-dependent formula, and know how to convert between the two conventions on the spot.

6.2 Binary Tree — definitions

• Binary tree: a tree in which every node has at most 2 children, conventionally called left and
right.
• Full (proper) binary tree: every node has either 0 or 2 children (never exactly 1).
• Complete binary tree (THE definition that “impressed” the panel — get this word-for-word
right): a binary tree in which every level is completely filled, except possibly the last level, and
the last level's nodes are filled from left to right with no gaps.
Why candidates commonly get this wrong (and what the panel is actually checking): people often
confuse “complete” with “full” (0-or-2-children) or with “perfect” (every level fully filled, every leaf at
the same depth). These are three genuinely distinct definitions, and the panel's remark that “previous
candidates gave false answers” almost certainly refers to exactly this confusion. State all three crisply
and the contrast itself becomes a strong answer.

Page 9 of 43
Data Structures & Algorithms — Interview Reference

• Perfect binary tree: every internal node has exactly 2 children AND every leaf is at the same
depth. A perfect binary tree is automatically both full and complete (the reverse is not true).
• Balanced binary tree: for every node, the heights of its left and right subtrees differ by at most
some small bound (commonly 1, as in an AVL tree) — a more flexible, performance-oriented
notion distinct from “complete” or “perfect.”
• Degenerate (pathological) tree: every node has only one child — structurally equivalent to a
linked list; height = n−1 for n nodes, the worst possible case for any tree-based operation.

6.3 The BST height → node-count derivation (Huda sir's exact question, worked in full)
Question as posed: “Given a balanced binary search tree of height h, what's the total number of nodes
in it?”
Work through this with the height-starts-at-0 convention (root has height 0), which is the convention
Huda sir asked for after the candidate's first attempt used height starting at 1.
1. At height 0 (just the root): exactly 1 = 2⁰ node.
2. At height 1 (root + 2 children, fully filled): the root contributes 1, plus 2 children = 2¹ — total so
far 1 + 2 = 3 nodes.
3. At height 2 (one more fully filled level): add 4 = 2² more nodes — total 1 + 2 + 4 = 7 nodes.
4. Generalizing: a perfectly filled binary tree of height h has, level by level, 2⁰, 2¹, 2², …, 2ʰ nodes.
The total node count is the sum of this geometric series: N = 2⁰ + 2¹ + … + 2ʰ = 2^(h+1) − 1.
This is the exact final answer Huda sir was looking for: N = 2^(h+1) − 1, where h is the height
measured with the root at height 0. (If you instead define height starting at 1 — i.e. the root itself
counts as “level 1” — the same tree of “level-height” h has h−1 edges of height in the 0-indexed
sense, giving N = 2^h − 1 instead. This is precisely the off-by-one correction the candidate had to make
live on paper — know both forms and which convention each corresponds to.)
• The geometric series formula itself, worth having ready independently: 1 + 2 + 4 + … + 2^k =
2^(k+1) − 1. This is simply the formula for the sum of a geometric series with ratio 2.
• Equivalent / inverse formula (also worth having ready — “given n nodes, what's the height”):
for a tree with N nodes that is as balanced/complete as possible, h = ⌊log₂(N)⌋ — i.e. height
grows logarithmically with the number of nodes. This is the entire reason balanced BSTs give
O(log n) operations: the height (which bounds the number of comparisons on a root-to-leaf
path) is logarithmic in the node count.

6.4 BST (Binary Search Tree) — the ordering property and operations
• BST property: for every node, all values in its left subtree are less than the node's value, and all
values in its right subtree are greater (assuming no duplicates; conventions vary slightly on
where duplicates go).
Operation Balanced BST Degenerate / unbalanced BST
Search O(log n) O(n)
Insert O(log n) O(n)

Page 10 of 43
Data Structures & Algorithms — Interview Reference

Operation Balanced BST Degenerate / unbalanced BST

Delete O(log n) O(n)
Find min / max O(log n) (leftmost / rightmost path) O(n)
• Why balance matters so much: every one of these operations runs in time proportional to the
tree's height, and height ranges from Θ(log n) (balanced) all the way up to Θ(n) (degenerate, e.g.
if you insert already-sorted data into a naive BST with no rebalancing). This is the single most
important “why” in this entire section.
• Self-balancing BSTs (know these exist, one line each): AVL tree (rebalances via rotations to
keep left/right subtree heights within 1 of each other at every node); Red-Black tree (rebalances
via a color-based invariant, used internally by many language standard libraries, e.g. C++'s
std::map and Java's TreeMap).

6.5 Tree traversals

Traversal Order Typical use

Copying/serializing a tree (lets you reconstruct
Pre-order Root → Left → Right
it by reading root-first)
In-order Left → Root → Right Visiting BST nodes in sorted order
Deleting a tree safely (children before parent),
Post-order Left → Right → Root
evaluating expression trees
Level-order Finding the shortest root-to-node path, printing
Level by level, left to right
(BFS) the tree level by level
• Key fact worth stating: in-order traversal of a BST always visits nodes in sorted (ascending)
order — a direct consequence of the BST ordering property, and a very common way to verify a
tree is a valid BST.
All four traversals run in O(n) time (each node visited exactly once) and O(h) extra space for the
recursion stack (or an explicit stack/queue), where h is the tree's height.

6.6 Tries (prefix trees) — brief, but good to recognize

A tree where each path from the root spells out a prefix of stored strings, with each edge labeled by a
character. Enables O(L) lookup/insert/prefix-search where L is the string length, independent of how
many strings are stored — used in autocomplete, IP routing tables, and dictionary/spell-check
implementations.

Page 11 of 43
Data Structures & Algorithms — Interview Reference

7. Heaps
7.1 Definition
A binary heap is a complete binary tree (Section 6.2 — every level fully filled except possibly the last,
which fills left to right) satisfying the heap property.
• Max-heap property: every parent's value is ≥ both of its children's values — the maximum
element is always at the root.
• Min-heap property: every parent's value is ≤ both of its children's values — the minimum
element is always at the root.
Important distinction: a heap is NOT a BST. There is no left-less-than-right-greater ordering between
siblings or across subtrees — the only guarantee is parent-vs-children. This is precisely why you can't
do an efficient “search for arbitrary value x” in a heap (that's O(n), no better than scanning); a heap is
specialized for repeatedly finding the min/max only.

7.2 Array representation (the standard implementation)

A binary heap is almost always stored as a flat array, exploiting the fact that it's a complete binary tree
— no explicit child/parent pointers are needed.
For a node at index i (0-indexed array):
left child index = 2*i + 1
right child index = 2*i + 2
parent index = (i - 1) / 2 (integer division)

• Why this works: completeness guarantees there are no gaps, so level-by-level left-to-right
numbering of nodes maps exactly onto consecutive array indices — this is the same indexing
idea used to address a complete binary tree without storing any pointers at all.

7.3 Operations and their complexity

Operation Time Mechanism

Peek min/max (root) O(1) Just read index 0
Append at the end, then “sift up” / “bubble up” —
Insert O(log n) repeatedly swap with the parent while the heap
property is violated
Swap root with the last element, remove the last
element, then “sift down” / “heapify” the new root —
Extract min/max O(log n)
repeatedly swap with the larger/smaller child while
violated
Build heap from n raw (Not O(n log n) as the naive “n inserts” analysis would
O(n)
elements suggest — see note below)
Why building a heap from scratch is O(n), not O(n log n) (a genuinely good “why” question if
pushed): you might guess “n inserts, each O(log n), so O(n log n).” But the standard build-heap

Page 12 of 43
Data Structures & Algorithms — Interview Reference

algorithm instead starts from an arbitrary array and sifts down from the bottom-most internal nodes
upward. Most nodes are near the bottom of the tree and only need to sift down a short distance; only
a few nodes near the root might sift the full O(log n) distance. Summing this more carefully across all
levels gives a geometric-series-like sum that totals O(n), not O(n log n).

7.4 Heap Sort

Build a max-heap from the array (O(n)), then repeatedly extract the max and place it at the end of the
unsorted region (n extractions, each O(log n)) — total O(n log n), in-place, but not stable (equal
elements can be reordered relative to each other).

7.5 Priority Queue

The abstract data type a heap is the standard implementation of: elements come out in priority order
rather than insertion order. Real-world uses: Dijkstra's shortest path and Prim's MST algorithm (both
repeatedly need “the next closest/cheapest unvisited node,” which a min-heap provides in O(log n) per
extraction), CPU task scheduling, event simulation.

8. Hashing
8.1 The core idea
A hash function maps a key (of potentially any size/type) to an index in a fixed-size array (the hash
table / hash map's underlying storage), giving average-case O(1) insert, lookup, and delete —
dramatically faster than the O(log n) of a balanced BST or O(n) of linear search, at the cost of losing any
ordering information.
• Properties of a good hash function: deterministic (same key always maps to the same index),
fast to compute, and distributes keys as uniformly as possible across the table to minimize
collisions.

8.2 Collisions and resolution strategies

A collision occurs when two different keys hash to the same index. No hash function can avoid collisions
entirely for an arbitrarily large key space mapped into a finite table (pigeonhole principle — see Section
10) — so every practical hash table needs a collision-resolution strategy.
• Chaining (open hashing): each table slot holds a linked list (or similar structure) of all entries
that hashed to that index. Simple, degrades gracefully, but each slot needs extra pointer
overhead.
• Open addressing (closed hashing): on a collision, probe for another open slot within the table
itself (linear probing: check the next slot; quadratic probing: check slots at increasing quadratic
offsets; double hashing: use a second hash function to determine the probe sequence). No extra
pointer overhead, but more sensitive to high load factors and clustering.

Page 13 of 43
Data Structures & Algorithms — Interview Reference

8.3 Load factor

Load factor α = n / m, where n is the number of stored entries and m is the number of table slots. As α
grows, collisions become more frequent and performance degrades; well-implemented hash tables
automatically resize (rehash into a larger table, typically doubling) once α crosses a threshold
(commonly around 0.7).”
• Average-case lookup time with chaining: O(1 + α) — the constant-time hash computation plus,
on average, scanning a chain of expected length α.

8.4 Hash map vs. sorted array vs. BST — the exact comparison the panel pushed on

Sorted array (binary

Hash map Balanced BST
search)
Average lookup O(1) O(log n) O(log n)
O(n) (pathological
Worst-case lookup O(log n) O(log n)
collisions)
Ordering preserved? No Yes Yes
Higher — extra slots
kept empty to control Lowest — tightly Moderate — pointer
Memory overhead load factor, plus per- packed, no extra per child, but no empty
entry structure slots
metadata/pointers
Range queries (“all Efficient (in-order
Not supported Efficient (binary search
keys between x and traversal between
efficiently both ends)
y”) bounds)
This is the exact answer structure for “what are the drawbacks of using a hash map instead of
binary search”: (1) memory inefficiency — hash tables intentionally keep spare capacity to control the
load factor, and pay per-entry overhead for chaining or open-addressing bookkeeping; (2) no ordering
— you lose the ability to do range queries, find a predecessor/successor, or iterate in sorted order, all
of which a sorted array or BST give for free; (3) average-case, not worst-case, O(1) — a hash map's
O(1) is an average over typical inputs assuming a decent hash function; an attacker who can choose
adversarial inputs (or simply bad luck with a weak hash function) can force many collisions and
degrade performance toward O(n).

8.5 Hash sets vs. hash maps

A hash set stores only keys (membership testing: “is x present?” in O(1) average); a hash map stores
key→value pairs. Internally, a hash set is typically just a hash map where the value is ignored/unit.

Page 14 of 43
Data Structures & Algorithms — Interview Reference

9. Graphs
9.1 Core terminology
• Graph G = (V, E): a set of vertices (nodes) V and a set of edges E connecting pairs of vertices.
• Directed vs. undirected: in a directed graph, an edge (u, v) only allows travel from u to v; in an
undirected graph, the edge allows travel both ways.
• Weighted vs. unweighted: weighted edges carry a cost/distance; unweighted edges are all
treated as cost 1.
• Degree of a vertex: the number of edges incident to it (in directed graphs, split into in-degree
and out-degree).
• Path: a sequence of vertices connected by edges. Simple path: no repeated vertices.
• Cycle: a path that returns to its starting vertex.
• Connected graph (undirected): there is a path between every pair of vertices.
• Dense vs. sparse graph: a graph is dense if |E| is close to its maximum possible value (Θ(V²) for
a simple undirected graph); sparse if |E| is much closer to Θ(V). This distinction is exactly what
the Prim's-vs-Kruskal's density question (Section 9.5) hinges on.

9.2 Representations

Check if edge (u,v) Iterate all

Representation Space Best for
exists neighbors of v
Dense
graphs, or
Adjacency matrix O(V²) O(1) O(V) when O(1)
edge lookup
matters
Sparse
graphs (most
Adjacency list O(V + E) O(degree(v)) worst case O(degree(v))
real-world
graphs)
Why this table matters beyond memorization: this single tradeoff — adjacency matrix wastes O(V²)
space on a sparse graph, but adjacency list wastes time chasing pointers on a dense graph — is the
entire justification behind the MST algorithm-choice question in Section 9.5.

9.3 Graph traversal — BFS and DFS

BFS (Breadth-First Search) DFS (Depth-First Search)

Stack (explicit, or implicitly via
Data structure Queue (FIFO)
recursion)
Level by level, outward from the As deep as possible down one branch
Explores
source before backtracking

Page 15 of 43
Data Structures & Algorithms — Interview Reference

BFS (Breadth-First Search) DFS (Depth-First Search)

Time O(V + E) O(V + E)
O(V) (stack/recursion depth + visited
Space O(V) (queue + visited set)
set)
Yes, for unweighted graphs (first time a No — does not guarantee shortest
Shortest path?
node is reached is via a shortest path) path
Topological sort, cycle detection,
Shortest path in unweighted graphs,
finding strongly connected
Typical uses level-order tree traversal, finding
components, maze/backtracking
connected components
problems
BFS(G, source):
visited = {source}
queue = [source]
while queue is not empty:
u = [Link]()
for each neighbor v of u:
if v not in visited:
[Link](v)
[Link](v)

9.4 Depth-Limited Search (DLS) — asked directly

DFS, but with an explicit maximum depth limit ℓ; the search does not expand any node beyond depth ℓ,
even if the goal lies deeper.
• Why it exists: plain DFS can go arbitrarily deep down a branch (or loop forever on an
infinite/cyclic state space) without ever finding a shallower solution elsewhere. DLS bounds this
by refusing to explore past depth ℓ.
• Tradeoff: DLS is incomplete if the actual goal lies deeper than ℓ (it will report failure even
though a solution exists) — choosing ℓ correctly requires some prior knowledge or estimate of
the solution depth.
• Iterative Deepening Search (IDS): the natural fix — run DLS repeatedly with ℓ = 0, 1, 2, … until a
solution is found. Combines DFS's space efficiency (O(depth) space) with BFS's completeness, at
the cost of re-exploring shallow nodes multiple times (which turns out to be a small overhead,
since most nodes in a tree are near the bottom).

9.5 Minimum Spanning Tree (MST) and the algorithm-choice question (asked directly)
An MST is a subset of edges connecting all vertices of a weighted, connected, undirected graph with no
cycles, minimizing the total edge weight.

Kruskal's algorithm
Sort all edges by weight; repeatedly add the next-cheapest edge as long as it doesn't create a cycle
(checked via a Union-Find / Disjoint Set Union data structure).

Page 16 of 43
Data Structures & Algorithms — Interview Reference

• Time complexity: O(E log E) for sorting the edges, plus O(E) Union-Find operations at
(amortized) near-O(1) each (with union by rank + path compression) — overall O(E log E), which
for an adjacency-matrix-style dense graph (E ≈ V²) becomes O(V² log V).

Prim's algorithm
Start from any vertex; repeatedly grow the MST by adding the cheapest edge that connects a vertex
already in the MST to a vertex not yet in it (a min-heap of candidate edges, or a simple array-scan, drives
the “cheapest next edge” selection).
• Time complexity using an adjacency matrix (no heap, simple array scan for the minimum):
O(V²) — V iterations, each scanning O(V) vertices to find the cheapest unvisited connecting
edge.
• Time complexity using an adjacency list + min-heap: O(E log V) — better for sparse graphs,
where E is much smaller than V².

The exact question and answer: “given a social network graph, which is the better MST
algorithm?”
Reasoning chain: social network graphs are typically dense (many people are connected to many other
people — think of how many mutual friends/connections exist) — so E approaches Θ(V²).

Algorithm Complexity (dense graph, E ≈ V²) Why

Matrix representation suits
dense graphs — O(1) edge
Prim's (adjacency matrix) O(V²) lookups are “free” when
most pairs are connected
anyway
Must sort ~V² edges, paying
Kruskal's (with DSU) O(V² log V) an extra log V factor that
Prim's avoids in this regime
The conclusion to state out loud: for a dense graph like a social network, Prim's algorithm (using an
adjacency matrix) at O(V²) beats Kruskal's at O(V² log V) — the extra log V factor from sorting all the
edges in Kruskal's becomes real overhead precisely because there are so many edges to sort in a
dense graph. (The comparison flips for sparse graphs: Prim's with a heap is O(E log V), Kruskal's is O(E
log E) — these are asymptotically similar, but Kruskal's is often preferred for sparse graphs since
sorting a small edge list is simple and the DSU overhead is low.)

9.6 Shortest path algorithms (good supporting context)

Handles negative
Algorithm Time complexity Notes
weights?
Shortest path
measured in edge
BFS N/A (unweighted only) O(V + E)
count, only valid for
unweighted graphs

Page 17 of 43
Data Structures & Algorithms — Interview Reference

Handles negative
Algorithm Time complexity Notes
weights?
Greedy; repeatedly
O((V + E) log V) with a min-
Dijkstra's No picks the closest
heap
unvisited vertex
Relaxes every edge V−1
Yes (and detects
Bellman-Ford O(V · E) times; slower but more
negative cycles)
general than Dijkstra's
All-pairs shortest paths
Floyd-Warshall Yes O(V³) in one run, via dynamic
programming
• Why Dijkstra's fails with negative weights: its greedy correctness relies on the invariant that
once a vertex is finalized (popped from the priority queue), no shorter path to it can ever be
found later — a negative edge can violate this by creating a shorter path through a vertex visited
after the supposedly-final shortest distance was already locked in.

9.7 Other graph concepts worth recognizing

• Topological sort: a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for
every directed edge (u, v), u appears before v. Used for task scheduling with dependencies. Only
possible if the graph has no cycles.
• Strongly connected components (SCC): maximal sets of vertices in a directed graph where every
vertex can reach every other vertex in the set. Found via Kosaraju's or Tarjan's algorithm, both
O(V + E).
• Diamond problem (multiple inheritance, asked directly — cross-listed here since it's
structurally a graph/DAG issue): if class D inherits from both B and C, and both B and C inherit
from a common base A, then D has two separate “paths” to A's members — creating ambiguity
about which inherited copy of A's data/methods D should use. Some languages (C++) resolve
this with virtual inheritance (ensuring only one shared copy of A exists); others (Java) avoid the
problem entirely by disallowing multiple inheritance of implementation, only allowing multiple
interface inheritance (which has no shared state to conflict over).

10. Sorting Algorithms

10.1 The master comparison table

In-
Algorithm Best Average Worst Space Stable? plac
e?
Bubble sort O(n) O(n²) O(n²) O(1) Yes Yes
Selection sort O(n²) O(n²) O(n²) O(1) No Yes

Page 18 of 43
Data Structures & Algorithms — Interview Reference

In-
Algorithm Best Average Worst Space Stable? plac
e?
Insertion sort O(n) O(n²) O(n²) O(1) Yes Yes
Merge sort O(n log n) O(n log n) O(n log n) O(n) Yes No
Quicksort O(n log n) O(n log n) O(n²) O(log n) No Yes
Heap sort O(n log n) O(n log n) O(n log n) O(1) No Yes
Counting sort O(n + k) O(n + k) O(n + k) O(k) Yes No
(k = the range of input values, for counting sort. Stable = equal elements retain their original relative
order after sorting.)

10.2 Bubble sort, Selection sort, Insertion sort — the simple O(n²) family
• Bubble sort: repeatedly scan adjacent pairs and swap if out of order; each full pass “bubbles”
the largest remaining element to its correct position. Best case O(n) only with an early-exit
optimization (stop if a full pass makes no swaps — the array is already sorted).
• Selection sort: repeatedly find the minimum of the unsorted remainder and swap it into place.
Always exactly O(n²) comparisons regardless of input order (no early exit is possible, since you
must scan the entire remainder every time to find the minimum) — this is why its best case is
also O(n²), unlike bubble or insertion sort.
• Insertion sort: build up a sorted prefix one element at a time, inserting each new element into
its correct position within the already-sorted prefix (shifting larger elements right). Best case
O(n) when the array is already sorted (each new element only needs one comparison to confirm
it's already in place). Efficient in practice for small or nearly-sorted arrays — this is why many
real-world hybrid sorts (e.g. Python's Timsort) fall back to insertion sort for small sub-arrays.

10.3 Merge sort — derivation of O(n log n)

Divide the array in half, recursively sort each half, then merge the two sorted halves in linear time.
mergeSort(arr):
if len(arr) <= 1: return arr
mid = len(arr) / 2
left = mergeSort(arr[:mid])
right = mergeSort(arr[mid:])
return merge(left, right) # O(n) to merge two sorted halves

• Recurrence relation: T(n) = 2T(n/2) + O(n) — two recursive calls on half the data, plus O(n) work
to merge.
• Solving via the recursion tree: at depth d, there are 2^d subproblems, each of size n/2^d, each
requiring O(n/2^d) merge work — so the total merge work at depth d is 2^d × O(n/2^d) = O(n),
the same at every level. The recursion has depth log₂(n) (halving n until it reaches 1). Total: O(n)
work per level × log₂(n) levels = O(n log n).

Page 19 of 43
Data Structures & Algorithms — Interview Reference

• Master Theorem (the general-purpose tool this is a special case of): for T(n) = aT(n/b) + O(n^d),
compare d against log_b(a). Here a=2, b=2, d=1, so log_b(a) = log₂(2) = 1 = d — this is the “case
2” / balanced case of the Master Theorem, which gives T(n) = O(n^d · log n) = O(n log n).
• Why O(n) space: merging requires auxiliary arrays to hold the two halves being merged (the
classic implementation is not in-place); this is the standard tradeoff merge sort makes for
guaranteed O(n log n) worst-case time and stability.

10.4 Quicksort — why average O(n log n) but worst-case O(n²)

Pick a pivot; partition the array so elements less than the pivot come before it and elements greater
come after; recursively sort each partition.
• Average case O(n log n): if the pivot reliably splits the array into two roughly-equal halves, the
recurrence is the same shape as merge sort's (T(n) = 2T(n/2) + O(n)), giving O(n log n).
• Worst case O(n²): if the pivot is consistently the smallest or largest remaining element (e.g.
always picking the first element as pivot on an already-sorted or reverse-sorted array), each
partition only shrinks the problem by 1 element instead of by half — the recurrence becomes
T(n) = T(n−1) + O(n), which sums to O(n²).
• Mitigations: randomized pivot selection, or median-of-three (pivot = median of first/middle/last
elements) — both make the pathological worst case astronomically unlikely for real-world or
even adversarial inputs that don't specifically know your pivot strategy.
Direct connection to the Security guide: this exact quicksort-vs-mergesort worst-case asymmetry is
precisely why the Security guide's algorithmic-complexity-attack section recommends mergesort over
quicksort whenever an adversary might supply the input — mergesort's worst case stays O(n log n) no
matter what, while quicksort's can be forced to O(n²).

10.5 Counting sort — breaking the O(n log n) “barrier”

Not a comparison sort — it counts occurrences of each distinct value (assuming values lie in a small
known range 0..k) and uses those counts to directly place elements into sorted output. O(n + k) time.
Why this doesn't contradict the famous “sorting is Ω(n log n)” lower bound: that lower bound
applies specifically to comparison-based sorts (algorithms that only learn information about element
order via pairwise comparisons) — counting sort uses the actual values directly (as array indices),
sidestepping the comparison model entirely. This is a genuinely good piece of depth to volunteer if
anyone asks “isn't n log n the best possible?”

11. Pigeonhole Principle and Combinatorial “Worst-Case Drawing”

Problems
These appeared repeatedly across your transcripts in slightly different costumes (balls, cards, aces) but
are all the exact same reasoning pattern. Master the pattern once and every variant becomes trivial.

Page 20 of 43
Data Structures & Algorithms — Interview Reference

11.1 The Pigeonhole Principle, stated precisely

If n items are placed into m containers (“pigeonholes”) and n > m, then at least one container must hold
more than one item.
• Generalized form: if n items are placed into m containers, at least one container holds at least
⌈n/m⌉ items (the ceiling of n/m).
The reframe that makes “worst-case drawing” problems click: every one of these questions is
secretly asking “what is the worst possible order in which I could draw items, before the pigeonhole
principle FORCES the outcome I want?” The answer is always: assume the worst possible luck happens
first (draw every item of every OTHER category completely, as a hostile adversary would arrange it),
and then the very next single draw is forced to give you what you need.

11.2 Worked example 1: “4 red, 6 green balls — how many to draw to ensure at least
2 green?”
Worst-case adversarial drawing order: the adversary lets you draw as many balls as possible WITHOUT
giving you 2 green balls. The worst case that still avoids “2 green” is: draw all 4 red balls, plus at most 1
green ball — that's 4 + 1 = 5 balls drawn, and you still only have 1 green.
The very next draw (the 6th ball) has no choice but to be green (since all reds are already gone and
you've only drawn 1 of the 6 greens) — giving you your 2nd green ball.
Answer: 5 + 1 = 6 balls must be drawn to GUARANTEE at least 2 green balls.
• General formula for this pattern (“at least k of color A, given a total of R of all other colors
combined”): R + (k−1) + 1 = R + k draws, where R = total count of every color you're trying to
avoid, and k = the count you need of your target color.

11.3 Worked example 2: “Worst case to draw 3 red cards from a standard deck?”
A standard 52-card deck has 26 red cards (hearts + diamonds) and 26 black cards (spades + clubs).
Worst case: draw all 26 black cards first (these never count toward your goal), then draw 2 red cards
(still short of 3) — that's 26 + 2 = 28 cards drawn, with only 2 reds so far.
The 29th card is forced to be red (only red cards remain in the deck at this point) — giving you your 3rd
red card.
Answer: 29 cards must be drawn to GUARANTEE at least 3 red cards.
• Using the general formula: R (all non-target cards) + k (target count needed) = 26 + 3 = 29.
Matches exactly.

11.4 Worked example 3: “Worst case to draw 2 aces from a standard 52-card deck?”
There are 4 aces and 48 non-ace cards in a standard deck.
Worst case: draw all 48 non-ace cards first, then 1 ace (still short of 2) — that's 48 + 1 = 49 cards drawn.
The 50th card is forced to be an ace (only aces remain) — giving you your 2nd ace.

Page 21 of 43
Data Structures & Algorithms — Interview Reference

Answer: 50 cards must be drawn to GUARANTEE at least 2 aces.

• Using the general formula: R (non-aces) + k (aces needed) = 48 + 2 = 50. Matches exactly.

11.5 The single reusable template

For any “worst-case draws to guarantee k items of a target category, out of a pool with R items
belonging to all OTHER categories combined” question:
Template formula: Answer = R + k, where R = the total count of everything that does NOT count
toward your goal, and k = how many of the target category you need to guarantee.
Sanity-check this against all three worked examples above — it matches every one. If a question instead
gives you multiple categories that ALL count toward avoiding the goal differently (e.g. “at least 2 of the
SAME color, could be any color”), the reasoning shifts slightly: with c colors, drawing c+1 items
guarantees two of the same color by pure pigeonhole (c colors = c pigeonholes, c+1 items = forced
repeat) — recognize when a question is really this simpler form rather than the “k of one specific target”
form above.

12. Memory Address Calculation (asked directly: “finding the address

of an element, row-major, matrix, base address given”)
12.1 1D array address formula
Formula: address(arr[i]) = base_address + i × size_of_element
Example: an int array (4 bytes per element) with base address 1000. address(arr[5]) = 1000 + 5×4 =
1020.

12.2 2D matrix address formula — row-major order

Row-major order (the default in C, C++, Python, Java) stores a matrix row by row in memory — the
entire first row, then the entire second row, and so on.
Formula (row-major, 0-indexed): address(matrix[i][j]) = base_address + (i × number_of_columns + j) ×
size_of_element
Derivation: to reach row i, you must skip over i complete rows, each of width number_of_columns
elements — that's i × number_of_columns elements skipped. Then move j more elements across within
row i itself. Multiply the total element offset by size_of_element to convert to a byte offset, and add to
the base address.
Worked example: a matrix with 5 columns, int elements (4 bytes), base address 2000. Find
address(matrix[2][3]).
5. Offset in elements = (2 × 5) + 3 = 13.
6. Offset in bytes = 13 × 4 = 52.
7. Address = 2000 + 52 = 2052.

Page 22 of 43
Data Structures & Algorithms — Interview Reference

12.3 Column-major order (the alternative — used by Fortran, MATLAB, R)

Stores the matrix column by column instead.
Formula (column-major, 0-indexed): address(matrix[i][j]) = base_address + (j × number_of_rows + i) ×
size_of_element
Same derivation logic, just with the roles of rows and columns swapped — know that this exists and
which languages use which convention, in case the question is phrased ambiguously.

12.4 1-indexed variants

If the matrix is 1-indexed instead of 0-indexed (some textbook conventions use this), subtract 1 from
each index before applying the formula above: address(matrix[i][j]) = base_address + ((i−1) ×
number_of_columns + (j−1)) × size_of_element.
Practical tip for the live viva: explicitly state which indexing convention (0- or 1-based) and which
storage order (row- or column-major) you're assuming before writing the formula — this is exactly the
kind of precision-under-pressure the panel rewards, mirroring the height-convention clarification
needed for the BST node-count question.

13. Dynamic Programming (DP)

DP is one of the highest-yield topics in any DSA course and viva — it shows up disguised as
“optimization,” “counting,” and “feasibility” questions far more often than it's labeled “DP” outright.
This section builds the general framework first, then works through the classic problems in full.

13.1 What DP actually is

Dynamic Programming solves a problem by breaking it into overlapping subproblems, solving each
subproblem only once, and reusing (“memoizing”) the result instead of recomputing it. It applies exactly
when a problem has both of these properties:
• Optimal substructure: an optimal solution to the problem can be constructed from optimal
solutions to its subproblems.
• Overlapping subproblems: the same subproblems recur many times if you solved this
naively/recursively — if every subproblem were distinct, there'd be nothing to gain by caching,
and plain recursion (or divide-and-conquer) would already be optimal.
This is the precise answer to “when do you use DP vs plain recursion?”: use plain divide-and-conquer
(Section 14) when subproblems DON'T overlap (e.g. merge sort's two halves are completely
independent); use DP when they DO overlap (e.g. naive Fibonacci recomputes fib(3) many times while
computing fib(10)).

Page 23 of 43
Data Structures & Algorithms — Interview Reference

13.2 Two implementation styles

• Top-down (memoization): write the natural recursive solution, but cache each subproblem's
result (in an array or hash map) the first time it's computed, and return the cached value on
every subsequent call instead of recomputing.
• Bottom-up (tabulation): identify the order subproblems must be solved in (smallest first), and
fill a table iteratively, building up to the final answer — no recursion at all.
Top-down (memoization) Bottom-up (tabulation)
Recursive, often more intuitive to
Code style Iterative
write first
Computes only needed Yes — only what the recursion Not necessarily — often fills the
subproblems? actually touches whole table
Recursion depth / stack overflow
Risk None — no recursion stack
on large inputs
Preferred for production / when
Typical use Easier first-draft correctness
stack depth is a concern

13.3 Worked example 1: Fibonacci (the canonical first example)

Naive recursive Fibonacci: fib(n) = fib(n−1) + fib(n−2), base cases fib(0)=0, fib(1)=1.
• Why naive recursion is exponential: the recursion tree for fib(n) branches into two calls at every
level, and crucially, fib(n−2) is computed independently by both the fib(n−1) branch and directly
— the same subproblems are recomputed exponentially many times. T(n) = T(n−1) + T(n−2) +
O(1), which solves to O(φⁿ) where φ is the golden ratio — colloquially just stated as O(2ⁿ).
# Top-down with memoization — O(n) time, O(n) space
memo = {}
function fib(n):
if n <= 1: return n
if n in memo: return memo[n]
memo[n] = fib(n-1) + fib(n-2)
return memo[n]
# Bottom-up tabulation — O(n) time, O(n) space (or O(1) with 2 variables)
function fib(n):
if n <= 1: return n
prev2, prev1 = 0, 1
for i in range(2, n+1):
curr = prev1 + prev2
prev2, prev1 = prev1, curr
return prev1

Why memoization alone collapses exponential to linear: with memoization, each distinct value of n
from 0 to the original input is computed exactly once (O(1) work per value, ignoring the recursive calls
which now hit the cache), so total work is O(n) instead of O(2ⁿ) — this single before/after contrast is
the cleanest illustration of why DP matters at all.

Page 24 of 43
Data Structures & Algorithms — Interview Reference

13.4 Worked example 2: 0/1 Knapsack (the canonical optimization DP)

Given n items, each with a weight w[i] and value v[i], and a knapsack capacity W, choose a subset of
items (each item taken entirely or not at all — hence “0/1”) maximizing total value without exceeding
total weight W.
• Recurrence: let dp[i][c] = the best achievable value using only the first i items, with capacity c
remaining.
dp[i][c] = dp[i-1][c] if w[i] > c (item
i doesn't fit)
dp[i][c] = max( dp[i-1][c], v[i] + dp[i-1][c-w[i]] ) otherwise (skip
item i, or take it)

• Base case: dp[0][c] = 0 for all c (no items considered yet → zero value).
• Time complexity: O(n × W) — one table cell per (item, capacity) pair, O(1) work per cell.
• Space complexity: O(n × W) naively, but reducible to O(W) by noticing each row only depends
on the row directly above it, so you can overwrite a single 1D array in place (iterating capacity
from high to low to avoid using an item twice).
Why this is called “pseudo-polynomial,” a good thing to mention if pushed on complexity: O(n×W)
looks polynomial in n and W, but W is a numeric VALUE (the capacity), not the size of the input in bits
— if W is enormous (say, 2³⁰), the table becomes infeasible even though n is small. This is why
knapsack is technically NP-hard in general, despite this DP solution looking efficient for small/bounded
W.

13.5 Worked example 3: Longest Common Subsequence (LCS) — the canonical

string/sequence DP
Given two strings A (length m) and B (length n), find the length of the longest subsequence common to
both (not necessarily contiguous, but order-preserving).
• Recurrence: let dp[i][j] = LCS length of A[0..i) and B[0..j).
dp[i][j] = dp[i-1][j-1] + 1 if A[i-1] == B[j-1] (characters
match — extend the LCS)
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) otherwise (skip a
character from A or from B)

• Base case: dp[0][j] = dp[i][0] = 0 (an empty string has LCS length 0 with anything).
• Time complexity: O(m × n).
• Space complexity: O(m × n) naively, reducible to O(min(m,n)) since each row only depends on
the previous row.
• Why this matters beyond the textbook: this exact recurrence underlies the Unix diff command,
DNA sequence alignment in bioinformatics, and version-control merge algorithms — genuinely
good real-world color to mention.

13.6 Worked example 4: Longest Increasing Subsequence (LIS)

Given an array, find the length of the longest strictly increasing subsequence.

Page 25 of 43
Data Structures & Algorithms — Interview Reference

• Naive DP — O(n²): let dp[i] = length of the LIS ending exactly at index i. dp[i] = 1 + max(dp[j] for
all j < i where arr[j] < arr[i]), or 1 if no such j exists. Answer = max over all dp[i].
• Optimized — O(n log n): maintain an array tails, where tails[k] = the smallest possible tail value
of an increasing subsequence of length k+1 found so far. For each new element, binary search
tails for the correct position to either extend or replace — binary search is valid because tails is
always kept sorted as an invariant of the algorithm.
A great “can you do better?” follow-up answer: the O(n²) DP is the natural first answer; volunteering
the O(n log n) binary-search refinement (and explaining WHY tails stays sorted) is a strong depth
signal.

13.7 Worked example 5: Edit Distance (Levenshtein distance)

Minimum number of insertions, deletions, or substitutions to transform string A into string B.
dp[i][j] = dp[i-1][j-1] if A[i-1]
== B[j-1]
dp[i][j] = 1 + min(dp[i-1][j], # delete from A
dp[i][j-1], # insert into A
dp[i-1][j-1]) # substitute otherwise

• Base case: dp[i][0] = i (delete all of A's first i characters), dp[0][j] = j (insert all of B's first j
characters).
• Time/space: O(m×n) / O(m×n), reducible to O(min(m,n)) space.

13.8 Worked example 6: Coin Change (minimum coins)

Given coin denominations and a target amount, find the minimum number of coins needed (or
determine it's impossible).
dp[0] = 0
dp[amount] = infinity for all amount > 0 (initialize)
for amount = 1 to target:
for each coin c in coins:
if c <= amount and dp[amount - c] + 1 < dp[amount]:
dp[amount] = dp[amount - c] + 1
return dp[target] if it's not infinity, else "impossible"

• Time complexity: O(amount × number_of_coins).

The greedy trap this problem exposes (important conceptual point): a greedy “always take the
largest coin that fits” strategy works for canonical coin systems (like standard currency: 1, 5, 10, 25)
but FAILS for arbitrary denominations — e.g. coins {1, 3, 4} and target 6: greedy picks 4+1+1 = 3 coins,
but the optimal is 3+3 = 2 coins. This is one of the cleanest examples of why greedy algorithms need a
proof of correctness (a matroid / exchange-argument structure) and aren't simply “DP without the
table.” See Section 15 for the full greedy-vs-DP treatment.

13.9 Common DP patterns to recognize (a mental checklist)

Pattern Signal phrases in the problem Example

1D sequence DP “subarray,” “subsequence,” LIS, max subarray sum

Page 26 of 43
Data Structures & Algorithms — Interview Reference

Pattern Signal phrases in the problem Example

single array input (Kadane's algorithm)
Two strings, or a grid with LCS, edit distance, unique
2D string/grid DP
movement paths in a grid
Knapsack-style “subset,” capacity/budget 0/1 knapsack, subset-sum,
(choose/skip each item) constraint partition problems
“merge,” “partition into ranges,” Matrix chain multiplication,
Interval DP
matrix chain multiplication palindrome partitioning
Problem has explicit “states” Best time to buy/sell stock with
State-machine DP
(e.g. holding/not holding stock) cooldown/fees

14. Greedy Algorithms

14.1 The greedy idea
At each step, make the locally optimal choice (the choice that looks best right now) without
reconsidering it later, hoping this builds a globally optimal solution. Greedy algorithms are usually
simpler and faster than DP — but they only produce a correct, optimal answer for problems with the
right structure.
• Greedy choice property: a globally optimal solution can be reached by making a sequence of
locally optimal choices — this must be proven for each specific problem, not assumed.
• Optimal substructure: same requirement as DP — an optimal solution contains optimal
solutions to subproblems.
The single most important conceptual point in this section — Greedy vs. DP: both rely on optimal
substructure. The difference is that DP explores (or memoizes) ALL choices at each step and picks the
best combination after the fact, while greedy commits to ONE choice at each step and never looks
back. Greedy is only correct when you can prove the locally best choice never needs to be
reconsidered — otherwise you need DP's exhaustive (but memoized) exploration. The coin-change
example in Section 13.8 is the cleanest concrete illustration: greedy fails for {1,3,4}/target=6
specifically because the locally-best choice (take the 4) turns out not to be part of the globally optimal
solution.

14.2 Worked example 1: Activity/Interval Selection

Given n activities, each with a start and end time, select the maximum number of non-overlapping
activities.
• Greedy strategy: sort activities by END time (not start time — this is the detail people get
wrong); repeatedly pick the next activity whose start time is ≥ the end time of the last picked
activity.

Page 27 of 43
Data Structures & Algorithms — Interview Reference

• Why sorting by end time (not start time) works: picking the activity that finishes earliest always
leaves the maximum possible remaining time for future activities — it can be proven by an
exchange argument that any optimal solution can be modified to include the earliest-finishing
activity without making the solution worse.
• Time complexity: O(n log n) for the sort, O(n) for the single greedy pass — O(n log n) overall.

14.3 Worked example 2: Huffman Coding

Build an optimal prefix-free binary encoding for a set of symbols given their frequencies, minimizing
total encoded length.
• Greedy strategy: repeatedly take the two lowest-frequency nodes (using a min-heap), merge
them into a new node whose frequency is their sum, and push the merged node back — repeat
until one node (the root) remains.
• Why it's correct: the two least-frequent symbols should always end up as the two deepest
(longest-code) leaves in an optimal tree — merging them first guarantees this.
• Time complexity: O(n log n) — n−1 merges, each a O(log n) heap extract+insert.
• Real-world relevance: this is literally how ZIP/DEFLATE-style compression and JPEG's entropy
coding stage work.

14.4 Worked example 3: Dijkstra's Algorithm, reframed as greedy

Already covered mechanically in Section 9.6 — worth explicitly naming as a greedy algorithm here: at
each step, greedily finalize the closest unvisited vertex, under the assumption (only valid for non-
negative weights) that no shorter path to it can ever be found later via a not-yet-visited vertex.

14.5 Worked example 4: Fractional Knapsack (the greedy counterpart to 0/1

Knapsack)
Same setup as 0/1 Knapsack (Section 13.4), but items can now be taken in any fraction (e.g. half an
item), not just all-or-nothing.
• Greedy strategy: compute value/weight ratio for every item, sort descending by ratio, greedily
take as much as possible of the highest-ratio item first, then the next, until the knapsack is full.
• Why this works here but the 0/1 version needs DP: the ability to take fractional amounts
removes the combinatorial “which subset” structure that makes 0/1 knapsack hard — with
fractions allowed, greedily maximizing value-per-unit-weight is provably optimal. This pairing
(fractional = greedy works, 0/1 = greedy fails, needs DP) is one of the best concrete teaching
examples for explaining exactly when greedy breaks down.

14.6 Worked example 5: Minimum Spanning Tree, reframed as greedy

Both Kruskal's and Prim's (Section 9.5) are greedy algorithms: Kruskal's greedily takes the globally
cheapest edge that doesn't form a cycle; Prim's greedily takes the cheapest edge that extends the
current tree. Correctness for both rests on the Cut Property of MSTs (for any cut/partition of the
vertices, the minimum-weight edge crossing the cut must be in some MST) — good to mention by name
if pushed on “why does greedy work for MST.”

Page 28 of 43
Data Structures & Algorithms — Interview Reference

15. Divide and Conquer (as a general paradigm)

15.1 The three-step pattern
8. Divide: split the problem into smaller subproblems of the same type.
9. Conquer: solve each subproblem recursively (down to a base case).
10. Combine: merge the subproblem solutions into a solution for the original problem.
Divide & Conquer vs. DP — the cleanest possible distinction: D&C subproblems are independent (no
overlap) — merge sort's left half and right half share no work. DP subproblems overlap — that's the
entire reason DP needs a memo table and D&C doesn't. If you ever find yourself solving the exact
same subproblem twice in a D&C recursion, that's the signal you actually need DP instead.

15.2 Algorithms you already know that are D&C (consolidating earlier sections under
this lens)
• Merge sort (Section 10.3): divide in half, conquer (recursively sort), combine (merge) — O(n log
n).
• Quicksort (Section 10.4): divide via partitioning around a pivot, conquer (recursively sort each
side), combine is trivial (no work needed — the partitions are already in their final relative
positions).
• Binary search (Section 2.3): divide the search space in half, conquer by recursing into the
relevant half, combine is trivial (just return the recursive result).

15.3 Worked example: Exponentiation by squaring (“fast power”)

Compute a^n efficiently.
• Naive approach: multiply a by itself n−1 times — O(n).
function power(a, n):
if n == 0: return 1
half = power(a, n // 2)
if n is even: return half * half
else: return half * half * a

• Time complexity: O(log n) — the problem size halves at every recursive call, the same halving
structure as binary search. This is a frequently-tested example of D&C applied somewhere other
than sorting/searching.

15.4 Worked example: finding the maximum subarray sum via D&C (Kadane's
alternative)
Split the array in half; recursively find the best subarray sum entirely in the left half, entirely in the right
half, AND the best subarray that crosses the midpoint (computed by scanning outward from the
midpoint in both directions); take the max of all three.

Page 29 of 43
Data Structures & Algorithms — Interview Reference

• Recurrence: T(n) = 2T(n/2) + O(n) — the same shape as merge sort, giving O(n log n).
Worth mentioning as a contrast: Kadane's algorithm (a single linear DP pass tracking “best sum
ending here”) solves the same problem in O(n), strictly better than this O(n log n) D&C approach — a
good example of how a DP reformulation can beat a D&C one when the structure allows it.

15.5 The Master Theorem (general tool, formally stated)

For a recurrence of the form T(n) = a·T(n/b) + O(n^d), where a ≥ 1, b > 1, and d ≥ 0, compare d to
log_b(a):

Case Condition Result

1 d < log_b(a) T(n) = O(n^(log_b(a))) — the recursive calls dominate
T(n) = O(n^d · log n) — balanced; this is merge sort's case
2 d = log_b(a)
(a=2,b=2,d=1)
3 d > log_b(a) T(n) = O(n^d) — the combine step dominates
• Worked check against binary search: T(n) = T(n/2) + O(1) — here a=1, b=2, d=0. log_b(a) =
log₂(1) = 0 = d → Case 2 → T(n) = O(n⁰ · log n) = O(log n). Matches what we already know.

16. String Algorithms

16.1 Naive pattern matching
To find a pattern P (length m) inside a text T (length n): try aligning P at every possible starting position
in T, and at each position check character by character whether it matches.
• Time complexity: O(n × m) worst case — n−m+1 starting positions, up to m character
comparisons at each.
• When the worst case actually triggers: highly repetitive text and pattern, e.g. T =
“aaaaaaaaaaaaab” and P = “aaaab” — every alignment matches almost the whole pattern
before failing on the last character, repeatedly.

16.2 Knuth-Morris-Pratt (KMP) — linear-time matching

KMP's key insight: when a mismatch occurs, the naive approach “forgets” everything it already knew
about the partial match and restarts from scratch one position over. KMP instead precomputes, for the
pattern itself, how much of a partial match can be reused after a mismatch — so it never re-examines a
text character it has already successfully matched.
• The LPS (Longest Prefix that is also a Suffix) array: precomputed once per pattern, lps[i] = the
length of the longest proper prefix of P[0..i] that is also a suffix of P[0..i]. This single array is what
lets KMP “skip” intelligently on a mismatch instead of restarting.
• Time complexity: O(m) to build the LPS array, O(n) for the actual scan — O(n + m) total, a strict
improvement over naive O(n×m).

Page 30 of 43
Data Structures & Algorithms — Interview Reference

The one-sentence intuition to give if asked “how does KMP achieve linear time”: it never moves the
text pointer backward, and uses the precomputed LPS array to decide how far to shift the pattern
pointer back on a mismatch — so each text character is examined only a bounded number of times in
total across the whole scan, not re-examined from scratch at every alignment.

16.3 Rabin-Karp — hashing-based matching

Compute a rolling hash of the pattern, and a rolling hash of every length-m substring of the text;
compare hashes first, and only do an actual character-by-character comparison if the hashes match (to
rule out hash collisions, since a hash match doesn't guarantee a true match).
• Rolling hash: the hash of the next window can be computed from the hash of the current
window in O(1) (by removing the contribution of the character leaving the window and adding
the one entering it), rather than rehashing the entire substring from scratch.
• Average time complexity: O(n + m) (assuming few hash collisions).
• Worst case: O(n × m) if many spurious hash collisions occur, requiring a full character
comparison each time.
• Practical use: well-suited to multi-pattern search (checking many patterns against one text
efficiently) and plagiarism/duplicate detection.

16.4 Tries, revisited as a string-algorithm tool (cross-reference Section 6.6)

Beyond simple prefix lookup, tries support efficient multi-pattern matching when combined with failure
links (the Aho-Corasick algorithm) — worth knowing the name exists, even without full derivation: it
generalizes KMP's “don't restart from scratch” idea to matching many patterns simultaneously in O(n +
total pattern length + number of matches).

16.5 Palindrome checking and related problems

• Checking if a string is a palindrome: two pointers from both ends moving inward, O(n) time,
O(1) space.
• Longest palindromic substring: the “expand around center” technique — for each possible
center (there are 2n−1 of them, accounting for both odd- and even-length palindromes), expand
outward while characters match. O(n²) time, O(1) extra space. (A more advanced O(n) solution,
Manacher's algorithm, exists but is rarely expected at this depth.)

17. Backtracking
17.1 The idea
Backtracking systematically explores all candidate solutions by building them incrementally, abandoning
(“backtracking” from) a partial candidate as soon as it's clear it cannot possibly lead to a valid complete
solution. It is fundamentally a refinement of brute-force search: instead of generating every full
candidate and then checking it, prune invalid branches as early as possible.

Page 31 of 43
Data Structures & Algorithms — Interview Reference

• Relationship to DFS: backtracking is essentially DFS over an implicit tree of partial solutions,
where each node represents a partial choice and we prune (don't recurse further) whenever a
partial choice is already known to be invalid or suboptimal.

17.2 Worked example: N-Queens

Place N queens on an N×N chessboard so that no two attack each other (no shared row, column, or
diagonal).
function solve(row, columns_used):
if row == N: record this as a valid solution; return
for col = 0 to N-1:
if placing a queen at (row, col) is safe given columns_used:
place queen, mark column/diagonals used
solve(row + 1, columns_used)
remove queen, unmark # <-- the "backtrack" step

• Time complexity: O(N!) worst case (no better general bound is known), but pruning early
(checking column/diagonal conflicts before recursing deeper, rather than only at the end) makes
it vastly faster in practice than generating all N^N placements blindly.

17.3 Worked example: generating all subsets / permutations

• All subsets (the power set): at each element, branch into two choices (include it or don't); 2ⁿ
leaves in the recursion tree, O(2ⁿ) time, matching the known count of subsets of an n-element
set.
• All permutations: at each position, try every not-yet-used element, recurse, then backtrack (un-
use it) before trying the next; O(n!) time, matching the known count of permutations.

17.4 Worked example: Sudoku solver

For each empty cell, try digits 1–9; if a digit doesn't violate row/column/box constraints, place it and
recurse to the next empty cell; if the recursion fails (no digit works for some later cell), undo the
placement and try the next digit — textbook backtracking, and a frequently-cited example because the
constraint-checking (not just the recursion shape) is what makes it efficient in practice despite a poor
worst-case bound.

17.5 Backtracking vs. DP — when each is the right tool

Both explore a space of choices, but backtracking is for problems where you need to enumerate or find
ANY/ALL valid complete solutions (and pruning invalid partial states is the main lever for efficiency),
while DP is for problems where you need an OPTIMAL value or count and the same subproblems recur
(so caching, not pruning, is the main lever). If a backtracking solution's recursive calls start repeating
identical subproblems, that's a sign the problem might be reformulable as DP for a better asymptotic
bound.

Page 32 of 43
Data Structures & Algorithms — Interview Reference

18. Advanced Trees

18.1 AVL Trees — self-balancing via rotations, worked in full
An AVL tree is a BST that maintains the invariant: for every node, |height(left subtree) − height(right
subtree)| ≤ 1 (the “balance factor” is always −1, 0, or +1). This guarantees height stays O(log n), so
search/insert/delete all stay O(log n) even in the worst case — directly solving the degenerate-BST
problem flagged in Section 6.4.

The four rotation cases

• Left-Left (LL) case: a node's left child is too tall, and that child's own left subtree is the heavy
side. Fix: a single right rotation at the unbalanced node.
• Right-Right (RR) case: mirror image of LL. Fix: a single left rotation.
• Left-Right (LR) case: a node's left child is too tall, but the heavy side is that child's RIGHT subtree
(a “zig-zag”). Fix: first left-rotate the left child, turning it into an LL case, then right-rotate the
original node.
• Right-Left (RL) case: mirror image of LR. Fix: first right-rotate the right child, then left-rotate the
original node.
Single rotation (LL/RR), worked mechanically: suppose node z is unbalanced because its left child y is too
tall, and y's own LEFT child x is the heavy side (the LL case). A right rotation at z means: y becomes the
new subtree root; z becomes y's right child; y's OLD right subtree becomes z's new left subtree (it's
moved, not discarded, preserving the BST ordering property throughout).
Why this preserves the BST property (the part worth being able to justify, not just recite): before
rotation, the in-order traversal order of the affected nodes is: x's subtree, x, y's old-right-subtree, y, z's
old-right-subtree (reading left to right). A right rotation just changes which node is the local root — it
does NOT change this left-to-right in-order sequence at all. Since BST validity is entirely defined by in-
order sequence being sorted, and rotation never changes that sequence, the result is still a valid BST.
• Time complexity: search/insert/delete are all O(log n) worst case (guaranteed, unlike a plain
BST). Each insert/delete triggers at most O(log n) rotations to restore balance (in practice, at
most one or two rotations are typically needed, but rebalancing checks may propagate up to
O(log n) ancestors).

18.2 Red-Black Trees (concept level — know it exists and the core tradeoff)
Another self-balancing BST, using a different invariant: every node is colored red or black, the root and
all leaves (nil nodes) are black, a red node never has a red child, and every path from a node to its
descendant nil leaves passes through the same number of black nodes.
• Comparison with AVL: Red-Black trees allow slightly looser balance than AVL (height can be up
to ~2× the minimum possible, vs. AVL's tighter bound), which means more lookups on average
but fewer rotations needed on insert/delete — making Red-Black trees the more common
choice for insert/delete-heavy workloads (used internally by C++'s std::map/std::set and Java's
TreeMap/TreeSet), while AVL is preferred when lookups dominate and insertions/deletions are
rare.

Page 33 of 43
Data Structures & Algorithms — Interview Reference

18.3 B-Trees (concept level — the disk-oriented generalization)

A generalization of a BST where each node can have many children (not just 2), keeping the tree very
shallow even for huge datasets. Designed specifically for systems where reading a node means a slow
disk/page access — minimizing the NUMBER of node accesses (tree height) matters far more than
minimizing comparisons within a node.
• Why more children per node helps here: each disk read can pull in a large block of data anyway,
so packing many keys into one node (one disk read) before branching is far more efficient than a
high, narrow binary tree that would need many separate disk reads to reach the same depth.
• Real-world use: the standard structure behind most relational database indexes and many
filesystems.

18.4 Segment Trees — range query structure

A binary tree built over an array where each node represents the aggregate (sum, min, max, etc.) of
some contiguous range of the array; the root represents the whole array, and each node's two children
represent its left and right half.
• Build time: O(n).
• Range query (e.g. “sum of elements from index i to j”): O(log n) — decompose the query range
into O(log n) precomputed node-ranges instead of summing element by element.
• Point update (change one element): O(log n) — only the O(log n) ancestors of that leaf need
their aggregates recomputed.
Why this beats the naive approach: naively, a range-sum query is O(n) (just sum the range directly)
and a point update is O(1) — fine if you only do one or the other many times, but bad if you need
MANY of both interleaved. A segment tree makes both O(log n), which is the right tradeoff when
updates and range queries are both frequent.

18.5 Fenwick Tree / Binary Indexed Tree (BIT) — a lighter-weight alternative

Solves the same core problem as a segment tree (range sum queries + point updates) using a clever
indexing trick on a single array, exploiting the binary representation of indices, rather than an explicit
tree structure.
• Time complexity: O(log n) for both point update and prefix-sum query (same asymptotic
complexity as a segment tree), but with a smaller constant factor and far less code/memory
overhead, since there's no explicit tree — just one array of the same size as the input.
• Limitation vs. segment trees: a basic Fenwick tree only directly supports prefix sums (and range
sums derived as a difference of two prefix sums) — segment trees are more general and directly
support arbitrary associative aggregate functions (min, max, gcd, etc.) and range updates more
naturally.

Page 34 of 43
Data Structures & Algorithms — Interview Reference

19. Bit Manipulation

A category covered in essentially every undergraduate DSA/CS course and frequently tested as quick-fire
questions, even though it didn't appear explicitly in your past transcripts.

19.1 Core bitwise operators and their identities

Operation Symbol Key identity / use

AND & x & 1 checks if x is odd; x & (x-1) clears the lowest set bit
OR | x | (1 << k) sets bit k
x ^ x = 0; x ^ 0 = x; used to find a “unique” element among
XOR ^
pairs (Section 19.3)
NOT ~ Flips every bit; ~x = -(x+1) in two's complement
Left shift << x << k multiplies x by 2^k
x >> k divides x by 2^k (integer division, careful with sign
Right shift >>
for negative x)

19.2 Common bit tricks (high interview yield)

• Check if a number is a power of 2: n > 0 and (n & (n-1)) == 0. Why it works: a power of 2 has
exactly one bit set (e.g. 8 = 1000); subtracting 1 flips that bit and all bits below it (0111), so
ANDing the two gives 0 only in this exact case.
• Count set bits (Brian Kernighan's algorithm): repeatedly do n = n & (n-1) and count iterations
until n becomes 0 — each iteration clears exactly the lowest set bit, so the loop runs exactly
once per set bit, giving O(number of set bits) rather than O(total bits).
• Get/set/clear/toggle bit k: get: (n >> k) & 1. Set: n | (1 << k). Clear: n & ~(1 << k). Toggle: n ^ (1
<< k).
• Swap two variables without a temp variable: a = a ^ b; b = a ^ b; a = a ^ b — works because
XOR is its own inverse (x ^ y ^ y = x).

19.3 Worked example: find the single non-duplicate in an array where every other
element appears exactly twice
XOR every element together. Since x ^ x = 0 for any x, every pair cancels out completely, leaving only the
unpaired (single) element.
function findSingle(arr):
result = 0
for x in arr:
result = result ^ x
return result

Page 35 of 43
Data Structures & Algorithms — Interview Reference

• Time complexity: O(n), and crucially O(1) extra space — a hash-set-based approach also solves
this but needs O(n) extra space, making the XOR trick a strong example of a clever constant-
space solution, worth volunteering if asked for something “better than the obvious approach.”

19.4 Why bit manipulation matters beyond “cute tricks”

Bitmasking is a standard technique for representing subsets compactly (a set of up to 32 or 64 elements
fits in a single integer, with bit i indicating whether element i is in the set) — used heavily in “subset DP”
problems (DP over all 2ⁿ subsets, where the subset itself is the DP state, encoded as a bitmask) and in
representing visited-state sets in graph/search algorithms compactly and with O(1) set-operations
instead of O(n) for an explicit list/set structure.

20. Advanced Graph Topics

20.1 Union-Find / Disjoint Set Union (DSU), implementation detail
Referenced in Section 9.5 (Kruskal's cycle detection) without implementation detail — worth knowing
precisely, since “why is Union-Find fast” is a natural, fair follow-up to the Kruskal's-vs-Prim's question.
• find(x): follow parent pointers up from x until reaching a node that is its own parent (the
“root” / representative of x's set).
• union(x, y): find each of their roots; if different, attach one root under the other, merging the
two sets.
• Optimization 1 — union by rank/size: always attach the smaller (or shorter) tree under the root
of the larger one, keeping trees shallow.
• Optimization 2 — path compression: during find(x), after locating the root, re-point every node
visited along the way directly to that root — flattening the tree for all future queries.
The complexity result worth quoting precisely: with BOTH optimizations together, the amortized
time per operation is O(α(n)), where α is the inverse Ackermann function — which grows so slowly
that it is less than 5 for any n that could ever be practically encountered. In practice, this is simply
described as “near-constant time, O(1) amortized.” With only one of the two optimizations, it's O(log
n) amortized; with neither, find/union degrade to O(n) worst case (a chain-shaped tree).

20.2 Articulation points and bridges

• Articulation point (cut vertex): a vertex whose removal increases the number of connected
components of the graph — i.e. a single point of failure for connectivity.
• Bridge (cut edge): an edge whose removal increases the number of connected components.
• Algorithm: a single DFS pass (Tarjan's algorithm) computing, for each vertex, its discovery time
and its “low-link” value (the earliest-discovered vertex reachable from its DFS subtree via at
most one back-edge). A vertex u is an articulation point if some child v in the DFS tree has low-
link[v] ≥ discovery-time[u] (the child's subtree cannot reach back above u except through u
itself). O(V + E) total.

Page 36 of 43
Data Structures & Algorithms — Interview Reference

• Real-world framing: finding single points of failure in a physical or logical network — directly
relevant to network reliability/security analysis (a nice bridge back to the Security guide's
network-attacker context, if you want to connect topics).

20.3 Network flow (concept level)

Given a directed graph where each edge has a capacity, and a designated source and sink, find the
maximum total flow that can be pushed from source to sink without exceeding any edge's capacity.
• Ford-Fulkerson method: repeatedly find an augmenting path (a path from source to sink with
spare capacity, found via BFS or DFS) and push as much flow as possible along it, until no
augmenting path remains.
• Max-flow min-cut theorem: the maximum possible flow equals the minimum-capacity cut (the
smallest total capacity of edges that, if removed, would disconnect source from sink) — a
genuinely elegant duality result worth knowing exists, even without a full proof.
• Time complexity: O(E × max_flow) for the basic method (can be slow if capacities are large); the
Edmonds-Karp refinement (always use BFS to find the augmenting path) bounds this at O(V ×
E²), independent of the actual capacity values.

21. Amortized Analysis

21.1 What amortized analysis is for
Some operations are occasionally expensive but the expense is rare enough that, averaged over a long
sequence of operations, the AVERAGE cost per operation is small — even though any single operation's
worst case looks bad in isolation. Amortized analysis formalizes “average cost over a sequence,” which is
a different and often more useful claim than either “worst case of one operation” or “average case over
random inputs.”

21.2 Worked example: dynamic array (e.g. Python list, C++ vector) append
A dynamic array starts with some fixed capacity; when it's full and a new element is appended, the
entire array is reallocated to a larger capacity (typically doubling) and every existing element is copied
over.
• Worst-case single append: O(n) — if this particular append happens to trigger a resize, every
one of the n existing elements must be copied.
• Amortized cost per append, over n total appends, using the doubling strategy: O(1). Proof
sketch: resizes happen at sizes 1, 2, 4, 8, …, n — a geometric series, so total copying work across
ALL resizes combined is 1+2+4+…+n = O(n) (geometric series sum, see Section 6.3). Spread that
O(n) total cost evenly across the n appends that occurred, and each append's share is O(n)/n =
O(1).
Why doubling specifically matters (and why growing by a FIXED amount each time would be bad): if
you instead grew the array by a constant amount (e.g. +10 slots) every time it filled up, you'd need
n/10 resizes total, each copying up to n elements — total copying work O(n²), giving O(n) amortized

Page 37 of 43
Data Structures & Algorithms — Interview Reference

cost per append instead of O(1). Doubling (geometric growth) is what makes the total copying work
sum to a geometric series (O(n)) rather than an arithmetic one (O(n²)).

21.3 The three standard amortized-analysis techniques (names worth recognizing)

• Aggregate method: directly bound the TOTAL cost of n operations, then divide by n (exactly
what was done above for the dynamic array).
• Accounting (banker's) method: assign each operation an amortized “charge” possibly higher
than its actual cost; the surplus is saved as “credit” to pre-pay for future expensive operations.
• Potential method: define a potential function over the data structure's state, and show that
(actual cost + change in potential) is bounded for every operation — a more formal/general
version of the accounting method, common in rigorous analyses of Fibonacci heaps and similar
structures.

22. Computability and Complexity Theory Basics

Standard closing material in most undergraduate algorithms courses — high-level fluency here (not
deep proofs) is what's typically expected.

22.1 P and NP
• P (Polynomial time): the class of decision problems solvable by a deterministic algorithm in
polynomial time (e.g. O(n), O(n²), O(n³) — any O(n^k) for constant k).
• NP (Nondeterministic Polynomial time): the class of decision problems for which a proposed
solution (a “certificate”) can be VERIFIED in polynomial time, even if no polynomial-time
algorithm is known to FIND that solution. Every problem in P is trivially also in NP (if you can
solve it quickly, you can certainly verify a solution quickly) — so P ⊆ NP is known for certain.
• The open question — “P vs NP”: whether P = NP, i.e. whether every problem whose solution
can be quickly VERIFIED can also be quickly SOLVED. This is one of the most famous open
problems in computer science/mathematics (a Clay Millennium Prize problem) — nobody has
proven it either way, though it is widely (not universally) believed that P ≠ NP.

22.2 NP-complete and NP-hard

• NP-complete: a problem that is both in NP, AND every other problem in NP can be reduced to it
in polynomial time — meaning it is, in a precise sense, “as hard as any problem in NP gets.” If
anyone ever finds a polynomial-time algorithm for ANY single NP-complete problem, that would
imply P = NP for ALL of NP at once (since everything in NP reduces to it).
• NP-hard: at least as hard as the hardest problems in NP (every NP problem reduces to it), but
not necessarily required to itself be IN NP (it might not even be a decision problem, or might not
have polynomial-time-verifiable solutions at all).
• Classic NP-complete problems worth naming: the Boolean Satisfiability Problem (SAT —
historically the first problem proven NP-complete, via the Cook-Levin theorem), the Traveling
Salesman Problem (decision version: “is there a tour of length ≤ k?”), the Knapsack decision

Page 38 of 43
Data Structures & Algorithms — Interview Reference

problem (“can we achieve value ≥ V within weight W?” — connecting directly back to Section
13.4's note that 0/1 Knapsack is NP-hard in general), Graph Coloring, and the Subset Sum
problem.
Why this connects back to everything earlier in this guide: every DP/greedy/backtracking algorithm
in this document solves a problem efficiently BECAUSE that specific problem has exploitable structure
(optimal substructure, the greedy-choice property, or effective pruning). NP-complete problems are
exactly the problems we currently have NO known way to exploit such structure for — backtracking
with pruning remains one of the best PRACTICAL approaches to many NP-complete problems
precisely because no polynomial algorithm is known.

23. Quick-Reference Drill Bank (every DSA question from your

transcripts, mapped to its section)
Question (as asked) Where it's covered One-line answer to anchor on
Give both interpretations: O(1)
Best-case search in an “array list” best case either way, but note
Section 2.4
(ambiguous: array or linked list?) binary search only applies to a
sorted array, never a linked list
Binary search time complexity, and O(log n); alternative is a hash map
Section 2.3, 8.4
an alternative? for O(1) average lookup
Memory inefficiency, loses
Drawback of using a hash map? Section 8.4 ordering, average-case (not worst-
case) O(1)
Every level full except possibly the
last, which fills left-to-right with
Definition of a complete binary tree Section 6.2
no gaps — distinct from “full” and
“perfect”
N = 2^(h+1) − 1, with height
BST of height h — total number of
Section 6.3 measured from h=0 at the root
nodes?
(clarify convention first)
Be ready for BST ordering property
BST and Graph questions following
Sections 6.4, 9 + traversals, plus basic graph
the height/node-count question
terminology as natural follow-ups
Have a genuine, specific, well-
“Why do you want to be a teacher” / Not a DSA topic —
rehearsed answer ready; this
motivational questions prepare separately
recurs in nearly every transcript
Covered in the
NAT = 1:1 IP translation; PAT =
PAT vs NAT Computer Networks
many-to-one via ports
guide

Page 39 of 43
Data Structures & Algorithms — Interview Reference

Question (as asked) Where it's covered One-line answer to anchor on

4 red, 6 green — draws to guarantee
Section 11.2 6 draws (template: R + k = 4 + 2)
2 green?
Address of an integer in a row-major address = base + (i × cols + j) ×
Section 12.2
matrix, base address given element_size
Regression predicts continuous
Regression vs classification (with Cross-reference your values (e.g. house price);
example) ML/DL guide classification predicts discrete
categories (e.g. spam/not-spam)
Use labeled data for an initial
Semi-supervised learning — how to
Cross-reference your model, then use it to pseudo-label
train with some labeled, some
ML/DL guide or constrain learning on the
unlabeled data?
unlabeled portion
n items, m containers, n>m ⇒
Pigeonhole principle Section 11.1 some container holds >1 item;
generalized: at least ⌈n/m⌉
Slides a learned filter/kernel
Cross-reference your across the input to extract local
What does a Convolution Layer do?
ML/DL guide spatial features (edges, textures,
etc.)
Worst case to draw 2 aces from a 52-
Section 11.4 50 draws (template: R + k = 48 + 2)
card deck?
Sequential/time-series data where
Cross-reference your order matters; LSTM adds gating
RNN, LSTM usage
ML/DL guide to fight vanishing gradients over
long sequences
Repeated subtraction (simple) or
Quotient and remainder of a/b
Section 5.3 repeated doubling for O(log a)
without / or %
(optimized)
DFS capped at a maximum depth
ℓ; trades completeness for
Depth-Limited Search (DLS) Section 9.4
bounded resource use; generalizes
to Iterative Deepening
Prim's with an adjacency matrix,
MST algorithm choice for a dense
Section 9.5 O(V²), beats Kruskal's O(V² log V)
(social network) graph
on dense graphs
Ambiguous shared base-class state
Diamond problem (multiple via two inheritance paths;
Section 9.7
inheritance) resolved via virtual inheritance (C+
+) or disallowed (Java)

Page 40 of 43
Data Structures & Algorithms — Interview Reference

Question (as asked) Where it's covered One-line answer to anchor on

Cross-reference your
IPv4: 20–60 bytes variable; IPv6:
IPv4 / IPv6 header sizes Computer Networks
40 bytes fixed
guide
gcd(a,b) = gcd(b, a mod b), base
GCD using recursion Section 5.2
case gcd(a,0)=a; O(log(min(a,b)))
K-means grouping customers by
Cross-reference your
Example of clustering purchase behavior, with no pre-
ML/DL guide
existing labels
Cross-reference your
Same as above — 20–60 bytes vs.
Header size of IPv4 and IPv6 Computer Networks
40 bytes fixed
guide

23.1 Full-syllabus topics beyond your transcripts (don't skip these — a lecturer
interview can examine the whole course, not just past patterns)

Topic Section Likely angle of questioning

“What makes a problem solvable by DP?” — optimal
Dynamic Programming 13 substructure + overlapping subproblems; be ready to derive a
recurrence live (knapsack or LCS are the most likely picks)
“When does greedy fail?” — use the coin-change {1,3,4}
Greedy algorithms 14 counterexample; “why does greedy work for MST/activity-
selection?” — cite the exchange argument / cut property
Divide & Conquer + Apply the Master Theorem live to a new recurrence, not just
15
Master Theorem merge sort's
“Why is naive matching O(nm)?” and “how does KMP avoid re-
String matching (KMP,
16 scanning?” — the LPS array is the key artifact to be able to
Rabin-Karp)
explain
N-Queens or subset/permutation generation — be ready to
Backtracking 17 state the time complexity and explain what pruning buys you
over brute force
Be ready to identify LL/RR/LR/RL from a small example and
AVL rotations 18.1 explain why a rotation preserves BST validity (in-order
sequence is unchanged)
“Why not just recompute the sum every time?” — O(log n)
Segment trees / 18.4,
update+query beats O(n) query / O(1) update when both are
Fenwick trees 18.5
frequent

Page 41 of 43
Data Structures & Algorithms — Interview Reference

Topic Section Likely angle of questioning

Power-of-2 check, counting set bits, and the XOR-cancellation
Bit manipulation 19
trick are the three highest-yield quick questions
Union-Find with path Natural follow-up to any Kruskal's question — “why is cycle-
20.1
compression checking fast?”
Amortized analysis “Is array append O(1)?” — answer precisely: amortized O(1),
(dynamic array 21 worst-case single call O(n), and explain why doubling (not
doubling) fixed increments) is what makes this work
P vs NP, NP- High-level fluency expected, not proofs — know what NP-
22
completeness complete means and name 2–3 classic NP-complete problems

24. Final Pre-Interview Checklist — DSA

• Can you state the precise difference between full, complete, perfect, and balanced binary trees
without hesitating?
• Can you derive N = 2^(h+1)−1 live on paper, starting from h=0, and also convert to the h-starts-
at-1 form if asked?
• Can you write binary search from memory, including the overflow-safe mid calculation?
• Can you state Big-O vs Big-Omega vs Big-Theta precisely, not just colloquially?
• Can you solve a pigeonhole “worst-case draws” problem on the spot for a new pair of numbers
(not just the ones you've memorized)?
• Can you justify Prim's vs Kruskal's for a dense vs sparse graph from first principles (not just
recalling the answer)?
• Can you explain why quicksort is O(n²) worst case but mergesort never is — and why that
matters for adversarial inputs?
• Can you compute a row-major matrix address live, and immediately adapt if asked about
column-major or 1-indexing?
• Can you explain why a hash map's O(1) is only average-case, with a concrete reason it can
degrade?
• Can you write GCD recursively and explain why it's O(log n) rather than O(n)?
• Can you write the 0/1 knapsack recurrence from memory and explain why it's only pseudo-
polynomial?
• Can you give a concrete example where greedy fails but DP succeeds (coin change with {1,3,4})?
• Can you apply the Master Theorem to a recurrence you haven't seen before, not just
T(n)=2T(n/2)+O(n)?
• Can you explain how KMP's LPS array avoids re-scanning matched characters?
• Can you identify an AVL LL vs LR imbalance case from a small drawn example?

Page 42 of 43
Data Structures & Algorithms — Interview Reference

• Can you explain why dynamic array append is amortized O(1) despite an O(n) worst case for a
single call?
• Can you state what NP-complete means and name at least two classic NP-complete problems?

Page 43 of 43