Part 2: Problem-Solving Framework and Patterns

From Random Guessing to Systematic Problem-Solving

Early in my interview preparation, I would read a problem and immediately start coding whatever solution came to mind. This approach failed spectacularly. I'd get stuck, write messy code, and struggle to explain my thinking.

Everything changed when I adopted a systematic framework. This structure not only improved my problem-solving but also made interviews less stressful because I had a reliable process to follow.

The UMPIRE Framework

I developed this mnemonic based on various methodologies I studied. It stands for:

• Understand

• Match

• Plan

• Implement

• Review

• Evaluate

Let me show you how I apply this in real interviews.

Step 1: Understand

What I Do

Before writing any code, I ensure I fully understand the problem:

# Problem: Given an array, return indices of two numbers that add to target

# My clarifying questions:
"""
1. Can I assume exactly one solution exists?
2. Can the same element be used twice?
3. Are negative numbers allowed?
4. What should I return if no solution exists?
5. Can the array be empty?
6. Is the array sorted?
"""

Real Example

Interviewer: "Find two numbers in an array that sum to a target."

My Response:

"Let me make sure I understand correctly:
- Input: array of integers and a target sum
- Output: indices of two numbers that add up to target
- Can I use the same index twice? [Wait for answer]
- Should I return any valid pair or all pairs? [Wait for answer]
- What if no solution exists? Return empty array or None?

Let me verify with an example:
Input: [2, 7, 11, 15], target = 9
Output: [0, 1] because nums[0] + nums[1] = 2 + 7 = 9

Does this match your expectations?"

The Understanding Checklist

I always cover these points:

✅ Input format and constraints ✅ Output format and requirements ✅ Edge cases ✅ Examples to verify understanding

Step 2: Match

Pattern Recognition

Based on problems I've solved, I recognize patterns by asking:

1. Data structure in problem? → Likely pattern

   • Array/String → Two Pointers, Sliding Window

   • Graph/Tree → BFS, DFS

   • Sorted array → Binary Search

2. What's being optimized? → Technique

   • Subarray/substring → Sliding Window

   • All combinations → Backtracking

   • Minimum/maximum → DP or Greedy

3. Constraint hints

   • O(n) time required → Hash Map

   • O(1) space required → In-place manipulation

   • Binary choices → Bit manipulation

Pattern Matching Diagram

The Core Coding Patterns

Based on my interview experience, these patterns cover 80% of problems:

Pattern 1: Two Pointers

When to use: Array/string problems involving pairs or sequences

My template:

def two_pointers_template(arr):
    """
    Two pointers moving towards each other or same direction
    """
    left, right = 0, len(arr) - 1
    
    while left < right:
        # Process current pair
        if condition:
            # Do something
            left += 1
        else:
            right -= 1
    
    return result

Real problem I solved: Valid Palindrome

def is_palindrome(s: str) -> bool:
    """
    Check if string is palindrome, ignoring non-alphanumeric
    
    My approach: Two pointers from both ends
    Time: O(n), Space: O(1)
    """
    left, right = 0, len(s) - 1
    
    while left < right:
        # Skip non-alphanumeric characters
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        
        # Compare characters (case-insensitive)
        if s[left].lower() != s[right].lower():
            return False
        
        left += 1
        right -= 1
    
    return True

# Test cases I used
print(is_palindrome("A man, a plan, a canal: Panama"))  # True
print(is_palindrome("race a car"))  # False

Pattern 2: Sliding Window

When to use: Contiguous subarray/substring problems

My template:

def sliding_window_template(arr, k):
    """
    Fixed or variable size window
    """
    window_start = 0
    window_sum = 0
    result = 0
    
    for window_end in range(len(arr)):
        # Add current element to window
        window_sum += arr[window_end]
        
        # Shrink window if needed
        while window_condition_violated:
            window_sum -= arr[window_start]
            window_start += 1
        
        # Update result
        result = max(result, window_sum)
    
    return result

Real problem: Maximum Average Subarray

def max_average_subarray(nums: list[int], k: int) -> float:
    """
    Find maximum average of contiguous subarray of size k
    
    My approach: Fixed-size sliding window
    Time: O(n), Space: O(1)
    """
    # Calculate initial window
    window_sum = sum(nums[:k])
    max_sum = window_sum
    
    # Slide the window
    for i in range(k, len(nums)):
        # Remove left element, add right element
        window_sum = window_sum - nums[i - k] + nums[i]
        max_sum = max(max_sum, window_sum)
    
    return max_sum / k

# My test cases
print(max_average_subarray([1, 12, -5, -6, 50, 3], 4))  # 12.75

Pattern 3: Hash Map (Fast Lookup)

When to use: Need to track seen elements or counts

My template:

def hash_map_template(arr):
    """
    Use dictionary for O(1) lookup
    """
    seen = {}  # or set() if just tracking existence
    
    for item in arr:
        if item in seen:
            # Found duplicate or complement
            return seen[item]
        
        # Store item with relevant info
        seen[item] = some_value
    
    return result

