Must-know algorithms for success in coding interviews

Preparing for coding interviews has become increasingly challenging due to the vast number of available practice questions. Platforms like LeetCode offer thousands of problems, making it overwhelming to complete them all. Instead of trying to solve every question, a more effective strategy is to learn the core concepts at a higher level, enabling the interviewee to apply these principles to various problems. One such strategy is to master the top algorithms that frequently appear in FAANG interviews. We can approach common interview problems more confidently by concentrating on these key algorithms. Most questions in FAANG interviews are based on a few main algorithms:

Binary search
Depth-first search in graphs
Breadth-first search in graphs
Two pointers
Dynamic programming

In this blog, for each algorithm, we’ll provide an overview of the core concepts, demonstrate how they can be applied to solve a particular LeetCode interview problem and share more examples of interview questions that utilize these techniques.

Binary search

Binary search is an algorithm for locating a specific value within a sorted list or array.

The search process starts by comparing the lookup value with the middle element of the array.

If the lookup value matches the middle element, the search is complete.
If the lookup value is less than the middle element, the search continues in the left half of the array.
Otherwise, the search focuses on the right half of the array.

Modified binary search: Adapting binary search lets us tackle more complex problems where finding a single element isn’t enough, such as locating a peak element or identifying a specific target in a rotated array. In these cases, modified binary search involves changing how we adjust the search range or handle specific conditions.

Here are some interview questions along with the essence of their solutions, illustrating how modified binary search can be applied to solve them:

Interview Problem	Problem Statement	Solution Summary
Finding a target in a rotated sorted array	Given a rotated sorted array, find a specific target value, returning its index if present or -1 if not.	Use binary search to determine which half of the array is sorted. Start by comparing the middle element of the array with the start and end elements to identify whether the left or right half is sorted. Then, decide which half to search based on where the target value would be located relative to the middle element and the sorted half.
Finding a peak element in an array	Given an array, find a peak element, where a peak is defined as an element that is greater than its neighbors.	Use binary search to compare the middle element with its neighbors. If the middle element is greater than its neighbors, it is a peak. If not, you must move to the half of the array where the neighbor is greater than the middle element. This is because if one neighbor is greater, there must be a peak in that direction (either to the left or right) due to the nature of the peak definition (an element greater than its neighbors).
Finding the first or last occurrence of a target value	Given a sorted array, find a target value’s first or last occurrence.	Use the binary search to locate any occurrence of the target. Once you find the target, modify the search to continue in the left half to find the first occurrence or the right half to find the last occurrence.

Depth-first search

Depth-first search (DFS) is an algorithm applied to graphs or trees to traverse their nodes by exploring as deeply as possible along each branch before backtracking. Here’s a breakdown of how DFS works:

Starting point: DFS begins at a selected node (the root in trees or any arbitrary graph node).
Traversal: It explores each branch of the graph or tree as deeply as possible before moving on to the next branch.
Visited nodes: Nodes are marked as visited to avoid processing the same node multiple times and to prevent infinite loops.

Consider the following illustration, which explains the working of DFS in a visual form:

1 / 13

DFS can be implemented in two ways: the recursive approach, where the function calls itself to explore each adjacent node until all reachable nodes are visited, and the iterative approach, which uses an explicit stack to keep track of nodes that need to be explored.

Before moving forward, consider the following coding problem and try to guess its solution:

Given the root of a binary tree, the task is to flatten the tree into a linked list. The left child pointer of each node in the linked list should always be NULL, and the right child pointer should point to the next node in the linked list. The nodes in the linked list should be in the same order as that of the preorder traversal of the given binary tree.

To view the answer, click the “Solution” button below.

Solution

The solution to flattening a binary tree into a linked list involves a depth-first traversal of the tree, where each node is rearranged so that the left subtree becomes empty and the right subtree forms a linear chain of nodes. This can be achieved by recursively flattening the left and right subtrees and then connecting the flattened left subtree to the current node’s right. The original right subtree is appended to the end of the flattened left subtree. This process ensures the tree is flattened in place, maintaining the structure of a singly linked list.

Let’s now explore the Paths in Maze That Lead to Same Room coding interview problem which can be solved using DFS.

Solving the Paths in Maze That Lead to Same Room problem

Let us now explore the Rotting Oranges coding interview problem that can be solved using BFS.

Problem statement: Given a maze represented as a grid, where each cell can be traversed up, down, left, or right, determine which rooms (cells) can be reached by more than one distinct path from a given starting position.

Solution: To solve this problem, you can use DFS and appropriate data structures. Here’s how it works:

Start at the initial position: Initiate the DFS traversal from the maze’s starting point. Use a stack (or recursion) to manage the nodes to be explored.
Explore each path: From the current position, explore all possible directions (up, down, left, right). To handle cycles and ensure rooms are not revisited unnecessarily, use a visited set or boolean matrix to mark cells already explored during the current DFS path.
Track paths to rooms: Maintain a set or dictionary to record rooms that have been reached. For each new room you enter, check if it’s already in the set. If it is, this indicates that multiple paths lead to this room.
Complete the search: Continue the DFS until all possible paths from the starting point have been explored. After the traversal, use the data collected in the set or dictionary to identify all rooms accessible by multiple paths.

Here are a few more graph problems that can be solved using DFS:

Clone graph: Given a reference to a node in a graph, clone the entire graph. Each node in the graph contains a value and a list of its neighbors. The cloned graph should be a deep copy of the original, preserving all node values and connections. DFS can be used to traverse and clone the graph structure.
Graph valid tree: Given the number of nodes and a list of edges representing an undirected graph, determine if the graph is valid. A valid tree must be connected and contain no cycles. DFS helps check for cycles and connectivity to determine if the graph is a valid tree.

Breadth-first search

Breadth-first search (BFS) is an algorithm applied to graphs or trees to traverse their nodes by exploring all nodes at the present depth level before moving on to nodes at the next depth level. Here’s a breakdown of how BFS works:

Starting point: BFS begins at a selected node (the root in trees or any arbitrary graph node).
Traversal: It explores all neighbors of the current node before moving on to the next level. This process continues level by level until all nodes have been visited.
Visited nodes: Nodes are marked as visited to avoid reprocessing and to ensure the algorithm terminates correctly.

BFS is particularly useful for finding the shortest path in unweighted graphs and exploring all nodes breadth-wise.

Consider the following illustration, which explains the working of BFS in a visual form:

1 / 13

BFS is typically implemented using an iterative approach with a queue data structure. Nodes are added to the queue as they are encountered, ensuring that nodes at the current level are processed before nodes at the next level. In contrast to DFS, BFS is not commonly implemented recursively because it requires maintaining state across levels, which is naturally suited to an iterative queue-based approach.

Let us now explore the Rotting Oranges coding interview problem that can be solved using BFS.

Solving the Rotting Oranges problem

Problem statement: Given a grid where each cell contains either a rotten orange, a fresh orange, or an empty cell, determine the minimum time required for all fresh oranges to rot. Rotten oranges spread to adjacent cells (up, down, left, right) every minute. If all fresh oranges can’t rot, return -1.

Solution: To solve this problem, you can use breadth-first search by adding the rotten oranges to a queue and continuing to rot the oranges adjacent to the oranges available in the queue. Here is the detailed algorithm:

Enqueue initial rotten oranges: Use a queue to store the position of all initially rotten oranges by traversing the grid along with their rotting time as 0. At the same time, count the number of fresh oranges.
BFS traversal: While the queue is not empty, process each rotten orange:
- Dequeue the current orange position and the time it became rotten.
- For each adjacent cell (up, down, left, right), check if it contains a fresh orange.
  - If it does, turn it into a rotten orange, reduce the fresh orange count, and enqueue the new rotten orange with the incremented time.
  - Also, keep track of the maximum time as it is incremented for new rotten oranges during BFS.
Check for remaining fresh ranges: After completing the BFS, check for any fresh oranges left.
- If there are, return -1 as it is impossible to rot all oranges.
- Otherwise, return the maximum time recorded, representing the minutes required for all oranges to rot.

Feel free to execute the following code that implements the above solution in the orangesRotting function and executes a few test cases in the driver code:

from collections import deque

def oranges_rotting(grid):
    num_rows, num_cols = len(grid), len(grid[0])
    rotten_queue = deque()
    fresh_count = 0

    # Initialize the queue with the position of rotten oranges and count fresh oranges
    for r in range(num_rows):
        for c in range(num_cols):
            if grid[r][c] == 2:
                rotten_queue.append((r, c, 0))  # (row, col, time)
            elif grid[r][c] == 1:
                fresh_count += 1

    # Directions for moving in the grid: right, down, left, up
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    minutes_elapsed = 0

    # BFS traversal
    while rotten_queue:
        row, col, time_elapsed = rotten_queue.popleft()
        minutes_elapsed = max(minutes_elapsed, time_elapsed)

        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            # Check if the new position is within bounds and has a fresh orange
            if 0 <= new_row < num_rows and 0 <= new_col < num_cols and grid[new_row][new_col] == 1:
                grid[new_row][new_col] = 2  # Make the orange rotten
                fresh_count -= 1
                rotten_queue.append((new_row, new_col, time_elapsed + 1))

    # If there are still fresh oranges left, return -1
    if fresh_count > 0:
        return -1

    return minutes_elapsed
    
