Facebook Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

BFS or DFS traversal would work,and we can use hash table to deal with cycles.
below is the DFS code:

//definition of the graph
struct Node
{
	int data;
	vector<Node*> neighbors;//
       //constructor.....
};
Node* DFSCopyGraph(Node* graph,unordered_map<Node*,Node*>& hmap)
{
	if(hmap.find(graph) != hmap.end())
		return hmap[graph];
	Node* graphCpy = new Node(graph->data);
	hmap[graph] = graphCpy;
	for(int i=0;i<graph->neighbors.size();i++)
		graphCpy->neighbors.push_back(DFSCopyGraph(neighbors[i]),hmap);
	return graphCpy;
}

- duckling March 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

I am not able to understand why to use a hashmap to separately track the nodes we already visited.
In the traversal (BFS or DFS) we keep track of visited/marked vertices to prevent infinite loops
then what is the need for the extra hashmap?

- jain.nehil November 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

We need to use a hash table which will take input as node of input graph and give output as node of new graph, if there is an input node that is not yet mapped then we need to allocate new node and insert that mapping into hash table.

- googlybhai March 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here's code for that:

#include <iostream>
#include <string>
#include <vector>
#include <map>

using namespace std;

struct nodeS;
typedef map<const nodeS*, nodeS*> NodeCacheT;

struct nodeS {
        int mVal;
        vector<nodeS*> mChildern;
        nodeS(int val) : mVal(val) {}
};

nodeS* CopyNode (NodeCacheT& cache, const nodeS* orig )
{
        if (orig == NULL) return NULL;
        NodeCacheT::iterator it = cache.find(orig) ;
        if (it != cache.end())
        {
                return it->second;
        }

        nodeS* copy = new nodeS(orig->mVal);
        cache.insert(make_pair(orig, copy));
        for (int i=0; i<orig->mChildern.size(); i++) {
                copy->mChildern.push_back(CopyNode(cache, orig->mChildern[i]));
        }
}

nodeS* CloneGraph (const nodeS* root) {
        NodeCacheT cache;
        return CopyNode(cache, root);
}

- sd March 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

One Typo:
CopyNode has to return copy in the end.

- Anonymous March 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

digraph or directed ; positive or negative weighted graph ; any cycles( particulary negative) ?

- Anonymous March 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It was for a directed graph with cycles

- Anonymous March 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It was for a directed graph with cycles
E.g. If we have a graph like A->B->C->D->B
the cloning algorithm will produce A'->B'->C'->D'->B'

- shubhra.datta March 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why don't you simply traverse the graph using dfs with standard coloring scheme to mark visited nodes? That should deal with cycles too.

- Andy March 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

As we copy a node, we insert it into the table. If we later find that one of a node’s neighbor is already in the table, we do not make a copy of that neighbor, but to push its neighbor’s copy to its copy instead. Therefore, the hash table would need to store a mapping of key-value pairs, where the key is a node in the original graph and its value is the node’s copy.

- alex March 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my Java code. DFS search, storing visiting nodes in a HashMap. Nodes must be labeled for the hash to work.

Complexity is O(|V| + |E|)

Usage:

// Build your graph. "root" is the root of the graph to be copied.
   GraphClone cloner = new GraphClone(root);
   Node newRoot = cloner.cloneGraph();

import java.util.HashMap;
import java.util.Map;

public class GraphClone {

	private Map<String, Node> visited = new HashMap<String,Node>();
	private final Node root;

	public GraphClone(Node root) {
        this.root = root;
    }

	public Node cloneGraph() {
		return cloneGraph(root);
	}
	
	
	private Node cloneGraph(Node node) {
		Node clone = visited.get(node.label); 
		if(clone != null)
			return clone;
		
		clone = new Node(node);
		visited.put(node.label, clone);

		for(int i = 0; i < node.children.length; i++) {
			Node child = node.children[i];
			Node childClone = cloneGraph(child);
			clone.children[i] = childClone;
		}
		
		return clone;
	}


	public static class Node {
		String label;
		Node[] children;
		
		private Node(String label) {
			this.label = label;
		}
		
		private Node(Node orig) {
			label = orig.label;
			children = new Node[orig.children.length];
		}
	}
}

- Barry Fruitman March 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You don't need to do any traversal. Just get the object structure which represents the graph (usually a list of vertex) and clone it. No need to put special attention to cycles etc.

- sriwantha March 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Everyone here is talking about the linked list implementation of graph. How would the solution change for adjacency matrix representation of the graph? I believe just returning a copy of adjacency matrix should do it.

- Epic_coder May 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why can't we just use ordinary DFS and push every node we've visited into the vector<Node>? Like the following code:

class Node{
public:
    
    int num_vertex;
    list<Node> neighbors;
};

void CloneGraph(Node curr, vector<Node> &copy, unordered_map<Node, bool> &is_visited) {
    
    if (is_visited[curr])
        return;
    
    is_visited[curr] = true;
    copy.push_back(curr);
        
    for (auto it=curr.neighbors.begin(); it!=curr.neighbors.end(); it++)
        if (!is_visited[*it])
            CloneGraph(*it, copy, is_visited);
    return;
}

- exthrash December 30, 2014 | 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