AnalysisFoundation
Count the real cost
Derive the exact comparison count and Θ bound for two consecutive loops of sizes n and n/2.
Technique: operation counting
Target: Θ(n)
Back homeReview the concept Review the concept Review the concept Review the concept Review the concept Review the concept Review the concept Review the concept Review the concept Review the concept Review the concept Review the concept Review the concept Review the concept Review the concept Review the concept Review the concept Review the concept Review the concept Review the concept Review the concept Review the concept Review the concept Review the concept Review the concept Review the concept Review the concept Review the concept Review the concept Review the concept Review the concept Review the concept Review the concept
From recognition to implementation
Practice bank
34 focused exercises covering traces, coding patterns, complexity arguments, and design choices. Each card tells you the intended technique and links back to the relevant lesson.
Filter the problem bank
Showing 34 of 34 exercises
Review the concept
AnalysisIntermediate
Growth-rate detective
Order log n, n log n, n², 2ⁿ, and n! and estimate which remain usable at n=50.
Technique: growth comparison
Target: justify feasibility
AnalysisChallenge
Trade memory for time
Compare repeated Fibonacci recursion, memoisation, and an iterative two-variable solution for n=45.
Technique: time–space trade-off
Target: O(n) time, O(1) space
LinearFoundation
Rotate in place
Rotate a vector right by k positions without allocating another vector.
Technique: three reversals
Target: O(n) time, O(1) extra
LinearIntermediate
Longest unique window
Find the length of the longest substring with no repeated character.
Technique: sliding window + frequency
Target: O(n) expected
LinearFoundation
Reverse by links
Reverse a singly linked list iteratively and state the loop invariant.
Technique: three pointers
Target: O(n) time, O(1) extra
LinearIntermediate
Detect a cycle
Detect whether a linked list contains a cycle without modifying nodes.
Technique: slow/fast pointers
Target: O(n) time, O(1) extra
LinearChallenge
LRU skeleton
Design get and put for a fixed-capacity least-recently-used cache.
Technique: hash map + doubly linked list
Target: O(1) expected operations
LinearFoundation
Balanced brackets
Validate (), [], and {} while reporting the first bad index.
Technique: stack of opening tokens
Target: O(n)
LinearIntermediate
Next greater value
For every array element, find the first greater element to its right.
Technique: monotonic stack
Target: O(n)
LinearIntermediate
Queue from stacks
Implement FIFO enqueue and dequeue using only two stacks.
Technique: lazy transfer
Target: O(1) amortized
LinearFoundation
Frequency table
Return the first array value whose frequency reaches two.
Technique: unordered_set
Target: O(n) expected
LinearChallenge
Adversarial hashing
Explain how poor hashing turns expected O(1) lookup into O(n), then propose two mitigations.
Technique: load factor + hash quality
Target: reason about guarantees
SearchingFoundation
First occurrence
Return the first index of target in a sorted array containing duplicates.
Technique: lower bound
Target: O(log n)
SearchingIntermediate
Minimum feasible speed
Given workloads and h hours, find the smallest integer speed that finishes all work.
Technique: binary search on answer
Target: O(n log range)
SearchingChallenge
Search rotated data
Locate a key in a strictly increasing array rotated at an unknown pivot.
Technique: identify sorted half
Target: O(log n)
SortingFoundation
Trace stability
Sort pairs by key and identify which syllabus algorithms preserve equal-key order.
Technique: stability analysis
Target: explain with counterexample
SortingFoundation
Nearly sorted input
Show why insertion sort is efficient when each item is at most k positions away.
Technique: inversion counting
Target: connect work to disorder
SortingIntermediate
Count inversions
Count pairs i<j with a[i]>a[j] without checking all pairs.
Technique: merge-sort augmentation
Target: O(n log n)
SortingChallenge
Kth smallest
Find the kth smallest element without fully sorting the input.
Technique: quickselect partition
Target: O(n) average
TreesIntermediate
Traversal reconstruction
Reconstruct a binary tree from preorder and inorder sequences with distinct keys.
Technique: index map + recursion
Target: O(n)
TreesFoundation
Validate a BST
Determine whether every node satisfies global BST bounds, not just its parent relation.
Technique: range propagation
Target: O(n)
TreesIntermediate
Lowest common ancestor
Find the lowest shared ancestor of two keys in a BST.
Technique: use ordering
Target: O(height)
TreesChallenge
AVL rotation journal
Insert 50,30,70,20,40,35 and record balance factors and rotations after each step.
Technique: height invariant
Target: correct LR/RL diagnosis
HeapsIntermediate
Running kth largest
Report the kth largest value after every item in a stream.
Technique: size-k min heap
Target: O(n log k)
HeapsChallenge
Merge sorted streams
Merge k sorted arrays while keeping only one candidate from each array.
Technique: custom heap entry
Target: O(N log k)
GraphsFoundation
Count components
Count connected components in an undirected graph and label every vertex.
Technique: repeated BFS/DFS
Target: O(V+E)
GraphsIntermediate
Unweighted shortest route
Return the actual shortest path between two vertices in an unweighted graph.
Technique: BFS + parent array
Target: O(V+E)
GraphsIntermediate
Dependency cycle
Detect a cycle in a directed dependency graph.
Technique: three-colour DFS
Target: O(V+E)
GraphsChallenge
Reliable shortest paths
Implement Dijkstra with stale-entry rejection and reconstruct the selected route.
Technique: min heap + relaxation
Target: O((V+E) log V)
GraphsIntermediate
Dynamic connectivity
Process union and connected queries using path compression and union by size.
Technique: DSU
Target: near-constant amortized
GraphsChallenge
Compare two MSTs
Run Prim and Kruskal on the same weighted graph and explain why their edge order differs but total weight agrees.
Technique: cut and cycle properties
Target: prove correctness intuition
SpatialIntermediate
Point-region query
Design a quadtree range query that skips quadrants not intersecting a rectangle.
Technique: spatial pruning
Target: output-sensitive reasoning
SpatialChallenge
Waste-route model
Choose graph and spatial structures for bin locations, road travel, updates, and daily route queries.
Technique: data-structure selection
Target: defend a composite design