Software Engineer
BAN USER- 0of 0 votes
AnswersGive an unsorted array find count of pairs of numbers[a,b] where a > b and b comes after a in the array.
- Software Engineer
Eg. {8,3,6,10,5}
the count of such numbers is 5. i.e. (8,3), (8,6), (8,5), (6,5) and (10,5)| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm
I told the same answer using hash table but the person asked if i could do without hashtable.
So the solution is sort the array , have one pointer pointing to the first and another pointing to the last. add the first and last , if the number is greater than the number we want then decrease the last pointer else increase the start pointer. keep doing this till we get the sum we want.
Cool, just that you could have made it even more simpler.
Keep a global counter and keep an internal node counter which keeps the count of the right subtree.
When you move right, increment the internal counter of the current node you are checking against, when you move left increment the global counter by one AND by the number in the internal counter.
So in the example i gave, insert 8, GC=0, insert 9, GC=0, internal counter of 8=1, insert 10, GC=0 internal counter of 8=2, and internal counter of 9=1.
now when you insert 7, increment global counter by one and add 2 to it since 8's internal counter is 2, that means there are 2 more numbers greater than 7.
So we get 3 as the answer.
Hope this is clear
i guess you mean Binary Search Tree.
Okie good direction, but still its not the exact answer.
Try your solution for 8 9 10 7
Binary search on a list?
- Software Engineer June 20, 2010Helps in faster insertion but still you have to do a compare linearly. And every time you insert a number in a large list you have to compare a lot. See if you can think of something else.
- Software Engineer June 20, 2010Seems fine to me. Just that u need to insert the element every time to keep it sorted. Maybe costly in large arrays. I had given a elegant solution. The hint was i could use any data structure i want.
- Software Engineer June 20, 2010Yes, this is brute force. Plus we just need the count. Dont have to print all the numbers.
- Software Engineer June 20, 2010private Node ConvertLL(Node root)
{
if (root == null)
return null;
Node rootNode = new Node(root.data);
rootNode.left = null;
rootNode.right = null;
if (root.left == null && root.right == null)
{
return rootNode; //Left Node
}
Node leftNode = ConvertLL(root.left);
Node rightNode = ConvertLL(root.right);
Node curNode = leftNode;
if(leftNode!=null)
while (curNode.right != null) //Move to the right end of the left segment
{
curNode = curNode.right;
}
Append(curNode, rootNode); //Append Left with currentRoot
Append(rootNode, rightNode); //Append currentRoot with Right
if (leftNode != null)
return leftNode;
else
return root;
}
private Node Append(Node NodeOne, Node NodeTwo)
{
if(NodeOne!=null)
NodeOne.right = NodeTwo;
if(NodeTwo!=null)
NodeTwo.left = NodeOne;
return NodeOne;
}
Yeah this is the best and simplest method. Dont know why people are giving complicated answers.
- Software Engineer June 16, 2010You are using 2 integers, q and l for storage. i guess l is to count the elements, but we are allowed to use just one.
- Software Engineer June 15, 2010Thats fine as long as he is storing the final value in just an integer.
- Software Engineer June 15, 2010I think the solution where we keep the current value and the max value of the elements below it is the best.
People here are telling that only storing the max value is enough, but that is not enough the reason being, if the max value is popped out[using a pop operation] then we need to rescan the stack to get the next max value which takes o(n) time. So best is to have each element store the current value and max value till that point.
Yes agreed, but this can be handled using Red Black trees, everything remains the same just that you need to recalculate the internal counter of each node when you do left or right rotation.
- Software Engineer June 28, 2010