Topological Sort Homework
Topological Sort Homework
Topological Sort Homework
Interview Camp
Technique: Topological Sort
Level: Hard
Diameter of a Graph: Given a directed graph, find the length of the longest path in the graph.
For example,
Questions to Clarify:
Q. Can the graph have cycles?
A. No. With cycles, the longest path is infinite in length.
Q. Can the graph be empty?
A. No, there will be at least one node.
Solution:
This solution uses Dynamic Programming along with Topological Sort.
Let's say you want to find the longest path to a Node A. If you knew the longest path to its parent
nodes, that would make things easy. You would find the parent that has the longest path, and then add
1 to it.
© 2017 Interview Camp (interviewcamp.io)
Interview Camp
So in short, you want to process each parent node before processing the node. This is perfect
for topological sort - because all the parents come before the child.
Here is the formula we come up with:
© 2017 Interview Camp (interviewcamp.io)
Interview Camp
longest-path(A) = max(longest-path(parents)
Now, we cannot execute this formula as it is. This is because we have no way of getting a
child's parent (we have directed graph with edges going from parent to child). So we flip
this around and process it from parent to child.
for each node A in topological order:
for each child node (say C)
C.longestPath = max(C.longestPath, A.longestPath + 1)
This way, by the time we reach C, we've processed all of C's parents.
Where do we store a node's longest path? We just assume that each Node has a longestPath field.
An alternate way is to create a Hash Table that maps a Node to its longest path.
Pseudocode:
(Note: Never write pseudocode in an actual interview. Unless you're writing a few
lines quickly to plan out your solution. Your actual solution should be in a real
language and use good syntax.)
diameter(Node start)
topoSort = topologicalSort(start)
diameter = 0
return diameter
Test Cases:
Edge Cases: single node
Base Cases: two nodes
Regular Cases: normal graph with many nodes
© 2017 Interview Camp (interviewcamp.io)
Interview Camp
while(!topoSort.isEmpty()) {
Node current = topoSort.pop();
diameter = Math.max(diameter, current.getLongestPath());
node.setState(State.VISITED);
stack.push(node);
}
/*
* Helper Code. Ask interviewer before implementing.
*/
public enum State {
UNVISITED,
VISITING,
VISITED;
}
© 2017 Interview Camp (interviewcamp.io)
Interview Camp
List<Node> neighbors;
int data;
State state;
int longestPath;
© 2017 Interview Camp (interviewcamp.io)