Back
Keentune
Data Structures & Algorithms curriculum 25 chapters
·
217 concepts
·
free
Everything the adaptive question bank can teach and test in Data Structures & Algorithms, from foundations through advanced practice. Work through it in order, or start practising and let the questions find your level.
Start practising Data Structures & Algorithms
New here? Read the Data Structures & Algorithms guide
A free 17-minute primer — the mental model, the mistakes beginners make, and what to practise first.
A. The programming model: arrays, loops and recursion
•
an element is reached by address arithmetic, so a[i] costs the same for every i
•
the last valid index of a length-n array is n−1; off-by-one is the classic bounds bug
•
two loops of n each run n² times; nesting multiplies, sequencing only adds
•
binary search is correct only on sorted input, and finds a key in ~log₂n probes
•
(lo+hi)/2 can overflow a fixed-width int; lo + (hi-lo)/2 cannot
•
first-true, lower bound and upper bound differ only in which half keeps the equal case
•
every call must move toward a base case, or the recursion never returns
•
each pending call holds a frame, so recursion depth costs memory as well as time
B. Bags, stacks, queues and linked lists
•
push and pop serve the most recently added item first, which is what makes undo and bracket matching easy
•
enqueue and dequeue preserve arrival order
•
a deque adds and removes at both ends in constant time, generalizing stack and queue
•
a node holds an item plus a reference to the next node; the chain is the list
•
inserting at the head is constant time because nothing shifts
•
inserting at position i in an array moves the n−i elements after it
•
reaching the kth node costs k link hops; there is no address arithmetic
•
a back pointer buys O(1) deletion given a node, and costs a pointer per node
•
doubling on overflow keeps append amortized constant; growing by one makes it linear
C. Analysis of algorithms and asymptotics
•
running time is characterized by how it scales with n, not by the constant in front
•
O is a ceiling, Ω is a floor, and Θ pins the growth from both sides
•
constants, lower-order terms and memory behavior; an O(n log n) sort can lose on small n
•
constant, log, linear, linearithmic, quadratic, exponential, and the gaps between them
•
changing base multiplies by a constant, so O(log n) needs no base
•
which input each describes, and why the worst case is the only guarantee
•
auxiliary space excludes the input, and "in place" means O(1) extra
•
total cost is the sum over levels; branching factor and depth set the class
•
T(n)=aT(n/b)+f(n) is decided by comparing f(n) against n^(log_b a)
D. Amortized cost and cost models
•
amortized is a worst-case average over a sequence, not an average over random inputs
•
bound the cost of the whole sequence, then divide by the number of operations
•
cheap operations prepay credit that the rare expensive one spends
•
a potential function makes the stored credit an explicit function of the structure's state
•
n appends copy 1+2+4+… < 2n elements in total, so each append is amortized constant
•
an amortized O(1) append still takes Θ(n) once, which is a latency problem, not an average one
•
each element is pushed and popped at most once, so a scan with an inner while-loop is still linear
E. Union-find and dynamic connectivity
•
answer "are these connected?" under interleaved unions, without recomputing components
•
find is constant, but union rewrites the whole id array, so building is quadratic
•
union becomes cheap, but an unbalanced tree makes find linear
•
always attach the smaller tree under the larger, which bounds depth by log n
•
flatten the path during find, so every later find along it is near-constant
•
weighting plus compression is O(α(n)) amortized, which is constant for any real n
•
it reports that two sites connect, never which route connects them
•
the left prefix holds the smallest items already in final position
•
~n²/2 compares but exactly n exchanges, which is why it wins when a move is expensive
•
the left prefix is sorted but not final; each new item is slid back into place
•
linear on nearly-sorted input and quadratic on reverse-sorted, unlike selection sort
•
its exchange count is exactly the number of inversions in the input
•
the same quadratic bound as insertion sort with strictly more exchanges
•
h-sorted subsequences let an item travel far in one step, which beats quadratic
•
recursive sorts switch to insertion sort under ~10 items because constants dominate there
G. Mergesort and divide and conquer
•
split, solve the halves recursively, combine; the combine step is what sets the cost
•
merging two sorted runs is one pass with two indices and an auxiliary array
•
T(n)=2T(n/2)+Θ(n) solves to Θ(n log n): log n levels of linear work
•
the standard implementation needs Θ(n) auxiliary space, so it is not in place
•
a tie takes the left run's element, which preserves input order
•
it needs no random access, which makes it the sort of choice for lists
•
merging streams is why it sorts data larger than memory and splits across cores
•
sort, split, recurse, then check only a constant-width strip across the divide
•
evaluating at roots of unity makes polynomial multiplication pointwise, in n log n
H. Quicksort, randomization and selection
•
after partitioning the pivot is in final position, smaller to its left, larger to its right
•
no auxiliary array, but a long-range exchange can reorder equal keys
•
an always-extreme pivot makes every partition of size n−1
•
with a first-element pivot, already-sorted input is precisely the worst case
•
randomizing makes the bad case improbable instead of input-determined
•
many equal keys make two-way partitioning quadratic unless they are handled
•
a less/equal/greater split makes the sort linear when the distinct keys are few
•
partitioning toward one side only finds the kth smallest in linear expected time, without sorting
I. Priority queues and heaps
•
insert and remove-the-maximum; the order of everything else is never maintained
•
every node is ≥ its children, so the maximum sits at the root
•
a heap needs no pointers: the children of k are at 2k and 2k+1
•
heap order is restored by moving one node up or down, one compare per level
•
both are O(log n) because a complete tree's height is ⌊log₂n⌋
•
bottom-up heapify is O(n); n successive inserts is O(n log n)
•
the underlying array is only partially ordered, so reading it top to bottom is not a sorted scan
•
build a heap, then repeatedly swap the root to the end: n log n with O(1) extra space
•
a size-k min-heap yields the k largest in O(n log k), without sorting everything
J. Sorting applications, stability and lower bounds
•
any comparison sort needs Ω(n log n) compares, by counting decision-tree leaves
•
key-indexed counting never compares two keys, so the bound does not apply to it
•
fixed-length keys are sorted from the right, variable-length keys from the left
•
a stable sort keeps equal keys in their input order
•
insertion and merge are stable; selection, quick and heap are not
•
sort by the secondary key first with a stable sort, or write one composite comparator
•
a comparator must be antisymmetric and transitive, or the sort can throw or silently corrupt order
•
production sorts mix insertion, merge and quick, and exploit runs that already exist
K. Symbol tables and searching
•
put and get by key; keys are unique and a repeat put overwrites
•
an unordered linked symbol table searches in Θ(n)
•
search drops to O(log n), but insertion still shifts ~n/2 entries
•
rank, select, floor, ceiling, min, max and range search all require an ordered table
•
rank counts the keys below a key; select returns the key at a rank
•
hashing buys faster lookup; ordering buys range and predecessor queries
•
mutating a stored key breaks the ordering or hashing that indexed it, and the entry is lost
•
a set is a symbol table with no values, and inherits exactly its costs
•
every key in the left subtree is smaller and every key in the right is larger
•
an inorder walk emits the keys in ascending order
•
every operation costs one root-to-node path, so the height is the whole story
•
random insertion order gives ~1.39 log n expected search cost
•
inserting keys in order builds a linked list with linear search
•
the successor is the leftmost node of the right subtree, or else the nearest larger ancestor
•
deleting a two-child node promotes its successor, and repeated deletion skews the tree
•
pre-, in- and post-order differ only in when the node is visited, and each fits a different task
•
breadth-first traversal is driven by a queue, not by recursion
M. Balanced search trees and B-trees
•
a guaranteed log n height converts an average case into a worst-case guarantee
•
a temporary 4-node splits and pushes its middle key up, so the tree grows at the root
•
a red link encodes a 3-node, which keeps the implementation binary
•
no two red links in a row and perfect black balance, which gives height ≤ 2 log n
•
a rotation changes the shape while leaving the inorder key sequence unchanged
•
hundreds of keys per node make the tree shallow, so a lookup costs only a few block reads
•
node size is chosen to match a disk block or a cache line, which is why databases use B-trees
•
random levels give expected log n search with no rotations and easier concurrency
•
map a key to an array index, so lookup becomes address arithmetic instead of search
•
the contract runs one way: equal objects must share a hash, unequal ones need not differ
•
by the pigeonhole principle, once keys outnumber slots some must share one
•
each slot holds a list, and the average search length is the load factor
•
store in the next free slot; deleting must rehash the rest of the cluster, not just blank the slot
•
a long probe run makes further insertions likelier to extend it, so the cost compounds
•
cost climbs sharply as α approaches 1, so tables grow and rehash every key
•
with every key colliding, a hash table degenerates to a list scan
•
no range, predecessor or sorted iteration, and iteration order is unspecified
•
false positives are possible, false negatives are not, and nothing can be deleted
•
a hash map for lookup plus a doubly linked list for recency gives O(1) get and put
O. Undirected graphs: representation and search
•
vertex, edge, degree, path, cycle and connected component
•
constant-time edge tests at Θ(V²) space, which suits dense graphs only
•
Θ(V+E) space with fast neighbor iteration, which is the default for sparse graphs
•
on a large graph the representation, not the traversal, is usually what decides feasibility
•
visit, mark, recur; the marked array is what makes the search terminate
•
recursion depth is the path length, so a long graph overflows the stack long before it runs out of time
•
BFS finds a fewest-edge path because it settles vertices in distance order
•
depth-first goes as far as it can and breadth-first goes level by level; both are Θ(V+E)
•
one search per unmarked vertex labels every component in linear time
•
a graph is bipartite exactly when a search two-coloring never conflicts
•
an edge to a marked vertex that is not the parent closes a cycle
P. Directed graphs, topological order and cycles
•
reachability is one-way, so "v reaches w" says nothing about the reverse
•
a directed acyclic graph is exactly the class that can be topologically ordered
•
reverse DFS postorder of a DAG is a valid topological order
•
repeatedly emit a zero-indegree vertex; any vertices left over prove a cycle
•
the test is an edge back to a vertex on the current recursion stack, not merely a marked one
•
mutual reachability, computed by Kosaraju's two passes using the reverse graph
•
contracting each strong component always leaves an acyclic graph you can order
•
build order, course prerequisites and spreadsheet recalculation are all topological sorts
Q. Minimum spanning trees
•
V−1 edges that connect every vertex and contain no cycle
•
the minimum-weight edge crossing any cut belongs to some MST
•
the maximum-weight edge on any cycle belongs to no MST
•
take the next-lightest edge unless it closes a cycle, and union-find is that cycle test
•
repeatedly add the lightest edge leaving the tree, chosen with a priority queue
•
Prim suits dense graphs, Kruskal suits sparse or already-sorted edge lists
•
MST algorithms only compare weights, so a negative edge changes nothing
•
the MST minimizes total weight, not the distance between any particular pair
•
the one primitive: improve dist[w] if the route through v is shorter
•
settle the nearest unsettled vertex; once settled, its distance is final
•
a negative edge found later can beat a settled vertex, which is what breaks that invariant
•
E log V with a binary heap against V² with a linear scan; density decides which wins
•
relaxing in topological order needs no priority queue and tolerates negative weights
•
V−1 rounds relaxing every edge, because a shortest path has at most V−1 edges
•
a Vth round that still improves proves a negative cycle, and then no shortest path exists
•
a V³ dynamic program over which intermediate vertices are allowed
•
negating the weights does not transfer the algorithm; longest simple path is NP-hard
S. Tries and string search
•
the key is the path from the root, and each node branches on the next character
•
search time depends on the key's length, not on how many keys are stored
•
an R-way trie stores R links per node, so the alphabet size dominates memory
•
the sorted suffixes plus the longest-common-prefix of adjacent pairs answer substring questions the trie cannot afford at scale
•
prefix match, keys-with-prefix and longest-prefix-of are what a hash table cannot answer
•
up to MN character compares, and the scan backs up in the text
•
precomputed shifts let the scan never re-read a text character
•
a rolling hash compares in constant time per shift, verifying only on a hash match
•
scanning the pattern right to left lets one mismatch skip nearly a whole pattern length
T. Recursion, memoization and dynamic programming
•
DP pays off exactly when the same subproblem recurs; plain recursion re-solves it exponentially
•
the optimum must be built from optima of subproblems, or the recurrence is simply wrong
•
cache results keyed by the arguments; the code stays recursive and computes only what it needs
•
fill a table in dependency order: no call stack, but you must know that order in advance
•
the state must capture everything the remaining decisions depend on, and nothing more
•
the running time is the number of states multiplied by the work per state
•
the canonical demonstration that caching collapses a re-computation tree
•
capacity-indexed states, and why the value-density greedy fails once items are indivisible
•
a grid over two sequences, with the recurrence branching on the last characters
•
the quadratic longest-increasing-subsequence DP has an n log n form over tail values
•
items outside and capacity inside counts combinations; swapping the loops counts permutations
•
the table holds the value; recovering the choices needs parent pointers or a back-walk
U. Greedy algorithms and paradigm choice
•
a locally optimal choice must be provably extendable to a global optimum
•
greedy needs an exchange argument or a structural property; passing test cases is not evidence
•
sorting by finish time is optimal; by start time or by duration it is not
•
the value-density greedy is optimal only when items can be split
•
repeatedly merging the two least frequent symbols yields an optimal prefix code
•
coin change over an arbitrary denomination set is the standard counterexample
•
greedy commits to one choice and never revisits; DP keeps every choice it cannot rule out
•
systematic search that abandons a branch the moment it cannot beat the best found so far
V. Array techniques and range queries
•
converging indices find a target pair in one linear pass once the array is sorted
•
a cycle in a linked list is proved when the two-step pointer meets the one-step pointer
•
grow while the constraint holds and shrink when it breaks; each index advances at most once
•
the technique is valid only when extending the window can only break the predicate, never fix it
•
one precomputation pass answers any range-sum query in constant time
•
when feasibility is monotone in the answer, search the answer space instead of the input
•
implicit binary indexing gives prefix sums and point updates in log n with almost no extra space
•
a precomputed table of 2^k-th ancestors answers an ancestor jump, and therefore an LCA query, in log n instead of walking parent by parent
•
a tree over ranges answers any associative range query, and supports range updates with lazy propagation
•
the ith bit contributes 2^i, which is why bit tricks are arithmetic in disguise
•
AND masks, OR sets, XOR toggles, NOT complements
•
a left shift by k multiplies by 2^k and a right shift divides, discarding the remainder
•
a signed right shift replicates the sign bit; an unsigned one fills with zeros
•
negation is invert-then-add-one, which is why the negative range is one wider than the positive
•
x & (1<<i) tests, x | (1<<i) sets, x & ~(1<<i) clears
•
x & -x isolates the lowest set bit and x & (x-1) clears it, which is how popcount runs once per set bit
•
x^x is 0, which finds the unpaired element and swaps two values without a temporary
X. Standard-library container complexity
•
appending is amortized constant; inserting or deleting at the front is linear
•
in on a list scans every element, while on a set or dict it hashes once
•
a deque is O(1) at both ends but O(n) to index in the middle
•
hashed lookup, insert and delete, with the same worst-case-linear caveat as any hash table
•
push and pop are log n, and a max-heap is obtained by negating the keys
•
the search is log n but the insertion is still linear, because the list has to shift
•
repeated concatenation is quadratic because each step copies; join in one pass instead
•
pick the container from what you do most: lookup, ordering, both ends, or ranked access
Y. Reductions, intractability and randomized algorithms
•
reducing A to B proves B is at least as hard as A; the reverse direction proves nothing
•
solvable in polynomial time versus merely verifiable in polynomial time
•
in NP, and every problem in NP reduces to it, so one fast solution would solve them all
•
NP-hard need not be in NP, and need not even be a decision problem
•
SAT, clique, vertex cover, Hamiltonian path, subset sum and graph coloring
•
exact exponential search, heuristics and approximations still solve real instances
•
convex hull is Ω(n log n) because sorting reduces to it
•
the maximum flow equals the minimum cut, and augmenting paths in the residual graph find both
•
one pass and O(k) space keep each of n streamed items with probability k/n
Keentune is not affiliated with or endorsed by the organizations whose documentation informs these maps.
Start practising Data Structures & Algorithms
All about Data Structures & Algorithms practice
All exam, test, and product names and trademarks are the property of their respective owners and are used here for identification and reference only. Keentune is independent study practice — not affiliated with, authorized, or endorsed by any of these organizations.
© 2026 SportaApp LLC