A practice prompt we wrote. No company or candidate report names it, so it carries no company tag.
How to answer
The sort is well known; what you’re judged on is the report when the input is wrong. Say so early: “The order is the easy output. The report is what a person reads when the install fails, so it has to name an edge they can remove.”
- Fix the direction out loud. “
deps['web'] = ['http']means http installs before web, so the edge runs from http to web.” A reversed edge installs every package before the packages it needs. - Ask about the edges of the input. What does a dependency nobody declared mean: a typo, or something already installed? Should output be deterministic? It should: two runs that install in different orders make failures hard to reproduce.
- Choose Kahn’s algorithm and say why. Count unmet dependencies, install whatever reaches zero, and use a heap so ties break alphabetically. It is iterative, so a deep chain can’t hit the recursion limit, and what it leaves is exactly the stuck set.
- Split the stuck set in two. Peel it again with missing dependencies treated as present: what peels is blocked by a missing package, and what stays is a cycle or waits on one. Print them differently: the cycle as a path,
a -> b -> c -> a, labeled so each arrow reads “needs”, and each blocked package with what it waits on. - Test the shapes that break it. A self-dependency, two separate cycles, a package blocked behind a cycle, a cycle whose member also needs a missing package, and a deep chain.
The trap is a bare “cycle detected” error, or listing every stuck package as the cycle. Neither tells the user which line of their file to change. The deployment order drill runs the same shape against a timer.
Follow-ups
What the interviewer may ask next, once your first answer is on the table.
- Two cycles share a package. Does your report name both, and if not, how would you report every cyclic group in one pass?
- Packages with no path between them could install in parallel. How do you group the order into waves, and how many waves do you need?
- A dependency names a package nobody declared. Is that a typo, something already on the machine, or an error?
- The graph has a chain tens of thousands of packages deep. Does your code still run?
Where answers go wrong
- Raising “cycle detected” with no names, or naming every stuck package as part of the cycle, so the user cannot tell which edge to remove.
- Writing the search recursively, so a long chain hits the recursion limit on a real repository.
- Getting the edge direction backwards and installing each package before the packages it needs.
Answer this in two minutes
Write the answer you would say out loud. The clock starts with your first word.
Model answer
“I’ll take a dict from each package to the packages it needs first, and return a plan: the order for everything that can install, then any cycles, blocked packages and missing dependencies. You said an undeclared dependency is an error, not something already installed, so it blocks whatever needs it.