Key Algorithms for Coding Interviews

What's up everybody, how's it going? In this video, I'm going to be covering 10 super important algorithms, data structures, and general topics or concepts that you need to know for coding interviews. Now two little caveats. The first one is that I'm going to be going through them pretty quickly. This video is not meant to teach you these topics, just to tell you about them. And secondly, these are not the 10 only things that you need to know for coding interviews. There's a lot more that you could know. These are just the 10 most important ones in my opinion. If you want to know everything there is to know about coding interviews and if you want to practice, which you should if you're trying to land a job as a software engineer, then definitely check out my company AlgoExpert. We've helped over 70,000 engineers prepare for their technical interviews. Go to algoexpert.io and use the promo code Clem, C-L-E-M, for a discount on the platform. Last thing before I jump into the first topic, I'm trying to grow my Instagram. I've been pretty bad at posting recently, but I just posted a new picture and I'm going to try posting a lot more pictures. of just my general life, not necessarily related to coding or software engineering, all sorts of things lifting my general life behind the scenes. So if you're interested in that, go check it out. Clement underscore Mihailescu. The link is in the description below. And now let's jump into the first thing that you absolutely need to understand really well for coding interviews, which is the logarithm, the math concept. It's probably the only real math concept that you need for coding interviews, but it is imperative that you understand how the logarithm works. You have to appreciate why a logarithmic time operation or algorithm is so much faster and therefore better than a linear time algorithm or operation. We have a free video about the logarithm on our Data Structures Crash Course on AlgoExpert. It's about 15 or 20 minutes. I think that I explained the concept pretty well there. Definitely go check it out. Once you understand the logarithm, you will do much better in your complexity analysis and coding interviews and therefore in your entire coding interviews. Now the second topic that is super important to master for coding interviews is graph traversal. And when I say graph traversal, I'm also talking about tree traversal, matrix traversal, because matrices are basically kind of like graphs in a way. You have to know how to do depth-first search, breadth-first search. I hate these two words, DFS, BFS. You have to know how to traverse through cyclic graphs. So you have to know how to keep track of visited nodes in some sort of auxiliary data structure. Super important. Most on-site interviews will have at least one interview that consists of a graph problem where you're going to have to traverse a graph. So definitely make sure that you're comfortable with graph traversal. Now, the third thing that you need to know for coding interviews, this is a specific algorithm, it's binary search. Binary search is a pretty easy algorithm. Most people learn it either at the beginning of their coding boot camp or in their intro algorithms class in college. It's a pretty easy algorithm, but most people, at least I know I did, take it for granted. and then kind of forget about it. And then they just stop using it and they resort to linear search. And this one ties back to the first point, the logarithm. Binary search is way, way, way, way, way better than linear search. Like so much better because it runs in log event time. And in a lot of coding interviews, you will have a difficult problem that involves binary search in the solution. Like a sub-problem of the greater problem will need binary search because you'll be repeatedly searching through sorted values, for example, and you'll want to use binary search. So be comfortable with binary search, be comfortable implementing it, be comfortable knowing when to use it when there's basically sorted values, and it's going to really help you a lot. The fourth concept that's very important for coding interviews is the sliding window technique. Now the sliding window technique is something that involves manipulating two pointers or two indices at the same time. as you're traversing through something like a string or an array. Basically, you've got a left pointer or left index, a right pointer, right index, and you move them simultaneously in an array or a string, usually to count frequencies of maybe characters or maybe to count the sums of subarrays in an array where you can add the number on the right and then subtract the number on the left. You can see how it's useful. And then sometimes you'll need to expand the window on the right and shrink it on the left. or other times you'll have variations where you're iterating through a data structure and then you are creating the two pointers and expanding them both at the same time outwards like in the longest palindromic substring problem. The point is being able to comfortably manipulate two pointers at the same time and traverse a data structure can be very useful. A lot of problems have that as a solution and so you want to be comfortable with it. The fifth topic that's super important for coding interviews is recursion. Now, recursion is useful for two reasons. First of all, really understanding recursion and being comfortable with recursion and solving things recursively is just very good from a logic perspective. Like it teaches you logic. It really makes sure that you understand how functions work, how function calls work, you know, what's returned from functions, all that good stuff. But then also there are a lot of problems that can be solved recursively much more easily than iteratively. Like implementing them recursively is just much easier. The code is much cleaner, much less code than their iterative counterparts. A good example is you know, in-order traversal of a tree. We have a problem on AlgoExpert that's a very hard problem, or a hard problem I forget, called iterative in-order traversal. And the reason it's hard is because traversing a tree in order iteratively is pretty difficult to implement, at least in code, whereas recursively it's pretty trivial. So if you're really good at recursion and you understand it well, then you're going to be able to solve certain problems in coding interviews much more easily than if you go down the iterative path. and you want to be able to have that ability. So definitely make sure your recursion is up to par. There are a lot of classic, pretty easy problems that just make sure you understand recursion really well, like Fibonacci or calculating the height of a binary tree or the depths of nodes in a binary tree. Just go do all those practice problems. It's really going to help you a lot. Okay, number six. Here I'm going to cheat a little bit and give you two algorithms that you want to know for coding interviews, inverting a binary tree and reversing a linked list. Now, hear me out. I know that these two algorithms are basically memes at this point. I have contributed, or rather Algoexpert has contributed, to perpetuating the memishness of these two algorithms because we use them in our ads on YouTube. But the reason it's important to know how to do these two things well is for inverting a binary tree, it's important because it's just a very easy problem. Like so many people make it sound like inverting a binary tree is super difficult. It's not. It's a very easy problem. It just comes down to traversing a tree and swapping values. Like, it's just very easy. If you're intimidated by inverting a binary tree, you probably just have a misconception of what it is to invert a binary tree. Go check out the problem on AlgoExpert. It's really easy, and it'll just give you confidence that it's an easy problem. Now, reversing a linked list is a little bit different. The reason it's important to know how to do that is because I think we can all agree that linked lists are an important data structure. They allow you to do operations much faster, or certain operations much faster than with arrays. and you're likely going to face a linked list problem in a coding interview. But if you've done a lot of linked list problems, like all the ones on AlgoExpert, you've probably noticed that linked list problems tend not to be too difficult algorithmically. It's just like the same thing every time, like shifting values in a linked list or rearranging a linked list. And if you know how to reverse a linked list, you probably will know how to do most other manipulations in a linked list that you could face in an interview, because it's basically the same thing. just knowing how to manipulate nodes in a linked list, knowing how to overwrite pointers, making sure to do so in a specific order such that you don't lose reference to nodes in the linked list, and voila. So know how to reverse a linked list and you will be great for most linked list problems. Number seven, suffix trees. So suffix trees are a pretty advanced data structure. They're a relatively complicated data structure, but the thing that I want to impart you with here is You can create a data structure that looks similar to a suffix tree just with objects like JavaScript objects or Python dictionaries very easily and it's a very powerful data structure that can help you especially with string problems. When you are trying to find whether a bunch of strings are contained in another string and you want to do so quickly, rather than iterating through all the strings and doing a bunch of you know substring matching and all that, creating a suffix tree or a tree-like structure that contains the strings in them is going to be much better. It'll be a much quicker solution, and it's going to impress your interviewers because it tends to be a pretty advanced data structure. So be comfortable with suffix trees. We've got a few problems about them on AlgoExpert. And let's move on to number eight, heaps. Heaps are another relatively advanced data structure, although not really because ultimately when we're talking about heaps in the context of coding interviews, usually we talk about binary creeps, creeps, binary creeps, binary heaps. which are basically like binary trees. And usually we're talking about minheaps or maxheaps that have a special property. And here again, we go back to that logarithm thing that we talked about in point number one. The reason heaps are super useful is because they have this logarithmic time operation to find the minimum value in the minheap or the maximum value in the maxheap. Being comfortable with heaps, really understanding how they work is going to help you a lot for all the problems where you have to repeatedly find the smallest or the largest values in groups of values. And I think that going through constructing a min heap or a max heap can be very empowering because it really shows you how the data structure works, how you can represent it very simply and elegantly within an array. And yeah, just make sure you know heaps. They will help you a lot in tough interview problems. Number nine, dynamic programming. A lot of the hardest coding interview problems that you're going to encounter can be solved with dynamic programming. Dynamic programming is this fancy term for really just being able to solve a problem that is pretty complex by first solving a smaller version of that problem. And to solve that smaller version of that problem, you solve an even smaller version of that problem all the way up until you can solve a trivial version of the problem. If you become comfortable with dynamic programming by doing a lot of such problems, a lot of dynamic programming problems, you will be super well equipped for these difficult problems. And yeah, it's a very useful tool. You got to know it for coding interviews. And in my opinion, Dynamic programming is one of those topics where practice really does make perfect. The best way to get good at dynamic programming is to do a lot of dynamic programming problems, which is why we have a lot on AlgoExpert. The tenth and final topic that I think is very important to know for coding interviews is sorting algorithms. Specifically, I'm going to go with quicksort and merge sort. All the sorting algorithms are important to understand, but I think quicksort and merge sort are really the two very famous and popular fast sorting algorithms. Heapsort is just, I don't know, screw Heapsort. But QuickSort and MergeSort, they're very important. The reason they're important is not so much that you're going to get asked to implement them, although you can. I remember at Two Sigma, the hedge fund in New York, I was asked, I think, to implement QuickSort, which is a bit of a weird question. I don't think that a company like Google would ask you that. But it's important to understand them because once you understand them, you truly understand why they run in n log n time, and you really understand why they're so much better than BubbleSort. And If you understand how they work fundamentally, it's hard to forget them. Like a lot of people say like, oh, you know, I haven't written Quicksort in so long, so I've forgotten how to do it. But if you understand how Quicksort works, you know, that you choose a pivot and that with the pivot, you just swap elements that are smaller to the left of the pivot and bigger to the right of the pivot, then you're able to reimplement it yourself pretty easily, even if you haven't done so in a super long time. So trying to understand the two algorithms, very helpful in my opinion. very empowering and it'll make you not like feel anxious about potentially not knowing them in a coding interview because you'll just be able to derive them on the spot. And on top of that, quick sort is particularly helpful because of quick select, which is a sort of variation of quick sort for searching for certain values, like searching for the kth smallest or largest value in an array. And if you know quick sort, if you know how quick sort works and you know how to reimplement quick sort because you can derive it, then you can implement quick select. which can be helpful in those types of problems, searching for the case smallest or largest value. So with that, these were my 10 top topics that I think you need to know. Like I said, I went through them pretty quickly. If you don't know any of these things right now, then you definitely need to practice and learn them. AlgoExpert is a great tool for you. Definitely check it out. Otherwise, if you found this video helpful, don't forget to smash the like button. It really helps me out. Subscribe to the channel if you haven't already. Follow me on LinkedIn and Twitter if you enjoy short form written content. Instagram if you like pictures, and I will see you. in the next video.

