Solving Coding Problems: Assumptions, Edge Cases, Complexity, and Tests

Welcome back. You have now practiced the core patterns in this module: hash lookup, sliding windows, two pointers, prefix sums, intervals, and binary search on the answer. The final skill is not another pattern. It is the ability to recognize the relevant pattern under time pressure and make your reasoning visible to an interviewer.

For a Principal or Staff-level backend interview, a coding round still evaluates implementation fundamentals. But the stronger signal is that you establish a precise contract, make a reasoned trade-off, write reliable Java, and verify it without waiting for someone else to find the bugs. This lesson gives you a repeatable 40-minute operating method and applies it to an interview-style problem.

---

What the interviewer is actually evaluating

A coding interview is rarely scored as “correct code” versus “incorrect code.” The usual evaluation has four dimensions:

1. Communication: Do you clarify ambiguity and make your approach understandable?
2. Problem solving: Do you form a valid baseline, select an appropriate pattern, and justify complexity?
3. Technical competency: Can you translate the plan into clean, working Java?
4. Testing: Do you actively search for failures, including boundary cases?

The practical implication is important: do not treat clarification and testing as ceremony before and after “the real work.” They are part of the work.

---

A 40-minute operating plan

The five-step framework below is useful because it turns a vague “solve it quickly” expectation into observable checkpoints.

Use this time budget as a default for a medium-difficulty problem. It is a guide, not a rigid script.

Time	Objective	Visible output
Minutes 0–4	Clarify and restate	A precise problem contract and one small example
Minutes 4–10	Plan and choose	Baseline, optimal approach, invariant, complexity
Minutes 10–25	Implement	Compilable Java with clear names
Minutes 25–34	Test and debug	Happy path, adversarial case, boundary case
Minutes 34–40	Explain and handle follow-ups	Complexity, trade-offs, possible extensions

Phase 1: Clarify with purpose

A senior candidate should not mechanically ask ten questions. Ask the few questions that determine the solution or define behavior at the boundary.

For an array or string problem, this is a high-value checklist:

Topic	Useful question	Why it matters
Input validity	“Can the input be null, or may I assume a non-null value?”	Defines error-handling contract
Empty input	“What should an empty input return?”	Avoids accidental indexing failures
Data semantics	“Does ‘substring’ mean contiguous?”	Determines whether sliding window applies
Data model	“Should I treat Java char values as sufficient, or must this support Unicode code points?”	Determines representation
Scale	“What are the input-size constraints?”	Tests whether a quadratic baseline is acceptable
Output	“Do you want the value, an index range, or the actual substring?”	Changes retained state

Then restate the confirmed contract concisely:

“To confirm: given a non-null string, I should return the length of the longest contiguous substring containing no repeated characters. For an empty string, the answer is zero. I will assume ordinary Java char semantics unless Unicode code-point handling is required.”

That restatement prevents misunderstanding, buys a small amount of thinking time, and demonstrates that you can turn ambiguous language into an implementable API contract.

Phase 2: Show the route before driving it

Before coding, give the interviewer a short decision narrative:

1. State a correct baseline.
2. Identify why it may be too slow.
3. Select a pattern and name its data structure.
4. State the invariant or central correctness idea.
5. Give time and space complexity.
6. Ask whether they would like you to proceed.

For interview settings, this can take less than a minute once you have found the approach.

A useful transition is:

“A straightforward solution would enumerate possible substrings and check for duplicates, which is quadratic in the worst case. Since the input can be large, I can do better with a variable sliding window and a map from character to most recent index. The window will always contain unique characters, and each character is processed once. That gives expected linear time. I’ll implement that approach.”

Phase 3: Code in meaningful chunks

Do not narrate every keystroke. Instead, announce the landmarks:

• “I’m establishing the input contract.”
• “Now I’ll create the map that stores last-seen indices.”
• “The key branch advances the left boundary only if the duplicate lies inside the current window.”
• “I’ll update the best length after restoring the invariant.”

This provides enough visibility without turning implementation into a running commentary.

At this level, favor the most readable standard-library solution. A clever but opaque Java stream pipeline is usually weaker than a direct loop whose invariant is obvious.

Phase 4: Test as an adversary

After code compiles, do not say, “I’m done.” Instead:

“I’ll walk through a normal case, then test cases that target window movement and boundary behavior.”

