Coding questions · Nextdoor

Implement ordering with dependency constraints

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.

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

Lexicographically Smallest Dependency Order

Constraints

0 <= u,v < n
If multiple nodes are available, choose the smallest id first

Examples

Example 1

Input: (4, [[0, 2], [1, 2], [2, 3]])
Output: [0, 1, 2, 3]

Example 2

Input: (3, [[0, 1], [1, 2], [2, 0]])
Output: 'IMPOSSIBLE'

Hints

Kahn topological sort with a min-heap gives the lexicographically smallest order.