MEPX
Chapter 9 of 10All chapters
  1. 1Why structure matters
  2. 2Arrays and lists
  3. 3Stacks and queues
  4. 4Hash maps and sets
  5. 5Trees
  6. 6Graphs
  7. 7Sorting and searching
  8. 8Recursion
  9. 9Algorithm strategies
  10. 10In practice

Chapter 9 of 10

Algorithm strategies

Greedy, divide and conquer, dynamic programming.

Three approaches

Greedy takes the best immediate step and is fast but only sometimes correct. Divide and conquer splits, solves and combines. Dynamic programming builds up answers to overlapping subproblems.

  • Greedy works when a local best is provably part of a global best.
  • Dynamic programming applies when subproblems repeat, which is what memoisation exploits.

Recognising the shape

Most interview problems are one of a dozen shapes: two pointers, sliding window, hash map counting, graph traversal, or a dynamic programming table. Recognising the shape is most of the work.