1. Ask for constraints and additional information

• Can there be floating point numbers or only integers?
• Can there be negative numbers? Zero?
• Are the numbers guaranteed to be sorted?
• Are there repeated elements?

2. Solve an instance of the problem manually

• The instance should be small enough to be solved manually, and big enough to see any patterns
• The instance should not be a special case
• This makes sure that you understand the question

3. Think about a brute force solution, if applicable

• Determine its time and space complexity

4. Gather ideas

• List everyting you know
• Are there any rules and patterns?
• Consider recursion
  • Top-down: can the problem for $n$ be trivially solved when the solution for $n-1$ is known?
  • Bottom-up: start with a base case; if you know the solution for $n=1$, can you solve the problem for $n=2$? If you know the solution for $n$, can you solve the problem for $n+1$?

5. Optimise the current solution

• Look for BUD (Bottlenecks, Unnecessary Work, Duplicated Work)
• Solve an instance of the problem manually and “reverse engineer” the intuitive manual approach
• Consider different data structures and algorithms
  • E.g. hash table ($\text{O}(1)$ insert and delete), binary search ($\text{O}(\text{log}\,n)$), sorting ($\text{O}(n\,\text{log}\,n)$, etc.
• Goal: optimise time and space complexity by considering time vs. space tradeoffs
• Run new solution through some small test cases to confirm that it works

6. Implement the solution

• Start with main method name, parameters, and return value
• Write modularised code, not plain code
  • That means, use method invocations instead of lengthy in-place code; you can implement the helper method later
• If necessary, use TODO comments

7. Test the implementation

• Run the implementation through small test cases
• Include edge cases: zero, negative numbers, empty string, empty list, etc.
• If you find a bug, fix it init in the code

Cheatsheet

PDF version Source: crackingthecodinginterview.com

Algorithm Design Canvas

A generic approach for solving any algorithm design question, as proposed by HiredInTech.

PDF version Source: hiredintech.com