14 Patterns to Ace Any Coding Interview Question

Are you preparing for a coding interview and feeling overwhelmed by the sheer number of practice problems out there? You're not alone. Many developers spend weeks solving hundreds of questions on platforms like LeetCode, often wondering if they've done enough. But what if I told you there's a more efficient way to prepare?

Instead of tackling endless problems, focus on mastering the underlying patterns. By understanding these core concepts, you can approach a wide variety of questions with confidence. In this comprehensive guide, we'll explore 14 essential patterns that will help you ace any coding interview question.

1. Sliding Window

The Sliding Window pattern is a powerful technique for solving problems involving arrays or strings where you need to find or calculate something within a specific range of elements.

How it works:

• Start with a window covering the first element
• Expand or contract the window based on certain conditions
• Move the window one element at a time
• Track the desired information as you slide the window

When to use it:

• You're dealing with a linear data structure (array, string, linked list)
• You need to find the longest/shortest substring or subarray
• You're asked to calculate something within a specific range of elements

Example problems:

• Maximum sum subarray of size 'K'
• Longest substring with 'K' distinct characters
• String anagrams

Code example (Python):

def max_sum_subarray(arr, k):
    max_sum = float('-inf')
    window_sum = 0
    start = 0
    
    for end in range(len(arr)):
        window_sum += arr[end]
        
        if end >= k - 1:
            max_sum = max(max_sum, window_sum)
            window_sum -= arr[start]
            start += 1
    
    return max_sum

2. Two Pointers

The Two Pointers pattern involves using two pointers to iterate through a data structure, often moving in tandem or towards each other.

How it works:

• Initialize two pointers, typically at the start and end of the array
• Move the pointers based on certain conditions
• Solve the problem by comparing or manipulating elements at the pointer positions

When to use it:

• You're working with sorted arrays or linked lists
• You need to find a set of elements that fulfill certain constraints
• You're looking for pairs, triplets, or subarrays

Example problems:

• Squaring a sorted array
• Triplets that sum to zero
• Comparing strings that contain backspaces

Code example (Python):

def two_sum(nums, target):
    left, right = 0, len(nums) - 1
    
    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
    
    return []

3. Fast and Slow Pointers

Also known as the "Hare and Tortoise" algorithm, this pattern uses two pointers moving at different speeds through a sequence.

How it works:

• Initialize two pointers, one moving faster than the other
• Move the pointers through the sequence
• Detect cycles or find specific elements based on where the pointers meet

When to use it:

• You're dealing with a cyclic linked list or array
• You need to find the position of an element or the length of a cycle
• You're working with a singly linked list where backward movement is not possible

Example problems:

• Linked List Cycle detection
• Palindrome Linked List
• Cycle in a Circular Array

Code example (Python):

def has_cycle(head):
    if not head or not head.next:
        return False
    
    slow = head
    fast = head.next
    
    while slow != fast:
        if not fast or not fast.next:
            return False
        slow = slow.next
        fast = fast.next.next
    
    return True

4. Merge Intervals

The Merge Intervals pattern is used to deal with overlapping intervals or ranges.

How it works:

• Sort the intervals based on start time
• Iterate through the intervals, merging overlapping ones
• Handle different types of overlap scenarios

When to use it:

• You're asked to merge overlapping intervals
• You need to find intersections between intervals
• You're dealing with scheduling or time-based problems

Example problems:

• Merge Intervals
• Insert Interval
• Maximum CPU Load

Code example (Python):

def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []
    
    for interval in intervals:
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])
    
    return merged

5. Cyclic Sort

Cyclic Sort is an efficient technique for sorting arrays containing numbers in a given range.

How it works:

• Iterate through the array
• Place each number in its correct position
• Swap elements until all numbers are in their correct indices

When to use it:

• You're dealing with arrays containing numbers in a given range
• The problem involves finding missing or duplicate numbers in an array

Example problems:

