I gave 127 interviews. Top 5 Algorithms they asked me.

Summary

This video script by Sahil offers insights into the top 5 algorithms frequently asked in coding interviews: the 'top k elements', 'sliding window', 'backtracking', 'dynamic programming', and graph traversal techniques like 'Breadth First Search' and 'Depth First Search'. It emphasizes that mastering a few key algorithms can significantly improve interview performance, as they are often the basis for solving a variety of problems. The script also touches on the importance of understanding data structures and provides links to related code examples for further learning.

Takeaways

• 📘 The speaker emphasizes that knowing every algorithm is not necessary to succeed in coding interviews, highlighting the 80-20 rule where 20% of algorithms are asked in 80% of interviews.
• 🔍 The top 5 algorithms frequently asked in interviews are to be discussed, with specific problems where they apply, aiming to help viewers identify the most important algorithms.
• 🔑 The 'top k elements' algorithm is crucial for various problems like finding the k largest/smallest numbers in an array or the k most frequent numbers, and can be efficiently solved using a heap data structure.
• 🔠 The 'Sliding window' algorithm is applicable to problems involving substrings or subarrays with certain constraints, and involves expanding and contracting a window while tracking characters or elements.
• 🌐 Backtracking is a method for exploring all possible solutions by building them step by step and is often implemented using recursion, as demonstrated by the Combination sum problem.
• 💡 Dynamic Programming is an approach that breaks a problem into smaller subproblems and utilizes the solutions of these subproblems to efficiently solve the original problem, as opposed to recalculating them.
• 🌟 Breadth First Search (BFS) and Depth First Search (DFS) are fundamental graph traversal algorithms, with BFS using a queue and DFS using a stack to explore vertices systematically.
• 🛣️ BFS is particularly useful for finding the shortest path between two vertices in a graph, while Dijkstra’s algorithm and Topological sort are related concepts worth exploring.
• 📚 Mastering Data Structures is essential for understanding and effectively applying algorithms, as they form the foundation for solving complex problems in coding interviews.
• 🎓 The speaker, Sahil, suggests that viewers watch another video for insights on mastering Data Structures and Algorithms, indicating a broader learning resource.
• 📈 The script suggests that while the top 5 algorithms are important, a comprehensive understanding of algorithms and data structures is necessary to excel in coding interviews.

Q & A

What is the 80-20 rule or Pareto’s principle in the context of coding interviews?

The 80-20 rule, or Pareto’s principle, as mentioned in the script, suggests that 20% of algorithms are asked in 80% of coding interviews. This principle is used to emphasize that mastering a smaller subset of algorithms can significantly increase one's chances of success in interviews.

Why is the 'top k elements' algorithm important in coding interviews?

The 'top k elements' algorithm is important because it appears in various types of problems such as finding the k largest or smallest numbers in an array or the k most frequent numbers. It's also used in 'Sliding Window' problems, making it a versatile and commonly asked algorithm in interviews.

What is the time complexity of finding the top k largest numbers in an array using sorting?

Sorting the array and then taking the k largest elements has a time complexity of O(nlogn), where n is the number of elements in the array. This is because the sorting operation itself typically takes O(nlogn) time.

How does the 'top k elements' algorithm improve upon the time complexity of sorting?

The 'top k elements' algorithm uses a heap data structure to maintain the top k largest numbers, which has a time complexity of O(nlogK). This is more efficient than sorting the entire array, especially when k is much smaller than n.

Can you explain the 'Sliding window' algorithm using the Largest Substring without repeating characters problem?

The 'Sliding window' algorithm for the Largest Substring without repeating characters problem involves using two pointers to expand and contract a window within the string. The algorithm expands the window by moving the right pointer until a repeating character is found, then contracts the window by moving the left pointer, ensuring the maximum window size without repeating characters.

What is Backtracking and how is it implemented?

Backtracking is a technique used to explore all possible solutions by building them step by step. It involves recursion and is implemented by going back (or 'backtracking') to previous steps and exploring other options when an invalid state is reached.

