Problem-Solving & Interview Framework

Why a framework

Under pressure, people jump straight into code and get lost. A fixed routine keeps you calm, shows the interviewer structured thinking, and catches bugs before they happen. Interviewers grade problem solving, communication, code quality and testing — not only whether the final code passes.

The six steps

1. Understand (2–5 min)

Restate the problem in your own words and ask clarifying questions:

• Input: types, sizes, ranges? Can it be empty? Negative numbers? Duplicates? Sorted?
• Output: return value or modify in place? Any order? What if no answer exists?
• Constraints: how large is n? (This hints at the target complexity — see the pattern guide.)
• Edge cases: single element, all equal, very large values, overflow.

2. Examples (2–3 min)

Work through one normal example and one edge case by hand. Write them down; you'll reuse them for testing. Often the pattern becomes visible while doing this.

3. Approach (5–10 min)

1. State the brute force and its complexity — it proves you understand the problem and gives a fallback.
2. Identify the bottleneck. What's repeated? What's searched over and over?
3. Apply a pattern to remove it (hash map, sorting, two pointers, DP…).
4. State the improved time and space complexity.
5. Get a nod from the interviewer before coding.

4. Code (15–20 min)

• Use meaningful names (left, right, window_count, not a, b, c).
• Write helper functions for self-contained pieces (is_valid, neighbors).
• Handle edge cases explicitly at the top.
• Keep narrating: “now I shrink the window while it's invalid…”
• If you forget an API, say so and use a reasonable stand-in — interviewers care more about logic.

5. Test (5 min)

• Trace your code (not your idea) with the small example, line by line, tracking variables.
• Then edge cases: empty, one element, duplicates, negative numbers, max values.
• Look specifically for: off-by-one errors, uninitialized variables, integer overflow, wrong loop bounds, missing return.

6. Analyze and discuss (2 min)

Restate time and space complexity. Mention trade-offs and possible follow-ups (streaming input, memory limits, parallelization).

A worked example

Problem: Given an array of integers and k, return the number of contiguous subarrays whose sum equals k.

1. Clarify: can numbers be negative? (Yes.) n up to 2·10⁴. Return a count.
2. Example: [1, 1, 1], k = 2 → subarrays [1,1] twice → 2. Edge: [1, -1, 0], k = 0 → [1,-1], [0], [1,-1,0] → 3.
3. Approach:
   • Brute force: all O(n²) subarrays with running sums → O(n²). Acceptable for 2·10⁴, but can we do better?
   • Negatives rule out a sliding window.
   • Prefix sums: subarray (i, j] sums to k iff P[j] − P[i] = k. Count previous prefixes equal to P[j] − k with a hash map → O(n) time, O(n) space.
4. Code:

def subarray_sum(nums, k):
    seen = {0: 1}
    prefix = count = 0
    for x in nums:
        prefix += x
        count += seen.get(prefix - k, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return count

5. Test [1, -1, 0], k = 0: prefixes 1 (count 0), 0 (seen[0] = 1 → count 1), 0 (seen[0] = 2 → count 3). ✓
6. Complexity: O(n) time, O(n) space.

Communication phrases that help

• “Let me make sure I understand: …”
• “A brute-force approach would be … which is O(n²). The repeated work is …, so I'll use … to avoid it.”
• “I'm going to assume … — is that okay?”
• “Let me trace through this with the example to check.”
• “One edge case I want to handle is …”

When you're stuck in an interview

• Say what you're thinking; interviewers often give hints when they see where you're going.
• Go back to examples and try a smaller one.
• Run through the “when stuck” list in the pattern guide.
• Offer the brute force and start optimizing from it — a working O(n²) beats an unfinished O(n).

Code quality checklist

• Clear variable names
• No duplicated logic (extract helpers)
• Edge cases handled up front
• No magic numbers without explanation
• Consistent interval conventions ([lo, hi) vs [lo, hi])
• Complexity stated

After the interview (for practice sessions)

Write a short note for each problem: the pattern, the key insight, and the mistake you made. Reviewing these notes before an interview is far more effective than re-reading solutions.