Return the Lexicographically Smallest Topological Order

Question

The question asks the candidate to implement an algorithm that returns the lexicographically smallest topological order of a directed acyclic graph (DAG).

Codemia · Accepted Answer

To solve the problem of returning the lexicographically smallest topological order of a directed acyclic graph (DAG), we need to understand both topological sorting and how to ensure that the order is lexicographically smallest. Topological sorting is a linear ordering of vertices such that for every directed edge u -> v, vertex u comes before vertex v in the ordering.

We can use Kahn's algorithm, which is based on maintaining a list of nodes with no incoming edges (in-degree of zero). To ensure the result is lexicographically smallest, we can utilize a min-heap (priority queue) to always process the smallest node available. The steps are as follows:
1. Calculate the in-degree of each node.
2. Initialize a min-heap with all nodes having in-degree of zero.
3. While the heap is not empty, extract the smallest node, add it to the result, and decrease the in-degree of its neighbors. If any neighbor's in-degree becomes zero, add it to the heap.

Here is a Python implementation of the approach described:
```python
import heapq
from collections import defaultdict

def lexicographically_smallest_topological_order(graph):
    in_degree = defaultdict(int)
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1
    min_heap = [u for u in graph if in_degree[u] == 0]
    heapq.heapify(min_heap)
    result = []

while min_heap:
        u = heapq.heappop(min_heap)
        result.append(u)
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                heapq.heappush(min_heap, v)
    return result
```
This code efficiently computes the lexicographically smallest topological order.

The time complexity of this algorithm is O(V + E), where V is the number of vertices and E is the number of edges, as each vertex and edge is processed once. The space complexity is O(V) for storing the in-degrees and the heap.

It is essential to consider edge cases such as an empty graph or a graph with only one node. Both should return an empty list or a list containing the single node, respectively. Additionally, if the graph has cycles, we need to handle that with appropriate error handling, as topological sorting is only applicable to DAGs.

Return the Lexicographically Smallest Topological Order

OpenAI

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Framing

Approach

Submit Your Answer

OpenAI Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string