How does the Combination Sum problem illustrate the concept of Backtracking?

The Combination Sum problem demonstrates Backtracking by starting with an empty combination and recursively adding numbers to the combination, updating the sum, and the index. If the sum exceeds the target or a valid combination is found, the algorithm backtracks to explore other combinations.

What is the main difference between Dynamic Programming and Backtracking?

While Backtracking explores all possible solutions from scratch, Dynamic Programming is more thoughtful about the solutions it explores. It breaks a problem into smaller subproblems and uses the solutions to these subproblems to build up to the solution of the original problem, often using memoization to avoid redundant calculations.

How does the script suggest solving the Combination Sum problem using Dynamic Programming?

The script suggests a Dynamic Programming approach where you start with the combinations that add up to the target sum minus the last number and then use the last number to generate new combinations that add up to the target sum.

What are the main differences between Depth First Search (DFS) and Breadth First Search (BFS)?

DFS explores as far as possible along each branch before backtracking, using a stack to implement Last In First Out (LIFO) order. BFS, on the other hand, explores all neighboring vertices at the present depth prior to moving on to vertices at the next depth level, using a queue for First In First Out (FIFO) order.

Why are Breadth First Search (BFS) and Depth First Search (DFS) important for coding interviews?

BFS and DFS are important for coding interviews because they are fundamental graph traversal algorithms used to solve a variety of problems, including finding the shortest path and exploring all possible paths in a graph.

What is the relationship between Topological Sort and Depth First Search (DFS)?

Topological Sort is closely related to DFS as it is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sort can be implemented using DFS to visit all vertices in a directed acyclic graph.

Outlines

00:00

📚 Essential Algorithms for Coding Interviews

The speaker begins by introducing the Bellman-Ford, A*, and Floyd Warshall algorithms, reassuring viewers that extensive knowledge of all algorithms is not necessary for success in coding interviews. Drawing from personal experience with interviews at top tech companies, the speaker emphasizes the 80-20 rule, suggesting that mastering a small subset of algorithms can suffice for the majority of interview scenarios. The video promises to reveal the top 5 algorithms frequently asked in interviews, along with their applications, aiming to provide viewers with the tools to identify the most relevant 20% of algorithms. The 'top k elements' algorithm is introduced as the fifth most common, with applications in finding the k largest/smallest numbers in an array and in sliding window problems. The use of a heap data structure is highlighted for its efficiency in maintaining the top k elements, offering a time complexity of nlog(K) as opposed to the less efficient nlogn of sorting.

05:00

🔍 In-Depth Exploration of Top Algorithms and Data Structures

The second paragraph delves deeper into the 'Sliding window' algorithm, a common approach to problems like finding the largest substring without repeating characters or the maximum sum subarray of a certain size. The explanation walks through the process of using two pointers to expand and contract a window while tracking characters, using the example of the largest substring without repeating characters. The paragraph also introduces Backtracking, a method for exploring all possible solutions by building them step by step and backtracking upon reaching invalid states, illustrated with the Combination sum problem. Dynamic Programming is contrasted with Backtracking, highlighting its more thoughtful approach to solution building by leveraging smaller subproblems. The example of the Combination sum problem is revisited to demonstrate how precomputed solutions for smaller targets can be used to find combinations for the target sum. The paragraph concludes with a brief mention of Breadth First Search (BFS) and Depth First Search (DFS), graph traversal algorithms used for different purposes, with BFS aimed at finding the shortest path and DFS for exhaustive branch exploration. The importance of understanding Data Structures for mastering these algorithms is stressed, and viewers are encouraged to watch another video for insights into mastering these concepts.

Keywords

💡Bellman-Ford algorithm

The Bellman-Ford algorithm is a graph search algorithm that finds the shortest path from a single source vertex to all other vertices in the graph. It is particularly useful for graphs in which some of the edges have negative weights. In the context of the video, it is one of the algorithms mentioned as part of the top 5 algorithms that the creator was asked about during interviews, emphasizing its importance in coding interviews.

