Compute build order from dependencies

Q: Compute build order from dependencies

This question evaluates a candidate's understanding of graph algorithms and dependency resolution, including topological ordering, cycle detection, and implementing deterministic tie-breaking for valid execution orders.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Compute build order from dependencies

Overview

Comments (0)