Facebook Interview Question
InternsCountry: United States
Perform DFS with a stack that represents the simple path you're currently on.
If you visit a node that's already in the simple path, you ignore it.
When you reach a cycle, record it if its size is smaller than the current
smallest recorded cycle.
import copy
# Assuming adjacency format
def solution(node):
cycle_path = None
# Assuming the node is indeed in the graph
# Assuming there is indeed a cycle
def dfs(orig_node, node, node_stack, stack_set):
node_stack.append(node)
stack_set.add(node)
for neighbor in node.neighbors():
if neighbor == orig_node:
if cycle_path is None or len(cycle_path) > len(node_stack):
cycle_path = copy.deepcopy(node_stack)
return
if neighbor
if neighbor not in stack_set:
dfs(orig_node, neighbor, node_stack, stack_set);
node_stack.pop()
stack_set.remove(node)
node_stack = []
stack_set = set()
dfs(node, node, node_stack, stack_set);
cycle_path.append(node)
return cycle_path
Another approach is to find the strongly connected components of the graph (or at least the sub-graph that is connected to the target node).
Let t the target node of directed graph G = (V, E). If t is in a cycle, then there is some vertex v such that there is an edge t -> v, and there is a directed path from v to t. So, for each such v, start a BFS to try to find the shortest path from v to t (if exists), return the minimum length path among them.
But it's possible to solve it with a single BFS, start the BFS as usual from t, that is, add t to the queue, but don't mark it as visited! mark each vertex as visited as they are discovered, and the first time you find t, you'll have the shortest cycle that contains t, keep a parent pointer structure so you can rebuild the path.
I would solve it as Follows.
Given the Node and Path class
class Node {
public int value;
public Node next;
public Node(int x) { value = x; next = null; }
}
class Path {
public ArrayList<Node> path;
public Path(ArrayList<Node> path){this.path = path;}
}
Since HashSet has O(1) for insertion and search we will use this for determining whether a node has been visited by our algorithm. When we find the first node in our cycle(first time we find a previously visited node) we can create our path.
public Path getShortestCycle(Node a) {
Node current = a;
HashSet<Node> visited = new HashSet<>();
while(current.next != null) {
if(!visited.contians(current)) {
visited.add(current);
} else { // We have found the start node for the cycle!
return computePath(current);
}
current = current.next;
}
return null; // Could not find path
}
// Computes the cycle starting at node a
private Path computePath(Node a) {
Node start = a;
Node current = a;
ArrayList<Node> path = new ArrayList<Node>();
while(current != a && current.next != null) {
if(current.next = a) {
path.add(current);
path.add(a);
return new Path(path);
} else {
path.add(current);
}
current = current.next;
}
return null; // Could not find path.
}
Straight forward BFS to find shortest path from s to s. Just ensure, the start node is not put into the visited nodes at first. Since there is no relaxation (unweighted graph) needed, the order of first discovery from BFS is as well the shortest path to that node. Store it's parent and don't care about rediscovery (as usually). If I get back to S, I have the shortest cycle.
Runtime is O(|V|+|E|), especially if there is no cycle, this might happen (e.g. if you
give me the root of a tree as start). Space is O(|V|).
The core of the algo is this code, assuming s is the given node:
the whole solution is
- Chris November 11, 2017