The first one is that I'm going to be going through them pretty quickly. This video is not meant to teach you these topics, just to tell you about them. And secondly, these are not the 10 only things that you need to know for coding interviews.

There's a lot more that you could know. These are just the 10 most important ones in my opinion. If you want to know everything there is to know about coding interviews and if you want to practice, which you should if you're trying to land a job as a software engineer, then definitely check out my company AlgoExpert.

We've helped over 70,000 engineers prepare for their technical interviews. Go to algoexpert.io and use the promo code Clem, C-L-E-M, for a discount on the platform. Last thing before I jump into the first topic, I'm trying to grow my Instagram.

I've been pretty bad at posting recently, but I just posted a new picture and I'm going to try posting a lot more pictures. of just my general life, not necessarily related to coding or software engineering, all sorts of things lifting my general life behind the scenes. So if you're interested in that, go check it out. Clement underscore Mihailescu.

The link is in the description below. And now let's jump into the first thing that you absolutely need to understand really well for coding interviews, which is the logarithm, the math concept. It's probably the only real math concept that you need for coding interviews, but it is imperative that you understand how the logarithm works. You have to appreciate why a logarithmic time operation or algorithm is so much faster and therefore better than a linear time algorithm or operation. We have a free video about the logarithm on our Data Structures Crash Course on AlgoExpert.

