Coding questions · TikTok
Compute pipeline order from dependencies
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.
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.
Pipeline Order from Dependencies
Constraints
- Pipeline labels are comparable strings
Examples
Example 1
Input: (['P1', 'P2', 'P3'], [['P1', 'P2'], ['P3', 'P2']])
Output: ['P2', 'P1', 'P3']
Example 2
Input: (['A', 'B'], [['A', 'B'], ['B', 'A']])
Output: 'IMPOSSIBLE'
Hints
- Reverse each dependency into an edge prerequisite -> dependent.