Master 15 Must-Know Patterns for Coding Interviews

August 30, 2024

Preparing for coding interviews can be daunting, especially when you’re faced with a wide range of problems that test your problem-solving abilities. However, understanding and mastering common coding patterns can significantly increase your chances of success. In this guide, we’ll walk through 15 must-know coding patterns that frequently appear in coding interviews, along with pseudocode and practical examples to help you grasp each concept.

🌟 1. Prefix Sum

Pattern Overview:
Prefix Sum is used to precompute cumulative sums of an array to enable efficient range sum queries.

Pseudocode:

python
def prefix_sum(array):
prefix = [0] * len(array) # Initialize a list to store prefix sums
prefix[0] = array[0] # The first element is the same as in the original array

for i in range(1, len(array)):
prefix[i] = prefix[i - 1] + array[i] # Add the current element to the previous prefix sum

return prefix # Return the list of prefix sums

Practical Example: Given an array arr = [1, 2, 3, 4, 5], compute the range sum from index 1 to 3.

Implementation:

python

arr = [1, 2, 3, 4, 5] prefix = prefix_sum(arr) range_sum = prefix[3] – prefix[0] # Result is 9

🌟 2. Two Pointers

Pattern Overview:
Two Pointers technique involves using two indices to traverse data structures to solve problems efficiently.

Pseudocode:

python
def two_pointers(arr, target):
    left, right = 0, len(arr) - 1  # Initialize the two pointers

    while left < right:
        current_sum = arr[left] + arr[right]  # Calculate the sum of the elements at the pointers

        if current_sum == target:
            return (left, right)  # Return the indices if the target sum is found
        elif current_sum < target:
            left += 1  # Move the left pointer to the right if the current sum is less than the target
        else:
            right -= 1

Practical Example: Find two numbers in a sorted array arr = [1, 2, 3, 4, 6] that add up to 6.

Implementation:

python

arr = [1, 2, 3, 4, 6] result = two_pointers(arr, 6) # Result is (1, 3)

🌟 3. Sliding Window

Pattern Overview:
Sliding Window is used to maintain a window of elements in an array or string and slide it across to find subarrays or substrings that meet specific conditions.

Pseudocode:

python
def sliding_window(arr, k):
max_sum = 0
window_sum = sum(arr[:k])

for i in range(len(arr) - k):
window_sum = window_sum - arr[i] + arr[i + k]
max_sum = max(max_sum, window_sum)

return max_sum

Practical Example: Find the maximum sum of any contiguous subarray of size k = 3 in arr = [2, 1, 5, 1, 3, 2].

Implementation:

python

arr = [2, 1, 5, 1, 3, 2] result = sliding_window(arr, 3) # Result is 9

🌟 4. Fast & Slow Pointers

Pattern Overview:
Fast and Slow Pointers are used to detect cycles in linked lists or arrays, or to find the middle of a list.

Pseudocode:

python
def has_cycle(head):
    slow, fast = head, head  # Initialize two pointers, slow and fast

    while fast and fast.next:
        slow = slow.next  # Move slow pointer one step
        fast = fast.next.next  # Move fast pointer two steps

        if slow == fast:
            return True  # A cycle is detected if slow and fast pointers meet

    return False  # No cycle detected if the loop exits

Practical Example: Detect if a linked list has a cycle.

Implementation:

python

# Assume ListNode is a class for linked list nodes cycle_detected = has_cycle(head) # Result is True/False

🌟 5. LinkedList In-Place Reversal

Pattern Overview:
This pattern reverses a linked list or its parts in-place without using extra space.

Pseudocode:

python
def reverse_linked_list(head):
    prev, current = None, head  # Initialize previous node as None and current node as head

    while current:
        next_node = current.next  # Save the next node
        current.next = prev  # Reverse the current node's pointer
        prev = current  # Move prev and current one step forward
        current = next_node

    return prev  # prev is the new head of the reversed linked list

Practical Example: Reverse a linked list with nodes 1 -> 2 -> 3 -> 4 -> 5.

Implementation:

python

# Assume ListNode is a class for linked list nodes new_head = reverse_linked_list(head) # List is now 5 -> 4 -> 3 -> 2 -> 1