# Driver code
def main():
    test_grids = [
        [
            [2, 1, 1],
            [1, 1, 0],
            [0, 1, 1]
        ],
        [
            [2, 1, 1],
            [0, 1, 1],
            [1, 0, 1]
        ],
        [
            [0, 2]
        ],
        [
            [0]
        ],
        [
            [1, 1, 1],
            [1, 2, 1],
            [1, 1, 1]
        ]
    ]

    for i, grid in enumerate(test_grids):
        print(f”Test Case {i + 1}:”)
        print(“Grid:”)
        for row in grid:
            print(row)
        result = oranges_rotting(grid)
        if result == -1:
            print(“Result: Not all oranges can rot.”)
        else:
            print(f”Result: All oranges will rot in {result} minute(s).”)
        print(“-” * 100)

if __name__ == “__main__”:
    main()

Rotting Oranges

Here are a few more graph problems that can be solved using BFS:

Bus routes: Given a list of bus routes and a starting stop, determine the minimum number of bus transfers required to reach a target stop. A list of stops represents each route, and you can switch between routes at common stops. BFS effectively finds the shortest path or minimum number of bus transfers needed to reach a destination.
Network delay time: Given a network of N nodes and a list of times representing the time taken for signals to travel between nodes, find the maximum time it takes for a signal to reach all nodes from a given starting node. If the signal can’t reach all nodes, return -1. BFS can be used to find the shortest path from the starting node to all other nodes, determining the maximum time needed for the signal to reach all nodes.

Two pointers

Interview questions that can be solved with the two-pointer technique typically involve finding pairs or groups of elements in a sorted array or list that satisfy specific conditions, often requiring an efficient traversal from both ends or adjusting pointers based on certain criteria. For example, in the Two Sum problem, the two-pointer technique can be used on an unsorted array by first sorting the array and then using two pointers to find two numbers that add up to a given target by adjusting the pointers based on the sum of the current pair.

Here is a step-wise explanation of how the two pointers technique works:

Initialization: Set up two pointers, left and right, and position them at the appropriate starting points. For example, in a sorted array, you might start left at the beginning (index 0) and right at the end (last index).
Traversal: While the left pointer is less than the right pointer:
- Calculate the value or condition involving the elements at the left and right pointers.
- Determine if the current condition is met (e.g., if the sum of the two elements equals the target value).
  - If the condition is met, return the result as needed.
  - If the condition is not met, adjust the pointers according to the problem’s requirements. Increment the left pointer if the current value is too small, and decrease the right pointer if the current value is too large.

Solving the Two Sum problem

Consider the following solution of the Two Sum problem which uses the above algorithm to find a pair of elements that add to a specific target:

def two_sum(nums, target):
    # Initialize two pointers
    left = 0
    right = len(nums) – 1
    
    # Traverse with two pointers
    while left < right:
        current_sum = nums[left] + nums[right]
        
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    
    # If no solution is found, return an indication (could be an empty list or raise an exception)
    return []

def main():
    # Diverse test cases with varying characteristics
    test_cases = [
        ([-5, -3, 0, 2, 4], -8),         # Array with negative and positive numbers, solution exists
        ([1, 1, 1, 1], 2),               # Array with all same numbers, a solution exists
        ([0, 0, 0, 0], 0),               # Array with all zeros, a solution exists
        ([-10, -5, 0, 5, 10], 0),        # Array with negative and positive numbers, solution exists
        ([2, 3, 4, 5, 6], 11),           # Medium array, solution exists
        ([-3, -2, -1, 1, 2, 3], 0),      # Array with both negative and positive numbers, solution exists
        ([1, 4, 5, 7, 11], 15),          # Medium array, solution exists
        ([2, 5, 7, 10], 16),             # Small array, no solution
        ([1, 1, 1, 1, 1], 3),            # Array with repeated elements, no valid pair for this target
        ([10, 20, 30, 40, 50], 70)       # Larger array, solution exists
    ]
    
    # Execute and print results for each test case
    for i, (nums, target) in enumerate(test_cases):
        print(f”Test Case {i + 1}:”)
        print(f”\tInput array: {nums}”)
        print(f”\tTarget: {target}”)
        result = two_sum(nums, target)
        if result:
            print(f”\tIndices of the two numbers that add up to {target}: {result}”)
        else:
            print(f”\tNo two numbers add up to {target}.”)
        print(“-” * 100)

# Run the driver code
if __name__ == “__main__”:
    main()

Here are a few more problems that can be solved using the two pointers technique:

Valid Palindrome: The two-pointer approach helps check whether a string reads the same forward and backward by comparing characters from both ends and moving toward the center.
Sum of Three Values: This problem requires finding three numbers in a sorted array that add to a given target. The solution can be achieved using two pointers to find pairs and a third pointer to traverse the array.
Sort Colors: Given an array with integers representing colors (0 for red, 1 for white, and 2 for blue), sort the array so that all 0s come first, followed by 1s, and then 2s. The two pointers technique can sort an array with three distinct values (such as 0, 1, and 2) using a single pass. By maintaining three pointers—one for the current position, one for the boundary of the smallest value (0), and one for the largest value (2)—you can ensure that each value is placed in its correct position in one traversal.

