Structured Problem-Solving Techniques

1. Problem Restatement

The first step in structured problem-solving is to restate the problem in your own words. This forces you to internalize the core issue and ensures you’re not misinterpreting the ask. Often, interviewers phrase problems vaguely to test your ability to clarify requirements. By rephrasing, you eliminate assumptions and confirm alignment with the expected outcome. For example, if asked to 'optimize a process,' restating it as 'reduce the time taken to complete Task X by 30%' makes the goal concrete. This technique also buys you time to think while demonstrating active listening. The key is to avoid parroting the problem; instead, distill it into a precise, actionable statement. This step works because it shifts your brain from passive reception to active engagement, laying the groundwork for deeper analysis. Without it, you risk solving the wrong problem or overlooking edge cases.

# Restate the problem: 'Find the longest substring without repeating characters'
# Rephrased: 'Given a string, identify the length of the longest contiguous sequence of unique characters'

def longest_unique_substring(s: str) -> int:
    # Edge case: empty string
    if not s:
        return 0
    
    # Track the last seen index of each character
    last_seen = {}
    start = 0
    max_length = 0
    
    for end, char in enumerate(s):
        # If the character is seen and within the current window, move the start
        if char in last_seen and last_seen[char] >= start:
            start = last_seen[char] + 1
        
        # Update the last seen index of the character
        last_seen[char] = end
        # Update the maximum length if the current window is larger
        max_length = max(max_length, end - start + 1)
    
    return max_length

# Test case
print(longest_unique_substring("abcabcbb"))  # Output: 3 ("abc")

2. Decomposition

Decomposition involves breaking a problem into smaller, independent sub-problems that can be solved individually. This technique works because it reduces cognitive load—your brain can only hold so many variables at once. By isolating components, you can focus on one piece at a time, verify correctness incrementally, and avoid feeling overwhelmed. For instance, if asked to design a system to recommend movies, you might decompose it into: (1) user preferences, (2) movie metadata, (3) similarity algorithms, and (4) ranking logic. Each sub-problem can then be tackled separately, with clear inputs and outputs. Decomposition also reveals hidden dependencies; if two sub-problems rely on the same data, you might merge them. The key is to ensure sub-problems are truly independent or have well-defined interfaces. This approach mirrors how complex systems are built in practice, where modularity enables scalability and maintainability. Without decomposition, you risk creating a monolithic solution that’s hard to debug or extend.

# Decompose: 'Find the k most frequent elements in an array'
# Sub-problems:
# 1. Count frequency of each element
# 2. Sort elements by frequency
# 3. Extract top k elements

def top_k_frequent(nums: list[int], k: int) -> list[int]:
    # Sub-problem 1: Count frequencies
    frequency = {}
    for num in nums:
        frequency[num] = frequency.get(num, 0) + 1
    
    # Sub-problem 2: Sort by frequency (descending)
    # Using a list of tuples (frequency, num) for sorting
    sorted_items = sorted(frequency.items(), key=lambda x: -x[1])
    
    # Sub-problem 3: Extract top k
    result = [num for num, freq in sorted_items[:k]]
    return result

# Test case
print(top_k_frequent([1,1,1,2,2,3], 2))  # Output: [1, 2]

3. Pattern Recognition

Pattern recognition is the ability to identify similarities between the current problem and past experiences or known frameworks. This technique works because it leverages your brain’s capacity for analogical reasoning—solving new problems by adapting solutions from familiar ones. For example, if you recognize that a problem resembles finding a path in a grid, you might apply graph traversal algorithms like BFS or DFS. Pattern recognition accelerates problem-solving by reducing the need to derive solutions from first principles. It also helps in anticipating edge cases; if a pattern includes a specific failure mode (e.g., cycles in graphs), you can proactively handle it. The key is to abstract the problem’s structure, ignoring superficial details. For instance, 'merge two sorted lists' and 'merge two sorted arrays' are the same problem in different contexts. This technique is powerful but requires exposure to diverse problems to build a mental library of patterns. Without it, you risk reinventing the wheel or missing optimizations.

