99. Classic Problems

This chapter tries to answer the question:

If you only have three days to prepare an interview, what problems are you gonna to practice?

A problem is classic not because it is hard to solve, but because:

• it represents a type of classic algorithm, or something you can find at the beginning of each chapter of a classic algorithm textbook, e.g. merge sort for divide and conquer, coin changes problem for dynamic programming, course schedule for topological sort, etc.

• a good solution involves using several basic data structure so that by solving one problem, people can review several data structures.

• the brute force solution is straightforward, but a much more efficient solution can be built by finding the pattern of the input/output, and such pattern is not too difficult to find (otherwise, the problem may not be solved in 30-40 mins)