Facebook Interview Question
Software Engineer / Developerspublic class Node
{
public int Value { get; set; }
public List<Node> Neighbors { get; set; }
public Node(int value)
{
this.Value = value;
}
}
public static Node CloneGraph(Node srcGraph)
{
if (srcGraph == null)
{
return null;
}
Dictionary<Node, Node> srcToDestNodeMapping = new Dictionary<Node, Node>();
Node destGraph = DfsCreateDestNodes(srcGraph, srcToDestNodeMapping);
foreach (Node srcNode in srcToDestNodeMapping.Keys)
{
foreach (Node neighbor in srcNode.Neighbors)
{
srcToDestNodeMapping[srcNode].Neighbors.Add(srcToDestNodeMapping[neighbor]);
}
}
return destGraph;
}
private static Node DfsCreateDestNodes(Node srcNode, Dictionary<Node, Node> srcToDestNodeMapping)
{
if (srcToDestNodeMapping.ContainsKey(srcNode))
{
return null;
}
Node destNode = new Node(srcNode.Value);
destNode.Neighbors = new List<Node>();
srcToDestNodeMapping.Add(srcNode, destNode);
foreach (Node n in srcNode.Neighbors)
{
DfsCreateDestNodes(n, srcToDestNodeMapping);
}
return destNode;
}
public class Node
{
public int Value { get; set; }
public List<Node> Neighbors { get; set; }
public Node(int value)
{
this.Value = value;
}
}
public static Node CloneGraph(Node srcGraph)
{
if (srcGraph == null)
{
return null;
}
Dictionary<Node, Node> srcToDestNodeMapping = new Dictionary<Node, Node>();
Node destGraph = DfsCreateDestNodes(srcGraph, srcToDestNodeMapping);
foreach (Node srcNode in srcToDestNodeMapping.Keys)
{
foreach (Node neighbor in srcNode.Neighbors)
{
srcToDestNodeMapping[srcNode].Neighbors.Add(srcToDestNodeMapping[neighbor]);
}
}
return destGraph;
}
private static Node DfsCreateDestNodes(Node srcNode, Dictionary<Node, Node> srcToDestNodeMapping)
{
if (srcToDestNodeMapping.ContainsKey(srcNode))
{
return null;
}
Node destNode = new Node(srcNode.Value);
destNode.Neighbors = new List<Node>();
srcToDestNodeMapping.Add(srcNode, destNode);
foreach (Node n in srcNode.Neighbors)
{
DfsCreateDestNodes(n, srcToDestNodeMapping);
}
return destNode;
}
by doing a bfs starting at given node we can visit all nodes, each time an new node is discovered (until the termination of bfs), create a new node copying its value, however leaving neightbors field null. create a hashtable mapping address of the old node to newly created node. now its just a matter of translation and returning the address (translated from old) of the new root.
- light April 20, 2012