home
›
cheatsheets
›
computer_science
›
core_algorithms
Free to read Every card and diagram, and Quiz me
2
Free account Star cards. Your Quiz me marks are kept, so next time you drill just what you missed
3
Pro All 61 answers on this sheet, My sheet across every topic, and PDFs
A free account keeps your stars and Quiz me marks. Pro adds all 61 answers on this sheet, My sheet across every topic, and PDFs.
/
Read
Quiz me
Comfortable
Compact
0
Click any code to copy it
Done 0 /0
To review 0
On this sheet
01 Binary search02 How the main sorts work03 Stable & library sorts04 Faster than n log n05 Sorting at scale06 Recursion & the call stack07 Cost of a recursion08 Backtracking09 Pruning big searches10 Greedy algorithms
The model Binary search checks the middle and drops half the range at each step, so a million items take about 20 checks. The data must be sorted by the key you search.No comparison sort beats O(n log n). Quicksort is usually fastest but can hit O(n^2). Merge sort is stable and always O(n log n), but needs O(n) extra memory. Every recursion needs a base case and a step that shrinks the problem. Each call waiting on a deeper one holds a stack frame, so deep recursion overflows the stack. The shape of the call tree sets the cost. One call on half the input gives log n. Two calls on halves plus a linear merge give n log n. Two calls on n-1 give 2^n. Backtracking tries a choice, explores it, then undoes it, and prunes paths that can't work. Greedy takes the best choice now and never goes back, so it needs a proof.Each tree shows one algorithm's calls, marked with its cost from the key. Binary search never makes the faded calls.
Binary search find a value in sorted data in O(log n) Write a binary search let lo = 0, hi = a.length - 1; while (lo <= hi) { const mid = lo + ((hi - lo) >> 1); can't overflow if (a[mid] === target) return mid; if (a[mid] < target) lo = mid + 1; drop the left half else hi = mid - 1; drop the right half } return -1; lo is where it would go
Find a value in a sorted array Halve the range each step. A million items need 20 checks.
Binary search or a linear scan Get data ready for binary search Sort it by the key you compare on. Keep it in an array.
Find one value in unsorted data Scan it in O(n). Sorting pays off only for many lookups.
Search a small array Scan it. Below about 100 items it's as fast or faster.
Tip On a linked list each probe walks the list, so binary search degrades to O(n).
Trap On unsorted data, binary search returns a wrong answer and raises no error.
First match, last match and insertion point Find the first match if (a[mid] < target) lo = mid + 1; else hi = mid; Start at hi = a.length. Loop while lo < hi.
Find the last match Mirror it. Move lo right on a match, rounding mid up.
Trap Stopping at the first equal value can land you in the middle of the duplicates.
Binary search on the answer Find the smallest value that works if (feasible(mid)) hi = mid; else lo = mid + 1; lo ends on the smallest value that works.
Search a function over real numbers Stop at a tolerance. 50 halvings take a range of 1 to 1e-15.
Tip Classic uses are the smallest capacity that meets a deadline, or the lowest maximum load.
Trap Prove the check is monotonic. If it flips back and forth, halving loses the answer.
Midpoint overflow and huge arrays Compute the midpoint safely mid = lo + (hi - lo) / 2 (lo + hi) / 2 can overflow on huge arrays.
Index billions of elements Use a 64-bit index. 32 bits wrap past two billion.
Search sorted data that doesn't fit in RAM Use a B-tree. Binary search makes each probe a disk seek.
Tip The bug bites in Java and C. JavaScript numbers stay exact far past any array size.
How the main sorts work quicksort, merge sort, heapsort and what each costs Sort costs at a glance Stable In place
O(n log n) average, O(n^2) worst. Sort with quicksort
O(n log n) always, O(n) extra. Sort with merge sort
O(n log n) always, O(1) extra. Sort with heapsort
O(n^2), near O(n) if nearly sorted. Sort with insertion sort
O(n + k) for keys in a range of k. Sort small integers with counting sort
O(d * (n + b)) for d digits, base b.Sort fixed-width keys with radix sort
Tip Start with the built-in sort. Switch only when a constraint rules it out.
Merge sort Split the list Halve it until each piece holds one item.
Merge two sorted halves Compare the two fronts, take the smaller, repeat.
Tip It needs no index access, so it also sorts linked lists and files on disk.
Quicksort Partition around a pivot Swap smaller items forward, then put the pivot after them.
Finish the sort The pivot is now in place. Sort each side the same way.
Tip It sorts inside the array. Its only extra memory is the stack, O(log n) on average.
Quicksort's worst case n 0 n-1 0 n-2 0 n-3 bad pivots A last-item pivot on sorted input leaves one side empty. n levels of n work make n^2.Spot what makes quicksort O(n^2) The first or last item as pivot, on sorted input.
Sort input full of equal keys Three-way partition. Equal keys get a middle group.
Pick a pivot no fixed input can beat Choose it at random. Expected time stays O(n log n).
Handle sorted input cheaply Use the median of the first, middle and last items.
Trap Median of three fixes sorted input, but a crafted input can still force O(n^2).
Heapsort Sort with a heap Build a max-heap. Swap the root to the end, sift down.
Explain why libraries rarely pick it Parent and child sit far apart, so it misses the cache.
Tip Its real job is a fallback. Introsort switches to it when quicksort recurses too deep.
Quicksort or merge sort Sort an array fast with little memory Quicksort. It sorts in place with a tight inner loop.
Keep ties in order or cap the worst case Merge sort. It's stable and never worse than O(n log n).
Explain why quicksort usually wins Merge sort copies to a second buffer and misses the cache.
Rank the n log n sorts on real hardware Quicksort first, heapsort last. Cache misses decide it.
Trap Quicksort isn't faster in Big-O. Both average O(n log n), and quicksort wins on cache use and constant factors.
Stable & library sorts keep ties in order, and know what your language runs Stable sorts Say what a stable sort does Items with equal keys keep their original order.
Sort by last name, then first name Sort by first name, then stable-sort by last name.
Name the stable sorts Merge, insertion and counting. Not quicksort or heapsort.
Explain what stability costs Memory or speed. Merge sort pays an O(n) buffer.
Make an unstable sort stable Break ties on the original index, at O(n) memory.
Trap An unstable sort can reorder equal keys, so sorting in two passes stops working.
What your language's sort runs Sort in Python sorted(xs) Powersort since 3.11, a stable Timsort variant.
Sort in Java list.sort(cmp) Timsort for objects, quicksort for primitives.
Sort in C++ std::sort(v.begin(), v.end()) Introsort, unstable. std::stable_sort keeps ties in order.
Sort numbers in JavaScript nums.sort((a, b) => a - b) Without a comparator, numbers sort as strings.
Tip JavaScript's sort has had to be stable since ES2019.
Timsort and introsort Explain how Timsort works Merges sorted runs. Insertion sort extends short ones.
Cost Timsort O(n) on sorted input, O(n log n) at worst. Stable.
Explain how introsort caps the worst case Quicksort until depth 2 log n, then heapsort.
Trap Introsort isn't stable. Quicksort and heapsort both reorder equal keys.
Faster than n log n the limit on comparison sorts, and how to get under it Why comparison sorts can't beat n log n Prove the n log n limit Telling n! orders apart takes log2(n!) comparisons, about n log n.
Name the sorts the limit doesn't cover Counting and radix sort. They never compare keys.
Tip Draw a decision tree with n! leaves. Its height is the worst-case comparison count.
Counting sort and radix sort Sort with counting sort Count each value, then place each item in its final slot.
Decide when counting sort fits Integer keys in a small, dense range, like 0 to 255.
Sort with radix sort A stable counting sort per digit, lowest digit first.
Tip Keys spread over billions of values make counting sort's array too big.
Trap Each digit's pass must be stable, or it scrambles the earlier digits.
Find the k-th smallest without sorting Find the k-th smallest or the median Quickselect, O(n) on average. Recurse only into k's side.
Answer many different k Sort once in O(n log n), then read each answer in O(1).
Guarantee linear-time selection Median of medians, O(n) at worst, or introselect.
Trap Quickselect is O(n^2) with bad pivots, and it reorders the array.
Sorting at scale data bigger than memory, many machines, many threads Sort more data than fits in memory Make sorted runs Sort memory-sized chunks and write each out as a run.
Merge the runs K-way merge, with a heap picking the next item.
Tune the merge width Wider merges cut passes but make reads smaller.
Tip Disk reads set the cost, not comparisons. Databases sort big ORDER BY results this way.
Sort across many machines Pick each machine's key range Sample the data to pick balanced split points.
Shuffle and sort Send records to their range's machine, then sort locally.
Tip No final merge is needed. The network shuffle usually takes most of the time.
Trap A poor sample skews the ranges, and one machine gets most of the data.
Sort on many threads Parallelize quicksort or merge sort Each recursive call is a task on its own range. No locks.
Find the serial bottleneck Quicksort's first partition, and merge sort's last merge.
Stop spawning tasks Below a few thousand items, run sequentially.
Find the limit on speedup The serial merge, by Amdahl's law. Memory bandwidth too.
Tip A work-stealing pool lets idle threads take waiting subtasks.
Trap False sharing. Threads writing slices on one cache line slow each other.
Sort when comparisons are expensive Compute an expensive sort key once per item sorted(items, key=score) Python calls score n times, not n log n.
Pick the sort with the fewest comparisons Merge sort, near the minimum. Heapsort compares more.
Tip Cache each pair's result if the same pair can come up again.
Recursion & the call stack base cases, stack frames and stack overflows Write a recursive function Name the two parts every recursion needs A base case, and a step that shrinks toward it.
Leave out the base case The calls never stop, and the stack overflows.
Choose recursion over a loop When the data branches, like trees or nested JSON.
Trap A base case the calls never reach fails the same way.
The call stack Say what each call pushes A frame with its arguments, locals and return address.
Say which call finishes first The deepest. Its frame pops and the caller resumes.
Know how much stack you get Often 1 to 8 MB. Ten thousand levels can overflow it.
Tip Each nested call gets its own copy of every local variable.
Trap Depth crashes the stack, not total work. A million-node list needs a million frames.
Turn recursion into a loop Rewrite tail recursion A while loop that updates the arguments in place.
Rewrite any other recursion Push pending work onto your own stack on the heap.
Raise the thread's stack size A stopgap. Bigger input brings the same crash back.
Tip Convert only when depth is a real risk. Readable, shallow recursion can stay.
Tail calls Spot a tail call The recursive call is the last thing the function does.
Name languages that guarantee tail calls Scheme, Lua and most functional languages.
Name languages that lack them CPython and Java. In JavaScript, only Safari has them.
Trap Tail form helps only where the runtime honors it. Otherwise write the loop.
Cost of a recursion recurrences, the Master Theorem and stack space Work out a recursion's running time Write the recurrence One call's work plus the cost of the calls it makes.
Count the branching factor Two calls per level is often O(2^n), as in naive Fibonacci.
Solve an uneven recurrence Draw the recursion tree and add up the work on each level.
Solve T(n) = aT(n/b) + f(n) The bigger of f(n) and n^(log_b a) wins. A tie adds log n.
Tip Merge sort is a tie, with a = 2, b = 2 and f(n) = n. That gives O(n log n).
Trap The Master Theorem fits only even splits, not T(n-1) recursions.
Work out a recursion's space Count the stack space Max depth times frame size. Only live calls count.
Keep quicksort's stack small Recurse on the smaller side first. Depth stays O(log n).
Tip Fast code can still crash from stack depth. Time analysis won't show it.
Backtracking try a choice, explore it, undo it The backtracking template function solve(state) { if (isComplete(state)) { record(state); return; } for (const choice of options(state)) { apply(choice, state); choose solve(state); explore undo(choice, state); unchoose } }
Tell backtracking from brute force Backtracking checks as it builds, not at the end.
Say why the undo step matters It resets shared state, so the next branch starts clean.
Trap The template alone explores the whole tree and times out. Prune inside the loop.
Why backtracking is exponential Estimate the search tree's size Up to b^d leaves for b choices over d steps.
Prune a branch Cut it once it can't succeed, like a queen under attack.
Make pruning pay off Never drop a real answer, and keep the check cheap.
Trap Pruning only helps when branches die early. Loose constraints mean brute force again.
Permutations, combinations and duplicates Generate permutations Try every unused item at each level. O(n!).
Generate combinations or subsets for (let i = start; i < nums.length; i++) Look forward only. Recurse with i + 1. O(2^n).
Skip duplicate answers if (i > start && nums[i] === nums[i - 1]) continue; Sort first, then skip equal siblings.
Tip Without the start index, combinations come out in every order.
Trap A hash set of results still builds every duplicate branch. Skip at the branch.
Pruning big searches what expert interviews add to backtracking Bound a search of billions of states Stop a search that could run forever Cap the depth or node count. Return the best so far.
Skip states you reached another way Memoize partial states, so a repeat costs nothing.
Search when the goal depth is unknown Iterative deepening, depth-first to 1, then 2, then 3.
Tip Iterative deepening keeps only O(d) memory and finds the shallowest answer first.
Trap The visited set can fill RAM itself. Hash compact keys, not whole objects.
Branch and bound Prune legal branches that can't win Cut branches whose bound can't beat the best so far.
Write the bound An optimistic estimate of the best score below a node.
Trap A bound that isn't optimistic prunes real optima. A loose one prunes little.
Fail fast with ordering and propagation Choose the next variable The most constrained one, with the fewest legal values.
Choose the next value The one that rules out the fewest neighbor options.
Find a dead end before recursing Forward checking. An empty neighbor domain ends it now.
Skip branches that mirror each other Fix a canonical order, or skip seen canonical keys. Only cut what you've proved symmetric.
Trap Ordering and propagation cost work at every node. On loosely constrained problems they can cost more than they save, so measure.
Greedy algorithms take the best choice now, and know when that's safe When greedy works Say what a greedy algorithm does Take the best-looking option each step and never go back.
Name the two properties greedy needs Greedy choice and optimal substructure.
Prove a greedy algorithm right Exchange argument. Swapping in the greedy pick is no worse.
Fit the most meetings into one room Sort by finish time, then take each one that fits.
Tip US coins work greedily. Take the biggest coin that fits, 25, then 10, 5 and 1.
When greedy fails Make 6 from coins of 1, 3 and 4 Greedy takes 4 + 1 + 1. The best is 3 + 3.
Test a greedy idea Hunt for a small counterexample. One loss rules it out.
Accept greedy on a hard problem When it has a proven ratio, like set cover's ln n.
Trap An unproven greedy fails silently. If you can't write the swap step, it's a heuristic.
Nothing matches. Try a shorter word, or clear the search.
Practice Guided practice One question at a time, with the ones you miss coming back. Practice 61 interview questions Full answers, from beginner to expert.
Found this useful? Pass it on.
Share on LinkedIn
Share on X
Copy link
This sheet stays free. With Pro , you can:
Every answer on this sheet. Read the full answer to all 61 questions it links, not just the 10 free ones.My sheet. The cards you star and the ones you miss in Quiz me, from every sheet, on one page to quiz and print.PDFs. Download this sheet and My sheet, laid out for A4, with every question a link to its answer.The rest of Pro. Every answer in the question library, and 1,000 AI credits a month.
