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:
pythondef 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:
pythonarr = [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:
pythondef 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:
pythonarr = [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:
pythondef 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:
pythonarr = [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:
pythondef 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:
pythondef 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:
pythondef 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:
pythonarr = [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:
pythonimport 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:
pythonarr = [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:
pythondef 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:
pythonintervals = [[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:
pythondef 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:
pythonarr = [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):
pythondef 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:
pythondef 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:
pythongraph = {‘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:
pythonfrom 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:
pythongraph = {‘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:
pythondef 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:
pythonmatrix = [[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:
pythondef 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:
pythondef 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:
pythondef 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:
pythondef 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
