Microsoft Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
What is the complexity of the topological sort? If there are n nodes, topological sort will basically be BFS of the graph which is of order O(|V|+|E|), now |E| can be of O(n^2) even in DAG. So will it be a O(n) solution? please correct me if I am wrong.
but if we do a topological sort with the edge direction reversed, then C will be pointing to both A and B, at that point how will u decide which edge to take ?
What if we reverse all the edges in the dependency graph and then perform topological sort.
- Anonymous November 12, 2011Although this will take more time .. but i am just curious to know if this will work or not ?