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_;
	unordered_set<Node*> adjacents_;
	Node(const string& label) : label_(label) {}
	void link(Node* v) { adjacents_.insert(v); }
};

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");

	a.link(&b);
	b.link(&c);
	c.link(&e);
	c.link(&d);
	d.link(&e);
	e.link(&f);
	e.link(&e);
	f.link(&b);
	f.link(&a);
	d.link(&g);
	d.link(&h);
	g.link(&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; // {}
}

- Chris November 11, 2017 | Flag Reply
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

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

- closingtime November 13, 2017 | Flag Reply
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.

- Anonymous November 11, 2017 | Flag Reply
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.

- Anonymous November 11, 2017 | Flag Reply
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)) {
			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.
}

- alldentobias November 11, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More