- Massage the problem: Yes, you read it right. If you’re unable to find a solution, take different examples and try solving them manually. Solve how a human would solve them. After a couple of examples, a pattern might emerge.
- Draw out examples: For Tree or Graph problems, it’s pretty easy to draw examples. For others, list sample inputs on the whiteboard, don’t just mention them. Draw an array. Walk through examples and see what the output should be. Verify with the interviewer.
- Ask the interviewer questions: This is crucial before you start brainstorming solutions. When you walk through the examples above, clarify things like:
- Is the array sorted?
- Is the graph directed?
- Can the graph have cycles?
- Can the input array be empty?
- Is the Tree a Binary Search Tree or a Binary Tree?
- And of course, more specific questions relevant to the problem.
- Consider several test cases: Don’t just consider one case. Consider edge cases, base cases, and odd cases. For example, let’s say you are given a binary tree problem. Consider the following cases:
- The tree has one node only,
- Node has a right child only,
- Node has a left child only,
- Node has both children, etc.
- See if a Data Structure fits the problem: Many questions are made with certain data structures in mind. For example, in many array and string problems, we need to repeatedly search for items. A hash table should come to mind immediately.
Or, many problems have graph-like relationships, with nodes and neighbors. For example, the famous Word Ladder problem treats a word as a node and adjacent words as neighbors.
- See if an Algorithm fits the problem: Many problems are designed with well-known algorithms in mind. In the Word Ladder example above, you can categorize it as a BFS or DFS problem when you visualize it as a graph.
- Try to extract the core problem: Beneath all the fluff, several problems boil down to one core problem.
- In Word Ladder, the core problem was graph search.
- In the famous Single Stock Trade Problem, the core problem is finding the maximum difference between two numbers such that the second number is ahead of the first.
- Try breaking it down into subproblems: If you knew the solution to a sub-problem, could you get the solution of a larger problem?
- In many Binary Tree problems, if you know the solutions for the left and right subtrees, you can find the solution for their parent node.
- Dynamic programming is completely based on the concept of building solutions from smaller subproblems.
- Don’t be scared of brute force solutions: Better something than nothing. Many candidates like to start by considering a brute-force solution and then thinking of improvements.
- Look for improvements in your algorithm: For example:
- Are you doing an O(n) lookup that can be sped up by using a hash table?
- Are you repeating recursive calls which can be memoized to improve performance?
- Are you initializing O(n^2) memory, when you only need O(n)?
Keep in mind that solving these problems is a skill. You will get better with practice.
Our original answer on Quora