Design comprehensive OA test cases

# A Repeatable, Time-Boxed Testing Approach ## 1) Workflow Overview (tight loop) - Clarify the contract: input domain, output format, tie-breaking rules, index base (0/1), stability, allowed ranges, and performance constraints. - Partition the input space (equivalence classes) and identify boundaries. - Draft 5–10 curated tests covering partitions and boundaries. - Implement a small, obviously-correct oracle (brute force or library) for small sizes; or define properties (metamorphic testing) if no exact oracle exists. - Build a tiny harness to run both solution and oracle on all cases (plus a brief fuzz pass) and diff outputs. - Add any failing random case to the curated set; iterate until stable. ## 2) Edge-Case Checklist (use for most algo/DS problems) Pick the items that apply to the problem type. - Size/shape - Empty input; minimal size (n=1); small n (2–5); near maximum allowed size. - Range/boundary values - Min/max integers; zeros; negatives; large magnitude; for floats: ±0, infinities, NaN (if applicable). - Ordering and structure - Already sorted; reverse sorted; random; nearly sorted; patterned (e.g., alternating high/low); all equal. - Duplicates/ties - No duplicates; many duplicates; ties that stress tie-breaking rules or stability. - Indexing/off-by-one - Edges around 0/1-based indexing; inclusive/exclusive interval ends; k=0/1/n cases for selection problems. - Content quirks - For strings: empty, whitespace, punctuation, Unicode, case sensitivity; for sets/maps: missing keys. - Graph/tree topology (if relevant) - Disconnected; single node; line/star/complete graphs; cycles vs DAG; degenerate trees (linked-list shape). - Constraints/validity - Invalid inputs if the problem allows/mentions them; error handling behavior. - Numeric robustness - Potential overflow; precision/tolerance for floats (define epsilon and comparison mode). - Determinism and stability - If multiple valid outputs, define comparison (order-insensitive, set equality, lexicographically smallest, stable output). - Performance edge - Larger random/structured case to smoke-test complexity (within platform time limits). Keep this as a mental (or written) checklist you can apply in minutes. ## 3) Quickly Generating Inputs and Expected Outputs Approaches (use one or combine): - Brute-force oracle (preferred when feasible) - Write a simple O(n^2) or backtracking solution for small n to be obviously correct. - Use it to compute expected outputs for small, curated and random cases. - Differential testing - Compare against a known-correct library or a trusted reference implementation (e.g., Python heapq for heap behavior, networkx for simple graph shortest paths on tiny graphs). - Metamorphic/property testing (when an exact oracle is hard) - Define properties that must always hold and use them as checks: - Idempotence: applying the function twice yields same result (e.g., sort(sort(x)) = sort(x)). - Invariance to permutation or scaling (where applicable). - Monotonicity: relaxing a constraint cannot reduce the optimum (e.g., with higher capacity, knapsack value should not decrease). - Decomposition/aggregation: f(a∪b) relates predictably to f(a) and f(b) (problem-dependent). - For floats, compare within tolerance: |a−b| ≤ 1e−9 or relative error criteria. - Hand-calculation for tiny cases - For 3–6 element examples, compute expected output manually to exercise corner logic. Small concrete example (Two-Sum variant) - Problem: given array nums and target T, return any pair of indices i≠j with nums[i]+nums[j]=T (order of indices unspecified). - Oracle (for n≤50): double loop over all pairs; return the first pair found using a canonical ordering (sorted indices) so comparisons are deterministic. - Properties: if you add a dummy element far from T, existing valid pairs remain valid; order of nums should not affect existence of a solution. ## 4) Comparing Against an Oracle (test harness) Harness essentials: - Unify IO - Normalize outputs before compare (e.g., sort pairs; convert lists to sets if order is irrelevant; define tie-breaking canonical form). - Deterministic randomness - Use a fixed seed for random case generation so failures are reproducible. - Diff and shrink - On mismatch, print minimal failing input; attempt to shrink by removing/perturbing elements while preserving failure (manual or simple heuristics). Add the reduced case to curated set. Minimal harness structure (language-agnostic pseudocode): - Define oracle(input) and solution(input). - For each curated test: assert normalize(solution(x)) == normalize(oracle(x)). - For k random tests (small n): generate x; compare; on fail, log seed and x; reduce and add to curated. ## 5) Deciding Coverage Is Sufficient (5–10 curated tests) Use a simple coverage matrix: rows = your equivalence classes; columns = chosen tests. Stop when: - Every applicable class has at least one representative test. - Boundary values for each dimension are hit (min, just-inside, just-outside when valid). - One degenerate case (empty/minimal) and one stress case (near-maximum) are included. - At least one adversarial/patterned input is included (e.g., all equal, reverse sorted). - A short fuzz run (e.g., 200–1000 small random cases) passes against the oracle or properties. A practical 10-case template (customize per problem): 1) Empty/minimal input. 2) Single element (or minimal valid multi-element input). 3) Two elements exercising both branches (e.g., in-order vs out-of-order). 4) Duplicates/ties that stress tie-breaking. 5) Mixed signs or 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 oracle, or a separate larger smoke test without oracle (property-checked only). 10) One random case with fixed seed; promote to curated if it ever fails. If you cannot write an exact oracle: - Replace exact comparisons with property checks and multiple metamorphic relations. - Use differential testing against two independent implementations (your own alternative approach or library) where possible. ## 6) Guardrails and Pitfalls - Define comparison semantics precisely (order-sensitive vs set equality; stability; index base). - For floating point, use absolute/relative tolerance; avoid direct equality. - Ensure deterministic outputs for multi-solution problems by canonicalizing. - Watch off-by-one errors around inclusive/exclusive ranges. - Log seeds and failing inputs; keep tests reproducible. ## 7) Summary Script You Can Execute Mentally in 5 Minutes - List partitions and boundaries using the checklist. - Draft 5–10 curated tests to cover them. - Code a tiny brute-force oracle for small n or define properties. - Build a minimal harness to run solution vs oracle, normalize outputs, and diff. - Run a short seeded fuzz; add any failing case to curated. - Stop when the coverage matrix is fully hit and fuzz is green.