• Find the Missing Number
• Find all Duplicate Numbers
• Find the Smallest Missing Positive Number

Code example (Python):

def cyclic_sort(nums):
    i = 0
    while i < len(nums):
        correct_pos = nums[i] - 1
        if nums[i] != nums[correct_pos]:
            nums[i], nums[correct_pos] = nums[correct_pos], nums[i]
        else:
            i += 1
    return nums

6. In-place Reversal of a Linked List

This pattern involves reversing the links between nodes in a linked list without using extra space.

How it works:

• Use three pointers: previous, current, and next
• Iterate through the list, reversing the links as you go
• Update the pointers in each iteration

When to use it:

• You need to reverse a linked list or a part of it
• You're asked to reverse every K elements in a linked list

Example problems:

• Reverse a Linked List
• Reverse a Sub-list
• Reverse every K-element Sub-list

Code example (Python):

def reverse_linked_list(head):
    prev = None
    current = head
    
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    
    return prev

7. Tree Breadth-First Search (BFS)

Tree BFS involves traversing a tree level by level, exploring all nodes at the current depth before moving to the next level.

How it works:

• Use a queue to keep track of nodes at each level
• Process nodes from left to right at each level
• Add child nodes to the queue for the next level

When to use it:

• You need to traverse a tree in level order
• You're asked to find the minimum depth of a tree
• You need to connect nodes at the same level

Example problems:

• Binary Tree Level Order Traversal
• Zigzag Traversal
• Level Averages in a Binary Tree

Code example (Python):

from collections import deque

