How to answer: Given a dependency graph, return a valid build order or explain why none exists.

What the interviewer is testing.

Graph traversal and cycle detection. Whether you recognise a graph problem and handle cycles.

An outline for this question.

1. Say that this is a topological sort and that a cycle means no valid order exists.
2. Count each node's incoming dependencies, and start from the nodes with none.
3. Remove a node, lower the counts of what depends on it, and add any that reach zero.
4. If fewer nodes come out than went in, there is a cycle. State O(V + E) time and space.

The mistake to avoid.

A depth-first search with no cycle check, which loops forever on a circular dependency.

The general method: clarify, plan, code, test.

The same shape works for most coding questions, whatever the topic.

• Restate the problem and ask about inputs, size limits and edge cases before you write anything.
• Describe your approach and its complexity out loud, then check it makes sense with the interviewer.
• Write clean code in small steps, narrating as you go.
• Walk through a normal case and an edge case by hand, then say what you would test.

Practice it, out loud.

Reading an outline is not the same as saying it. Answer this question in a mock interview, in your own words, then compare it with the outline above.

Practice this questionSee live interview help

More to practice.

• Tell me about yourself and why this role is the right next step.

  Software Engineering, Behavioral

• Given a string, return the first non-repeating character and explain the complexity.

  Software Engineering, Coding

• Design an LRU cache with O(1) get and put operations.

  Software Engineering, Coding

• Design a notification service for email, SMS, and push at large scale.

  Software Engineering, System Design

This is a Replysis practice question. It is not a leaked or official question from any company, and the outline is a guide to structure, not a script. Use your own experience and facts.