Dynamic programming

If you have a problem that has the following properties:

The main problem can be divided into smaller, similar subproblems.
Combining the solutions of these subproblems can lead to a solution for the larger problem.
The solutions to the smaller problems can be used multiple times in computing solutions to relatively larger subproblems.

Then, your problem falls under the category of dynamic programming.

Having smaller and similar subproblems is termed overlapping subproblems, while the ability to combine the solutions of these overlapping subproblems to find the solution to the actual problem is called optimal substructure.

Let’s understand the example of the Coin Change problem to understand its overlapping subproblems and optimal substructure.

Solving the Coin Change problem

Problem: You have $4, and the coin denominations are $1 and $3. You want to discover how many ways you can make $4 using these coins.

Subproblem: The coin change problem’s subproblem involves determining the number of ways to make a smaller amount using the given coin denominations.

For our example, the subproblems would be finding the number of ways to make amounts like 0, 1, 2, and 3 dollars using these denominations.

Optimal substructure: The optimal substructure in the coin change problem means that to find the number of ways to make $4, we can use the solutions of smaller amounts like $3 and $1.

To find the number of ways to make $4, you may consider:
- Number of ways to make $3 plus a $1 coin
- Number of ways to make $1 plus a $3 coin

Combining the solutions of subproblems: Once you have the number of ways to make smaller amounts, you can use these results to determine the number of ways to make the target amount.

To find the number of ways to make $4:

Using a $1 coin and the number of ways to make $3= 2 ways (take a $1 coin and a $3 coin, or a $1 coin + $1 coin + $1 coin + $1 coin)
Using a $3 coin and the number of ways to make $1 = 1 way only (Take a $3 coin and a $1 coin)

So, total ways to make $4 = 2 (ways from using a $1 coin) + 1 (way from using a $3 coin) = 3 ways.

Here are a few more problems that can be solved using dynamic programming:

0/1 knapsack problem : Given a set of items, each with a weight and a value, determine the maximum value that can be achieved without exceeding a given weight capacity. The maximum value is found by combining the results of including or excluding each item and considering the maximum value obtained from smaller subproblems.
Longest common subsequence: Given two strings, find the length of the longest subsequence that is common to both strings. A subsequence is a sequence that appears in the same order but not necessarily consecutively. The longest common subsequence is found by comparing characters in the two strings and recursively determining the maximum length subsequence by including or excluding characters.
Minimum cost climbing stairs: Given an array cost where cost[i] represents the cost of stepping on the i^th stair, find the minimum cost to reach the top of the staircase. You can start from the 0^th or 1^st stair and climb either one or two stairs at a time. The minimum cost to reach each step is computed by adding the current step’s cost to the previous steps’ minimum cost, combining results from steps that lead to the current step.

Next steps

Once you’ve mastered the algorithms discussed, continue exploring additional algorithms and expanding your practice.

If you are preparing for a coding interview at big tech companies like FAANG, consider exploring the courses offered at Educative for comprehensive preparation, including data structures, algorithms, coding interview preparation, and dynamic programming.

Grokking Dynamic Programming: A Deep Dive Using Java

Data Structures for Coding Interviews in Python

Grokking Coding Interview Patterns in Python

One of Educative’s most popular courses, Grokking the Coding Interview Patterns, is available in six languages: Python, Java, C++, C#, JavaScript, and Go. It covers 26 coding patterns to help you recognize and apply known solutions during interviews.

Also, check out these specialized speedrun courses that provide a path to mastering LeetCode-style problems, helping you enhance your interview performance at leading tech companies:

Ishrat Fatima
January 16, 2025

Frequently Asked Questions

Some essential algorithms include Sorting, Searching (like Binary Search), Graph Algorithms (DFS, BFS), Dynamic Programming, Greedy Algorithms, and Divide and Conquer.

The best way to practice is by solving algorithm-based problems on platforms like Educative, LeetCode, Codeforces, and GeeksforGeeks. Try to solve problems that require you to implement the algorithm from scratch and understand its time and space complexity.

Rather than memorizing algorithms, focus on understanding how they work and when to apply them. Explaining and adapting algorithms to different problems is more valuable in an interview setting.

Prioritize algorithms like dynamic programming, graph algorithms, sorting, searching, and greedy algorithms, as these topics frequently appear in interviews at FAANG and other major tech companies.

You’re ready when you can confidently solve algorithm-based problems of varying difficulty, explain your thought process, and analyze the complexity of your solutions. Regular practice and mock interviews can help assess your readiness.