DevPath
Tracks

Solving Coding Problems Under Pressure

A repeatable method for interview problems: clarify, work an example, state brute force, optimize, code, and test. Worked end to end on a real problem.

beginner40 min#interviews#problem-solving#umpire#sliding-window#testing

Prerequisites: Arrays and Dynamic Arrays, Big-O and Complexity Analysis

Why it matters

In a coding interview the code is only part of what is judged. The other part is how you think out loud: do you understand the problem, explore options, notice trade-offs, and check your own work? Candidates who dive straight into code often solve the wrong problem or get stuck with no way forward. A fixed routine gives you something to do when your mind goes blank, and it shows the interviewer exactly the skills they are looking for.

Intuition

Solving a problem is like navigating a new city. You would not start driving before knowing the destination, and you would not take the first road without checking it leads somewhere. First confirm where you are going (clarify), look at a small piece of the map (an example), take any known route even if slow (brute force), then look for a shortcut (optimize). Only then do you drive (code), and at the end you check you arrived (test).

How it works

Follow these steps in order. They overlap with the UMPIRE method (understand, match, plan, implement, review, evaluate); the names are less important than the habit.

  1. Clarify. Restate the problem in your own words. Ask about input size and type, empty input, duplicates, negative numbers, case sensitivity, and what to return when there is no answer. Ask whether you may modify the input.
  2. Work an example. Pick a small input, solve it by hand, and narrate the steps. Then try an edge case. This often reveals the algorithm.
  3. State a brute force. Say the simple solution and its complexity, even if slow. It proves you can solve the problem and gives a baseline to improve.
  4. Optimize. Look for wasted work. Ask what you recompute, whether sorting helps, whether a hash map trades space for time, whether two pointers or a window applies. Name the pattern and why it fits.
  5. Agree on the plan, then code. Tell the interviewer the approach and complexity before typing. Write clean code with clear names and small helper functions.
  6. Test. Trace your code on the example by hand, then on edge cases (empty, single item, all the same, maximum size). Fix bugs calmly.
  7. Analyze. State final time and space complexity and mention what you would improve with more time.
 clarify -> example -> brute force -> optimize -> plan -> code -> test -> analyze
    ^                                                              |
    +------------- found a bug or a misunderstanding <-------------+
Clarify
Example
Brute force
Optimize
Plan
Code
Test
Analyze
The routine in order. Testing can send you back to any earlier step when you find a bug or a misunderstanding, which is normal rather than a failure.

Worked problem

Problem: given a string s, return the length of the longest substring that contains no repeated character.

Clarify: Is the string ASCII or Unicode? Case sensitive? Is the empty string allowed (yes, answer 0)? We want the length, not the substring.

Example: for abcabcbb, the answer is 3 (abc). For bbbbb it is 1. For pwwkew it is 3 (wke; note pwke is a subsequence, not a substring).

Brute force: try every start and end, and check whether the substring has duplicates. With a set check that is O(n^3) in the worst case; stopping extension at the first repeat from each start makes it O(n^2). Space is O(min(n, alphabet)).

Optimize: from each start we rescan characters we already looked at. Instead keep a window [left, right] that always has no duplicates. Move right forward one character at a time. If the new character already appears inside the window, jump left just past its previous position. Remember the last index of each character in a map. Each character is visited once, so the time is O(n), and the space is bounded by the alphabet size.

The one subtle detail is the jump: only move left forward, never backward. A character seen before the window began must not pull left back, so take the maximum of the current left and the previous position plus one.

Here is the optimized window on abcabcbb. left and right mark the window; letters inside it are all different.

a
0
left
b
1
c
2
right
a
3
b
4
c
5
b
6
b
7
right=2: window abc has no repeats, length 3. best = 3.
step 1 / 7

The window only grows or jumps forward; it never moves back. The best length stays 3, matching the answer for abcabcbb.

OperationTimeNotes
Brute force (every substring)O(n^3)Check each substring for duplicates
Brute force (stop at first repeat)O(n^2)Restart from each start index
Sliding window with last-seen mapO(n)Each character handled once

Code: brute force, optimized, and a test harness

A good habit is to keep the brute force and use it to check the optimized version on many inputs. Here a tiny seeded generator produces deterministic pseudo-random strings.