💡A* algorithm

The A* algorithm is a popular pathfinding and graph traversal algorithm used in computer science. It finds the path with the least cost from a start node to a goal node, taking into account the cost of the path and an estimated cost to the target. The video script positions it among the top algorithms that interviewees should be familiar with, suggesting its prevalence in the job interview process.

💡Floyd-Warshall algorithm

The Floyd-Warshall algorithm is an all-pairs shortest path algorithm that computes the shortest paths between every pair of vertices in a weighted graph. It is mentioned in the script as one of the key algorithms that interviewees may encounter, highlighting its relevance in coding interviews.

💡80-20 rule

The 80-20 rule, also known as Pareto's principle, states that roughly 80% of the effects come from 20% of the causes. In the video, the creator applies this principle to coding interviews, suggesting that mastering a small subset of algorithms can prepare you for the majority of interview questions, which is a key message of the video.

💡top k elements algorithm

The 'top k elements' algorithm is a method used to find the k largest or smallest numbers in an array efficiently. The video explains that this algorithm uses a heap data structure to maintain the top k numbers, which is more efficient than sorting the entire array. It is a core concept in the video, as it demonstrates a specific algorithm that interviewees are likely to encounter.

💡heap data structure

A heap is a specialized tree-based data structure that satisfies the heap property. In a max heap, for example, the parent node is always greater than or equal to its child nodes. The video script uses the heap as part of the 'top k elements' algorithm, illustrating how it can be used to efficiently find the largest numbers in an array.

💡Sliding window algorithm

The sliding window algorithm is a technique used to solve problems that involve a subset of an array that can 'slide' over the array. The video script explains how this algorithm can be used to find the largest substring without repeating characters, among other problems, making it a central concept in the video's discussion of interview preparation.

💡Backtracking

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions and abandons a candidate as soon as it determines that the candidate cannot possibly be extended to a valid solution. The video script uses the example of the combination sum problem to illustrate how backtracking works, making it a key concept in the video.

💡Dynamic Programming

Dynamic Programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable when the subproblems are not independent, i.e., the solution to one subproblem may involve solutions to other subproblems. The video script contrasts dynamic programming with backtracking and uses the combination sum problem to demonstrate its application, which is a central theme in the video.

💡Breadth First Search (BFS)

Breadth First Search (BFS) is a graph traversal algorithm that explores all the vertices of a graph in breadthward motion, i.e., it visits all the vertices at the present depth prior to moving on to vertices at the next depth level. The video script explains that BFS is used to find the shortest path between two vertices and is implemented using a queue, which is a key concept in the video's discussion of graph traversal algorithms.

💡Depth First Search (DFS)

Depth First Search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking. The video script positions DFS as a counterpart to BFS, explaining its use in graph traversal and its implementation with a stack, which is a key concept in the video.

Highlights

The speaker emphasizes that knowing every algorithm is not necessary to succeed in coding interviews.

80-20 rule or Pareto’s principle is applied to coding interviews, suggesting that 20% of algorithms are asked in 80% of the interviews.

The video aims to identify the top 5 algorithms frequently asked in coding interviews.

The 'top k elements' algorithm is introduced as the 5th most asked algorithm, with applications in various problems including finding k largest/smallest numbers or most frequent numbers in an array.

Heap data structure is recommended for the 'top k elements' algorithm to efficiently track the top k largest numbers with a time complexity of nlog(K).

The 'Sliding window' algorithm is the 4th most asked, used in problems like finding the largest substring without repeating characters.

The process of the 'Sliding window' algorithm involves expanding and shrinking a window using two pointers and updating character information.

Backtracking is the 3rd most asked algorithm, exploring all possible solutions step by step and using recursion.

The Combination sum problem is used to illustrate the backtracking approach, where combinations are built and invalid states are backtracked.

