Katkat
Back

Return a Topological Order or Detect a Cycle

RunloopSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to implement Kahn's algorithm for topological sorting while incorporating a priority-based tie-breaking mechanism to ensure deterministic output.

Problem Description

You are given a directed graph represented as a list of directed edges edges and an integer n representing nodes labeled from 0 to n-1. Your goal is to return a topological ordering of the graph.

If the graph contains a cycle, return an empty list. To ensure the topological order is deterministic, whenever there are multiple nodes with an in-degree of 0, you must always select the node with the smallest numerical value to process next.

Function Signature

def get_deterministic_topo_order(n: int, edges: list[tuple[int, int]]) -> list[int]:

Constraints

  • 1 <= n <= 10^4
  • 0 <= len(edges) <= 10^5
  • Duplicate edges may exist and should be ignored.

Examples

Example 1: Input: n = 3, edges = [(0, 1), (0, 2)] Output: [0, 1, 2] Explanation: Node 0 has 0 in-degree. After removing it, 1 and 2 both have 0 in-degree; since 1 1 -> 2 -> 0), so no topological order is possible.

Edge Cases

  • A graph with no edges should return [0, 1, ..., n-1].
  • A disconnected graph should still return a valid global topological sort using the smallest-node-first rule.

Hints

Hint 1

Use an array to track the in-degree of each node and an adjacency list to represent the graph.

Hint 2

Use a Min-Priority Queue (min-heap) to keep track of all nodes currently having an in-degree of 0.

Hint 3

If the final resulting list contains fewer than `n` nodes, a cycle must exist.

Follow-up questions

  • What is the time and space complexity of your solution, and how does the use of the min-heap affect the time complexity?
  • How would you modify this algorithm if you needed the lexicographically largest topological sort instead?
  • Can you solve this using Depth-First Search (DFS) instead of Kahn's algorithm? What are the trade-offs regarding determinism?