Your tests should have a purpose. A random selection of examples is less valuable than a set that targets likely defects.

---

Worked interview simulation: longest unique substring

Consider this prompt:

Given a string s, return the length of its longest substring that contains no repeated characters.

This is familiar enough to study, but you should practice the process as if the prompt were new. The goal is not to memorize this particular code. The goal is to make the reasoning reusable whenever a problem involves a contiguous region that must satisfy a changing constraint.

Clarification and contract

A strong opening might be:

“I’ll first confirm that substring means contiguous. Should an empty string return zero? Can I assume s is non-null, and should I optimize for large input sizes? I’ll also assume Java char values are the intended character unit unless full Unicode code-point support is required.”

Assume the interviewer confirms:

• s is non-null;
• empty input returns 0;
• input may be large;
• ordinary char semantics are sufficient;
• only the maximum length is required, not the substring itself.

Establish a baseline

One baseline is to choose every starting position and extend rightward until a duplicate appears, using a set for the current candidate substring.

In the worst case, when all characters are distinct, this examines a quadratic number of character positions:

$$O(n^2)$$

The extra space is at most:

$$O(\min (n,|\Sigma |))$$

where $\Sigma$ is the set of possible characters.

The baseline is correct, and stating it matters. It demonstrates that you can always make progress even before you find the optimal approach. But for a large string, we can avoid reprocessing characters by retaining a single moving window.

Choose the sliding-window invariant

Maintain:

• windowStart: the first index of the current candidate window;
• windowEnd: the index currently being processed;
• lastSeen: a map from each character to its most recent index;
• bestLength: the maximum valid window length observed so far.

The invariant is:

Immediately after processing windowEnd, the substring from windowStart through windowEnd has no duplicate characters, and lastSeen records the most recent occurrence of every character processed.

When you encounter a character seen earlier:

• If its previous index is outside the current window, it is irrelevant.
• If its previous index is inside the current window, move windowStart to one position after that previous index.
• Update the character’s most recent index.
• Update the best length.

The subtle condition is that windowStart must never move backward.

Consider "abba":

Current character	Previous index	windowStart before	windowStart after	Valid window
a at index 0	none	0	0	a
b at index 1	none	0	0	ab
b at index 2	1	0	2	b
a at index 3	0	2	2	ba

At the last character, a was last seen at index 0, which is already before the current window. Resetting windowStart to 1 would be a bug because it would reintroduce a duplicate b. The condition previousIndex >= windowStart prevents that error.

Why the algorithm is correct

At each position, the algorithm preserves the invariant:

• If the current character does not appear in the current window, extending the window preserves uniqueness.
• If it does appear, moving windowStart just past its earlier occurrence removes the only duplicate caused by adding the current character.
• Storing the current index ensures the map remains accurate for future positions.

For every windowEnd, the algorithm holds the longest valid substring that ends at that position. Taking the maximum length across all positions therefore gives the global longest valid substring.

Each index is processed once, and windowStart only moves forward. With a hash map, expected running time is:

$$O(n)$$

The map stores at most one entry per distinct character encountered:

$$O(\min (n,|\Sigma |))$$

---

Java implementation with executable tests

This version makes the agreed contract explicit. It uses a HashMap because we need the most recent index of each character, not merely whether the character is present.

import java.util.HashMap;
import java.util.Map;

public final class LongestUniqueSubstring {

    private LongestUniqueSubstring() {
    }

    public static int longestUniqueSubstringLength(String text) {
        if (text == null) {
            throw new IllegalArgumentException("text must not be null");
        }

        Map<Character, Integer> lastSeenIndex = new HashMap<>();
        int windowStart = 0;
        int bestLength = 0;

        for (int windowEnd = 0; windowEnd < text.length(); windowEnd++) {
            char currentCharacter = text.charAt(windowEnd);
            Integer previousIndex = lastSeenIndex.get(currentCharacter);

            if (previousIndex != null && previousIndex >= windowStart) {
                windowStart = previousIndex + 1;
            }

            lastSeenIndex.put(currentCharacter, windowEnd);

            int currentLength = windowEnd - windowStart + 1;
            bestLength = Math.max(bestLength, currentLength);
        }

        return bestLength;
    }

