Quick Overview

Compute build order from dependencies evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Compute build order from dependencies

Company: Veeva Systems

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given a directed graph represented as a mapping where each key X maps to a list of tasks that depend on X (i.e., X must be completed before each listed task). Example: A: [B, C], B: [D, E], C: [D]. Implement solve(A) that outputs a valid execution order of all tasks reachable from A so that each task appears after all of its prerequisites. If multiple valid orders exist, break ties alphabetically. Detect and report cycles, and state the time and space complexity of your approach.

Quick Answer: Compute build order from dependencies evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

You are given a directed dependency graph as an adjacency mapping `graph`, where each key `X` maps to a list of tasks that depend on `X` (meaning `X` must be completed *before* every task in that list). You are also given a start node `start`. Example: `{'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['D']}` means B and C depend on A; D and E depend on B; D depends on C. Implement `solve(graph, start)` that returns a valid execution (topological) order of **all tasks reachable from `start`**, such that every task appears after all of its prerequisites. When several tasks are simultaneously available (no remaining unmet prerequisites), break ties by choosing the alphabetically smallest one first, so the output is deterministic. If the reachable subgraph contains a cycle (no valid order exists), return the string `"CYCLE"`. Return type: a list of node labels for a valid DAG, or the string `"CYCLE"` if a cycle is detected among the reachable nodes.

Constraints

  • Only nodes reachable from `start` (by following dependency edges) are included in the output.
  • Node labels are strings; alphabetical order is standard string comparison.
  • A node not appearing as a key in `graph` is treated as having no dependents (empty adjacency).
  • When multiple tasks have all prerequisites met at the same time, the alphabetically smallest is emitted first.
  • If the reachable subgraph contains a cycle, no valid order exists and the function returns "CYCLE".

Examples

Input: ({'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['D']}, 'A')

Expected Output: ['A', 'B', 'C', 'D', 'E']

Explanation: The prompt example. A has no prerequisites, so it goes first. B and C both depend only on A; alphabetically B precedes C. D depends on both B and C, so it comes after both; E depends on B. The deterministic order is A, B, C, D, E.

Input: ({'A': ['C', 'B'], 'B': ['D'], 'C': ['D'], 'D': []}, 'A')

Expected Output: ['A', 'B', 'C', 'D']

Explanation: Even though A lists C before B in its adjacency, both become available together after A, and the alphabetical tie-break emits B before C. D waits for both B and C.

Hints

  1. First restrict the problem to the subgraph reachable from `start` via DFS/BFS — unreachable tasks should never appear in the output.
  2. Use Kahn's algorithm (repeatedly remove nodes with in-degree 0). To break ties alphabetically, store the currently-available nodes in a min-heap instead of a plain FIFO queue.
  3. Detect cycles by counting emitted nodes: if you process fewer nodes than exist in the reachable subgraph, the remaining nodes form (or feed into) a cycle.

Loading coding console...