MySmartCoPilot
Ask Passes Your pass 7 days left 1 day left Last day

Your country

Tools that support it use your country for local currency, number formats, units and paper size. Your choice is saved only in this browser.

Coding Interview Patterns Module 21

Topological sort and DAGs interview questions

Interview questions on topological sort and DAGs: short warm-ups, then what each harder question tests, the first step of a good answer and its follow-ups.

21 questions: 4 warm-ups and 17 with model answers · Levels: Fresher to staff

Warm-up questions

Short questions with short answers, each answered in full.

  1. Fresher to mid

    Kahn's algorithm output 6 of a graph's 9 nodes, and then its queue was empty. What does that tell you?

    Answered in the lesson Topological order with Kahn's algorithm

  2. Fresher to mid

    Why does Kahn's algorithm take O(V + E) time?

    Answered in the lesson Topological order with Kahn's algorithm

  3. Fresher to mid

    When does a depth-first topological sort reverse its finishing order, and when must it not?

    Answered in the lesson Topological order with DFS

  4. Fresher to mid

    Kahn's algorithm with a min-heap and with a max-heap returns the same order. What does that tell you?

    The graph has exactly one topological order. Every valid order lies between the smallest and the largest valid order when orders are compared number by number, and the min-heap gives the smallest while the max-heap gives the largest. If they are equal, every valid order equals them. It also means that one node was ready at every step, because two ready nodes would have let the two heaps choose differently. As a test it costs two runs of O((n + m) log n); the direct test, Kahn's algorithm stopped at the first step with two ready nodes, needs one run and no heap, in O(n + m).

    From the lesson Smallest and unique topological orders

Questions with model answers

