# A Repeatable, Time-Boxed Approach to Self-Designed OA Test Cases The core idea: testing on an OA is not "type in a few inputs and hope." It is a tight, repeatable loop you can run in a few minutes per problem: > **clarify the contract → partition the input space → curate 5–10 cases → check against an oracle or invariants → short seeded fuzz → promote failures → stop on a coverage rule.** The four things the question asks for map directly onto stages of that loop, so I'll walk them in order and then cover the harness, the stopping rule, and the pitfalls. --- ## 0) First, clarify the contract Before writing any test I nail down the spec, because most "edge-case" surprises are actually under-specified-contract surprises: - **Input domain:** value ranges, allowed types, size limits, whether invalid/degenerate inputs are in scope. - **Output contract:** format, index base (0- vs 1-based), inclusive/exclusive interval ends. - **Tie-breaking:** is *any* valid answer accepted, or is there a required canonical/lexicographically-smallest output? This single question decides whether I can compare exact outputs against an oracle, or must instead check *validity*. - **Performance:** the size ceiling and time limit — a correct-but-slow solution can still fail. This step is what makes the rest reusable: every later decision (how to compare, what to fuzz) flows from the contract. --- ## 1) A repeatable edge-case checklist (applies to most algo / DS problems) I keep a fixed mental checklist and pick the rows that apply. The value is that I never have to invent a test plan from scratch. - **Size / shape:** empty input; minimal ($n=1$); small ($n=2$–$5$); near the maximum allowed size. - **Range / boundary values:** min/max integers; zeros; negatives; very large magnitude; for floats: $\pm 0$, infinities, NaN where applicable. - **Ordering / structure:** already sorted; reverse sorted; nearly sorted; random; patterned (alternating high/low); all-equal. - **Duplicates / ties:** none; many duplicates; ties that stress tie-breaking or stability. - **Indexing / off-by-one:** edges around 0- vs 1-based indexing; inclusive vs exclusive interval ends; $k = 0, 1, n$ for selection/window problems. - **Content quirks:** strings — empty, whitespace, punctuation, case, Unicode; maps/sets — missing keys, collisions. - **Graph / tree topology (if relevant):** single node; disconnected; line/star/complete; cycle vs DAG; degenerate tree (linked-list shape). - **Validity:** invalid inputs *only if the problem says they can occur*; otherwise don't waste time on them. - **Numeric robustness:** overflow (e.g. sum of large $n$ large values); float precision/tolerance. - **Multiplicity / determinism:** if several outputs are valid, decide the comparison mode (set equality, order-insensitive, canonical form) up front. - **Performance edge:** one large structured/random case to smoke-test that complexity fits the time limit. This is the heart of the answer to sub-ask (1): it's a *reusable* partition of the input space (equivalence classes) plus the *boundaries* of each class. --- ## 2) Quickly generating inputs and expected outputs The bottleneck is rarely the input — it's the *expected output*. I use, in rough order of preference: **a. Brute-force oracle (preferred when feasible).** Write a deliberately simple, "obviously correct" solution for small $n$ — an $O(n^2)$ scan, full backtracking, exhaustive enumeration. It does not need to be fast; it needs to be unarguably right. Then use it to compute expected outputs for both my curated cases and a stream of random small cases. This converts "hand-compute the answer" (slow, error-prone) into "trust a trivial program." **b. Differential testing against a trusted reference.** Compare against a known-correct library on small inputs — e.g. Python `heapq` for heap behavior, `sorted` for ordering semantics, `itertools` for combinatorics, a simple library shortest-path on tiny graphs. Two independent implementations agreeing is strong evidence. **c. Hand-calculation for tiny cases.** For 3–6 element inputs I compute the answer by hand. These are the cases I most trust and the ones that catch corner logic the brute force might share. **d. Property / metamorphic testing — when no exact oracle is cheap.** When I can't produce *the* answer (e.g. "return any valid pair", or a hard optimization where brute force is exponential beyond tiny $n$), I assert invariants that any correct output must satisfy: - **Idempotence:** $\text{sort}(\text{sort}(x)) = \text{sort}(x)$. - **Permutation invariance:** shuffling the input must not change the *existence* of a solution (and for order-insensitive answers, not the answer set). - **Monotonicity under relaxed constraints:** raising knapsack capacity cannot *decrease* the optimal value. - **Validity check:** for "return any valid pair $(i,j)$ with $\text{nums}[i] + \text{nums}[j] = T$," I don't need the oracle's exact pair — I just verify the returned pair satisfies the constraint (or, if the answer is "no pair exists," that brute force agrees no pair exists). For floats I always compare with tolerance: $|a - b| \le \varepsilon$ (absolute) or a relative-error criterion — never `==`. **Concrete mini-example (Two-Sum-any-pair):** - Oracle for $n \le 50$: double loop returning the first valid pair in canonical (sorted-index) order. - Comparison: don't compare the pair directly (multiple pairs may be valid) — instead **check validity** of my output and only fall back to "both say no solution" when the array has none. - Metamorphic check: appending an element far from $T$ must not destroy an existing valid pair. --- ## 3) Comparing against the oracle (and writing one yourself) **When the platform gives an auto-generated reference answer:** I feed it my own inputs and read back the correct output, then compare. The only real work left is generating diverse inputs (step 2) — but I still have to compare *correctly* (below), because the reference often emits one specific valid answer among many. **When I must supply correctness myself:** the brute force from step 2a *is* my oracle; for "any valid answer" problems my **validity checker** is the oracle. **Comparison discipline (this is where naive testing silently lies):** - **Normalize / canonicalize** before comparing: sort pairs/lists, convert to a set when order is irrelevant, round floats, pick a canonical tie-break — otherwise two correct answers look like a mismatch. - **Set vs order-sensitive vs validity:** choose deliberately per the contract from step 0. For multi-solution problems, prefer a *validity* check over exact equality. - **Deterministic randomness:** seed the random generator so any failure is reproducible. - **Shrink on failure:** when a random case fails, reduce it (drop/perturb elements while it still fails) to the minimal reproducing input, then **promote it into the curated set** so it never regresses. --- ## 4) Deciding coverage is sufficient (and stopping under time pressure) I stop based on a small **coverage matrix**, not a gut feeling: rows = applicable equivalence classes from the checklist, columns = my chosen tests. I submit when: - Every applicable class has at least one representative. - Each dimension's boundaries are hit (min, just-inside, just-outside-when-valid). - At least one degenerate case (empty/minimal) **and** one stress case (near-maximum) are present. - At least one adversarial/patterned input is included (all-equal, reverse-sorted, degenerate topology). - A short **seeded fuzz** pass (a few hundred to ~1000 small random cases) is green against the oracle or properties. A practical ~10-case template, customized per problem: 1. Empty / minimal input. 2. Single element (or minimal valid multi-element input). 3. Two elements exercising both branches (in-order vs out-of-order). 4. Duplicates / ties that stress tie-breaking. 5. Mixed signs / special values (negatives, zeros, large magnitude). 6. Already-sorted structure. 7. Reverse-sorted structure. 8. Patterned adversarial input (all-equal, alternating extremes, or degenerate tree/graph). 9. Near-maximum size *small enough for the oracle*, or a separate larger smoke test checked only by properties/timing. 10. One seeded random case; promote it to curated if it ever fails. **Time-budget triage** (the realistic OA situation): I front-load the highest-leverage cases — empty/minimal, the boundary of each dimension, and the multi-solution comparison trap — because those catch the most bugs per minute. If I have one slot left, I spend it on the *untested* edge category most likely to be exercised by hidden tests rather than re-eyeballing code I already trust; once the coverage matrix is filled and fuzz is green, I submit rather than gold-plating. --- ## Harness sketch (language-agnostic) ``` seed_rng(FIXED_SEED) def check(x): got = solution(x) if has_exact_oracle: assert normalize(got) == normalize(oracle(x)), (x, got) else: assert is_valid(x, got) and satisfies_properties(x, got), (x, got) for x in curated_tests: check(x) for _ in range(N_FUZZ): # small n only x = gen_random_small() try: check(x) except AssertionError as e: x_min = shrink(x) # minimize failing input log(seed, x_min) curated_tests.append(x_min) ``` Key properties: fixed seed (reproducible), normalization before compare, validity fallback when there's no exact answer, and automatic promotion of failures. --- ## Pitfalls and guardrails - **Off-by-one / interval ends:** test inclusive vs exclusive and the 0- vs 1-based boundary explicitly. - **Overflow:** test sums/products that exceed 32-bit (and watch the language's integer semantics). - **False mismatches:** unspecified output order is the #1 cause of "my correct code fails my own test" — canonicalize or check validity. - **Float equality:** always tolerance-based. - **Reproducibility:** log seeds and failing inputs. --- ## Addressing the follow-ups - **Correlated-bug blind spot (oracle and solution share the same misreading of the spec):** This is the real limit of differential testing — two implementations built from the same wrong mental model agree on every case. Mitigations: derive the oracle from a *different* angle (exhaustive enumeration vs the clever algorithm), add **hand-calculated** tiny cases (an independent third source of truth), and use **metamorphic** properties that follow from the problem statement rather than from my interpretation of it. Re-reading the spec against the failing-looking sample tests is also a tell. - **Checking "any valid answer" without enumerating:** Write a **validity predicate**, not an output comparator — verify the returned answer satisfies all constraints (e.g. the pair sums to $T$, the schedule violates no precedence, the path is connected and within budget). That checks *validity*. Checking **optimality** is harder: I need either a brute-force optimum to compare the *objective value* (not the answer itself) against, or a proven bound; validity alone won't catch a sub-optimal-but-feasible answer. - **Bugs small-$n$ testing can never surface:** Anything that only appears at scale — **time-limit / complexity** failures (an $O(n^2)$ that passes $n=20$ but TLEs at $10^5$), **integer overflow** that only triggers with large magnitudes/counts, recursion-depth/stack limits, and memory limits. For those I add a *large* smoke test checked only by timing and invariants (no oracle): confirm it finishes within the limit and that cheap properties still hold, and I reason about the complexity directly rather than relying on the oracle. - **Two minutes left, one untested category:** Decide by *expected value*. If the untested category is plausibly in the hidden tests and cheap to construct (e.g. empty input on a parsing problem), add the case. If the code path is simple and I've already eyeballed it, a quick targeted re-read may catch more than another similar case. If the coverage matrix is otherwise full and fuzz is green, submit — chasing marginal coverage past that point usually costs more than it returns. --- ## Summary (the 5-minute script) 1. Clarify the contract (ranges, index base, tie-breaking, perf). 2. List partitions + boundaries from the checklist. 3. Curate 5–10 cases covering them. 4. Build a tiny brute-force oracle for small $n$, or define validity/metamorphic properties. 5. Run a minimal harness: normalize outputs, diff or check validity, short seeded fuzz; promote failures. 6. Stop when the coverage matrix is full and fuzz is green — then submit.