What's up everyone Sam here from byte-by-byte.com. Today I want to tell you about an exercise that you can be doing that's going to increase your creativity in your interviews, so that you never end up solving the wrong solution and getting rejected because you didn't come up with the most optimal solution in your interview. So stay tuned for that.
Alright today we're talking about this exercise that you can do to increase your creativity, and this is a quick one that you can do whenever you're practicing. So you should just include this in your existing practice routine. The idea here is that before you start coding up a problem, you're actually going to take about 15 minutes to brainstorm every possible solution that you can come up with for a given problem. And by doing this we're getting rid of the idea that we have to start with the perfect solution, and we have to come up with exactly the answer that our interviewer is gonna want right off the bat. Because that's not a realistic thing. Our interviewer is not expecting us to come up with the perfect solution right away. And having that mentality can totally screw us up in our interview.
So what we're going to do is we're gonna take a problem whether we're on Leet Code or Cracking the Coding Interview or one of the problems on Byte-by-Byte.com, and just spend about 15 minutes going through the problem and trying to come up with every possible solution that you can come up with. It doesn't matter how crazy the solution is. It just has to work. And to give you guys an example of this let's consider a problem that I like to use which is printing out a linked list in reverse order.
So there's a very simple problem there are a lot of ways that we can do this. We could reverse the linked list and print it out, we just iterate over it and print out the items. We could do it recursively. We could recursively go to the end of the list and then print the items out as we return backwards. We could add the items to a stack. We could iterate over the list where we're gonna iterate all the way to the end and then iterate again to the N minus 1th item and then the N minus 2th item and third item and fourth and fifth and six until we get back to the front of the list and then we've printed them in reverse order. We could do something completely different. Maybe we have, maybe we could add everything to a tree and then iterate the tree in order. It seems like a stupid solution but it would work. Right? As long as we maintain that order. And so we could go through this and continue to write down all these solutions. And then the following step is just that we're gonna evaluate all these solutions. So I want you to write down all these solutions.
You should be having a piece of paper in front of you when you're practicing anyway because you really should be practicing on a piece of paper. And just write down all these possible solutions and then go through what is the time complexity and what is the space complexity. Once you do that all you have to do is say well which of these solutions is the best one? Right? It's not that hard to figure out once you look at the space complexity and the time complexity, which solution is the optimal solution. And then you can start actually coding that up. But take the time to really think and really brainstorm even the most wild ideas. And you're not going to have to do this once you get to your interview as long as you practice. Because you're gonna build up that creativity muscle and these ideas are gonna come to you more clearly. So that once you're in your interview you have a good idea of what the sorts of possibilities are that are available to you. What sorts of things are gonna work and what sorts of things might not work. And then all you have to do is consider a couple possibilities, figure out what a brute force solution is just to be safe so that you have a back-up plan. Go through a couple possibilities. Figure out the one with the best space complexity and the best time complexity, and then code it up. So for the example of our reverse printing a linked list in reverse order, we had sort of two solutions or three solutions that were fairly comparable.
If we reverse the linked list that's going to take O of one space complexity and O of n time complexity. Because it doesn't take us any space to reverse the link list. And it takes us O of N time to reverse it, and then it takes us O of N time to iterate over the list. And so that's gonna be the best solution that we have in terms of time and space complexity, but it has the downside of us we're having to reverse the linked list, and modify the input. Which we may not be allowed to do depending on the situation. So let's consider that would be our best possibility if we can modify the input, but then if we can't modify the input what is our best option?
Well if we did it recursively that's going to take O of N space, because we have our recursive stack and then it's gonna take O of N time, because it's gonna have to iterate over all the elements. Or we could add elements to a stack manually, or an array manually, and then iterate over it. Which is also going to take O of N time and O of N space. So we can really choose in this case from any of those possibilities because they're all going to be good options. And now we can we have clearly evaluated what are going to be the best solutions for this problem, and we know how to proceed.
So that's all I got for you today. And if you enjoyed this video please like and subscribe below. And also head over to www.DynamicProgrammingBook.com and you can download my free e-book on dynamic programming. We've had about 3,000 people go through this book and everyone really seems to love it. And I think it's gonna make a huge difference for you if you're struggling at all with dynamic programming. So definitely check it out, and I look forward to talking with you guys again soon.