🌟 6. Monotonic Stack

Pattern Overview:
A Monotonic Stack maintains a stack where the elements are in a monotonic order, either increasing or decreasing.

Pseudocode:

python
def next_greater_elements(nums):
    stack = []
    result = [-1] * len(nums)  # Initialize the result list with -1 for each element

    for i in range(len(nums)):
        while stack and nums[stack[-1]] < nums[i]:
            result[stack.pop()] = nums[i]  # Update result with the next greater element

        stack.append(i)  # Push the current index onto the stack

    return result

Practical Example: Find the next greater element for each element in arr = [2, 1, 2, 4, 3].

Implementation:

python

arr = [2, 1, 2, 4, 3] result = next_greater_elements(arr) # Result is [4, 2, 4, -1, -1]

🌟 7. Top ‘K’ Elements

Pattern Overview:
This pattern uses a heap to track the top ‘K’ elements in a dataset.

Pseudocode:

python
import heapq

def top_k_elements(nums, k):
    return heapq.nlargest(k, nums)

Practical Example: Find the top 3 largest elements in arr = [3, 2, 1, 5, 6, 4].

Implementation:

python

arr = [3, 2, 1, 5, 6, 4] result = top_k_elements(arr, 3) # Result is [6, 5, 4]

🌟 8. Overlapping Intervals

Pattern Overview:
This pattern handles problems that involve overlapping intervals by sorting and merging intervals.

Pseudocode:

python
def merge_intervals(intervals):
    # Sort the intervals based on the starting time
    intervals.sort(key=lambda x: x[0])

    merged = []  # Initialize the list to store merged intervals

    for interval in intervals:
        # If merged is empty or there is no overlap with the last interval, append the current interval
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            # If there is an overlap, merge the intervals by updating the end time
            merged[-1][1] = max(merged[-1][1], interval[1])

    return merged

Practical Example: Merge overlapping intervals in intervals = [[1, 3], [2, 6], [8, 10], [15, 18]].

Implementation:

python

intervals = [[1, 3], [2, 6], [8, 10], [15, 18]] result = merge_intervals(intervals) # Result is [[1, 6], [8, 10], [15, 18]]

🌟 9. Modified Binary Search

Pattern Overview:

This pattern involves modifying the standard binary search to handle problems with variations like searching in rotated arrays.

Pseudocode:

python
def search_rotated_array(nums, target):
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2

        # If the target is found, return its index
        if nums[mid] == target:
            return mid

        # Determine which side is properly sorted
        if nums[left] <= nums[mid]:  # Left side is sorted
            if nums[left] <= target < nums[mid]:  # Target is in the left side
                right = mid - 1
            else:  # Target is in the right side
                left = mid + 1
        else:  # Right side is sorted
            if nums[mid] < target <= nums[right]:  # Target is in the right side
                left = mid + 1
            else:  # Target is in the left side
                right = mid - 1

    # If the target is not found, return -1
    return -1

Practical Example: Search for the target 5 in a rotated array arr = [4, 5, 6, 7, 0, 1, 2].

Implementation:

python

arr = [4, 5, 6, 7, 0, 1, 2] index = search_rotated_array(arr, 5) # Result is 1

🌟 10. Binary Tree Traversal

Pattern Overview:
Binary Tree Traversal involves visiting nodes in a binary tree in a specific order (inorder, preorder, postorder).

Pseudocode (Inorder Traversal):

python
def inorder_traversal(root):
    result = []

    def dfs(node):
        if node:
            dfs(node.left)           # Traverse the left subtree
            result.append(node.val)  # Visit the node
            dfs(node.right)          # Traverse the right subtree

    dfs(root)
    return result

Practical Example: Perform an inorder traversal on a binary tree.

Implementation:

python

# Assume TreeNode is a class for tree nodes result = inorder_traversal(root) # Result is nodes visited in inorder sequence

🌟 11. Depth-First Search (DFS)

Pattern Overview:
DFS explores all nodes in a depthward motion before exploring breadthwise, useful for traversing or searching tree/graph structures.

Pseudocode:

