Compute pipeline order from dependencies
Company: TikTok
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a set of pipelines and a list of directed dependency pairs (A, B) meaning pipeline A depends on pipeline B and therefore B must run before A. Return one valid execution order that satisfies all dependencies, or report that no such order exists if there is a cycle. For example, for pipelines [P1, P2, P3] with dependencies [(P1, P
2), (P3, P
2)], produce a valid order such as [P2, P1, P3]. Describe the algorithm, data structures used, and time/space complexity. Provide code using both a DFS-based topological sort and Kahn’s algorithm, and discuss how you would handle tie-breaking among independent pipelines and very large graphs.
Quick Answer: This question evaluates understanding of graph algorithms and dependency resolution, specifically topological sorting and cycle detection, along with competence in choosing appropriate data structures and analyzing time/space complexity.
Dependencies are pairs (A, B) meaning A depends on B, so B must run before A. Return a lexicographically smallest valid order, or IMPOSSIBLE on a cycle.
Constraints
- Pipeline labels are comparable strings
Examples
Input: (['P1', 'P2', 'P3'], [['P1', 'P2'], ['P3', 'P2']])
Expected Output: ['P2', 'P1', 'P3']
Input: (['A', 'B'], [['A', 'B'], ['B', 'A']])
Expected Output: 'IMPOSSIBLE'
Hints
- Reverse each dependency into an edge prerequisite -> dependent.