Real problem: Two Sum (the classic)

def two_sum(nums: list[int], target: int) -> list[int]:
    """
    Find indices of two numbers that sum to target
    
    My approach: Hash map to store complements
    Time: O(n), Space: O(n)
    """
    seen = {}  # {value: index}
    
    for i, num in enumerate(nums):
        complement = target - num
        
        # Check if complement exists
        if complement in seen:
            return [seen[complement], i]
        
        # Store current number
        seen[num] = i
    
    return []  # No solution found

# Edge cases I always test
print(two_sum([2, 7, 11, 15], 9))  # [0, 1]
print(two_sum([3, 2, 4], 6))        # [1, 2]
print(two_sum([3, 3], 6))           # [0, 1]

Pattern 4: Fast and Slow Pointers

When to use: Detecting cycles, finding middle element

My template:

def fast_slow_template(head):
    """
    Two pointers moving at different speeds
    """
    slow = fast = head
    
    while fast and fast.next:
        slow = slow.next       # Move 1 step
        fast = fast.next.next  # Move 2 steps
        
        if slow == fast:
            # Cycle detected or middle found
            return True
    
    return False

Real problem: Linked List Cycle

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

def has_cycle(head: ListNode) -> bool:
    """
    Detect if linked list has a cycle
    
    My approach: Floyd's Tortoise and Hare
    Time: O(n), Space: O(1)
    """
    if not head:
        return False
    
    slow = fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        # If they meet, there's a cycle
        if slow == fast:
            return True
    
    return False

Pattern 5: Binary Search

When to use: Sorted array or search space can be binary searched

My template:

def binary_search_template(arr, target):
    """
    Search in sorted array or search space
    """
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2  # Avoid overflow
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1  # Not found

Real problem: Search in Rotated Sorted Array

def search_rotated(nums: list[int], target: int) -> int:
    """
    Search in rotated sorted array
    
    My approach: Modified binary search
    Time: O(log n), Space: O(1)
    """
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if nums[mid] == target:
            return mid
        
        # Determine which half is sorted
        if nums[left] <= nums[mid]:
            # Left half is sorted
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            # Right half is sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    
    return -1

# My test cases
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0))  # 4
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 3))  # -1

Step 3: Plan

My Planning Process

Before implementing, I verbalize my plan:

"I'll use a hash map approach because:
1. We need O(1) lookup for complements
2. Single pass through array
3. Space trade-off is acceptable

The algorithm:
1. Create empty hash map
2. For each number:
   - Calculate complement (target - number)
   - Check if complement exists in map
   - If yes, return indices
   - If no, add current number to map

Time: O(n) - single pass
Space: O(n) - hash map storage

Let me verify with the example..."

Complexity Analysis

I always state complexities upfront:

def my_solution(arr):
    """
    My approach: [Description]
    
    Time Complexity: O(n log n) - sorting dominates
    Space Complexity: O(1) - in-place operations
    
    Breakdown:
    - Sorting: O(n log n)
    - Two pointers: O(n)
    - Total: O(n log n)
    """
    pass

Step 4: Implement

My Coding Best Practices

From conducting interviews, I value:

1. Clean Structure

# Bad - rushed implementation
def solve(a,t):
    d={}
    for i in range(len(a)):
        if t-a[i] in d:return [d[t-a[i]],i]
        d[a[i]]=i

# Good - clear and readable
def two_sum(nums: list[int], target: int) -> list[int]:
    """Find indices of two numbers that sum to target"""
    seen = {}
    
    for index, number in enumerate(nums):
        complement = target - number
        
        if complement in seen:
            return [seen[complement], index]
        
        seen[number] = index
    
    return []

2. Handle Edge Cases

def process_array(arr: list[int]) -> int:
    """Process array with edge case handling"""
    # Handle empty array
    if not arr:
        return 0
    
    # Handle single element
    if len(arr) == 1:
        return arr[0]
    
    # Main logic
    result = 0
    for num in arr:
        result += num
    
    return result

3. Use Descriptive Names

# Bad
def f(n):
    r = []
    for i in range(n):
        if i % 2 == 0:
            r.append(i)
    return r

# Good
def get_even_numbers(max_number: int) -> list[int]:
    """Return list of even numbers from 0 to max_number"""
    even_numbers = []
    
    for number in range(max_number):
        if number % 2 == 0:
            even_numbers.append(number)
    
    return even_numbers

Step 5: Review

My Testing Approach

After implementing, I test systematically:

def test_solution():
    """
    Test cases I always include:
    1. Normal case
    2. Edge cases (empty, single element)
    3. Boundary values
    4. Invalid inputs
    """
    # Normal case
    assert two_sum([2, 7, 11, 15], 9) == [0, 1]
    
    # Edge cases
    assert two_sum([3, 3], 6) == [0, 1]  # Duplicate numbers
    assert two_sum([1, 2], 10) == []     # No solution
    
    # Boundary
    assert two_sum([0, 4, 3, 0], 0) == [0, 3]  # Zero values
    
    print("All tests passed!")

