Algorithmic Problem Solving
This is the strategy to use when you're faced with a new problem that you've never solved before and you're being asked to work through during the interview.Let's look at a step by step approach to solve a new problem so that you feel empowered when you're dealing with the question that you've never thought about before.
Step 1
So the first step is to make sure that you really understand the question.- What the parameters involved?
- What is the goal for the solution?
Your first task is to ask lots of questions. When faced with a hard question, ask as many questions as you can think of to tease out the relevant assumptions that the interviewer has in mind or that might be relevant for your solution to tease out the scope of the problem. Understand what you're trying to analyze and solve.
Step 2
Now once you've asked a lot of questions to make sure that you clarify the problem and know where to go, then the next step is to confirm your understanding by working through an example.Working through an example is really useful because both it lets you get those creative juices flowing and start thinking towards a solution.
It also lets you take some time and think through the problem very concretely about what difficulties might be involved, where are the sticking points of any solution we'd have to solve. And also if there are any hidden assumptions or implicit questions that you might need to address again and go back to that first step of asking more questions to the interviewer to make sure that you've mapped out the scope of the solution that you need to come up with.
Okay, so at this point we have a very good sense of the task at hand and we're ready to solve it.
Step 3
So in the next stage of the strategy we try to come up with a first solution. You want to make sure that at least you got some approach to solving the problem, even if it's not a good approach. This is the brute force approach.You've got some way of tackling it. And this approach does not have to be clever or elegant. But you want to make sure that you've got a correct solution.
Step 4
And so as you're developing this brute force approach as first naive solution to the problem, the next step is to test it. Now, that means testing it with normal input as well as edge cases. Make sure that your brute-force approach can handle both.And then think through a little bit if you were to implement this first solution, how would you do it? What data structures would be useful? How would those data structures interact with the problem that you're working with? In particular, what performance would you get out of this implementation? And any trade-offs that you might be thinking about in terms of maybe using more memory to speed up the performance, or vice verse. So, we've got a solution. But we didn't spend very much time trying to make it clever or elegant.
Step 5
So our next step of the strategy is to iterate this whole process of coming up with a candidate approach to solving the problem. Evaluating, testing and poking at it, making sure that it does what you want it to do or if it doesn't, thinking about ways to fix it and refine your solution as much as you can.And you'll notice when you're in the interview that often, the interviewer will try to guide you towards iterating your solution, asking you if it could be made better, asking you if there are any trade-offs that have in mind. And you want to think through this checklist of how you evaluate your strategy at each stage of the problem solving process.
Now when we iterate, we come up with a great solution, that we think at the high level will do a pretty good job. We've done an asymptotic analysis. We have a sense of how long asymptotically, so in the Big O notation each of the operations involved will take.
Step 6
Finally in Step 6 of our strategy, we finally write some code. And so only once we've done this very thorough analysis of the problem, you have a very good sense of what you want to implement, now you can start writing some code on the whiteboard.Programming on a white board in the interview situation is quite different from typing it out in a computer. It's a good idea to practice on whiteboard during preparation.