# Pattern: 'Find the first missing positive integer' resembles 'bucket sort'
# Recognize that the answer must be in [1, n+1] for an array of length n

def first_missing_positive(nums: list[int]) -> int:
    n = len(nums)
    
    # Step 1: Place each number in its correct bucket (if possible)
    for i in range(n):
        # While the current number is in [1, n] and not in its correct position
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            # Swap to place nums[i] in its correct position
            correct_pos = nums[i] - 1
            nums[i], nums[correct_pos] = nums[correct_pos], nums[i]
    
    # Step 2: Find the first position where the number doesn't match the index
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    
    # If all positions are correct, the answer is n + 1
    return n + 1

# Test case
print(first_missing_positive([3, 4, -1, 1]))  # Output: 2

4. Hypothesis Testing

Hypothesis testing involves forming an educated guess about the solution and validating it through logical deduction or experimentation. This technique works because it shifts your approach from passive analysis to active verification, reducing uncertainty. For example, if asked to determine whether a linked list has a cycle, you might hypothesize that a slow and fast pointer will meet if a cycle exists. You then test this by simulating the pointers’ movement. The key is to choose hypotheses that are falsifiable—you should be able to prove or disprove them quickly. This technique is especially useful when the problem has multiple potential solutions, as it narrows the search space. It also helps in debugging; if your hypothesis fails, the failure itself often reveals new insights. For instance, if your hypothesis assumes a sorted input but the test case is unsorted, you’ll quickly realize the need to handle both cases. Hypothesis testing works because it mirrors the scientific method, where progress is made through iteration and refinement. Without it, you risk pursuing dead-end solutions or overcomplicating the problem.

# Hypothesis: 'A linked list has a cycle if a slow and fast pointer meet'
# Test the hypothesis by implementing Floyd's Tortoise and Hare algorithm

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def has_cycle(head: ListNode) -> bool:
    if not head or not head.next:
        return False
    
    slow = head
    fast = head.next
    
    # Move slow by 1, fast by 2; if they meet, there's a cycle
    while slow != fast:
        if not fast or not fast.next:
            return False
        slow = slow.next
        fast = fast.next.next
    
    return True

# Test case
node1 = ListNode(3)
node2 = ListNode(2)
node3 = ListNode(0)
node4 = ListNode(-4)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node2  # Creates a cycle
print(has_cycle(node1))  # Output: True

5. Backward Reasoning

Backward reasoning starts from the desired outcome and works backward to identify the steps needed to reach it. This technique works because it flips the problem-solving process, often revealing hidden constraints or prerequisites that forward reasoning might miss. For example, if asked to find the minimum number of steps to reach a target in a grid, you might start from the target and explore all possible paths backward to the start. This approach is particularly effective for problems with a clear end state but ambiguous initial conditions. It also helps in identifying sub-goals; if the target requires X, what must be true to achieve X? This technique is powerful in dynamic programming, where solutions are built by combining results of smaller sub-problems. The key is to ensure that each backward step is reversible—if you can’t trace the path forward, the reasoning is flawed. Backward reasoning works because it aligns with how humans naturally plan, by envisioning the goal and working toward it. Without it, you risk getting stuck in local optima or overlooking elegant solutions.

# Backward reasoning: 'Find the minimum number of coins to make an amount'
# Start from the amount and subtract coin values to reach 0

def coin_change(coins: list[int], amount: int) -> int:
    # Initialize a DP array where dp[i] is the min coins for amount i
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # Base case: 0 coins needed for amount 0
    
    # For each amount from 1 to target, find the minimum coins
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                # If using this coin, the remaining amount is i - coin
                dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

# Test case
print(coin_change([1, 2, 5], 11))  # Output: 3 (5 + 5 + 1)

Interview questions

All Reasoning interview questions →

Check yourself

Take the full Reasoning quiz →