· By John Kavanagh

Testing an Algorithm When the Example is Not Enough

The objective lenses and stage of a laboratory microscope.
Image by Akram Huseyn, licensed from Unsplash.

The example passes. That's encouraging, but it mostly tells us that the implementation agrees with one example chosen to explain the question. It doesn't tell us whether the code understands the rule that example was illustrating.

I want algorithm tests to challenge the decision the implementation makes. If a loop is supposed to prevent reusing an item, the tests should contain an input where reuse changes the answer. If a query includes its right endpoint, the tests should notice when that endpoint quietly disappears.

This doesn't require a vast testing framework. A small, obviously correct reference and a carefully bounded collection of inputs often provide more useful evidence than a long list of familiar examples. The important part is making the reference independent of the optimisation we're trying to verify.


Write the Promise Before the Test Cases

Start by stating the accepted inputs and the meaning of the output. Are values unique? Can they be negative? Are range endpoints inclusive? Does order matter in a counted result? May the implementation mutate the input?

Those questions decide what a test should assert. A function that returns a valid optimum may be correct even if it chooses a different tied answer from our preferred example. Conversely, a function returning the right value whilst unexpectedly rearranging the input may violate a caller's expectations.

Separate promised inputs from unsupported ones. A judge may guarantee a non‑empty rectangular matrix, so a solution need not handle a ragged array. A public utility may need validation. Testing the latter behaviour is sensible only when we've decided to provide it.

I also distinguish mathematical correctness from numeric representation. Integer counting, floating‑point approximation, overflow, and input size can each impose different limits. An expected result copied from an imprecise calculation isn't made exact by putting it in an assertion.


Build a Slow Reference with Fewer Ideas in It

An optimised implementation usually saves work by remembering a summary or skipping candidates. Its reference can afford to do that work directly on small inputs.

For a range sum, add every element in the requested interval. For a subset problem, enumerate subsets. For a shortest path on a tiny graph, compare with a different established method or exhaustive simple paths where the problem permits them. The reference should be easy to inspect, not impressive.

The phrase "independent" matters. If the production function uses a prefix difference and the test calculates its expected answer using the same prefix difference, both can share the same off‑by‑one error. Two implementations of one mistake do not form a consensus worth keeping.

Independence isn't absolute. Both versions still rely on the language and the problem's definition. The useful aim is to remove the particular recurrence, index transformation, or optimisation that is most likely to be wrong.


A Complete Small‑Input Verifier

Here is a prefix‑sum query implementation together with a direct‑sum reference. The verifier generates every array of lengths one through five over the values minus one, zero, and one, then checks every valid inclusive range.

type RangeQuery = (left: number, right: number) => number;

const makeRangeQuery = (values: readonly number[]): RangeQuery => {
  const prefix: number[] = [0];
  for (const value of values) {
    prefix.push(prefix[prefix.length - 1] + value);
  }
  return (left, right) => prefix[right + 1] - prefix[left];
};

const directSum = (
  values: readonly number[],
  left: number,
  right: number,
): number => {
  let total = 0;
  for (let index = left; index <= right; index += 1) total += values[index];
  return total;
};

const verifyRangeQueries = (
  build: (values: readonly number[]) => RangeQuery,
): number => {
  let checked = 0;
  for (let length = 1; length <= 5; length += 1) {
    for (let encoded = 0; encoded < 3 ** length; encoded += 1) {
      let remaining = encoded;
      const values = Array.from({ length }, () => {
        const value = (remaining % 3) - 1;
        remaining = Math.floor(remaining / 3);
        return value;
      });
      const query = build(values);
      for (let left = 0; left < length; left += 1) {
        for (let right = left; right < length; right += 1) {
          const expected = directSum(values, left, right);
          const actual = query(left, right);
          if (actual !== expected) {
            throw new Error(JSON.stringify({ values, left, right, expected, actual }));
          }
          checked += 1;
        }
      }
    }
  }
  return checked;
};

const checked = verifyRangeQueries(makeRangeQuery);
console.log(`Checked ${checked} ranges.`);

Compile this as TypeScript for a modern JavaScript runtime, then run the emitted JavaScript. It has no package imports or test‑runner dependency. A successful run prints Checked 4647 ranges.; a failure throws an error containing the exact array, endpoints, expected total, and actual total.

The generator treats the encoded counter as a base‑three number. Each digit selects one of the three permitted values, so every array in the chosen domain appears once. There are 363 arrays in total. For length n, there are n × (n + 1) / 2 inclusive ranges, which explains why the query count exceeds the array count.

The reference adds source elements directly. It doesn't share the prefix array or its endpoint conversion. Negative values and zeroes make cancellation visible, whilst single‑element ranges expose missing endpoints immediately.


