Understand the problem
- Make sure the problem is well defined and understood. Try to rephrase the problem in different ways to double verify the understanding is correct.
- Understand the constraints and optimization goals of the expected solution. There will be many conflicting dimensions of a solution (e.g. performance, security, scalability ... etc), knowing what can be traded off is important.
- While you are thinking about the solution, try to make it visual. e.g. Sketch the solution on a whiteboard to help you think.
- See if you can solve the problem by using a simple-minded, brute force search. Try all the possible combinations of solution to determine which one works. But get a sense of the BigO complexity analysis to judge whether the brute-force approach is feasible.
- See if you translate the problem into a search problem. Then you can utilize existing search algorithm (e.g. hill climbing, A*, BFS, DFS ... etc) to help.
- By exploit the nature of the problem, see if you can define your solution recursively. Assume that you already have a solution with the problem of the smaller size, can you use that to construct the current solution. e.g. Can you define F(n) based on F(n-1), F(n-2) .... etc. And also try to see if you can translate the recursive solution into an iterative one.
- At this point, you may have found multiple solutions. Do a BigO analysis in both time and space and pick the one that aligns with your optimization goal.
- Walk through some simple examples to test out your solution, include some boundary cases in the examples to see how your solution handle those corner cases.
- Prototype your solution. Define some measurement and instrument your prototype. Run it and compare the result with what you expect.