python
def dfs(graph, start):
    visited = set()  # Initialize an empty set to keep track of visited nodes

    def dfs_helper(node):
        if node not in visited:
            visited.add(node)  # Mark the current node as visited
            for neighbor in graph[node]:  # Explore all the neighbors
                dfs_helper(neighbor)  # Recursively visit each neighbor

    dfs_helper(start)  # Start the DFS from the initial node
    return visited  # Return the set of visited nodes

Practical Example: Perform a DFS on a graph starting from node A.

Implementation:

python

graph = {‘A’: [‘B’, ‘C’], ‘B’: [‘D’], ‘C’: [‘E’], ‘D’: [], ‘E’: []} visited_nodes = dfs(graph, ‘A’) # Result is {‘A’, ‘B’, ‘D’, ‘C’, ‘E’}

🌟 12. Breadth-First Search (BFS)

Pattern Overview:
BFS uses a queue to explore all neighbors at the present depth level before moving on to nodes at the next depth level.

Pseudocode:

python
from collections import deque

def bfs(graph, start):
    visited, queue = set(), deque([start])  # Initialize visited set and queue with the start node

    while queue:
        node = queue.popleft()  # Dequeue a node from the front of the queue

        if node not in visited:
            visited.add(node)  # Mark the node as visited
            queue.extend(graph[node] - visited)  # Add all unvisited neighbors to the queue

    return visited  # Return the set of visited nodes

Practical Example: Perform a BFS on a graph starting from node A.

Implementation:

python

graph = {‘A’: set([‘B’, ‘C’]), ‘B’: set([‘D’]), ‘C’: set([‘E’]), ‘D’: set(), ‘E’: set()} visited_nodes = bfs(graph, ‘A’) # Result is {‘A’, ‘B’, ‘C’, ‘D’, ‘E’}

🌟 13. Matrix Traversal

Pattern Overview:
Matrix Traversal involves navigating through a matrix in a specific direction/order, such as row-wise, column-wise, or diagonally.

Pseudocode:

python
def traverse_matrix(matrix):
    for row in matrix:
        for element in row:
            print(element, end=' ')

def traverse_matrix(matrix): for row in matrix: for element in row: print(element, end=’ ‘)

Practical Example: Traverse a 2D matrix row by row.

Implementation:

python

matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] traverse_matrix(matrix) # Prints: 1 2 3 4 5 6 7 8 9

🌟 14. Backtracking

Pattern Overview:
Backtracking involves recursively exploring all potential solutions and abandoning paths that don’t meet the required conditions.

Pseudocode:

python
def backtrack(path, options):
    if end_condition:  # Base case: check if the end condition is met
        results.append(path[:])  # Add a copy of the current path to results
        return
    
    for option in options:
        path.append(option)  # Choose an option by adding it to the current path
        backtrack(path, options)  # Explore further with the updated path
        path.pop()  # Undo the choice (backtrack) to explore other options

Practical Example: Generate all permutations of [1, 2, 3].

Implementation:

python
def permute(nums):
    result = []

    def backtrack(path, options):
        if not options:  # If no more options are available, add the path to the result
            result.append(path[:])  # Add a copy of the current path to the result
            return

        for i in range(len(options)):
            # Choose the current element and add it to the path
            path.append(options[i])

            # Explore with the current element removed from the options
            backtrack(path, options[:i] + options[i+1:])

            # Backtrack by removing the last element added to the path
            path.pop()

    backtrack([], nums)
    return result

# Example usage
result = permute([1, 2, 3])
# Result is [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

🌟 15. Dynamic Programming (DP)

Pattern Overview:
Dynamic Programming breaks problems into overlapping subproblems, storing solutions to subproblems and reusing them to solve larger problems.

Pseudocode:

python

def fib(n): if n <= 1: return n dp = [0] * (n + 1) dp[1] = 1 for i in range(2, n + 1): dp[i] = dp[i – 1] + dp[i – 2] return dp[n]

Practical Example: Calculate the 10th Fibonacci number using DP.

Implementation:

python
def fib(n):
    if n <= 1:
        return n

    dp = [0] * (n + 1)  # Initialize a list to store Fibonacci numbers up to n
    dp[1] = 1  # The first Fibonacci number is 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]  # Calculate the i-th Fibonacci number

    return dp[n]  # Return the n-th Fibonacci number

result = fib(10) # Result is 55