State Exactly What Exhaustive Means

This verifier is exhaustive over a deliberately small domain. It isn't exhaustive over all JavaScript arrays, all integer magnitudes, or the maximum input size permitted by an interview problem.

That qualification is useful evidence, not an apology. Small domains exercise combinations densely. Larger targeted cases then cover limits the small domain cannot reach, such as stack depth, numeric magnitude, long carry chains, or the allocation size of a table.

For the range‑sum example, add a maximum‑length array and values near the problem's permitted extremes. Those tests check arithmetic bounds and construction behaviour. They do not need every possible range if a few strategically chosen intervals cover the specific concern.

Keep performance claims separate. Passing a large input establishes that this run completed, not a portable latency guarantee. A benchmark needs a defined workload, runtime, environment, and measurement method. A correctness loop is not a benchmark merely because we looked at a clock afterwards.


Check Properties Without Mistaking Them for Answers

A property states a relationship between results. Splitting a range into two adjacent pieces should preserve its total. Reversing an array and reflecting the query coordinates should preserve a corresponding sum. Querying the same range twice should give the same result.

These checks are valuable because they can generate related tests without requiring a new handwritten answer for each one. They are also incomplete. A function that returns zero for every query satisfies the splitting property, so that property alone proves very little.

For a counting problem, permuting input values might preserve the result if positions are otherwise interchangeable. Appending a zero doubles the number of sign assignments in Target Sum, but it does not double the result of every counting algorithm. Properties belong to the question, not to the general category "dynamic programming".

My guide to choosing dynamic‑programming state helps identify which choices a state represents. That same definition often suggests useful properties and, just as usefully, tells us which tempting properties are false.


Deliberately Break a Plausible Line

To see whether a test protects an important behaviour, introduce a small known fault locally. In this example, change the query from prefix[right + 1] - prefix[left] to prefix[right] - prefix[left]. The first non‑zero single‑element range should expose it.

Restore the correct code after observing the failure. The retained evidence should identify the mutation and the failing input, not leave an accidentally broken implementation as the final artefact.

Other useful mutations include reversing a knapsack loop, removing a zero base case, changing a strict comparison to a non‑strict one, or allocating matrix rows with a shared reference. Each mutation represents a real misunderstanding the explanation is supposed to prevent.

A mutation surviving the suite means the tests didn't distinguish it on the tested inputs. Sometimes the mutation is equivalent under the promised constraints; sometimes the suite has a gap. Inspect it before declaring a percentage meaningful. A score without that judgement is another number looking for a job.


Make Random Failures Reproducible

Random generation can reach shapes a small alphabet misses, but an unrecorded random failure is difficult to investigate. Use a deterministic generator or retain the seed, input, and generator version needed to reproduce the case.

When a large generated case fails, shrink it. Remove elements, reduce magnitudes, or simplify edges whilst keeping the failure. A minimal counterexample often explains the mistaken invariant much faster than a screen full of data.

Keep the reduced case as a named regression alongside the broader generator. The generator explores; the small case communicates. They serve different purposes and don't need to compete for the same test.

For floating‑point algorithms, retain the tolerance and expected magnitude too. A failure caused by a test demanding bit‑for‑bit equality after a different multiplication order needs a different response from a sign error or an overflow.


Preserve the Example People Actually Read

An article can have a correct tested implementation and an incorrect displayed snippet if the two copies drift. I prefer extracting or comparing the exact code used in the article with the source being compiled and executed.

The same principle applies to documentation in a repository. Verify the public example, including its setup assumptions and expected output, rather than a nearby helper that happens to share its name. If a code renderer changes whitespace or adds presentation markup, inspect the displayed code as well as its stored source.

For ordinary repository tests, use the existing runner and assertion conventions. Node's strict assertion API is also useful for small standalone verifiers. The inline example throws directly so that its only moving parts are the generator, reference, implementation, and comparison.

My Subarray Sum Equals K article builds on prefix totals for a more involved counting problem. A direct enumeration of all small subarrays makes a useful independent reference there, too, even though it would be too slow as the final algorithm.


Finish with Evidence You Can Explain

For a review, I'd record the exact source version, the reference strategy, the generated domain, selected limit cases, and any known limitations. If a deliberate fault was rejected, record which one. If a test couldn't run, say so rather than treating preparation as execution.

The aim isn't to produce the largest possible test count. It's to make a credible connection between the problem's rules and what the implementation has actually demonstrated.

One passing example is a useful beginning. An independent reference, bounded exhaustive checks, targeted limits, and a few well‑chosen properties turn that beginning into something I'd be comfortable maintaining.


Looking for technical direction?

I support teams that need senior judgement on React, Next.js, headless CMS architecture, performance, migrations, and technical SEO.