What each question tests, the first step of a good answer and the follow-ups to expect.

  1. Mid to senior

    A build tool orders 3,000 packages with Kahn's algorithm and stops after building 2,400 of them. The developer asks what to fix. What do you report, how do you show them one actual cycle, and what does the extra work cost?

    What it tests
    What the nodes left over by Kahn's algorithm are, telling nodes on a cycle from nodes stuck behind one, extracting a concrete cycle, and keeping the report cheap and stable.
    First step
    Start from why the queue ran dry: each of the 600 packages left has a dependency that was never built, and that dependency is one of the 600 too. So all 600 are on a cycle or depend on one, and most of them are only stuck. Ask how to separate the two groups before you list anything.
    Follow-ups

    From the lesson Topological order with Kahn's algorithm

    Opening the model answers with your pass…

    Model answers open with any MySmartCoPilot pass.

    • Pro pass · 1 week₹79$2.99
    • 30 days₹179$5.99
    • 1 year₹1,699$45

    One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

    Choose a passI have a licence key

    It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 5 minutes

  2. Mid to senior

    A spreadsheet has 50,000 formula cells. A user edits one input cell, and the change reaches 1,200 cells through their formulas. How do you recompute only those cells, each after the cells it reads, and what goes wrong if you reuse in-degrees counted over the whole sheet?

    What it tests
    Running Kahn's algorithm on the part of a graph that a change reaches, counting in-degrees inside that part only, and costing the work against a full recalculation.
    First step
    Find the affected cells first: a breadth-first search from the edited cell, along the edges from each cell to the cells that read it, reaches the 1,200. Then decide what each affected cell has to wait for before it can be recomputed, and ask what happens to a cell that also reads a cell the edit does not reach.
    Follow-ups

    From the lesson Topological order with Kahn's algorithm

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 5 minutes

  3. Mid to senior

    Your recursive depth-first install order passes every test, then crashes in production on a chain of 60,000 packages, each requiring the next. Why does it crash, and how do you change the code without changing the order it returns?

    What it tests
    Why depth, not size, breaks a recursive search, the limits of each language, and rewriting a post-order search with an explicit stack that opens and finishes nodes in exactly the same order.
    First step
    Name the limit first: each nested call holds a stack frame until it returns, and on a chain the first call returns only after the last, so 60,000 frames are needed at once. Then list what one call remembers, the package it is working on and how far through its requirements it has got, because that is what your own stack must hold.
    Follow-ups

    From the lesson Topological order with DFS

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 4 minutes

  4. Fresher to mid

    A teammate's depth-first install order marks each package "seen" and appends it after its requirements. It passes all the review tests. Which input makes it return a wrong answer, and what is the smallest change that fixes it?

    What it tests
    Telling a node on the current path from a finished one, finding the smallest failing input, and proving that the three-state fix reports loops without reporting a node reached twice.
    First step
    Ask what an arrow to a seen package can mean. The package may be finished, which is harmless, or still on the current path, which means a loop, and one mark makes the two look the same. Then try the smallest loop you can write before anything larger.
    Follow-ups

    From the lesson Topological order with DFS

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 4 minutes

  5. Mid to senior

    A registry holds 2 million packages and 9 million requirements. A user asks to install one package. How do you work out what to install and in which order, and what does it cost compared with ordering the whole registry?

    What it tests
    Searching only the part of a graph that one target reaches, costing the work by that part, and handling packages that are shared, installed already or on a loop.
    First step
    Notice that only the packages the requested one needs, directly or through others, matter. A depth-first search started from that package alone reaches exactly those, and nothing else. Estimate how many that is for a typical package before you choose anything that touches all 2 million.
    Follow-ups

    From the lesson Topological order with DFS

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  6. Fresher to mid

    A degree planner tells a student that Algorithms can be taken in term 3 at the earliest. She insists she could take it in term 2. How do you show that the planner is right, and which change to the rules would make her right?

    What it tests
    The lower bound that a chain of prerequisites gives, the induction showing that Kahn's levels meet it, and the assumptions the answer rests on.
    First step
    Find the chain that forces term 3: Programming I, then Programming II, then Algorithms, each in a strictly later term than the one before. Then ask which rule that argument depends on, and what becomes of it if a prerequisite may be taken in the same term.
    Follow-ups

    From the lesson Scheduling with prerequisites

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 4 minutes

  7. Mid to senior

    A university caps every term at 4 courses, and a degree has 40 courses with prerequisites. A teammate's planner takes, each term, the 4 ready courses with the longest chain ahead of them. Is that optimal? What would you build, and how would you know how good its plans are?

    What it tests
    Recognising a scheduling problem that is NP-complete in general, judging a greedy plan against lower bounds, and choosing an exact search where it is affordable.
    First step
    Look for a small plan on which the rule chooses badly: when ready courses tie, taking the wrong ones can push a long chain back by a term. Then write down two lower bounds that every plan must meet, so that each plan the rule produces can be judged.
    Follow-ups

    From the lesson Scheduling with prerequisites

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 4 minutes

  8. Mid to senior

    A release pipeline of 300 jobs with dependencies takes 94 minutes from start to finish. You can make one job twice as fast. How do you choose the job, and how do you check the new length quickly for each candidate?

    What it tests
    Critical paths and slack, why only jobs without slack matter, and how a shorter critical path can make another path critical.
    First step
    Compute earliest and latest start times with a forward and a backward pass, because only jobs with zero slack can shorten the release at all. Then ask how much a candidate saves, which the longest path that avoids it limits.
    Follow-ups

    From the lesson Scheduling with prerequisites

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 4 minutes

  9. Mid to senior

    Why does taking the smallest ready node at every step give the lexicographically smallest topological order? A colleague worries that a small choice now could force a larger number later.

    What it tests
    An exchange argument, why the comparison only cares about the first difference, and when a greedy choice stops being safe because the goal is different.
    First step
    Compare orders the way the problem does: at the first place where two orders differ, the smaller number wins, and nothing after it matters. So only ask which node can come first in a valid order, and whether moving the smallest ready node to the front of any valid order can break a pair.
    Follow-ups

    From the lesson Smallest and unique topological orders

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 4 minutes

  10. Mid to senior

    A league publishes a final ranking of 120 teams and says it follows from 400 head-to-head results, each one a winner placed above a loser. How do you check that the results force exactly this ranking, and what do you report when they do not?

    What it tests
    Uniqueness of a topological order, checking a given order in linear time, and reporting a useful counterexample instead of a bare no.
    First step
    First make sure no result contradicts the ranking. Then use the fact that a ranking is forced exactly when every two neighbours in it are decided directly by some result: list the 119 neighbour pairs and look each one up among the results.
    Follow-ups

    From the lesson Smallest and unique topological orders

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  11. Senior to staff

    Jobs are numbered 1 to n, and some must run before others. Operations wants job 1 as early as possible, then job 2 as early as possible given that, and so on. A teammate runs Kahn's algorithm with a min-heap. Why is that wrong, and what is right?

    What it tests
    Telling the lexicographically smallest order from the order that puts small labels early, the rule that builds the order from the back, and its proof.
    First step
    Try the smallest input that separates the two goals: three jobs, with job 3 before job 1. The min-heap starts with job 2, because it is ready and small, and job 1 ends up last. Ask which job the team's rule wants in the last place, and build from there.
    Follow-ups

    From the lesson Smallest and unique topological orders

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 4 minutes

  12. Mid to senior

    A reviewer says your solution for recovering an alphabet from a sorted word list is incomplete, because it compares only neighbouring words and never word 1 with word 50. Defend it, or fix it.

    What it tests
    Transitivity of dictionary order, why each neighbouring pair gives at most one edge, and the cost of comparing every pair of words instead.
    First step
    Ask what comparing word 1 with word 50 could add. If every pair of neighbours is in order under some alphabet, is the whole list in order under it? Dictionary order is transitive, so follow the chain of neighbours from word 1 to word 50.
    Follow-ups

    From the lesson Inferring an alphabet from sorted words

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  13. Mid to senior

    Your code returns an empty alphabet for a 5,000-word glossary that a linguist insists is sorted. What do you report so that the linguist can find and fix the problem in the data?

    What it tests
    Telling the two causes apart, extracting a cycle with the word pairs behind each of its edges, and making the report short enough to act on.
    First step
    There are only two causes: a word listed before its own prefix, or a cycle among the letter edges. Check the first while extracting the edges, and remember for every edge the pair of neighbouring words that produced it, so that a cycle can be traced back to words.
    Follow-ups

    From the lesson Inferring an alphabet from sorted words

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  14. Senior to staff

    Sorted words arrive one at a time from a scanner, millions in all, and the alphabet should be known as early as possible. How do you process the stream, and when can you announce the full alphabet?

    What it tests
    Extracting edges from consecutive words with memory bounded by the alphabet, keeping the graph consistent as edges arrive, and knowing when the order is fixed.
    First step
    Each new word needs only the previous one: compare the two, add at most one edge, and forget the older word. Memory then depends on the alphabet, not on the stream. Then ask what has to be true of the edges before you may say the order is complete.
    Follow-ups

    From the lesson Inferring an alphabet from sorted words

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 4 minutes

  15. Mid to senior

    A colleague finds the most scenic route through a downhill trail network with Dijkstra's algorithm, taking the largest score first. It passes the examples. Why is it wrong, what do you use instead, and what changes if the network may have cycles?

    What it tests
    Why settling a node early fails when maximising, why a topological order makes every value final, and why longest simple paths are NP-hard once cycles are allowed.
    First step
    Dijkstra's algorithm settles a node once no later route can improve it, which holds for shortest paths with non-negative lengths. Ask whether that still holds when you maximise: can a route found later, through a junction not settled yet, beat a score already settled?
    Follow-ups

    From the lesson Dynamic programming on DAGs

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  16. Mid to senior

    A service returns the number of routes between two stops of a one-way network, modulo 1,000,000,007. Users report wrong counts, but only for long networks and only from the JavaScript client. What is going on, and how do you fix it in every client?

    What it tests
    How route counts grow, the exact limits of floating-point and 64-bit integers, where to reduce modulo p, and how to test against exact arithmetic.
    First step
    Estimate how large the counts get before any modulus. On a chain where each stop leads to the next two, they grow like Fibonacci numbers and pass 2⁵³ after about 78 stops. Then look at where the JavaScript client takes the modulus, and what its numbers can hold exactly.
    Follow-ups

    From the lesson Dynamic programming on DAGs

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  17. Senior to staff

    A city's elevation grid has 4,000 × 4,000 cells. Cyclists want the longest route that only climbs, moving between neighbouring cells. How do you compute it, and how do you keep memory and stack depth under control?

    What it tests
    Seeing a DAG that is never built, choosing an order of the cells without building edges, and the costs of sorting against memoised search on 16 million cells.
    First step
    Every climbing step goes from a lower cell to a higher one, so no route can come back to a cell: the cells and the climbing steps form a DAG that never has to be built. Ask which order of the cells puts every lower neighbour of a cell before the cell itself.
    Follow-ups

    From the lesson Dynamic programming on DAGs

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

All Coding Interview Patterns interview questions · The Coding Interview Patterns track