[MUSIC] So this week we're talking about Algorithmic Problem Solving. And this is the strategy that you want to have 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. So what we'll be doing in this video is talking about a step by step approach to starting to solve such a problem so that you feel empowered when you're dealing with the question that you've never thought about before. So the first thing that you want to do when you're asked a question is to make sure that you really understand what's being asked. What the parameters involved are and what the goal for the solution would be. And so your first task is to ask lots more 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 that's being asked. And to try to understand what it is that you're trying to analyze and to solve. Now once you've asked a lot of questions to make sure that you clarify the problem and know where to go, what you should do is confirm your understanding by working through an example. And working through an example is really useful because both it lets you get those creative juices flowing and start thinking towards a solution. But 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 of the interview to really 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. So in the next stage of the strategy we just try to come up with a first solution. You want to make sure that at least you got some approach to solving the problem that's being solved. So, at least even if it's not a good approach you've been able to do what's asked of you. And so we call this the brute force approach. You take a hammer and you hit the problem with it. You make sure that you can nail that problem down. You've got some way of tackling it. And this approach does not need to be clever. It doesn't need to be elegant, but you want to make sure that you've got a correct solution. And so as you're developing this brute force approach as first naive solution to the problem, what you want to do is test it. Now, that means testing it with normal input, what you'd expect the problem to have to handle. But also with 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 would 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. 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 it, testing it, 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 really try and nail down as good a solution as we 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 are 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 we iterate, we iterate, we come up with a great solution, that we think at the high level we'll do a pretty good job. We've done an asymptotic analysis. We have a sense of how long asymptotically, so in the go notation each of the operations involved were take. And 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, I have a very good sense of what we want to implement, now you can start writing some code on the whiteboard. Now in the rest of the week what we'll be doing is taking this strategy and applying it two concrete examples of questions that you might be asked in an interview and then we'll also be talking about, how to do this programming on a white board in the interview situation which is really quite different from typing it out in a computer and so that's coming up next.
