Answers

Making it fast enough

How long a piece of work takes before you run it, and the handful of arrangements of data that most of the difference comes from.

1. Why doesn't breadth-first search give the cheapest path once the links have different costs?Breadth-first search counts links rather than costs, so it can return a route with fewer links that is more expensive than a longer route.
2. Why is O(2n) treated the same as O(n)?Because it describes how cost grows rather than exact cost, doubling every cost does not change the growth class.
3. How does a hash function turn a word into an array index?A hash function reads the word as bytes, mixes them into one large number, then takes the remainder after dividing by the table size to get an index from zero to size minus one.
4. How can you check whether something is in a set without storing every item?Record a few hashed marks per item in a bitmap; all marks set means probably present, any mark clear means certainly absent.
5. What's the difference between memoized recursion and filling a DP table bottom-up?Memoised recursion keeps the calls and only solves states it reaches; a bottom-up table removes the calls, fills every entry in a dependency-safe order, and is usually faster when most entries are needed.
6. Why can a hash table find something without scanning everything else?A hash table does not search its contents faster. It computes where the item must sit from the key itself, so the number of stored items never enters the calculation.
7. Why can't a hash table give me the next key in order?Because a good hash deliberately scatters neighbouring keys, so the table keeps no record of which key comes after which; finding the next key means reading every entry.
8. Why does a hash table need to grow before it is completely full?Because what makes lookup fast is how full the table is, not how big it is: near full, a lookup turns into a scan well before the last slot is taken.
9. Why does breadth-first search always find the path with the fewest links?Breadth-first search meets points in order of how many links they are from the start, so the first time it reaches a point it has used the fewest possible links.
10. Why do databases use B-trees rather than binary search trees for indexes?Because a database index pays for disk blocks read, not comparisons made, and a wide shallow tree needs only a few block reads per lookup.
11. How does a heap know the smallest item without keeping the whole collection sorted?A heap only keeps each parent no larger than its children, so the top is always the smallest even though the rest is not sorted.
12. How does merge sort get n log n by splitting and merging?Splitting halves the number of runs each round, so there are about log base 2 of n rounds; merging every item once per round gives n log n.
13. Why is merge sort O(n log n) when it keeps splitting the array in half?Splitting in half gives about twenty levels for a million items, and merging at every level still touches all million items, so the total is twenty million rather than a million times a million.
14. How do I know when there is no order that satisfies all the dependencies?If you repeatedly remove anything with nothing still waiting on it and cannot remove everything, the dependencies contain a loop, so no valid order exists.
15. Which grows faster, n log n or n squared?The squared option grows faster: doubling the input multiplies the log-times-linear option by a little over two, but multiplies the squared option by four.
16. Why do nested loops multiply their running times instead of adding them?Because the inner loop runs in full once for every pass of the outer loop, so the cost is one count times the other, not one plus the other.
17. How does binary search find something in a sorted list so fast?Binary search is fast because each comparison halves the remaining sorted range, so a thousand items need about ten probes and a million need about twenty, rather than one probe per item.
18. Why does binary search only work if the list is sorted?Because only in a sorted list does one comparison against the middle tell you that half the items cannot be the one you want.
19. Why does inserting already sorted numbers turn a binary search tree into a linked list?Because each new number is bigger than every number already stored, so it is always attached down the right side, and the tree becomes a chain as deep as the number of items.
20. When is picking the locally best option actually guaranteed to give the best overall answer?Only when a proof shows that some best overall answer can contain the locally best first choice, and the same holds for every later step; otherwise one counterexample can break it.
21. What is memoization and why does caching recursive results make it so much faster?Memoisation stores each answer once and reuses it, so a recursion that repeats the same subproblems stops redoing work and becomes a table lookup instead.
22. How do I find out if a graph is really in two separate pieces?Walk from one point, mark everything you can reach, then start again at any unmarked point; the number of walks is the number of separate pieces.
23. Why is it safe to keep taking the cheapest link that doesn't create a loop?Because the cheapest link joining two separate pieces is the cheapest way across a split, and swapping it into any rival solution cannot raise the total cost.

The other subjects