Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
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.
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);
}
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.
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];
}
}
}
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> ©, 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;
}
BFS or DFS traversal would work,and we can use hash table to deal with cycles.
below is the DFS code:
- duckling March 07, 2013