It's about 15 or 20 minutes. I think that I explained the concept pretty well there. Definitely go check it out.

Once you understand the logarithm, you will do much better in your complexity analysis and coding interviews and therefore in your entire coding interviews. Now the second topic that is super important to master for coding interviews is graph traversal. And when I say graph traversal, I'm also talking about tree traversal, matrix traversal, because matrices are basically kind of like graphs in a way.

You have to know how to do depth-first search, breadth-first search. I hate these two words, DFS, BFS. You have to know how to traverse through cyclic graphs.

So you have to know how to keep track of visited nodes in some sort of auxiliary data structure. Super important. Most on-site interviews will have at least one interview that consists of a graph problem where you're going to have to traverse a graph.

So definitely make sure that you're comfortable with graph traversal. Now, the third thing that you need to know for coding interviews, this is a specific algorithm, it's binary search. Binary search is a pretty easy algorithm.

Most people learn it either at the beginning of their coding boot camp or in their intro algorithms class in college. It's a pretty easy algorithm, but most people, at least I know I did, take it for granted. and then kind of forget about it.

And then they just stop using it and they resort to linear search. And this one ties back to the first point, the logarithm. Binary search is way, way, way, way, way better than linear search.

Like so much better because it runs in log event time. And in a lot of coding interviews, you will have a difficult problem that involves binary search in the solution. Like a sub-problem of the greater problem will need binary search because you'll be repeatedly searching through sorted values, for example, and you'll want to use binary search.

