Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Topological Sort (medium)

Topological Sort is used to find a linear ordering of elements that have dependencies on each other. For example, if event ‘B’ is dependent on event ‘A’, ‘A’ comes before ‘B’ in topological ordering.

This pattern defines an easy way to understand the technique for performing topological sorting of a set of elements and then solves a few problems using it.

Let’s see this pattern in action.

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

For input

7, [[6, 4], [6, 2], [5, 3], [5, 4], [3, 0], [3, 1], [3, 2], [4, 1]],

This is a valid output but it's not accepting:

[5,6,3,4,0,1,2]
A

Anonymous

· 2 years ago

I believe this is a wrong evaluation of a valid test case

Wrong Answer 0.134 ms

Your Input

4

[[3,2],[3,0],[2,0],[2,1]]

Output

[3,2,1,0]

Expected

[3,2,0,1]

It's clearly valid from the example 2

Example 2

Input: Vertices=4, Edges=[3, 2], [3, 0], [2, 0], [2, 1]
Output: Following are the two valid topological sorts for the given graph:
1) 3, 2, 0, 1
2) 3, 2, 1, 0

Here is my code using a dfs approach

from collections import defaultdict

class Solution:
  def top_sort_util_dfs(self, graph, node, visited, in_progress, stack):
    visited[node] = True
    in_progress.add(node)

    for neighbor in graph[node]:
      if neighbor in in_progress:
        return False  # Cycle detected
      if not visited[neighbor]:
        if not self.top_sort_util_df
A

Anonymous

· 3 years ago

5

[[4,2],[4,3],[2,0],[2,1],[3,1]]

The expected output is not correct.

Show 1 reply
A

Anonymous

· 3 years ago

5 [[4,2],[4,3],[2,0],[2,1],[3,1]]

Show 1 reply
A

Anonymous

· 3 years ago

I stumbled upon on different sources that DFS as well can be used to solve this task. I can't say how important that is, but it seems that it is important. At least, reading the article gives an intuition that only BFS is the viable approach.

A

Anonymous

· 4 years ago

I'm confused on the line:

inDegree.put(i,0); graph.put(i, new ArrayList());

what exactly are they looking to achieve?

Show 1 reply
A

Anonymous

· 4 years ago

Is [6, 5, 3, 4, 0, 2, 1] also a valid sort output for example 3?

Show 1 reply
A

Anonymous

· 5 years ago

It's not clear to me why this is indicative of a cycle in the graph:

if (sortedOrder.size() != vertices) // topological sort is not possible as the graph has a cycle return new ArrayList();

If there's a cycle, then wouldn't the algorithm have just ran endlessly?

Show 2 replies
A

Anonymous

· 5 years ago

Is this Kahn's algorithm?

Show 1 reply

Reading Progress

0%

Vote for new content