Compute build order from dependencies

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.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Compute Build Order from Dependencies

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".

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.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

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.

Recommended Approach

Model the states explicitly and use BFS for unweighted shortest paths, Dijkstra for weighted non-negative paths, or topological DP for DAGs. Track visited states at the right granularity so cycles do not cause repeated work.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

BFS is O(V + E) time and O(V) space for a standard graph. Expanded-state problems multiply those bounds by the number of state dimensions.

Edge Cases and Tests

Disconnected graph, source equals target, cycles, duplicate edges, unreachable target, and whether the answer counts nodes, edges, moves, or transfers.