Preparing for Interviews? Try Our Prep Guide

Are you gearing up for technical interviews?

Our Interview Prep Guide was created by principal-level engineers who have not only conducted thousands of interviews collectively, but they actually shaped the interview process and trained other interviewers at Meta. The guide has helped thousands of engineers prepare for algorithms-focused interviews. It covers topics like:

• Linked Lists
• Arrays
• Binary Trees
• Node-based Data Structures
• Heaps
• Dynamic Programming
• Hashing

👀 Sneak Peek

You can download the full guide here, but here's a first look at some of the content covered in the guide.

🗒 Array

We assume that you already have exposure to the syntax of how to use arrays. On a fundamental level, the most important thing to understand about arrays is that they are fundamentally contiguous chunks of memory.

N^2 runtime sorting algorithms

1. First, let's make sure you understand all the common N^2 runtime sorting algorithms: Insertion Sort, Selection Sort and Bubble Sort. Watch these videos for a review of each:

• Insertion Sort
• Selection Sort
• Bubble Sort

1. Make sure you understand all the runtimes in the chart at the bottom of this link.
2. Finally, code up the solution to each approach here.

Binary Search
Binary search is one of the most common algorithmic patterns to learn. The purpose of binary search is to find items faster in a sorted collection. By leveraging binary search, you are able to reduce your search time from O(n) to O(logn).

1. Watch this video to learn the technique.
2. Then, code up your solution here.
3. Finally, apply this technique to solving this problem.

Sliding Window & Two Pointers
Sliding window and two pointer techniques are names for a specific type of algorithm. When applied properly, these techniques are intended to reduce a nested loop O(n^2) approach to an O(n) algorithm by reducing the need for the nested loop. To do this, we need to store extra information that is updated as we traverse the array using a single pointer.

1. Watch this video to learn the approach and what types of problems benefit from this technique.
2. Apply that same approach to solve this problem.
3. Finally, see if you can figure how to solve this problem. At first glance, this problem may not seem like it has to do with sliding window at all. Can you figure out how it does?

Merge Sort
Now, let's get into some of the more efficient O(nlogn) sort algorithms. These algorithms are significantly harder to follow than the previous algorithms. We recommend learning only one out of merge, quick and heap unless you've exhausted the rest of this guide. Merge sort is a good one to learn because it also forces you to have a solid grasp of recursion.

1. Watch this video for an overview of merge sort.
2. If this is the first time you're seeing this, watch this video for a more in depth walkthrough.
3. Finally, code up the solution here

Quick Sort
Quicksort is another O(nlogn) relies on the concept of a "pivot".

1. Watch this video for an overview of quick sort.
2. If this is the first time you're seeing this, watch this video for a more in depth walkthrough.
3. Finally, code up the solution here.

⭕️ Node Data Structure

We are about to learn about a couple of data structures that are based on a Node class. At first glance, it feels like these data structures have very little to do with day to day engineering. So, before we dive into these structures, let's learn about why learning these does actually help improve you underlying engineering skills.

Watch this video, where our founder Sophie Novati explains: what's the point of studying node based data structures?!

🔗 Linked List

Linked lists are the most simple type of Node data structure. Each Node in a linked list holds a value as well was a pointer to the next Node in the list. Watch the following video for an intro to the Linked List class.

Watch this video, where our founder Sophie Novati explains: why Linked Lists are like scavenger hunts.

Basic Linked List

1. Watch this video to get an overview of the linked list data structure.
2. Read this article to learn the difference between an array and a linked list.
3. Watch this video to understand is its advantages (and disadvantages) compared to the array data structure.
4. If you are relatively new to the Linked List data structure, do the following problems as practice:

• Practice creating the basic linked list here.
• Practice removing an element from a linked list here.
• Practice removing an element, given an index, from a linked list here.
• Practice adding an element, given an index, from a linked list here.
• Practice iterating through and searching for a value in a linked list here.

1. Solve this problem on Leetcode to delete a node from a linked list.