Dynamic Programming is the 2nd most asked algorithm, solving problems by breaking them into smaller subproblems.

A modified version of the Combination sum problem demonstrates how Dynamic Programming can be used to build solutions incrementally.

Breadth First Search (BFS) and Depth First Search (DFS) are the top algorithms, used for graph traversal with different exploration strategies.

BFS and DFS are implemented using queues and stacks respectively, due to their exploration strategies.

BFS is used for finding the shortest path between two vertices, while Dijkstra’s algorithm and Topological sort are related and important for coding interviews.

A deep understanding of Data Structures is essential to master the discussed algorithms and succeed in coding interviews.

The speaker, Sahil, offers further resources for mastering Data Structures and Algorithms.

Transcripts

Bellman-Ford algorithm, A* algorithm and Floyd Warshall algorithm.

If you have never heard about any of these, don’t worry about it.

You see, I have interviewed at all these companies and got offers from Google, Facebook, Amazon

and some others.

If there’s one thing I have learnt from my experience, it’s this.

You do not need to know every algorithm in this world to crack coding interviews.

In most interviews, they are asking you very similar kinds of questions.

And if you have heard of the 80-20 rule or Pareto’s principle, you know that 20% of

algorithms will be asked in 80% of the interviews.

In this video, I will tell you the top 5 algorithms I was asked in my interviews so that you can

pick the top 20% algorithms by yourself.

I will also share exact problems where these algorithms can be applied.

This video is going to be very information dense.

At number 5, we have the “top k elements” algorithm.

“top k elements” algorithm shows up in many different problems.

Finding k largest or smallest numbers in an array or finding the k most frequent numbers

in an array are some examples where you would need to know this algorithm.

It also shows up in some “Sliding Window” problems.

We will cover “sliding window” shortly.

For the purpose of this video, let’s look into finding k largest numbers in an array.

Sorting the array and taking k largest elements is one way of doing it but it’s not optimal

because the big O of doing this would be nlogn.

That’s why, in the “top k elements” algorithm, we use a heap data structure to

track top k largest numbers.

Now if you don’t know what a heap is and want me to make a video on the top 5 most

asked Data structures, let me know in the comments.

For simplicity, just know that a heap makes getting the maximum or minimum number very

efficient.

In the “top k elements” algorithm, we add the first k numbers of the array on a

heap.

For every number after that, we put it on the array and right after doing that, we remove

the minimum number from the heap.

This way, we maintain the heap size of K and the heap always contains the largest K numbers

we have seen so far.

This step of adding and removing the number from the heap has a big O of logK and we do

this for every number of the array which is n times.

So, the big O of the “top k elements” algorithm is nlog(K) instead of nlogn.

At number 4, we have the “Sliding window” algorithm.

This algorithm shows up in many problems like Largest Substring without repeating characters,

Maximum Sum subarray of size k and Largest substring with k distinct characters etc.

Here, we will learn the “Sliding window” algorithm using the Largest Substring without

repeating characters problem.

You can pause the video if you need some time to understand the problem better.

In the first step, we initialize two pointers: left and right at the beginning of the array.

Now, we increment the right pointer to expand the window between left and right.

As we do this, we store the information of all the characters present inside the window.

We keep incrementing the right pointer and updating this information until we find a

character that’s already present in the window.

We have reached the maximum window size because the right index can not be part of this window

due to the repeating character.

So, we will update the answer and start shrinking the window by incrementing the left pointer

until the repeating character goes outside the window.

As we increment the left pointer, we will remove the characters that are no longer there

in the window from the stored information.

Once the left pointer reaches its final state, we start incrementing the right pointer again

to expand the window and repeat this process.

To help you understand this algorithm better, I will provide the link to this code in the

description.

At number 3, we have Backtracking.

In Backtracking, we explore all possible solutions by building them step by step.

When we reach an invalid state, we backtrack or go back and start exploring other possible

solutions.

Backtracking is usually implemented using recursion.

I know that none of this makes sense right now.

