Implement ordering with dependency constraints
Company: Nextdoor
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
You are given n items labeled 0..n−1 and a list of precedence constraints edges[i] = [u, v] meaning u must appear before v. Return a valid ordering of all items that satisfies all constraints. If multiple orders exist, return the lexicographically smallest by item ID; if a cycle exists, return "IMPOSSIBLE." Analyze time and space complexity and provide working code. Follow-up: extend your solution to support groups where certain items must appear as contiguous blocks; respect both intra-group and inter-group dependencies and return any valid sequence or "IMPOSSIBLE."
Quick Answer: This question evaluates understanding of dependency resolution and ordering within graph-based problems, including cycle detection, lexicographic tie-breaking, and extensions requiring certain items to appear as contiguous groups.
Given n items 0..n-1 and precedence edges [u, v] meaning u must appear before v, return the lexicographically smallest valid ordering. Return "IMPOSSIBLE" if a cycle exists.
Constraints
- 0 <= u,v < n
- If multiple nodes are available, choose the smallest id first
Examples
Input: (4, [[0, 2], [1, 2], [2, 3]])
Expected Output: [0, 1, 2, 3]
Input: (3, [[0, 1], [1, 2], [2, 0]])
Expected Output: 'IMPOSSIBLE'
Input: (3, [])
Expected Output: [0, 1, 2]
Hints
- Kahn topological sort with a min-heap gives the lexicographically smallest order.