A question that I got asked on the interview at Facebook on 2016 that I wasn’t able to finish coding within interview time frame. Finally got a chance to put it into code.
I used a LeetCode as a JS platform to test a code: https://leetcode.com/problems/clone-graph/description/
/**
* Definition for undirected graph.
* function UndirectedGraphNode(label) {
* this.label = label;
* this.neighbors = []; // Array of UndirectedGraphNode
* }
*/
/**
* @param {UndirectedGraphNode} graph
* @return {UndirectedGraphNode}
*/
var cloneGraph = function(graph) {
//test for an empty input
if (!graph) return null;
var hashMap = new Map();
var mainQueue = [];
var start = graph;
mainQueue.push(graph);
hashMap.set(graph, new UndirectedGraphNode(graph.label));
//use Breadth First Search to visit all nodes
while(mainQueue.length > 0) {
//take first element in the queue
graph = mainQueue[0];
//remove visited node from the queue
mainQueue.splice(0,1);
for (var i=0; i<graph.neighbors.length; i++){
//add all unvisited neighbor nodes to the queue
if (!hashMap.has(graph.neighbors[i])) {
mainQueue.push(graph.neighbors[i]);
hashMap.set(graph.neighbors[i], new UndirectedGraphNode(graph.neighbors[i].label));
}
//push neighbors into new graph
hashMap.get(graph).neighbors.push(hashMap.get(graph.neighbors[i]));
}
}
return hashMap.get(start);
};
//run a test
var aNode = new UndirectedGraphNode('0');
var bNode = new UndirectedGraphNode('1');
var cNode = new UndirectedGraphNode('2');
aNode.neighbors.push(bNode, cNode);
bNode.neighbors.push(cNode);
cNode.neighbors.push(cNode);
console.log(aNode);
console.log(cloneGraph(aNode));