Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Topological Sort

.....

.....

.....

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