So be comfortable with binary search, be comfortable implementing it, be comfortable knowing when to use it when there's basically sorted values, and it's going to really help you a lot. The fourth concept that's very important for coding interviews is the sliding window technique. Now the sliding window technique is something that involves manipulating two pointers or two indices at the same time. as you're traversing through something like a string or an array.

Basically, you've got a left pointer or left index, a right pointer, right index, and you move them simultaneously in an array or a string, usually to count frequencies of maybe characters or maybe to count the sums of subarrays in an array where you can add the number on the right and then subtract the number on the left. You can see how it's useful. And then sometimes you'll need to expand the window on the right and shrink it on the left. or other times you'll have variations where you're iterating through a data structure and then you are creating the two pointers and expanding them both at the same time outwards like in the longest palindromic substring problem. The point is being able to comfortably manipulate two pointers at the same time and traverse a data structure can be very useful.

A lot of problems have that as a solution and so you want to be comfortable with it. The fifth topic that's super important for coding interviews is recursion. Now, recursion is useful for two reasons.

First of all, really understanding recursion and being comfortable with recursion and solving things recursively is just very good from a logic perspective. Like it teaches you logic. It really makes sure that you understand how functions work, how function calls work, you know, what's returned from functions, all that good stuff.

But then also there are a lot of problems that can be solved recursively much more easily than iteratively. Like implementing them recursively is just much easier. The code is much cleaner, much less code than their iterative counterparts.

A good example is you know, in-order traversal of a tree. We have a problem on AlgoExpert that's a very hard problem, or a hard problem I forget, called iterative in-order traversal. And the reason it's hard is because traversing a tree in order iteratively is pretty difficult to implement, at least in code, whereas recursively it's pretty trivial.

So if you're really good at recursion and you understand it well, then you're going to be able to solve certain problems in coding interviews much more easily than if you go down the iterative path. and you want to be able to have that ability. So definitely make sure your recursion is up to par. There are a lot of classic, pretty easy problems that just make sure you understand recursion really well, like Fibonacci or calculating the height of a binary tree or the depths of nodes in a binary tree.

Just go do all those practice problems. It's really going to help you a lot. Okay, number six. Here I'm going to cheat a little bit and give you two algorithms that you want to know for coding interviews, inverting a binary tree and reversing a linked list. Now, hear me out.

I know that these two algorithms are basically memes at this point. I have contributed, or rather Algoexpert has contributed, to perpetuating the memishness of these two algorithms because we use them in our ads on YouTube. But the reason it's important to know how to do these two things well is for inverting a binary tree, it's important because it's just a very easy problem.

Like so many people make it sound like inverting a binary tree is super difficult. It's not. It's a very easy problem. It just comes down to traversing a tree and swapping values. Like, it's just very easy.

If you're intimidated by inverting a binary tree, you probably just have a misconception of what it is to invert a binary tree. Go check out the problem on AlgoExpert. It's really easy, and it'll just give you confidence that it's an easy problem. Now, reversing a linked list is a little bit different. The reason it's important to know how to do that is because I think we can all agree that linked lists are an important data structure.

They allow you to do operations much faster, or certain operations much faster than with arrays. and you're likely going to face a linked list problem in a coding interview. But if you've done a lot of linked list problems, like all the ones on AlgoExpert, you've probably noticed that linked list problems tend not to be too difficult algorithmically. It's just like the same thing every time, like shifting values in a linked list or rearranging a linked list.

And if you know how to reverse a linked list, you probably will know how to do most other manipulations in a linked list that you could face in an interview, because it's basically the same thing. just knowing how to manipulate nodes in a linked list, knowing how to overwrite pointers, making sure to do so in a specific order such that you don't lose reference to nodes in the linked list, and voila. So know how to reverse a linked list and you will be great for most linked list problems.

