Return a Valid Dependency Installation Order

Quick Overview

Produce a valid dependency installation order with DFS state tracking, cycle detection, dependency-only packages, and exactly-once handling of shared prerequisites.

Return a Valid Dependency Installation Order

Company: Verily

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Given a map from each package to the list of packages it depends on, return an installation order in which every dependency is installed before its dependent. Install each package once, including packages that appear only in dependency lists. Report a cycle when no valid order exists. ### Constraints & Assumptions Any valid topological order is acceptable. Treat missing map entries as packages with no listed dependencies. Duplicate dependency mentions must not duplicate installation. ### Clarifying Questions to Ask - Can the graph contain cycles or disconnected components? - Are packages appearing only as dependencies considered leaf packages? ```hint Distinguish unfinished from finished visits Encountering a package on the current recursion path means something different from encountering one already installed. ``` ### What a Strong Answer Covers - Three-state traversal or an equivalent indegree method. - Appending a package only after all dependencies finish. - Cycle detection and exactly-once output across shared dependencies. ### Follow-up Questions - How would you identify packages that can be installed in parallel? - How would you avoid recursion-depth limits for a long dependency chain?

Overview: Produce a valid dependency installation order with DFS state tracking, cycle detection, dependency-only packages, and exactly-once handling of shared prerequisites.

Read the full Verily Software Engineer interview experience this question came from

Verily logo
Verily
Nov 4, 2026
mediumSoftware EngineerOnsiteCoding & Algorithms
0
0

Given a map from each package to the list of packages it depends on, return an installation order in which every dependency is installed before its dependent. Install each package once, including packages that appear only in dependency lists. Report a cycle when no valid order exists.

Constraints & Assumptions

Any valid topological order is acceptable. Treat missing map entries as packages with no listed dependencies. Duplicate dependency mentions must not duplicate installation.

Clarifying Questions to Ask Guidance

  • Can the graph contain cycles or disconnected components?
  • Are packages appearing only as dependencies considered leaf packages?

What a Strong Answer Covers Guidance

  • Three-state traversal or an equivalent indegree method.
  • Appending a package only after all dependencies finish.
  • Cycle detection and exactly-once output across shared dependencies.

Follow-up Questions Guidance

  • How would you identify packages that can be installed in parallel?
  • How would you avoid recursion-depth limits for a long dependency chain?