The Slow Death of Assumptions: Time, Space, Testing, and Debugging

By FreePare Team · Fri Aug 07 2026 · 10 min read

A trace-first lab for C23, Java 25, and Python 3.14

"Fast enough" is not a property of source code. It is a claim about an implementation, an input distribution, a machine, a runtime, and a measurement. "Works on my machine" has the same weakness: it hides the conditions under which the observation was made.

This lab replaces both phrases with four artifacts: a cost model, an edge-case matrix, an exact build command, and a minimal reproducible failure.

Learning contract

You will learn to:

• define the input variable and counted operation before writing Big O;
• separate best, average, worst, and amortized cases;
• separate auxiliary space, call-stack space, retained input, and output space;
• build tests for empty, duplicate, boundary, malformed, Unicode, overflow, and resource-failure cases;
• turn a failing observation into a small program another developer can run;
• pass a 12-point exit lab with at least 10 points.

Twelve-minute baseline

Do not run code yet.

1. What is n when sorting strings: number of strings, total characters, or both?

2. Which operation are you counting in a hash-table lookup?

3. Can the same algorithm have O(n) best case and O(n^2) worst case?

4. Is recursion stack memory auxiliary space?

5. If a function must return n results, may you erase output space from the analysis?

6. Give one input that separates stable from unstable sorting.

7. Which test exposes mid = (low + high) / 2 overflow?

8. Is one emoji always one Java char?

9. What happens if a successful fwrite is followed by a failing fclose?

10. Which compiler warning would you enable before opening a debugger?

11. What is the smallest input that reproduces your current bug?

12. Which environment facts must accompany a benchmark?

Score 10-12: go to the exit lab. Score 7-9: focus on the missed section. Below 7: complete the worked trace in order.

1. Build a cost model before writing Big O

An analysis is incomplete until it names:

• the input variables;
• the counted operation;
• the case being analyzed;
• auxiliary and output space separately;
• assumptions about libraries and representations.

Worked comparison: duplicate detection

Suppose the input is an array of n integers.

static boolean hasDuplicateSlow(int[] values) {
    for (int i = 0; i < values.length; i++) {
        for (int j = i + 1; j < values.length; j++) {
            if (values[i] == values[j]) {
                return true;
            }
        }
    }
    return false;
}

Count integer-equality comparisons.

• Best case: the first pair matches, so the count is 1, or Theta(1).
• Worst case: all values are distinct, so the count is (n - 1) + ... + 1 = n(n - 1)/2, or Theta(n^2).
• Auxiliary space: Theta(1).
• Output space: Theta(1).

Now trade memory for expected speed:

import java.util.HashSet;
import java.util.Set;

static boolean hasDuplicateExpectedLinear(int[] values) {
    Set<Integer> seen = new HashSet<>();
    for (int value : values) {
        if (!seen.add(value)) {
            return true;
        }
    }
    return false;
}

Under the documented hash-table assumptions, this performs n expected constant-time insert attempts: expected Theta(n) time and Theta(n) auxiliary space. It is not a universal worst-case Theta(n) claim. Java's HashSet documentation explicitly frames basic-operation performance in terms of proper hash dispersion.

Multiple input variables matter

For containsCommon(a, b), write n = a.length and m = b.length. A nested comparison is O(nm), not automatically O(n^2). Building a set from a and scanning b is expected O(n + m) time with O(n) auxiliary space.

For a graph, use V vertices and E edges. For strings, you may need both item count and total character/code-unit count. One symbol called n can hide the real workload.

Amortized is not average

Appending to a dynamic array occasionally triggers allocation and copying. One append can cost Theta(n), while a sequence of appends has constant amortized cost per append under geometric growth. Amortized analysis bounds a sequence of operations; average-case analysis assumes a probability distribution. They answer different questions.

Space has categories

For a recursive depth-first traversal of a tree with height h:

• the input tree is retained input, not newly allocated auxiliary storage;
• recursion uses Theta(h) call-stack space;
• an output list of all values uses Theta(n) output space;
• any separate visited set uses Theta(n) auxiliary heap space.

On a balanced tree, h is logarithmic. On a chain-shaped tree, h = n. The algorithm name "DFS" does not determine the stack depth; the input shape does.

String construction counterexample

This Java loop repeatedly creates larger immutable strings:

static String joinBad(String[] parts) {
    String result = "";
    for (String part : parts) {
        result += part;
    }
    return result;
}

If total output length is L, the simple copying model can accumulate quadratic work. Use a builder so growth is explicit:

static String joinBetter(String[] parts) {
    StringBuilder result = new StringBuilder();
    for (String part : parts) {
        result.append(part);
    }
    return result.toString();
}

Do not claim a precise runtime from Big O alone. Constants, allocation strategy, cache behavior, JIT compilation, and input distribution still matter.

2. Build an edge-case matrix

Tests should attack the contract, not decorate the happy path.

Safe midpoint

Use this form for an inclusive integer search range:

int mid = low + (high - low) / 2;

