Topological Sort on string

Question

Given a directed acyclic graph (DAG) represented by a list of strings, where each string represents a task and directed edges indicate dependencies between tasks, implement a function to perform a topological sort on the strings. The output should be a list of strings in a valid topological order, ensuring that for every directed edge from task A to task B, task A appears before task B in the output. If a valid topological order is not possible, return an empty list.

Codemia · Accepted Answer

The problem requires us to perform a topological sort on a directed acyclic graph (DAG) represented by tasks and their dependencies. The core pattern in this problem is the use of graph traversal techniques, specifically Kahn's Algorithm or Depth-First Search (DFS) for topological sorting. Kahn's algorithm is particularly useful here because it allows us to keep track of the in-degrees of each node (task) and process nodes with zero in-degrees, ensuring that we respect the dependency order. This method is efficient for scenarios involving multiple dependencies and provides a straightforward way to detect cycles in the graph.

1. **Construct the Graph**: Create a graph as an adjacency list from the given list of strings. Each string represents a task, and the directed edges are determined by dependencies provided as a list of tuples (A, B) where A depends on B.
2. **Calculate In-degrees**: Maintain a count of incoming edges (in-degrees) for each task to identify which tasks can be processed first (those with in-degree of 0).
3. **Initialize a Queue**: Start with a queue that contains all tasks with an in-degree of 0.
4. **Process the Queue**: While the queue is not empty, remove a task from the queue, add it to the result list, and decrease the in-degree of its neighbors. If any neighbor's in-degree becomes 0, add it to the queue.
5. **Check for Cycles**: If the result list does not contain all tasks, it indicates a cycle, and we should return an empty list. Otherwise, return the result list as the topological order.

**Example**: For tasks ['A', 'B', 'C', 'D'] with dependencies [('A', 'B'), ('B', 'C'), ('A', 'C'), ('C', 'D')], we can construct a graph and determine the order of execution as ['A', 'B', 'C', 'D'].

Here is the Python implementation for the given problem:

```python
from collections import defaultdict, deque

def topological_sort(tasks, dependencies):
    # Step 1: Construct the graph and in-degree count
    graph = defaultdict(list)
    in_degree = {task: 0 for task in tasks}

for a, b in dependencies:
        graph[a].append(b)
        in_degree[b] += 1

# Step 2: Initialize the queue with tasks having 0 in-degree
    queue = deque([task for task in tasks if in_degree[task] == 0])
    result = []

# Step 3: Process the queue
    while queue:
        current_task = queue.popleft()
        result.append(current_task)

for neighbor in graph[current_task]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

# Step 4: Check for cycles
    if len(result) != len(tasks):
        return []  # Cycle detected, return empty list

return result
```

This code constructs the graph, processes tasks based on their dependencies, and checks for cycles effectively.

The time complexity of this solution is O(V + E), where V is the number of vertices (tasks) and E is the number of edges (dependencies). This is because we traverse each vertex and edge once while constructing the graph and processing the queue. The space complexity is O(V + E) as well, due to the storage needed for the graph representation and the in-degree count. Given the constraints typically found in such problems, this solution is efficient and scalable.

1. **No Dependencies**: If the tasks are independent (e.g., ['A', 'B', 'C']), the result should simply be the list of tasks in any order.
2. **Single Task**: For a single task without dependencies (e.g., ['A']), the output should be ['A'].
3. **Circular Dependencies**: If there's a cycle (e.g., dependencies [('A', 'B'), ('B', 'A')]), the function should return an empty list.
4. **Empty Input**: If given an empty list of tasks, the output should also be an empty list. 
5. **Multiple Valid Outputs**: The function may return multiple valid topological orders as long as the dependencies are respected.

Topological Sort on string

DoorDash

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

DoorDash 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