You can download the high resolution version using the link at the bottom 👇
1. Arrays
The most fundamental data structure. Arrays are stored contiguously in memory.
2. Linked Lists
These also store an ordered list of elements, but the values are not contiguous in RAM. Linked list nodes have pointers connecting them.
3. HashMaps
Probably the most useful data structure as well. They use a hash function to map keys to indexes within an array. This allows us to have an amortized time of O(1) for most operations.
4. Queues
Typically used to process elements in the same order as they are added. These follow a FIFO (first-in first-out approach). Queues can be double-ended, which allow you to add and remove elements from both the front and the back.
5. Trees
A Binary Tree is an ordered tree data structure where each node is connected to at most two more nodes (called the left and the right child). Being ordered means we can perform DFS and BFS in O(log n) time.
6. Tries/Prefix Trees
Here, each node represents a character in the alphabet and can have at most 26 children. This allows us to save space when inserting words. Tries are useful for auto-complete features and allow us to search for words using their prefix.
7. Heaps
Heaps are a nearly complete binary tree, with potentially the last level being not full. They are implemented with arrays under the hood. Heaps serve as priority queues, and always have the smallest (min-heap) or the largest (max-heap) item stored at the root node.
8. Graphs
A graph is a bunch of nodes (vertices) connected by edges. Linked Lists and Trees are also special type of graphs, but a more general graph can have an arbitrary number of vertices connected to it. A good way to represent graphs in interviews is through an adjacency list.
Everyone hates Dynamic Programming (DP). Yes, it's tough, but after practice, you realize that many DP problems follow a similar template.
It boils down to optimized recursion - we solve problems by breaking them down into smaller overlapping subproblems.
The optimization DP makes is after solving each subproblem, we store (or cache) the results in a table to avoid redundant computations.
Here are 4 common DP patterns:
1) 0/1 Knapsack - We must select items with maximum profit while respecting a weight constraint, with each item only available once to put into the knapsack.
3) Longest Common Subsequence - The problem of finding the longest sequence of characters that appears in the same order (not necessarily consecutively) within two or more given strings.
4) Number Of Unique Paths - Count the number of unique paths from the top left to the bottom right in a 2D grid, where we are only allowed to move down or to the right.
Most people mistakenly assume a nested loop runs in quadratic time.
But this is not always the case. For it to run in quadratic time, there are specific requirements, and actually, it might even have a different complexity!
Take a look at four examples (left to right):
1) The inner loop runs n times on each iteration of the outer loop, which evaluates O(n²). This is the simplest and a common case you've probably encountered.
2) In the sliding window algorithm, the outer for loop runs 𝗲𝘅𝗮𝗰𝘁𝗹𝘆 n times, where n = arr.size(), and the while loop can run 𝗮𝘁 𝗺𝗼𝘀𝘁 n times in total, meaning if it executed n times for one iteration, it won't run at all for other iterations. - O(n). This is also known as amortized analysis.
3) The outer loop runs from i = 0 to i < n, while the inner loop runs from j = i to j < n, meaning for each i, it executes (n - i). If we expand this summation, the leading term becomes O(n²) .
4) The inner loop multiples j by 2 at each iteration, meaning it follows the sequence 1, 2, 4, 8, 16. The number of iterations is:
j = 2^k ≤ n, which is k = log₂n <-- by the definition of the logarithm.
This means that the inner loop runs log n times, which is why the nested loops run in O(n log n) time.
---
🚀 Join over a million people preparing for coding interviews -> neetcode.io/
As much as I like algorithms & data structures, it's not really scratching the itch for me anymore.
I've been doing NeetCode fulltime for 2+ years now and I've been loving it.
But I don't get to work on technical things as much, and it's been really weighing on me.
A lot of people assume burn out is caused by "too much work".
In my case, it's not the workload that's the problem, it's the work itself. It's a little boring.
Personally, I would rather do 60 hours of interesting work, than 20 hours of mind numbingly boring work.
---
I plan on making some changes. I'm gonna start doing more deep technical stuff, centered around distributed systems, operating systems and database internals.
The things I really enjoy.
I want it to be valuable for other people, but social media engagement isn't my goal anymore.
I'm just gonna create exceptional content, and let the rest take care of itself.
I also plan on having more conversations with really smart people on my YouTube channel. I did that once last year and I was surprised how well it performed.
If you're growing tired with all the surface level SWE content on social media nowadays, you might like it!
---
Btw there won't be any changes to neetcode.io I will still work on it, and I have some really exceptional people helping me with it now.
In a coding interview, graphs can be given in many different formats. You might not even be told that the input is a graph.
Here are four most common graph representations in coding interviews ⬇️
𝟭. 𝗔𝗱𝗷𝗮𝗰𝗲𝗻𝗰𝘆 𝗠𝗮𝘁𝗿𝗶𝘅 - An n x n 2D matrix where the value in each square denotes whether there exists an edge between two vertices.
𝟮. 𝗠𝗮𝘁𝗿𝗶𝘅 - A more subtle but common format where each square represents a vertex. The problem statement will tell you how these vertices are connected.
𝟯. 𝗔𝗿𝗿𝗮𝘆 𝗼𝗳 𝗘𝗱𝗴𝗲𝘀 - You will be given a 2D array and each element will contain a pair of vertices that have an edge connecting them. They appear in [v1,v2] format, meaning there is an edge going from v1 to v2.
𝟰. 𝗔𝗱𝗷𝗮𝗰𝗲𝗻𝗰𝘆 𝗟𝗶𝘀𝘁 - The most convenient format, typically implemented with a hashmap. The key represents a vertex and the value represents the list of its neighbors.
—
Preparing for coding interviews? Check out neetcode.io/
Arrays are one of the most common interview topics.
Here are four to patterns that are a must know.
𝟭. 𝗞𝗮𝗱𝗮𝗻𝗲'𝘀 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺 - An efficient algorithm used to find the maximum subarray sum.
𝟮. 𝗧𝘄𝗼 𝗣𝗼𝗶𝗻𝘁𝗲𝗿𝘀 - Use two pointers, e.g. left and right, typically starting at different positions, e.g., start and end of an array, and move them based on specific conditions to solve the problem.
𝟯. 𝗦𝗹𝗶𝗱𝗶𝗻𝗴 𝗪𝗶𝗻𝗱𝗼𝘄 - Expand the window by adding elements from the right until the constraint is broken. Shrink the window by removing elements from the left. Repeat until a valid window is found.
𝟰. 𝗣𝗿𝗲𝗳𝗶𝘅 𝗦𝘂𝗺 - Used to calculate the running sum of a subarray efficiently.
—
Preparing for coding interviews? Check out neetcode.io/
Graphs are common in coding interviews, but they are used in many other places too.
For example, the Six degrees of separation is the idea that all people (vertices) are six or fewer social connections (edges) away from each other.
Here's a list of 5 common graph algorithms that are common in coding interviews.
1. Depth First Search (DFS) Prioritizes depth first. This search will go as deep as possible exploring each node before hitting the base case, after which it explores other nodes. A hash set is used to keep track of visited nodes.
2. Breadth First Search (BFS) Prioritizes breadth first. It explores all possible neighbors of a vertex before moving on to the next level of neighbors, sometimes also called layers. This uses a queue and a hash set, and can be used to find the length of the shortest path from one vertex to the other.
3. Union-Find Used to combine disjoint sets. It's useful for when we want to know the number of connected components in a graph. It's also used in Kruskal's algorithm for detecting cycles.
4. Topological Sort Implemented on a directed acyclic graph, it's used to order vertices such that for every directed edge u -> v, vertex u appears before vertex v. This is useful if an interview problem talks about pre-requisites where one condition must be fulfilled before moving on to the next.
5. Dijkstra's Algorithm A greedy algorithm that operates on weighted graphs, used to find the shortest path from one source to all other vertices in the graph. It uses a min heap to pick the shortest path at each step and a hash set to avoid cycles.
NeetCodeIO
Top 8 Data Structures for Coding Interviews.
You can download the high resolution version using the link at the bottom 👇
1. Arrays
The most fundamental data structure. Arrays are stored contiguously in memory.
2. Linked Lists
These also store an ordered list of elements, but the values are not contiguous in RAM. Linked list nodes have pointers connecting them.
3. HashMaps
Probably the most useful data structure as well. They use a hash function to map keys to indexes within an array. This allows us to have an amortized time of O(1) for most operations.
4. Queues
Typically used to process elements in the same order as they are added. These follow a FIFO (first-in first-out approach). Queues can be double-ended, which allow you to add and remove elements from both the front and the back.
5. Trees
A Binary Tree is an ordered tree data structure where each node is connected to at most two more nodes (called the left and the right child). Being ordered means we can perform DFS and BFS in O(log n) time.
6. Tries/Prefix Trees
Here, each node represents a character in the alphabet and can have at most 26 children. This allows us to save space when inserting words. Tries are useful for auto-complete features and allow us to search for words using their prefix.
7. Heaps
Heaps are a nearly complete binary tree, with potentially the last level being not full. They are implemented with arrays under the hood. Heaps serve as priority queues, and always have the smallest (min-heap) or the largest (max-heap) item stored at the root node.
8. Graphs
A graph is a bunch of nodes (vertices) connected by edges. Linked Lists and Trees are also special type of graphs, but a more general graph can have an arbitrary number of vertices connected to it. A good way to represent graphs in interviews is through an adjacency list.
You can find the high resolution image & cheat sheet here: neetcode.io/courses/lessons/8-data-structures
(free & mobile friendly)
4 months ago | [YT] | 952
View 16 replies
NeetCodeIO
Everyone hates Dynamic Programming (DP). Yes, it's tough, but after practice, you realize that many DP problems follow a similar template.
It boils down to optimized recursion - we solve problems by breaking them down into smaller overlapping subproblems.
The optimization DP makes is after solving each subproblem, we store (or cache) the results in a table to avoid redundant computations.
Here are 4 common DP patterns:
1) 0/1 Knapsack - We must select items with maximum profit while respecting a weight constraint, with each item only available once to put into the knapsack.
🟡 Target Sum - neetcode.io/problems/target-sum
2) Unbounded Knapsack - Similar to 0/1 knapsack, but each item can be selected multiple times to maximize profit without exceeding the weight limit.
🟡 Coin Change - neetcode.io/problems/coin-change
3) Longest Common Subsequence - The problem of finding the longest sequence of characters that appears in the same order (not necessarily consecutively) within two or more given strings.
🟡 LCS - neetcode.io/problems/longest-common-subsequence
🔴 Edit Distance - neetcode.io/problems/edit-distance
4) Number Of Unique Paths - Count the number of unique paths from the top left to the bottom right in a 2D grid, where we are only allowed to move down or to the right.
🟡 Unique Paths - neetcode.io/problems/count-paths
---
If you wanna learn these patterns more in-depth, I cover them in the Advanced Algorithms course on neetcode.io/ 🚀
5 months ago | [YT] | 1,120
View 15 replies
NeetCodeIO
Just update the NeetCode All list from 584 problems -> 793 problems.
I'm not saying you need to solve 793 problems to prepare for interviews. But every one of these will have a detailed video solution (free).
For most people, I would recommend just going through the NeetCode 150 or even better, the NeetCode 250 to learn the main patterns.
After that, you can probably solve problems at random from the All list.
---
I'll be taking a break from making the daily LC videos. Unfortunately, it might be a while before we reach 1000 LC videos made.
But I'm looking forward to trying something new.
Let's see if I'm really just a LC monkey, or if these skills I've built up can translate into another domain 🐵
NeetCode 150 -> neetcode.io/practice?tab=neetcode150
NeetCode 250 -> neetcode.io/practice?tab=neetcode250
NeetCode All -> neetcode.io/practice?tab=allNC
5 months ago (edited) | [YT] | 501
View 26 replies
NeetCodeIO
A Nested Loop Is Not Always O(n²)!
Most people mistakenly assume a nested loop runs in quadratic time.
But this is not always the case. For it to run in quadratic time, there are specific requirements, and actually, it might even have a different complexity!
Take a look at four examples (left to right):
1) The inner loop runs n times on each iteration of the outer loop, which evaluates O(n²). This is the simplest and a common case you've probably encountered.
2) In the sliding window algorithm, the outer for loop runs 𝗲𝘅𝗮𝗰𝘁𝗹𝘆 n times, where n = arr.size(), and the while loop can run 𝗮𝘁 𝗺𝗼𝘀𝘁 n times in total, meaning if it executed n times for one iteration, it won't run at all for other iterations. - O(n). This is also known as amortized analysis.
3) The outer loop runs from i = 0 to i < n, while the inner loop runs from j = i to j < n, meaning for each i, it executes (n - i). If we expand this summation, the leading term becomes O(n²) .
4) The inner loop multiples j by 2 at each iteration, meaning it follows the sequence 1, 2, 4, 8, 16. The number of iterations is:
j = 2^k ≤ n, which is k = log₂n <-- by the definition of the logarithm.
This means that the inner loop runs log n times, which is why the nested loops run in O(n log n) time.
---
🚀 Join over a million people preparing for coding interviews -> neetcode.io/
5 months ago | [YT] | 543
View 9 replies
NeetCodeIO
As much as I like algorithms & data structures, it's not really scratching the itch for me anymore.
I've been doing NeetCode fulltime for 2+ years now and I've been loving it.
But I don't get to work on technical things as much, and it's been really weighing on me.
A lot of people assume burn out is caused by "too much work".
In my case, it's not the workload that's the problem, it's the work itself. It's a little boring.
Personally, I would rather do 60 hours of interesting work, than 20 hours of mind numbingly boring work.
---
I plan on making some changes. I'm gonna start doing more deep technical stuff, centered around distributed systems, operating systems and database internals.
The things I really enjoy.
I want it to be valuable for other people, but social media engagement isn't my goal anymore.
I'm just gonna create exceptional content, and let the rest take care of itself.
I also plan on having more conversations with really smart people on my YouTube channel. I did that once last year and I was surprised how well it performed.
If you're growing tired with all the surface level SWE content on social media nowadays, you might like it!
---
Btw there won't be any changes to neetcode.io I will still work on it, and I have some really exceptional people helping me with it now.
5 months ago | [YT] | 2,046
View 103 replies
NeetCodeIO
In a coding interview, graphs can be given in many different formats. You might not even be told that the input is a graph.
Here are four most common graph representations in coding interviews ⬇️
𝟭. 𝗔𝗱𝗷𝗮𝗰𝗲𝗻𝗰𝘆 𝗠𝗮𝘁𝗿𝗶𝘅 - An n x n 2D matrix where the value in each square denotes whether there exists an edge between two vertices.
𝟮. 𝗠𝗮𝘁𝗿𝗶𝘅 - A more subtle but common format where each square represents a vertex. The problem statement will tell you how these vertices are connected.
𝟯. 𝗔𝗿𝗿𝗮𝘆 𝗼𝗳 𝗘𝗱𝗴𝗲𝘀 - You will be given a 2D array and each element will contain a pair of vertices that have an edge connecting them. They appear in [v1,v2] format, meaning there is an edge going from v1 to v2.
𝟰. 𝗔𝗱𝗷𝗮𝗰𝗲𝗻𝗰𝘆 𝗟𝗶𝘀𝘁 - The most convenient format, typically implemented with a hashmap. The key represents a vertex and the value represents the list of its neighbors.
—
Preparing for coding interviews? Check out neetcode.io/
6 months ago | [YT] | 821
View 11 replies
NeetCodeIO
Arrays are one of the most common interview topics.
Here are four to patterns that are a must know.
𝟭. 𝗞𝗮𝗱𝗮𝗻𝗲'𝘀 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺 - An efficient algorithm used to find the maximum subarray sum.
𝟮. 𝗧𝘄𝗼 𝗣𝗼𝗶𝗻𝘁𝗲𝗿𝘀 - Use two pointers, e.g. left and right, typically starting at different positions, e.g., start and end of an array, and move them based on specific conditions to solve the problem.
𝟯. 𝗦𝗹𝗶𝗱𝗶𝗻𝗴 𝗪𝗶𝗻𝗱𝗼𝘄 - Expand the window by adding elements from the right until the constraint is broken. Shrink the window by removing elements from the left. Repeat until a valid window is found.
𝟰. 𝗣𝗿𝗲𝗳𝗶𝘅 𝗦𝘂𝗺 - Used to calculate the running sum of a subarray efficiently.
—
Preparing for coding interviews? Check out neetcode.io/
6 months ago (edited) | [YT] | 1,382
View 13 replies
NeetCodeIO
Fine, I shaved
sadge
6 months ago | [YT] | 1,277
View 132 replies
NeetCodeIO
Should I keep the mustache, yes or no?
6 months ago | [YT] | 176
View 59 replies
NeetCodeIO
Graphs are common in coding interviews, but they are used in many other places too.
For example, the Six degrees of separation is the idea that all people (vertices) are six or fewer social connections (edges) away from each other.
Here's a list of 5 common graph algorithms that are common in coding interviews.
1. Depth First Search (DFS)
Prioritizes depth first. This search will go as deep as possible exploring each node before hitting the base case, after which it explores other nodes. A hash set is used to keep track of visited nodes.
2. Breadth First Search (BFS)
Prioritizes breadth first. It explores all possible neighbors of a vertex before moving on to the next level of neighbors, sometimes also called layers. This uses a queue and a hash set, and can be used to find the length of the shortest path from one vertex to the other.
3. Union-Find
Used to combine disjoint sets. It's useful for when we want to know the number of connected components in a graph. It's also used in Kruskal's algorithm for detecting cycles.
4. Topological Sort
Implemented on a directed acyclic graph, it's used to order vertices such that for every directed edge u -> v, vertex u appears before vertex v. This is useful if an interview problem talks about pre-requisites where one condition must be fulfilled before moving on to the next.
5. Dijkstra's Algorithm
A greedy algorithm that operates on weighted graphs, used to find the shortest path from one source to all other vertices in the graph. It uses a min heap to pick the shortest path at each step and a hash set to avoid cycles.
To download the full cheat sheet with code samples see: neetcode.io/courses/lessons/5-graph-algorithms
(it's free and I won't collect your email)
7 months ago | [YT] | 740
View 7 replies
Load more