Walking Through Code

In interviews, I trace through with an example:

"Let me trace through with [2, 7, 11], target=9:

i=0, num=2:
  complement = 9-2 = 7
  7 not in seen
  seen = {2: 0}

i=1, num=7:
  complement = 9-7 = 2
  2 IS in seen!
  return [0, 1]

Perfect, it works as expected."

Step 6: Evaluate

Optimization Questions

I always ask myself:

1. Can I improve time complexity?

   • Current: O(n²) → Can I use hash map for O(n)?

2. Can I reduce space?

   • Current: O(n) → Can I solve in-place?

3. Are there edge cases I missed?

   • Negative numbers?

   • Very large inputs?

   • Special characters?

Example Optimization

# Initial solution - O(n²)
def has_duplicate_v1(nums: list[int]) -> bool:
    """Check if array has duplicates - brute force"""
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False

# Optimized - O(n) time, O(n) space
def has_duplicate_v2(nums: list[int]) -> bool:
    """Check if array has duplicates - hash set"""
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

# Further optimized - O(n log n) time, O(1) space
def has_duplicate_v3(nums: list[int]) -> bool:
    """Check if array has duplicates - sorting"""
    nums.sort()  # Modifies input
    for i in range(len(nums) - 1):
        if nums[i] == nums[i + 1]:
            return True
    return False

Communication During Implementation

What I Say While Coding

"I'm going to create a hash map to store numbers we've seen...
[writes code]

Now I'll iterate through the array...
[writes code]

For each number, I'll calculate its complement...
[writes code]

Let me add a comment here to clarify this edge case...
[adds comment]

Hmm, I need to handle the case where the array is empty.
Let me add that check...
[adds validation]
"

When I Get Stuck

"I'm thinking about two approaches:
1. Brute force O(n²) - nested loops
2. Hash map O(n) - single pass

The brute force is straightforward but slow.
Let me think about the hash map approach...

Actually, can I ask a clarifying question about [specific constraint]?

Okay, that helps. Let me proceed with the hash map solution."

Complete Example: Problem-Solving in Action

Let me show you a full problem solution using UMPIRE:

Problem: Valid Parentheses

U - Understand

Given: String containing '(', ')', '{', '}', '[', ']'
Find: Whether string is valid (brackets properly closed)

Questions:
- Can string be empty? Yes → return True
- Only these 6 characters? Yes
- Order matters? Yes - must close in correct order

Examples:
"()" → True
"()[]{}" → True  
"(]" → False
"([)]" → False

M - Match

Pattern: Stack (LIFO)
Why: Need to match most recent opening bracket

P - Plan

1. Use stack to track opening brackets
2. For each character:
   - If opening bracket → push to stack
   - If closing bracket:
     - Check if matches top of stack
     - If matches, pop stack
     - If doesn't match or stack empty, return False
3. Return True if stack is empty

Time: O(n), Space: O(n)

I - Implement

def is_valid_parentheses(s: str) -> bool:
    """
    Check if string has valid parentheses
    
    Approach: Stack to match brackets
    Time: O(n), Space: O(n)
    """
    # Map closing to opening brackets
    bracket_map = {
        ')': '(',
        '}': '{',
        ']': '['
    }
    
    stack = []
    
    for char in s:
        if char in bracket_map:
            # Closing bracket
            if not stack or stack[-1] != bracket_map[char]:
                return False
            stack.pop()
        else:
            # Opening bracket
            stack.append(char)
    
    # Valid if all brackets matched
    return len(stack) == 0

R - Review

# Test cases
print(is_valid_parentheses("()"))      # True
print(is_valid_parentheses("()[]{}"))  # True
print(is_valid_parentheses("(]"))      # False
print(is_valid_parentheses("([)]"))    # False
print(is_valid_parentheses(""))        # True

E - Evaluate

Time: O(n) - single pass ✓
Space: O(n) - stack worst case ✓
Edge cases handled ✓
Can't optimize further ✓

Key Takeaways

From my interview experience:

1. Have a framework - UMPIRE keeps you organized under pressure

2. Recognize patterns - Most problems fit known patterns

3. Communicate constantly - Explain your thinking out loud

4. Start simple - Get a working solution, then optimize

5. Test thoroughly - Don't assume your code works

6. Know when to ask for hints - It's better than being stuck silent

What's Next?

In Part 3: Data Structures Fundamentals, we'll dive deep into:

• Arrays and strings with real interview problems

• Hash tables and their applications

• Linked lists implementation and problems

• Stacks and queues practical usage

We'll solve 10+ real problems using the patterns we learned!

---

This framework is based on hundreds of problems I've solved and dozens of interviews I've conducted.