Detecting Cycles
A cycle in a linked list happens when a node's next pointer points to a node previously in the linked list. Cycle detection is a classic problem in linked lists. One of the classic methods to detect a cycle uses a two pointer technique, where one pointer is the "fast" pointer and the other is the "slow" one.Watch this video for an explanation of this approach. Note that this video refers to the "fast" pointer as the hare, and the "slow" pointer as the tortoise, but these are functionally equivalent.

Intersection of Two Lists
Now, let's solve another classic problem with linked list — to find the intersection of two lists. You will be solving this problem on Leetcode.

1. Watch this video for a basic solution to the problem.
2. And this one for a more clever approach.

🎄 Binary Tree

Binary trees are the next most simple type of Node data structure. They are almost identical to linked lists except that instead of one next pointer, each Node in a binary tree points to two other Nodes. While this seems like a small change, it makes the data structure a lot more difficult to iterate over.

Basic Binary Tree

1. Watch this video to get an overview of the binary tree data structure.
2. Learn two different ways to traverse through a binary tree: BFS and DFS.

• Read this article to get an overview of the techniques.
• Watch this video for a verbal explanation of the approaches.
• Practice applying this technique by solving the problem here.

1. If you are relatively new to the Binary Tree data structure, do the following problems as practice:

• Read this article to learn how to count the nodes in a binary tree.
• Read this article to learn how to get the height of a binary tree. Watch this video for an explanation of the same algorithm.
• Watch this video to see how to use a very similar technique to solve a different problem: to find the max value in a binary tree.
• Practice inverting a binary tree here.

Binary Search Tree

1. Watch this video to get an overview of the binary search tree data structure.

• Practice adding a new element to a binary search tree here.

1. Watch this video to learn how to search in a binary search tree.
2. If you are relatively new to the Binary Search Tree data structure, do the following problems as practice:

• Find the minimum and maximum value in a Binary Search Tree here.
• Check if an element exists in a Binary Search Tree here.
• Delete a leaf node in a Binary Search Tree here.
• Delete a leaf node with just one child in a Binary Search Tree here.
• Delete a leaf node with two children in a Binary Search Tree here.

1. Now, consider the problem you solved above where you found the maximum value in a binary tree. How would you solve this problem in a binary search tree? This solution should actually be much easier – think about why!
2. Watch this video to learn how to check if a binary tree is a valid binary search tree or not.

• Practice this solution by solving the problem here.

Balancing Binary Trees
Balancing a binary search tree is not just another algorithm. It's quite a hard one. Keeping a tree balanced also has extremely important implications for its runtime.

1. Watch this video for an overview of what balanced means and how to check if a binary tree is balanced or not.
2. Watch this video to understand why this concept of balanced is important.

#️⃣ Hashing

Hashing is one of the most fundamental concepts that make many of our primitive data structures work (sets / hash sets, dictionaries / hash tables). This section gets into some of the gnarly details of the hash function. Just as you don't need to understand how a microwave works to be able to use it, it is entirely possible to be an engineer using these sets / dictionaries without an understanding of the underlying technique that makes it possible, but understanding it will push you to understand things at a deeper level as an engineer.

Understanding the Hash Function

1. Watch this video for a review of the dictionary / hash table data structure.
2. Hash functions are the core innovation that make hash tables possible, but not all hash functions are created equal. Watch this video to get an understanding of what makes a good hash function.
3. It is possible for a hash function to output the same value for two different keys. That, in the context of a hash table, leads to a collision. Watch this video to understand two of the most common strategies.
4. Watch this video to learn a less common strategy called quadratic probing.
5. As you may know, the cost of lookup, insertion and deletion into a hash table is considered to be O(1). However, when we run out of space in a hash table, we have to do an expensive O(n) operation. So, how can the insertion be considered to be O(1)?

• First, watch this video to understand what a resizing means.
• Then, watch this video understand what amortized runtime is.

....and more! Download the full guide below.

FAQ