    public static void main(String[] args) {
        expectEquals(0, longestUniqueSubstringLength(""));
        expectEquals(3, longestUniqueSubstringLength("abcabcbb"));
        expectEquals(1, longestUniqueSubstringLength("bbbbb"));
        expectEquals(3, longestUniqueSubstringLength("pwwkew"));
        expectEquals(2, longestUniqueSubstringLength("abba"));
        expectEquals(3, longestUniqueSubstringLength("dvdf"));

        try {
            longestUniqueSubstringLength(null);
            throw new AssertionError("Expected IllegalArgumentException for null input");
        } catch (IllegalArgumentException expected) {
            // Expected contract behavior.
        }

        System.out.println("All tests passed.");
    }

    private static void expectEquals(int expected, int actual) {
        if (expected != actual) {
            throw new AssertionError(
                    "Expected " + expected + " but got " + actual
            );
        }
    }
}

The test cases are deliberately selected:

Input	Expected length	What it tests
""	0	Empty-input boundary
"abcabcbb"	3	Standard repeated-character behavior
"bbbbb"	1	All characters identical
"pwwkew"	3	Window jumps past an internal duplicate
"abba"	2	Prevents the left boundary from moving backward
"dvdf"	3	A duplicate outside the current window must be ignored
null	Exception	Explicit input contract

In an interview, you need not write an entire main method unless asked. But you should be able to state these cases, trace at least one of them, and add lightweight test calls in the shared editor.

---

A concise presentation script

After planning and before coding, a complete explanation can sound like this:

“I’ll use a variable sliding window. The brute-force approach considers many overlapping substrings and is quadratic in the worst case. Instead, I’ll maintain a window containing no duplicate characters and a hash map from each character to its last index. When I see a character whose previous occurrence is still inside the window, I move the left boundary to one position after that occurrence. The left boundary only moves forward, so each character is processed a constant number of times. This is expected $O(n)$ time and $O(\min (n,|\Sigma |))$ space. I’ll preserve the invariant that the current window always contains unique characters.”

After coding, give a different, verification-oriented summary:

“I’ll test an empty string, a string with all duplicates, and abba, which checks that a previous occurrence before the current window does not move the left boundary backward. The map stores only the most recent index, so the window remains valid after each character. The final complexity remains expected $O(n)$ time and $O(\min (n,|\Sigma |))$ space.”

This is substantially stronger than ending with, “It should work.”

---

Recovering when the interview does not go to plan

A timed interview will not always be smooth. Your recovery behavior is itself evaluative.

If you do not find the optimal approach quickly

By roughly minute 10, state and implement a correct baseline if you have one.

“I have a correct quadratic approach. Given the remaining time, I’ll implement it cleanly first, then I’ll return to reducing repeated work if time permits.”

A correct baseline, clearly bounded and honestly evaluated, is far better than silently searching for a perfect solution.

If you find the pattern but are uncertain about correctness

State the invariant and trace a counterexample-prone input before coding. For sliding windows, strings such as "abba" and "tmmzuxt" reveal boundary-update bugs much faster than only testing "abcabcbb".

If your code has a bug

Do not apologize repeatedly or rewrite everything. Localize the failure:

1. State the failing input and expected behavior.
2. Trace only the relevant variables.
3. Identify the violated invariant.
4. Apply the smallest correction.
5. Retest the original case and one nearby case.

That is the same disciplined debugging behavior expected in production work.

If the interviewer asks for a broader variant

First clarify whether the original contract has changed. For example, asking for the actual substring requires retaining the best start index, not merely the best length. Asking for full Unicode code-point semantics changes the iteration strategy. Do not silently over-engineer the initial answer for every hypothetical extension.

---

Key takeaways

• A coding interview evaluates communication, problem solving, implementation, and testing, not merely whether the final code works.
• Use a time budget: clarify early, choose an approach before coding, preserve time for verification.
• Ask only clarification questions that affect the contract, algorithm, or boundary behavior.
• Present a baseline before the optimized solution; this shows structured reasoning and gives you a fallback.
• State an invariant before implementation. It is both a correctness tool and a communication tool.
• Test with intent: include a normal input, an empty or singleton boundary, and an adversarial case designed to expose a likely bug.
• When stuck, make your current reasoning visible and recover systematically rather than going silent.

You have completed the coding-pattern and interview-execution module. The next module moves to linear data structures, trees, heaps, and recursive search, beginning with monotonic stacks for next-greater-element and range-boundary problems.