Skip to main content
CodeSparring

Check it against a version that is obviously correct

Level 5: Level 5: Judging Code You Did Not Writemedium24 mindifferential testingbrute forcecode reviewverification

Write the slow, dull, clearly-right implementation and make the clever one agree with it. A brute force you trust is a specification you can execute.

When you cannot tell by reading

Some code is optimized past the point where reading it settles the question. A single pass with a dictionary replaces a double loop, and now correctness depends on an argument about what the dictionary holds at each step. You can follow that argument, and you can also be wrong about it, confidently, in about forty seconds.

There is a way out that costs almost nothing. Write the version that is too slow to ship and too simple to be wrong, then make the fast one agree with it on every input you can generate.

def count_pairs_slow(nums, target):
    """Every pair, checked directly. Quadratic and obviously right."""
    total = 0
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                total += 1
    return total

Nobody ships this. But as a reference oracle it is worth more than the clever version, because you can verify it by reading it once, and then it verifies everything else for free.

Check yourself
Your quadratic reference and the generated single-pass version disagree on one input. What have you learned?

The differential loop

Generate inputs, run both, compare, stop at the first disagreement.

def first_disagreeing_target(nums, targets):
    for target in targets:
        if count_pairs_fast(nums, target) != count_pairs_slow(nums, target):
            return target
    return -1

That is the whole technique. Its power comes from where the inputs come from: you no longer have to be clever about choosing them, because you are not predicting the answer, only comparing two answers. So you can throw thousands of ugly inputs at it, including inputs you would never have thought to write down.

The inputs that find bugs fastest are the ones with structure a human would not bother typing: lots of duplicates, all the same value, everything negative, one element, empty.

Check yourself
A single-pass version tracks values it has seen in a set: for n in nums, if target - n in seen: total += 1, then seen.add(n). With nums = [1, 1, 1] and target = 2, what does it return, and what is right?

When the oracle is the shipped code

Differential testing is not only for speed. It is the fastest way to review a rewrite, a refactor, or a migration, because you already have a version everyone trusts: the one in production.

for row in sample_rows:
    assert new_pricing(row) == old_pricing(row)

Every disagreement is either a bug in the new code or an undocumented behavior of the old code that somebody depends on. Both are things you want to find before the deploy rather than after.

Check yourself

Sort each review situation by whether a reference oracle is available to you cheaply.

A single-pass rewrite of a function that used to use two nested loops
A new pricing rule that has never existed before
A caching layer added in front of an existing lookup
A generated regex replacing a hand-written parser
A first implementation of a recommendation ranking

The two ways this goes wrong

The oracle is wrong too. If you write the reference from the same misunderstanding of the contract, both versions agree and both are wrong. Guard against it by making the reference dumb enough that its correctness is visible in one reading, and by keeping a couple of hand-checked examples alongside.

Nothing generates interesting inputs. A differential loop over ten hand-picked ordinary inputs finds nothing that ten ordinary example tests would not. The inputs have to include the shapes you find uncomfortable.

Interview nuance: offering to write the brute force first is a strong move in an interview, not a weak one. "Let me get the obviously correct version down so I have something to check the optimized one against" shows you know that the optimization is the risky part. Plenty of candidates jump straight to the clever solution and then cannot tell whether it works.

Check yourself
You have a trusted quadratic reference and a generated linear version. You run 10000 random lists of length 5 through both and find no disagreement. What is the honest conclusion?
Worked example (Python)
def count_pairs_slow(nums, target):
    total = 0
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                total += 1
    return total


def count_pairs_fast(nums, target):
    seen = set()
    total = 0
    for n in nums:
        if target - n in seen:
            total += 1
        seen.add(n)
    return total


print(count_pairs_slow([1, 1, 1], 2), count_pairs_fast([1, 1, 1], 2))   # 3 2

Apply

Your turn

The task this lesson builds to.

Write a function first_disagreeing_target(nums, targets) that returns the first value in targets for which count_pairs_fast(nums, target) disagrees with count_pairs_slow(nums, target), or -1 when the two agree on every target in the list.

Both functions are in the starter. count_pairs_slow is the reference oracle: it checks every pair directly, so it is slow and correct. count_pairs_fast is the single-pass version under review. Neither should be changed. No target in the graded inputs is negative, so -1 is safe as the "they always agreed" answer.

Keep first_disagreeing_target as the last function in the file.

3 hints and 4 automated checks are waiting in the workspace.

Practice

Make it stick

A second problem on the same idea, so it survives past today.

A leaderboard service needs the top scores for a game, and four implementations are sitting in a pull request. All four look reasonable, all four return the right answer in the reviewer's manual test, and the service has started serving a leaderboard that is subtly wrong for some games.

Write a function check(name) that returns True only when the candidate stored under name is a correct top_k, and False otherwise.

The contract: top_k(scores, k) returns the k largest scores in descending order, keeping duplicates. k may be 0, and it may be larger than the list, in which case every score is returned. The caller's list must not be modified.

sorted(scores, reverse=True)[:k] is a correct and obviously right oracle, so use it to produce the expected value rather than writing expectations by hand. Keep check as the last function in the file.

3 hints and 4 automated checks are waiting in the workspace.