def level_order_traversal(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        current_level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(current_level)
    
    return result

8. Tree Depth-First Search (DFS)

Tree DFS involves exploring a tree by going as deep as possible along each branch before backtracking.

How it works:

• Use recursion or a stack to traverse the tree
• Explore one branch completely before moving to the next
• Choose between pre-order, in-order, or post-order traversal

When to use it:

• You need to search for a node in a tree
• You're asked to find a path with specific properties
• You need to traverse a tree in a specific order

Example problems:

• Binary Tree Path Sum
• All Paths for a Sum
• Path with Maximum Sum

Code example (Python):

def dfs_inorder(root):
    result = []
    
    def inorder(node):
        if node:
            inorder(node.left)
            result.append(node.val)
            inorder(node.right)
    
    inorder(root)
    return result

9. Two Heaps

The Two Heaps pattern uses two heaps (one min heap and one max heap) to efficiently track the median of a stream of numbers or find the smallest/largest elements in two halves of a dataset.

How it works:

• Maintain a max heap for the lower half of the numbers
• Maintain a min heap for the upper half of the numbers
• Balance the heaps after each insertion

When to use it:

• You need to find the median of a stream of numbers
• You're asked to find the smallest/largest elements in two halves of a dataset

Example problems:

• Find the Median of a Number Stream
• Sliding Window Median
• IPO (Initial Public Offering)

Code example (Python):

import heapq

class MedianFinder:
    def __init__(self):
        self.small = []  # max heap
        self.large = []  # min heap

    def addNum(self, num: int) -> None:
        if len(self.small) == len(self.large):
            heapq.heappush(self.large, -heapq.heappushpop(self.small, -num))
        else:
            heapq.heappush(self.small, -heapq.heappushpop(self.large, num))

    def findMedian(self) -> float:
        if len(self.small) == len(self.large):
            return (-self.small[0] + self.large[0]) / 2.0
        else:
            return float(self.large[0])

10. Subsets

The Subsets pattern is used to deal with problems involving combinations and permutations of a set of elements.

How it works:

• Start with an empty set
• Iteratively add each element to existing subsets to create new subsets
• Use recursion or bit manipulation for generating all subsets

When to use it:

• You need to find all possible combinations or permutations of a set
• You're dealing with problems involving power sets

Example problems:

• Subsets
• Permutations
• Combination Sum

Code example (Python):

def subsets(nums):
    result = [[]]
    
    for num in nums:
        result += [subset + [num] for subset in result]
    
    return result

11. Modified Binary Search

This pattern is an adaptation of the classic binary search algorithm to solve more complex problems involving sorted arrays.

How it works:

• Initialize start and end pointers
• Calculate the middle index
• Compare the middle element with the target
• Adjust the search range based on the comparison

When to use it:

• You're searching in a sorted array, list, or matrix
• You need to find an element or a condition in a sorted structure

Example problems:

• Search in Rotated Sorted Array
• Find Minimum in Rotated Sorted Array
• Search in a Sorted Infinite Array

Code example (Python):

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

12. Top 'K' Elements

This pattern is used to solve problems involving finding the top or bottom K elements of a dataset.

How it works:

• Use a heap to keep track of the K elements
• Iterate through the dataset, updating the heap as necessary
• The heap will maintain the K elements of interest

When to use it:

• You need to find the K largest/smallest elements
• You're asked to sort a nearly sorted array

Example problems:

• Kth Largest Element in an Array
• Top K Frequent Elements
• Sort Characters By Frequency

Code example (Python):

import heapq

def top_k_frequent(nums, k):
    count = {}
    for num in nums:
        count[num] = count.get(num, 0) + 1
    
    return heapq.nlargest(k, count.keys(), key=count.get)

13. K-way Merge

The K-way Merge pattern is used to efficiently merge K sorted arrays or lists.

How it works:

• Use a min-heap to keep track of the smallest elements
• Add the first element from each array to the heap
• Continuously remove the smallest element and add the next from its array

When to use it:

• You need to merge K sorted arrays or lists
• You're dealing with a problem involving multiple sorted inputs

Example problems:

• Merge K Sorted Lists
• Kth Smallest Element in M Sorted Lists
• Smallest Range Covering Elements from K Lists

Code example (Python):

import heapq

def merge_k_sorted_arrays(arrays):
    min_heap = []
    result = []
    
    for i, arr in enumerate(arrays):
        if arr:
            heapq.heappush(min_heap, (arr[0], i, 0))
    
    while min_heap:
        val, array_index, element_index = heapq.heappop(min_heap)
        result.append(val)
        
        if element_index + 1 < len(arrays[array_index]):
            next_element = arrays[array_index][element_index + 1]
            heapq.heappush(min_heap, (next_element, array_index, element_index + 1))
    
    return result

14. Topological Sort

Topological Sort is used to find a linear ordering of elements that have dependencies on each other, typically in a directed acyclic graph (DAG).

How it works:

• Build a graph representation of the elements and their dependencies
• Calculate the in-degree (number of incoming edges) for each node
• Use a queue to process nodes with no dependencies (in-degree of 0)
• Remove processed nodes and update in-degrees of their neighbors

When to use it:

• You're dealing with problems involving dependencies or prerequisites
• You need to find a valid ordering of tasks or events

Example problems:

• Course Schedule
• Alien Dictionary
• Minimum Height Trees

Code example (Python):

from collections import defaultdict, deque

def topological_sort(num_vertices, edges):
    graph = defaultdict(list)
    in_degree = {i: 0 for i in range(num_vertices)}
    
    for src, dest in edges:
        graph[src].append(dest)
        in_degree[dest] += 1
    
    queue = deque([v for v in range(num_vertices) if in_degree[v] == 0])
    result = []
    
    while queue:
        vertex = queue.popleft()
        result.append(vertex)
        
        for neighbor in graph[vertex]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    return result if len(result) == num_vertices else []

Conclusion

Mastering these 14 patterns will significantly improve your ability to tackle a wide range of coding interview questions. Remember, the key is not to memorize solutions but to understand the underlying patterns and how to apply them. With practice, you'll be able to recognize which pattern to use for a given problem quickly.

As you prepare for your coding interviews, focus on:

1. Understanding the core concepts of each pattern