Python traps · Chapter 12 of 16

Set order is not an order

Build it in your browser: a real editor and terminal, AI that explains, and tests that tell you when it works.

  • Part: Time
  • 3 tasks
  • Python
  • In the all labs plan

The first 2 chapters of Python traps are free. This one comes with the all labs plan.

Why you need this

Python randomizes the hash of strings once per process, as a defence against attacks that send many keys built to land in the same place. So the same string gets a new hash in every run:

print(hash("roti"))
print(hash(17))
$ python3 hashes.py
4554648070533309973
17
$ python3 hashes.py
-1939911222394501257
17

Numbers hash to themselves, so a set of small ints often looks sorted and stable, and a set of strings looks fine for the whole life of one process. Nothing errors. Only a restart, with a new seed, shuffles it: exactly Kunal's clue. PYTHONHASHSEED sets the seed by hand. It is for reproducing and testing; pinning it in production switches off that defence, and the code would still depend on luck.

What you build: 3 tasks

Each task has tests. You write the code in the lab's editor and press Check.

  1. Task 1

    repro.py: Prakash's route in the wrong order

    Write reproduce() in repro.py. Build Prakash's lunch stops, in delivery order, as a list of dicts with "order" and "area": D2041 Dadar, D2044 Dadar, D2047 Bandra, D2050 Andheri, D2052 Andheri, D2055 Powai. Return route_areas(stops) from routes.py.

    The check runs your reproduce() twice, each time in a fresh python3 with a fixed hash seed: beside the original routes.py, with PYTHONHASHSEED=2, it must return ['Powai', 'Bandra', 'Dadar', 'Andheri'] (the four areas out of order), and beside a fixed routes.py it must return ['Dadar', 'Bandra', 'Andheri', 'Powai'] under every seed. So it must really build those stops, in that order, and call route_areas. No real waiting and no input(): reproduce() must finish within 3 seconds.

  2. Task 2

    routes.py: every route sheet in delivery order

    Fix route_areas(stops) in routes.py. It must give a list with each area once, in the order of that area's first stop, and the same list in every run of the program, whatever the hash seed. An area that comes back later in the route keeps its first place. No stops give [].

    Keep route_sheet and its line as they are: "<rider>: <area> > <area> > ...". The check imports a fresh copy of your routes.py and uses its own riders and stops, not Prakash's, and runs your code in fresh Pythons under several hash seeds. Sorting the areas is as wrong as the bug: the same every run, but not the route.

  3. Task 3

    test_routes.py: a test that would have caught it

    Write a pytest file, test_routes.py, that would have caught this bug before it reached the riders. The check runs your file under fixed hash seeds, three ways: beside the original routes.py, where at least one test must fail; beside the fixed routes.py, where every test must pass; and beside a wrong fix that sorts the areas, where at least one test must fail.

    So assert the exact list route_areas gives, for stops in four or more areas whose delivery order is not alphabetical (a set rarely lands on that exact order, and sorting never does). No real waiting: each test must finish within 3 seconds.

What you will learn

  • repro.py: Prakash's route in the wrong order
  • routes.py: every route sheet in delivery order
  • test_routes.py: a test that would have caught it

More in Time

Build "Set order is not an order" yourself

DabbaDrop runs on Python, and Kunal, its senior developer, keeps assigning you tickets. Each is a real trap interviews love to ask about. A real editor and terminal in your browser, AI that explains, and a Check that says when it works.

The first 2 chapters of Python traps are free. This one comes with the all labs plan.