Arranging heights based on number of persons of greater height standing in front of him | Saikat's space
You are given two arrays, first array contain integer which represent heights of persons and second array contain how many persons in front of him are standing who are greater than him in terms of height and forming a queue. Ex
A: 3 2 1
B: 0 1 1
It means in front of person of height 3 there is no person standing; person of height 2 has one person in front of him who has greater height than him, similar to person of height 1. Your task is to arrange them. Output should be:
3 1 2
https://moonstonelin.wordpress.com/2016/04/22/reconstruct-tree/
https://www.careercup.com/question?id=4699414551592960
https://www.careercup.com/question?id=24532662
http://www.weiming.info/zhuti/JobHunting/32513203/
Read full article from Arranging heights based on number of persons of greater height standing in front of him | Saikat's space
You are given two arrays, first array contain integer which represent heights of persons and second array contain how many persons in front of him are standing who are greater than him in terms of height and forming a queue. Ex
A: 3 2 1
B: 0 1 1
It means in front of person of height 3 there is no person standing; person of height 2 has one person in front of him who has greater height than him, similar to person of height 1. Your task is to arrange them. Output should be:
3 1 2
public class Node
{
public Person Person { get; set; }
public int LeftSelfCount { get; set; }
public Node Left { get; set; }
public Node Right { get; set; }
public Node(Person person, int leftSelfCnt)
{
this.Person = person;
this.LeftSelfCount = leftSelfCnt;
this.Left = null;
this.Right = null;
}
}
public class Tree
{
public Node Root { get; set; }
public Tree()
{
this.Root = null;
}
public void Insert(Person p)
{
if (this.Root == null)
{
this.Root = new Node(p,
1
);
}
else
{
if (p.AheadTallerCount < this.Root.LeftSelfCount)
{
this.Root.LeftSelfCount++;
InsertHelper(this.Root, this.Root.Left, p);
}
else
{
InsertHelper(this.Root, this.Root.Right, p);
}
}
}
public void InOrder(Node node, List<Node> result)
{
if (node == null)
{
return;
}
InOrder(node.Left, result);
result.Add(node);
InOrder(node.Right, result);
}
private void InsertHelper(Node parent, Node child, Person p)
{
if (child == null)
{
if (p.AheadTallerCount < parent.LeftSelfCount)
{
parent.Left = new Node(p,
1
);
}
else
{
parent.Right = new Node(p,
1
);
}
}
else
{
if (p.AheadTallerCount < child.LeftSelfCount)
{
child.LeftSelfCount++;
InsertHelper(child, child.Left, p);
}
else
{
InsertHelper(child, child.Right, p);
}
}
}
}
public List<Person> ReConstructTree(List<Person> people)
{
people.Sort(this.SortByHeight);
Tree tree = new Tree();
foreach (Person p in people)
{
tree.Insert(p);
}
List<Node> list = new List<Node>();
tree.InOrder(tree.Root, list);
List<Person> result = new List<Person>();
foreach (var n in list)
{
result.Add(n.Person);
}
return result;
}
private int SortByHeight(Person p
1
, Person p
2
)
{
if (p
1
.Height < p
2
.Height)
{
return
1
;
}
else if (p
1
.Height > p
2
.Height)
{
return
-1
;
}
else
{
return
0
;
}
}
https://www.careercup.com/question?id=4699414551592960
https://www.careercup.com/question?id=24532662
http://www.weiming.info/zhuti/JobHunting/32513203/
Read full article from Arranging heights based on number of persons of greater height standing in front of him | Saikat's space