sakshisharma
BAN USER- 1of 1 vote
Answers
- sakshisharma in United Statespublic interface Triangle { /** * Three segments of lengths A, B, C form a triangle iff * * A + B > C * B + C > A * A + C > B * * e.g. * 6, 4, 5 can form a triangle * 10, 2, 7 can't * * Given a list of segments lengths algorithm should find at least one triplet of segments that form a triangle (if any). * * Method should return an array of either: * - 3 elements: segments that form a triangle (i.e. satisfy the condition above) * - empty array if there are no such segments */ int[] getTriangleSides(int[] segments); }
| Report Duplicate | Flag | PURGE
Linkedin Software Developer Algorithm
One simple approach to this problem can be: we know the ROOT of the tree is the one where the parent is null in the list. Once we figure out the parent, we can iteratively figure out its children and their children- by looping over the complete list and finding out the ones that point the current node as its parent. To build tree efficiently, we can use queue to keep track of the tree built till then. The running time would be O(n^2), with constant space (not really, we are keeping a queue as well)
public static Node buildTree(List<Relation> data){
if(data==null) return new Node();
Node root=new Node();
int children=0;
for(int i=0;i<data.size();i++){
Relation x=data.get(i);
if(x.parent==null){
root=new Node(x.child,null,null);
break;
}
}
if(root==null) return root;
Queue<Node> q=new LinkedList<Node>();
q.add(root);
while(!q.isEmpty()){
Node x=q.poll();
for(int i=0;i<data.size();i++){
Relation y=data.get(i);
if(y.parent==x.id){
Node n=new Node(y.child,null,null);
if(y.isLeft)
x.left=n;
else x.right=n;
q.add(n);
children++;
if(children==2){
children=0;
break;
}
}
}
}
return root;
}
Another way to approach this problem for a better running time could be by using a HashMap. We can hash the list with key as the parent and value as a list of its children. And then iteratively generating the tree. This solution would be O(n) time complexity and O(n) space complexity.
public static Node buildTree(List<Relation> data){
if(data==null) return new Node();
Node root=new Node();
HashMap<Integer,ArrayList<Relation>> tree = new HashMap<Integer,ArrayList<Relation>>();
for(Relation d:data){
if(d.parent==null)
root=new Node(d.child,null,null);
else{
if(tree.containsKey(d.parent)){
ArrayList<Relation> value=tree.get(d.parent);
value.add(d);
} else {
ArrayList<Relation> value = new ArrayList<Relation>();
value.add(d);
tree.put(d.parent,value);
}
}
}
if(root==null) return root;
Queue<Node> q = new LinkedList<Node>();
q.add(root);
while(!q.isEmpty()){
Node x = q.poll();
if(tree.containsKey(x.id)){
ArrayList<Relation> value=tree.get(x.id);
for(Relation v:value){
Node child = new Node(v.child,null,null);
q.add(child);
if(v.isLeft)
x.left=child;
else x.right=child;
}
}
}
return root;
}
Repmarktrejjo, Data Engineer at Accolite software
I’m Mark.I believe life is too short to be serious all the time, so if you cannot laugh ...
Repcarmenrhargis, Associate at Achieve Internet
Hi, I am Gladys, I live in Florida, USA, I am working as a project manager in a Life’s ...
If you have already sorted the array, you don't really need to verify that all the three conditions hold true.
- sakshisharma April 04, 2015Lets say a and b are the smallest of the three sides. If a+b>c is true, then obviously b+c>a and c+a>b will follow.