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.
- why you would use one over an array
- how they are implemented at a super high-level
ℹ - 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.
- insertion sort
- selection sort
- merge sort
- quick sort
- quick select
For quick sort and merge sort:
- how do they compare?
- what is each's space-time complexity?
- is either in-place?
You might also want to know how to implement:
- bubble sort
- gnome sort
- sleep sort (kidding, but read about it if you're interested)
- breadth first search
- depth first search
- pre-order
- in-order
- post-order
- bellman-ford
- djisktra
- binary search tree - or at the very least, how it applies to searching
- how to solve the single source shortest path problem
* 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:
- add an element
- extract an element
you should practice implementing these functions that heaps depend on:
- parent
- left child
- right child
- shift down
- shift up
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:
- a complete tree is
- a balanced tree is
- a full tree is
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:
- what generics are
- why they are useful or how they allow us to re-use code
// creating an array of ints without generics
int[] myArray = new int[] {};
// creating lists for ints and strings, respectively
IntList myIntList = new IntList();
StringList myStringList = new StringList();
// creating a list for each using generics
List<int> myGenericIntList = new ArrayList<int>();
List<string> myGenericStringList = new ArrayList<string>();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:
let prev = null;
let reverse = null;
let it = head;
while (it !== null) {
prev = it;
it = it.next;
let temp = {
val: prev.val,
next: reverse,
};
reverse = temp;
}
return reverse;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.
- implement a linked list
- iterate over the linked list
- remove a node
- insert a node in the front of the list
- insert a node at the end of the list
- insert a node arbitrarily
- insert a node in a sorted list
- remove a duplicates
- insert a node in a sorted list, disallowing duplicates
- reverse the list
- turn it into a doubly-linked list
- stacks
- the pop operation
- the push operation
- why a linked list would ever be used as opposed to an array? ie, what is the most obvious advantage?
- time complexities for interacting with a linked list
know some basic terminology about graphs (if you did the graph traversal section, you should have encountered these) and their implications:
- directed or undirected
- cyclic or acyclic
- weighted or unweighted
- non-negative graphs
know common ways to represent graphs:
- edge list
- adjacency list
- adjacency matrix
- node objects
have more time? read about:
- closures
- scopes
- function call-stack
- weakly typed vs strongly typed languages
- implicit typing and type inferencing
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.
- What is your process?
- Do you mentally test your code? (remember, since you are coding on a whiteboard, you can't just guess and check. You need to make your own tests cases and run each test case manually in your head).
- Do you come up with a solution in plain English before coding? Do you discuss, out loud, all of the different possible approaches for solving this problem?
- Do you know the time complexities and the implications of the data structures and algorithms you're using?
My final tips for your interview are this:
- slow down, breath. Are you rambling? Stop and breath.
- think everything out loud, so the interviewer knows what's going on in your head. They want to help you, but they can't if they don't know what you're thinking.
- don't be afraid to be quiet and think, either.
- ask tons of clarifying questions.
- don't be afraid to discuss brute force solutions.
Cheers, and good luck.