This is a quick and dirty list of all the stuff you should know before you walk into an interview for a big name tech company. This will not cover any software topics, only computer science topics. This will help you in the coding portion of interviews, not in design portions.
ℹ️ - Use the language you are most familiar with for any of this content. Don't use a language you don't use everyday, or it will show. "...how do you truncate an array again?" Remember that a lot of interviewers expect you to code on a whiteboard. There will be no autocomplete or google to help you if you forget the name of a function. At the very least, you should have written code to do these things at least once. Ideally, you could do each without a reference.
ℹ️ - hashtables are basically the answer to every code question, so you better know this. It should be your first thought when you start a question. "I wonder if I could use a hashtable for this?" If not, good, no harm done. But if the problem could have been solved with a hashtable, and you didn't think of that, the interviewer will notice.
For quick sort and merge sort:
You might also want to know how to implement:
* consider studying the linked list section before attempting this section if you have extra time.
Recursion is useful, and you might surprise your interviewer if you get stuck on a recursion problem.
The priority queue is an awesome data structure. At the very least, know this exists. It depends on a data structure called a heap, but if you don't want to learn that, then just assume that it's some black magic that is yours to abuse to your heart's content.
For all of the above, you should be able to reason about time complexity.
ℹ️ - The rest I would not consider "need to know", because they are usually implemented for you. But basic linear/logn searches and graph traversal are a must. If not simply because they're like the abcs of computing, and you don't want to look illiterate.
what is a heap and why is it useful?
how do you:
you should practice implementing these functions that heaps depend on:
Ideally you've implemented a binary search tree at least once. Even better if you've implemented balanced ones. At any rate, it might help to know what:
Read about the bst, and maybe be able to speak to some degree about how you can define its height, number of levels, or number of nodes in terms of powers of two or logs of two. Are these properties useful at all? How?
What data structure does a bst with only left children and no right children look like?
If you went to uni, then these concepts are generally considered in the 200 level in the states. So, you should probably know them if you went to uni for computer science.
ℹ️ - This is first on this list for a reason. You will definitely surprise your interviewer if you don't how to use generics. The caveat is that if you mostly work in a language like python or javascript, you would have never encountered this concept. But if you say you know Java and you can't use generics then this will raise alarms to your interviewer.
you should understand:
Someone wrote this List class without knowing what type of data you were going to put into it. That's because it doesn't matter. The operations for adding an int to a list are the exact same as they are for adding a string to a list. That means they can defer assigning types to its contents until the exact moment you need to use it. Instead of writing one class for each data type we want to contain, we only need one generic class. This becomes insanely powerful as the number of types you want to parameterize increases.
For instance, consider Java's Dictionary<TKey, TValue> class, which means you now have the square of the number of types in Java combinations that you don't have to write classes for. You can just use the one generic class, instead.
What are pointers and references? You should read about them and obtain a rudimentary understanding. They are very important, but usually you don't notice they exist unless you're programming at a very low-level language.
ℹ️ - In the context of programming languages, low-level means you're closer to writing 1's and 0's, whereas high-level means you're closer to writing English.
for what it's worth, if you're new to this, linked lists are hard. They seem super simple when you draw pictures of them, until you're doing stuff like:
What does this function do? Despite appearing to simply set a bunch of variables to references of themselves in a random order, this function will actually reverse a linked-list. Doesn't seem so simple.
No interviewer will ever directly ask you a question about a linked list, and you could probably derive any of these during any interview, but if you have extra time to waste learning this, it will be good for you. Maybe even learn this first, because it might help you with the graph stuff.
know some basic terminology about graphs (if you did the graph traversal section, you should have encountered these) and their implications:
know common ways to represent graphs:
read about:
I can't recommend enough these resources:
this is quite possibly the best resource ever to exist on learning any data structures or algorithms concepts.
this is an excellent pool of practice questions. Practice solving these problems on a white board, talking aloud to yourself as you solve them. Ideally, you should be able to solve any easy problem in 15 minutes and any medium/hard problem in 45 minutes. Don't beat yourself up over the med/hard ones though, some of them are really hard.
I also recommend subscribing for premium leet code (at the time of writing, $30/mo) for at least one month in order to take the interview track for the specific company you're applying for. This is a lot better than messing around randomly solving leetcode problems hoping that it's useful. Remember, you should not be focusing on learning how to solve any one specific problem on this site. Instead, focus on honing your problem-solving abilities.
My final tips for your interview are this:
Cheers, and good luck.