So, let’s understand backtracking with the help of this very famous problem called Combination

sum.

In this problem, you are given a list of positive numbers and a target sum.

You need to pick some numbers from the list so that they add up to the target sum.

In the end, you have to return all unique ways or combinations that satisfy this condition.

You are allowed to pick a number more than once.

In this example, 2, 3 and 3 add up to the target sum of 8.

So, it’s one of the combinations in the answer.

Pause the video if you need more time to understand the problem.

Let’s create different combinations from scratch.

We start at index 0 with an empty combination and current combination sum of zero.

Wherever the total sum of a combination is more than target, we backtrack or return because

adding more positive numbers to the combination will only increase the combination sum and

can’t lead to a valid answer.

If the combination sum is the same as the target, we add it to the answer and return.

Otherwise, for every number that comes after the current index, we add it to the combination,

update the combination sum, update the current index and call the function recursively.

Updating the current index ensures that we only get unique combinations in the answer.

I will link this code in the description for you to check out.

Backtracking is used in many problems like Word Ladder, Permutations and Sudoku Solver.

At number 2, we have Dynamic Programming.

In Backtracking, we explored all possible solutions from scratch piece by piece.

In Dynamic programming, we are more thoughtful about the solutions that we explore while

still building our solutions from scratch.

And we do this by breaking a problem into smaller subproblems.

Let’s take the example of Combination sum and see how we can solve it with Dynamic Programming.

The problem asks us to find all possible unique combinations that add up to target sum using

all the numbers or candidates.

But let me change this problem a little bit.

Imagine that I give you all the combinations that add up to target sum, target sum - 1,

target sum - 2 using all the given numbers except the last one.

And now, I will give you the last number.

Can you use this new information to find all the combinations that add up to the target

sum using all the numbers?

You can pause the video and take a moment to think.

You can start from the left.

Until you reach the target sum equal to the last number, do nothing.

For the target sum equal to the last number, you can simply add the last number by itself

as a new combination.

For the target sum equal to last number + 1, you can just add the last number to all

the combinations that add up to 1 and all those combinations would now add up to the

last number + 1.

Add the last number to all the combinations with target sum equal to 2 and all those combinations

would now add up to the last number + 2.

And you can keep doing this until you reach the target sum.

And voila!

You have found your answer.

If you look at the code, you keep track for all sums from 1 to target with this array.

For target sum equal to 0, add a combination which is an empty list.

Now start with the first number and keep adding more numbers with this for loop.

And for a particular target sum, just add more combinations by using all the combinations

for target sum - current number.

I will leave a link to this code in the description.

At the very top, we have Breadth First Search and Depth First Search.

I have kept them together because both of them are used for graph traversal and are

very similar.

Let's start with Depth First Search or DFS.

In DFS, you start from a vertex and explore as far as possible along each branch.

If you reach a point where there is no unvisited neighboring vertex to explore, you backtrack

and try to find another branch that is unvisited.

In BFS, you explore the neighboring vertices first before moving onto the other deeper

univisited vertices.

DFS is implemented using a Stack whereas BFS is implemented using a queue.

That’s because in DFS, you want to explore the neighbors of the last vertex that you

visited first.

So, you want Last in First Out which is what Stack does.

In BFS however, you want to explore the neighbors of the first vertex you visited first.

So, you want First in First out which is what Queues are for.

I will link a couple videos in the description that explain this in much more detail.

BFS is used to find the shortest path from Vertex A to Vertex B. Another famous algorithm

that does the same is Dijkstra’s algorithm.

An algorithm that is closely related to DFS and is a must for coding interviews is Topological

sort.

I recommend you to read Dijkstra’s algorithm and Topological sort on your own.

To master all the algorithms we discussed today, you need to have a deep understanding

of Data Structures.

And you can not crack coding interviews just with these 5 algorithms obviously.

If you want to know how I mastered Data Structures and Algorithms, watch this video.

My name is Sahil and I will see you in the next one.