Mock interview: Clone graph

Here is the link.

	using System;
	// To execute C#, please define "static void Main" on a class
	// named Solution.
	class Solution
	{
	static void Main(string[] args)
	{
	for (var i = 0; i < 5; i++)
	{
	Console.WriteLine("Hello, World");
	}
	}
	}
	class Graph {
	// private int id;
	private HashSet<int>[] edges;
	private int total;
	// mapping
	Dictionary<int, int> cloneMap;
	public Graph(List<int[]> input, int n) // here
	{
	if(input == null)
	return;
	var length = input.Count; // n - is not total number of edges - interviewer hint - review
	total = length;
	edges = new hashSet<int>[total];
	for(int i = 0; i < length; i++)
	{
	edges[i] = new HashSet<int>();
	}
	foreach(var edge in input)
	{
	// undirected
	var start = edge[0];
	var end = edge[1];
	edges[start].Add(end);
	edges[end].Add(start);
	}
	}
	///[0,1],[0,2],[1,2]
	public Graph CloneGraph(Graph g)
	{
	cloneMap = new Dictionary<int, int>();
	if(g == null)
	return g;
	var clone = new Graph();
	clone.total = g.total;
	clone.edges = new HashSet<int>[g.total];
	var edges = g.edges; // original
	for(int i = 0; i < g.total; i++)
	{
	//edge[0] - hashset {1, 2} start = 0,
	var set = edges[i]; // {1, 2}
	foreach(var id in set) // 2
	{
	if(!cloneMap.ContainsKey(i)) // 0
	{
	// clone node - clone node i
	clone.edges[i] = new HashSet<int>(); // clone the node - erase
	cloneMap.Add(i, i );
	// clone this id
	clone.edges[i].Add(id); // but I added it first, clone id node later
	}
	else
	{
	var cloneId = cloneMap[i];
	clone.edges[cloneId].Add(id);
	}
	}
	}
	return clone;
	}
	}
	// all the nodes of the exisiting graph in new graph -> easy
	// all the edges of the existing graph in new graph
	//
	/*
	0 -> 1
	0 -> 2
	1 -> 2
	n = 3 [[0,1],[0,2],[1,2]]
	three nodes
	0, 1, 2 in the graph
	[0,1] this means 0 is connected to 1 and 1 is connected to zero
	0 - 1
	0 - 2
	1 - 2
	visited[]
	0 -> clone 0
	clone id - same id
	0 - 1
	0 - 2
	determine if the node 1 is cloned or not, if it is not, clone first
	all connected
	fully connected
	all nodes -> go through connected vertex
	0, 1, 2
	mapping - hashMap [node, cloneNode] -> add new mapping
	clone edge ->
	- map
	clone the graph
	undirected graph
	0 - {1, 2}
	1 - {0, 2}
	2 - {2, 1}
	HashSet<int>[n] -
	*/

view raw cloneGraph.cs hosted with ❤ by GitHub

Continue