Practice problem · Snowflake · Medium

Topological Sort: Layers and Workers

A nightly data pipeline runs numbered jobs, and some jobs cannot start until others have finished. 3 stages in Python written by you, with an assistant that only answers. Pro.

Stage 1 of 3: Run order

A nightly data pipeline runs numbered jobs, and some jobs cannot start until others have finished.

Implement run_order(n, pairs) in pipeline.py. It returns an order in which the jobs can run, or [] when there is none.

  • The jobs are numbered 0 to n - 1, with 1 <= n <= 100,000.
  • pairs is a list of up to 200,000 pairs. A pair (a, b), a tuple or a list of two job numbers, means job a must finish before job b starts: b waits for a.
  • Return a list holding every job exactly once in which a comes before b for every pair. Any such list is accepted.
  • When no such list exists, return []. That happens exactly when the pairs contain a cycle, such as (0, 1), (1, 2) and (2, 0); a pair (a, a) is a cycle on its own.
  • A pair may appear more than once; it means the same as once. A job may appear in no pair at all.
  • A chain of pairs may pass through every job. Each call returns within 2 seconds for 50,000 jobs and 200,000 pairs.
  • The standard library's graphlib is not available: the ordering is yours to write, and test_helpers.py makes import graphlib fail.

Example

pairs = [(4, 2), (2, 0), (4, 5), (5, 0), (1, 3), (5, 3)]
run_order(6, pairs)             # one valid answer: [1, 4, 2, 5, 0, 3]
run_order(6, pairs + [(0, 4)])  # []: 0 waits for 2, 2 waits for 4, and 4 now waits for 0

Notes

  • The tests check an answer by its properties, with check_run_order in test_helpers.py: every job once and every pair in order. Any valid order passes.
  • Four tests time one call each, on a chain through all 50,000 jobs, on 50,000 jobs with 200,000 pairs, on 50,000 jobs where job 0 comes before every other one (100,000 pairs), and on 50,000 jobs with no pairs; each prints its seconds.
  • On the starter, all 16 tests in tests/test_part1.py fail.

Done when Submit goes green.

Constraints

  • Python 3.12 standard library only; graphlib is blocked by the tests
  • Editable: pipeline.py
  • Read-only: test_helpers.py and all tests/test_*.py files
  • Inputs are always valid: jobs are numbered 0 to n - 1 and every pair names two of them

What comes after stage 1

The next stages open once the tests for the one before them pass. Each raises the bar, the way an interviewer does in the room.

  1. Stage 2: Layers. Group the jobs into rounds, each job in the earliest round that everything it waits for allows.
  2. Stage 3: Workers and durations. Jobs take different times and only a few run at once: which job each free worker starts, and when.

The files you get

  • Yours to edit: pipeline.py.
  • Read-only: test_helpers.py.
  • Tests you can read and run: tests/test_part1.py. Hidden tests run on Submit.

The round: no AI, an assistant that only answers

Snowflake runs this round without AI. Here the closest format is answer-only: the assistant answers your questions and reviews your code when you ask, the way an interviewer would, and never writes a line of it. The interviewer asks about your decisions as you go, and the report states the format. You can switch to the agent format when you press Begin.

Frequently asked, briefly answered

Is Topological Sort: Layers and Workers free?

It is a Pro problem. Free plan includes one complete problem, plus the first stage of several more, so you can see how a round works before you pay.

Which company asks something like this?

Snowflake. It is modelled on Snowflake's coding round, which runs without AI. Based on candidates' reports of Snowflake interviews. Nyrion wrote this version, so the question you get may differ.

Do I bring my own AI tool?

No. The real round has no AI, so this one opens answer-only: an assistant that answers your questions and can't write code. You can switch to an agent that proposes changes when you press Begin.

What does the interviewer ask?

6 questions along the way about your own code, and one at the end about the whole session. A weak answer gets one follow up. The answers go into the report, which ends with a hire or no hire verdict.

Start the problem

Sign in and the problem opens where you left it. New here? An account takes a minute to create, and the Pro plan starts at the first stage of this problem.

Start this problem → Sign in

More like it: every practice problem, Snowflake's interviews, the AI coding interview guide.