It avoids overflowing the addition low + high when both endpoints are large and non-negative.

Why that form and not the obvious one is a question about the type rather than about search: Integer Boundaries works through what the addition does when it leaves the range, and Loops That Finish and Functions You Can Trust works through where the check belongs in the contract.

Unicode is a representation problem

Java String uses UTF-16 code units; char is a 16-bit code unit, not a universal character container (JLS 4.2.1 and 4.3.3). Python strings are sequences of Unicode code points, but user-perceived grapheme clusters may still contain multiple code points (Python str).

Test at least:

ASCII:        A
Precomposed:  é
Combining:    e + U+0301
Supplementary: 😀

If the requirement is "reverse what the user sees," neither a byte reversal nor a naïve code-unit reversal is sufficient.

Bytes, Bounds, and Unicode Gremlins takes this apart unit by unit — bytes, code units, code points, grapheme clusters — and shows which API counts which.

Parsing must consume what the contract requires

In Java, distinguish "parse an integer token" from "accept an integer prefix." A strict parser should reject trailing junk:

static int parseAge(String raw) {
    String value = raw.strip();
    int age = Integer.parseInt(value);
    if (age < 0 || age > 150) {
        throw new IllegalArgumentException("age out of range: " + age);
    }
    return age;
}

The syntax check and domain-range check are separate responsibilities.

3. Make the build reproducible

Record tool versions and run from a clean directory.

C23 with GCC

gcc --version
gcc -std=c23 -Wall -Wextra -Wpedantic -Wconversion -Wshadow \
  -fsanitize=address,undefined -g demo.c -o demo
./demo

Treat warnings as review inputs before enabling -Werror for a controlled build. GCC documents both warning options and instrumentation options.

Java 25

java --version
javac --release 25 -Xlint:all Demo.java
java -ea Demo

Assertions are useful for internal invariants in a lab, but public input validation must not depend on -ea because assertions can be disabled.

Python 3.14

python3.14 --version
python3.14 -X dev -m unittest -v
python3.14 -m pdb failing_case.py

Use the standard pdb debugger and tracemalloc when allocation evidence matters.

Formatting belongs in the reproducible workflow too. Pin formatter and linter versions in the project rather than assuming every machine uses the same defaults.

4. Turn a bug into evidence

Use this reduction loop:

1. Write the exact observed result and expected result.

2. Freeze the failing input.

3. Record language, compiler/runtime, flags, operating system, and architecture.

4. Remove unrelated I/O, frameworks, concurrency, and data.

5. Keep removing code until one more removal makes the failure disappear.

6. Add one assertion that fails for the bug.

7. Fix the cause, then keep the assertion as a regression test.

Example bug:

int last(const int *values, size_t length) {
    return values[length];
}

Minimal failing input: one-element array, length = 1. The valid last index is length - 1. With AddressSanitizer, the failure becomes a concrete out-of-bounds report instead of a vague "sometimes crashes" description.

The repaired contract must also decide what happens when values == NULL or length == 0. Returning a sentinel may be ambiguous; an output parameter plus status code can represent failure explicitly.

Benchmark without lying to yourself

A defensible benchmark records:

• exact source revision and build flags;
• warm-up policy for managed runtimes;
• input generator, size, and distribution;
• number of forks/runs and raw measurements;
• CPU, memory, OS, and runtime versions;
• what was included or excluded from timing;
• median and spread, not only the best run.

Do not time logging, file generation, or random-data construction unless those operations belong to the workload. Do not publish a single number as if it were a law of the algorithm.

Exit lab

Twelve points across the four artifacts this lab is named for, and the learning contract sets the pass mark at ten. The two points you can afford to lose may not all come from one artifact.

1. A cost model (3 points). For containsCommon(a, b), write the input variables, the counted operation, the case, and auxiliary and output space separately — once for the nested comparison and once for the set-and-scan version. One point for naming two input variables instead of one n; one for stating which operation you counted; one for keeping auxiliary space and output space apart.

2. An edge-case matrix (3 points). Take binary search over a sorted int[] and fill every row of the matrix in section 2 with a concrete input rather than a description. One point for an input that would overflow the unsafe midpoint; one for an input that separates "found an occurrence" from "found the first occurrence"; one for the empty array.

3. An exact build command (3 points). Write the commands that reproduce your run in the language you used: version, build flags, execution. One point for pinning the version, one for the warning flags, one for saying which of those flags would have caught the bug in task 4 before a debugger was opened.

4. A minimal reproducible failure (3 points). Start from last() in section 4 and run the seven-step reduction until one more removal makes the failure disappear. One point for the frozen input, one for an assertion that fails for the bug and stays after the fix, one for the environment facts recorded beside the result.

The whole lab is one habit under four names, so score it that way: any task that states a result without the conditions under which it was observed loses its last point, however correct the result is.

Tags: coding-interview-patterns, computer-science-fundamentals, coding-practice, coding-fundamentals, coding-interview-tips, programming-fundamentals, problem-solving-framework, technical-interview-basics