Testing adversarial inputs

How do you choose an approach?

Choosing an approach means connecting the problem’s required operations to the structures and algorithms you have learned. Start with the input, the requested output, and the constraints. Build a simple correct solution, identify its expensive work, and look for a structure that avoids repeating it.

Example: If a solution repeatedly scans earlier values to ask “have I seen this before?”, consider a set. If it repeatedly sums fixed ranges in unchanged data, consider prefix sums. Explain why the chosen approach fits before writing code.

Understand the idea

Adversarial tests target assumptions rather than random variety alone. Include empty/singleton, duplicates, all-negative, monotone, disconnected, overflow-scale, and equal-boundary inputs as relevant. Differential tests compare independent algorithms on small domains.

Work through an example

The lab checks 605 combinations of short arrays over {-1,0,1} and five targets. These expose repeated prefixes and negative sums, while keeping a trustworthy baseline affordable.

Time and space complexity

Exhaustive testing is exponential in length, so bound the domain deliberately.

Why it works

Every test's expected answer comes from the contract or an independent reference calculation.

Common mistakes

A fixed handful of examples is not exhaustive.
A seeded random test is reproducible but still limited.

Chapter lab · Python implementation

Interview readiness means selecting an approach without a chapter label. The lab compares an obvious quadratic subarray-sum baseline with prefix hashing on exhaustive small inputs. Work from a contract, articulate why the optimized state is sufficient, then use counterexamples and delayed review to expose fragile reasoning.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

from itertools import product

def brute_count(values,target):
    count=0
    for left in range(len(values)):
        total=0
        for right in range(left,len(values)):
            total+=values[right]
            count+=total==target
    return count

def fast_count(values,target):
    frequencies={0:1}; prefix=answer=0
    for x in values:
        prefix+=x
        answer+=frequencies.get(prefix-target,0)
        frequencies[prefix]=frequencies.get(prefix,0)+1
    return answer

def verify_small():
    cases=0
    for length in range(5):
        for values in product([-1,0,1],repeat=length):
            for target in range(-2,3):
                assert brute_count(values,target)==fast_count(values,target)
                cases+=1
    return cases

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert verify_small()==605
assert fast_count([1,-1,1],1)==3
assert brute_count([],0)==0

CHECK YOUR UNDERSTANDING