Big O you can measure, and why hash sets win

#Why it matters

Few job descriptions name data structures and algorithms, yet most software hiring processes include a coding round built on them. Interviewers want an efficient approach, a clear statement of its cost, and correct code. The most common single improvement is replacing a nested loop with a hash map or set.

#The concept

Big O describes how running time or memory grows with input size n, ignoring constants:

Hash maps and sets (Python dict and set, Java HashMap and HashSet) give average O(1) insert and lookup. Trading O(n) extra memory for O(1) lookups turns many O(n squared) problems into O(n).

How to answer: state the brute force and its complexity, improve it, state the new time and space complexity, then code it and test edge cases (empty input, one element, duplicates, negatives).

#Worked example: does any pair of orders sum to a target?

import random
import time


def has_pair_bruteforce(amounts: list[int], target: int) -> bool:
    for i in range(len(amounts)):
        for j in range(i + 1, len(amounts)):
            if amounts[i] + amounts[j] == target:
                return True
    return False


def has_pair_hashset(amounts: list[int], target: int) -> bool:
    seen = set()
    for amount in amounts:
        if target - amount in seen:
            return True
        seen.add(amount)
    return False


random.seed(1)
for n in (1_000, 2_000, 4_000):
    amounts = random.sample(range(1, 10_000_000), n)
    target = -1  # impossible, so both functions do their worst-case work
    t0 = time.perf_counter()
    has_pair_bruteforce(amounts, target)
    t1 = time.perf_counter()
    has_pair_hashset(amounts, target)
    t2 = time.perf_counter()
    print(f"n={n:>5}: brute force {1000 * (t1 - t0):8.1f} ms   hash set {1000 * (t2 - t1):5.2f} ms")

assert has_pair_hashset([499, 1250, 780], 1279) is True
assert has_pair_hashset([499, 1250, 780], 1000) is False
assert has_pair_hashset([500, 500], 1000) is True
assert has_pair_hashset([500], 1000) is False
print("checks passed")

One run on a laptop (your times will differ, the pattern will not):

$ python3 complexity.py
n= 1000: brute force     12.2 ms   hash set  0.06 ms
n= 2000: brute force     46.6 ms   hash set  0.20 ms
n= 4000: brute force    208.8 ms   hash set  0.37 ms
checks passed

Each time n doubles, the brute force takes about four times longer, exactly what O(n squared) predicts, while the hash-set version roughly doubles, as O(n) predicts. At a million orders the brute force would need about 500 billion comparisons; the hash set needs one million lookups.

The checks cover the edge cases: a matching pair, no pair, two equal amounts ([500, 500] with target 1000 must be True, which is why we check seen before adding the current amount) and a single element.

#Common mistakes

• Jumping to code. State the approach and its complexity first; interviewers grade the reasoning.

• Forgetting space complexity. The hash set is O(n) memory; say so, and mention the sorted two-pointer alternative with O(1) extra space.

• Hidden costs, such as x in some_list inside a loop (O(n) each time) or string concatenation in a loop in some languages.

• Skipping edge cases. Test empty, single, duplicate and extreme inputs out loud.

#Interview angle

After solving, expect "can you do better?" or "what if the data does not fit in memory?". Good follow-ups: sort and use two pointers for O(1) extra space; for data too large for memory, partition by hash into files, or stream with a bounded structure.

#Practice task

1. Write first_repeated_order_id(ids) in O(n) and prove it with timings at three sizes.

2. Implement the sorted two-pointer version of the pair search and compare its time and memory with the hash set.

#Further reading

• Python wiki: time complexity of built-in operations

• Big-O cheat sheet