## Facebook Interview Question for Interns

Country: United States

Comment hidden because of low score. Click to expand.
2
of 2 vote

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:

``````unordered_map<Node*, Node*> parents;
deque<Node*> q{ 1, s };

while (!q.empty()) {
Node* u = q.back();
q.pop_back();
for (auto v : u->adjacents_) {
if (parents.count(v) > 0) continue;
parents[v] = u;
if (v == s) {
q.clear();
break;
} else {
q.push_front(v);
}
}
}``````

the whole solution is

``````#include <string>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;

struct Node
{
string label_;
Node(const string& label) : label_(label) {}
};

vector<Node*> shortest_cycle_path(Node* s)
{
unordered_map<Node*, Node*> parents;
deque<Node*> q{ 1, s };

while (!q.empty()) {
Node* u = q.back();
q.pop_back();
for (auto v : u->adjacents_) {
if (parents.count(v) > 0) continue;
parents[v] = u;
if (v == s) {
q.clear();
break;
} else {
q.push_front(v);
}
}
}

// recover path
vector<Node*> path;
auto current = s;
do {
path.push_back(current);
current = parents[current];
} while (current != nullptr && current != s);
if (current != nullptr) path.push_back(s);
if (path.size() == 1) path.clear(); // no cycle
reverse(path.begin(), path.end());
return path;
}

ostream& operator << (ostream& os, const vector<Node*>& v) {
os << "{";
bool first = true;
for (auto n : v) {
if (first) {
cout << n->label_;
first = false;
} else {
cout << "," << n->label_;
}
}
os << "}";
return os;
}

int main()
{
/*
/------(f)<-   /--\
v   ---/     \ v   |
(a) /   ----->(e)---/
| /   /       ^
vv    |      /
(b)-->(c)-->(d)-->(g)->(h)
\         ^
-------/
*/
Node a("a");
Node b("b");
Node c("c");
Node d("d");
Node e("e");
Node f("f");
Node g("g");
Node h("h");

cout << shortest_cycle_path(&b) << endl; // {b,c,e,f,b}
cout << shortest_cycle_path(&a) << endl; // {a,b,c,e,f,a}
cout << shortest_cycle_path(&e) << endl; // {e,e}
cout << shortest_cycle_path(&g) << endl; // {}
}``````

Comment hidden because of low score. Click to expand.
2
of 2 vote

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

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)
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).

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Modify the graph matrix such that distance from target node (S) to S is infinity. And then use Dijsktra's algo to reach S to S.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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)) {
} 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) {
return new Path(path);
} else {
}
current = current.next;
}
return null; // Could not find path.
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.