GeekLion
BAN USERusing System;
using System.Collections.Generic;
using System.Linq;
namespace test
{
public class TreeNode
{
public int val { get; set; }
public TreeNode left { get; set; }
public TreeNode right { get; set; }
public TreeNode(int x)
{
val = x;
}
}
public class FindDupNodes
{
public FindDupNodes()
{
List<TreeNode> tree = new List<TreeNode>();
tree = ConstructTree();
TreeNode node = FindMaxDups(tree);
Console.WriteLine($"{node.val} -- {node?.left?.val} -- {node?.right?.val}");
}
public List<TreeNode> ConstructTree()
{
List<TreeNode> nodes = new List<TreeNode>();
TreeNode t1 = new TreeNode(1);
TreeNode t2 = new TreeNode(2);
TreeNode t3 = new TreeNode(3);
TreeNode t4 = new TreeNode(4);
t1.left = t2; t1.right = t3;
t2.left = t4;
t3.left = t2;
t3.right = t4;
nodes.Add(t1);
nodes.Add(t2);
nodes.Add(t3);
nodes.Add(t4);
return nodes;
}
public TreeNode FindMaxDups(List<TreeNode> tree)
{
//get the root
TreeNode rootNode = tree.Where(t => t.val == 1).FirstOrDefault();
//iterate over in recursion and see which one appears more than once
IterateTree(rootNode, tree);
int maxValue = nodeCounts.Max(n => n.Value); //.Select(nd => nd.Key);
List<TreeNode> maxNodes = nodeCounts.Where(n => n.Value == maxValue).Select(n => n.Key).ToList();
return maxNodes.FirstOrDefault();
}
public Dictionary<TreeNode, int> nodeCounts = new Dictionary<TreeNode, int>();
public void IterateTree(TreeNode currentNode, List<TreeNode> tree)
{
if (currentNode == null)
return;
if (nodeCounts.ContainsKey(currentNode))
nodeCounts[currentNode] = nodeCounts[currentNode] + 1;
else
nodeCounts.Add(currentNode, 1);
if (currentNode.left == null && currentNode.right == null)
return;
IterateTree(currentNode.left, tree);
IterateTree(currentNode.right, tree);
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace something
{
public class AirportOrdering
{
public AirportOrdering()
{
Dictionary<string, string> unorderedList = new Dictionary<string, string>();
unorderedList.Add("ITO", "KOA");
unorderedList.Add("ANC", "SEA");
unorderedList.Add("LGA", "CDG");
unorderedList.Add("KOA", "LGA");
unorderedList.Add("PDX", "ITO");
unorderedList.Add("SEA", "PDX");
foreach (KeyValuePair<string, string> element in unorderedList)
{
Console.WriteLine($"{element.Key}, {element.Value}");
}
Console.WriteLine("----------------OUTPUT---------");
Dictionary<string, string> orderedList = GetOrderedList(unorderedList);
foreach (KeyValuePair<string, string> element in orderedList)
{
Console.WriteLine($"{element.Key}, {element.Value}");
}
Console.ReadKey();
}
public Dictionary<string, string> GetOrderedList(Dictionary<string, string> unorderedList)
{
Dictionary<string, string> orderedList = new Dictionary<string, string>();
KeyValuePair<string, string> startAirport = new KeyValuePair<string, string>();
startAirport = unorderedList.Where(u => unorderedList.ContainsValue(u.Key) == false).FirstOrDefault();
if (startAirport.Key == null)
return orderedList;
orderedList = orderList(startAirport, unorderedList);
return orderedList;
}
public Dictionary<string, string> orderList(KeyValuePair<string, string> startPt, Dictionary<string, string> unorderedList, Dictionary<string, string> currentList = null)
{
if (currentList == null)
currentList = new Dictionary<string, string>();
if (currentList.Count() == unorderedList.Count() || startPt.Key == null)
return currentList;
currentList.Add(startPt.Key, startPt.Value);
KeyValuePair<string, string> next = new KeyValuePair<string, string>();
next = unorderedList.Where(u => u.Key == startPt.Value).FirstOrDefault();
orderList(next, unorderedList, currentList);
return currentList;
}
}
}
Consider this as a directed graph and traverse the graph using Breadth First/Depth First. I prefer Breadth first.
- GeekLion May 14, 2018- While traversing, create a dictionary to store the count of adjacent vertices to each vertex
adj(a) = 2
adj(b) = 2
adj(c) = 0
adj(d) = 1
- Set prevNode = null
- Get the nodes with minimum value in dictionary and set that as start node -- node c
- Choose the one that includes prevNode or pick one if prevNode == null
- Store it in a list
- Keep on looping and you will get the order
- Print the list