def brute_force(s):
    best = 0
    for i in range(len(s)):
        seen = set()
        for j in range(i, len(s)):
            if s[j] in seen:
                break
            seen.add(s[j])
            best = max(best, j - i + 1)
    return best
 
def optimized(s):
    last_seen = {}
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1  # jump past the previous copy
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best
 
def lcg(seed):
    state = seed
    while True:
        state = (state * 1103515245 + 12345) % 2147483648
        yield state
 
samples = ["abcabcbb", "bbbbb", "pwwkew", "", "a", "abba"]
for s in samples:
    print(repr(s), optimized(s))
 
rng = lcg(42)
mismatches = 0
for _ in range(500):
    length = next(rng) % 12
    text = "".join("abcd"[next(rng) % 4] for _ in range(length))
    if brute_force(text) != optimized(text):
        mismatches += 1
print("random checks done, mismatches:", mismatches)

Both versions print:

'abcabcbb' 3
'bbbbb' 1
'pwwkew' 3
'' 0
'a' 1
'abba' 2
random checks done, mismatches: 0

The case abba is the one that catches the classic bug. When the second a arrives, the stored index of the first a is before left (which already moved past the first b), so the guard last_seen[ch] >= left stops left from moving backward. Without that guard the answer would be wrong. Randomized comparison against the brute force found no mismatches across 500 small strings.

The guard matters on abba. Watch the last step, where left must not move.

a
0
left
b
1
right
b
2
a
3
right=1: window ab, length 2. best = 2.
step 1 / 4

At the last step the old `a` is at index 0, left of the window, so the guard last_seen[ch] >= left is false and left stays at 2. Without the guard left would jump back to 1 and the window would wrongly contain two b characters.

Common pitfalls

  • Coding immediately. Two minutes of clarifying prevents ten minutes of rewriting.
  • Skipping the brute force. If you cannot see the optimal solution, a correct slow one earns credit and often leads to the better idea.
  • Not testing. Say "let me trace this on an example" and do it line by line. Bugs found by you look far better than bugs found for you.
  • Ignoring edge cases. Empty input, one element, duplicates, and extreme sizes.
  • Silent optimization attempts. Explain trade-offs, such as space for time, aloud.
  • Panic edits. When a test fails, stop and reason about why before changing code. Random tweaks make things worse.
  • Wrong complexity claims. Count loops and hidden costs, such as string concatenation or in checks on lists.

Practice

Apply the method to Two Sum easy

Hint

State the brute force first. What do you want to look up quickly?

Show solution

Clarify: exactly one answer? may an element be reused? Brute force: check every pair, O(n^2). Optimize: while scanning, store each value's index in a map; for each number look up target - number. That is O(n) time and O(n) space. Test with duplicates like [3, 3] and target 6.

Write three edge cases for the worked problem easy

Hint

Think about size, repetition, and position of the repeat.

Show solution

Good choices: the empty string (0), a string with all distinct characters such as abcdef (6, the window never shrinks), and abba (2, the repeat refers to a character already outside the window).

Longest substring with at most two distinct characters medium

Hint

Same window idea. What do you count instead of last positions?

Show solution

Keep a map from character to count inside the window. Expand right, add the character, and while the map has more than two keys, shrink from left, decrementing counts and removing zeros. Track the best window size. O(n) time, O(1) space because at most three keys exist.

Narrate a stuck moment medium

Hint

What can you always say when you do not see the optimization?

Show solution

A strong script: "I can solve it in O(n^2) by trying all pairs. The wasted work is re-scanning the same items, so let me see whether sorting or a hash map avoids that." Then test the idea on your example. Naming the bottleneck is progress even before you have the answer.

Interview questions

  1. What do you do first when given a problem? Restate it, ask clarifying questions about inputs, edge cases, and constraints, and confirm with an example.
  2. What if you only see the brute force? State it with its complexity, code it if time is short, then look for repeated work to eliminate.
  3. How do you know you are done? The code is traced on the example and on edge cases, and you can state its time and space complexity.
  4. What do you do when the interviewer gives a hint? Accept it gracefully, restate how it changes your approach, and continue. Taking hints is normal and expected.

Interviewers look for: communication, a systematic process, testing without being asked, and the ability to improve a first solution.

Quick check

In the sliding window solution for the longest substring without repeats, why do we take left = max(left, previous + 1) rather than always previous + 1?

Finished this lesson?

Further resources

Related lessons