Number seven, suffix trees. So suffix trees are a pretty advanced data structure. They're a relatively complicated data structure, but the thing that I want to impart you with here is You can create a data structure that looks similar to a suffix tree just with objects like JavaScript objects or Python dictionaries very easily and it's a very powerful data structure that can help you especially with string problems.

When you are trying to find whether a bunch of strings are contained in another string and you want to do so quickly, rather than iterating through all the strings and doing a bunch of you know substring matching and all that, creating a suffix tree or a tree-like structure that contains the strings in them is going to be much better. It'll be a much quicker solution, and it's going to impress your interviewers because it tends to be a pretty advanced data structure. So be comfortable with suffix trees.

We've got a few problems about them on AlgoExpert. And let's move on to number eight, heaps. Heaps are another relatively advanced data structure, although not really because ultimately when we're talking about heaps in the context of coding interviews, usually we talk about binary creeps, creeps, binary creeps, binary heaps.

which are basically like binary trees. And usually we're talking about minheaps or maxheaps that have a special property. And here again, we go back to that logarithm thing that we talked about in point number one.

The reason heaps are super useful is because they have this logarithmic time operation to find the minimum value in the minheap or the maximum value in the maxheap. Being comfortable with heaps, really understanding how they work is going to help you a lot for all the problems where you have to repeatedly find the smallest or the largest values in groups of values. And I think that going through constructing a min heap or a max heap can be very empowering because it really shows you how the data structure works, how you can represent it very simply and elegantly within an array. And yeah, just make sure you know heaps.

They will help you a lot in tough interview problems. Number nine, dynamic programming. A lot of the hardest coding interview problems that you're going to encounter can be solved with dynamic programming. Dynamic programming is this fancy term for really just being able to solve a problem that is pretty complex by first solving a smaller version of that problem. And to solve that smaller version of that problem, you solve an even smaller version of that problem all the way up until you can solve a trivial version of the problem.

If you become comfortable with dynamic programming by doing a lot of such problems, a lot of dynamic programming problems, you will be super well equipped for these difficult problems. And yeah, it's a very useful tool. You got to know it for coding interviews.

And in my opinion, Dynamic programming is one of those topics where practice really does make perfect. The best way to get good at dynamic programming is to do a lot of dynamic programming problems, which is why we have a lot on AlgoExpert. The tenth and final topic that I think is very important to know for coding interviews is sorting algorithms.

Specifically, I'm going to go with quicksort and merge sort. All the sorting algorithms are important to understand, but I think quicksort and merge sort are really the two very famous and popular fast sorting algorithms. Heapsort is just, I don't know, screw Heapsort.

But QuickSort and MergeSort, they're very important. The reason they're important is not so much that you're going to get asked to implement them, although you can. I remember at Two Sigma, the hedge fund in New York, I was asked, I think, to implement QuickSort, which is a bit of a weird question. I don't think that a company like Google would ask you that. But it's important to understand them because once you understand them, you truly understand why they run in n log n time, and you really understand why they're so much better than BubbleSort.

And If you understand how they work fundamentally, it's hard to forget them. Like a lot of people say like, oh, you know, I haven't written Quicksort in so long, so I've forgotten how to do it. But if you understand how Quicksort works, you know, that you choose a pivot and that with the pivot, you just swap elements that are smaller to the left of the pivot and bigger to the right of the pivot, then you're able to reimplement it yourself pretty easily, even if you haven't done so in a super long time. So trying to understand the two algorithms, very helpful in my opinion.

very empowering and it'll make you not like feel anxious about potentially not knowing them in a coding interview because you'll just be able to derive them on the spot. And on top of that, quick sort is particularly helpful because of quick select, which is a sort of variation of quick sort for searching for certain values, like searching for the kth smallest or largest value in an array. And if you know quick sort, if you know how quick sort works and you know how to reimplement quick sort because you can derive it, then you can implement quick select.

which can be helpful in those types of problems, searching for the case smallest or largest value. So with that, these were my 10 top topics that I think you need to know. Like I said, I went through them pretty quickly.

If you don't know any of these things right now, then you definitely need to practice and learn them. AlgoExpert is a great tool for you. Definitely check it out. Otherwise, if you found this video helpful, don't forget to smash the like button.

It really helps me out. Subscribe to the channel if you haven't already. Follow me on LinkedIn and Twitter if you enjoy short form written content. Instagram if you like pictures, and I will see you. in the next video.

Transcript for:Key Algorithms for Coding Interviews

Transcript for:
Key Algorithms for Coding Interviews