Lunatic Server Solutions Interview Question for Java Developers
- 0of 0 votes
Answershi to all tech brains.
- dev May 25, 2012 in United States
we made an interview round and ask this problem.
problem needs complete solution in java.
Any one of you who can solve it may appreciate and will get some benefits.
In this problem, you have to implement a sorting algorithm called Tournament sort, which uses a complete
binary tree.
The depth D of the tree will be given as input. Also, N positive integers will be given, where N is the Dth
power of 2 (ie, 2 ** D).
Construct a complete binary tree of depth D and fill in the leaf nodes with the N given integers in the order
given ie. the first integer should be at the leftmost leaf and the last integer should be at the rightmost leaf.
Next, update all the non-leaf nodes in the tree such that each nonleaf node contains the maximum of the
values in its children. Thus, the root will contain the maximum of all the N integers.
Implement a procedure ’maxdelete’ which essentially removes the maximum value from the tree and updates
the tree as follows:
1. traverse the tree from the root
2. find the leaf with the maximum value ie. the value at the root. (note that in this tree, if the value at a
non-leaf node is T, either its left child or its right child will have value T).
3. replace the value at that leaf node with -1 and
4. update the rest of the non-leaf nodes such that each non-leaf node contains the maximum of the
values in its children.
Perform the ’maxdelete’ operation 3 times on the tree and print out the INORDER traversal of the tree after
each operation.
Example
Given depth = 2
Given integers: 25 57 37 48
Constructed and updated tree:
57
/ \
57 48
/ \ / \
25 57 37 48
after first 'maxdelete'
48
/ \
25 48
/ \ / \
25 -1 37 48
after second 'maxdelete'
37
/ \
25 37
/ \ / \
25 -1 37 -1
after third 'maxdelete'
25
/ \
25 -1
/ \ / \
25 -1 -1 -1
Input Specification
The input will consist of a positive integer D followed by a positive integer N (where N is the Dth power of
2) followed by N positive integers. All the integers are separated by a single space and will be on a single
line. There will be no duplicates among the N integers. D will be greater than 1 and less than 9.
Output Specification
The output should consist of 3 lines. Each line should contain the INORDER traversal of the tree after a
’maxdelete’ operation. All the integers on a line should be separated by a single space.
Sample Input/Output
Input
2 4 25 57 37 48
Output
25 25 -1 48 37 48 48
25 25 -1 37 37 37 -1
25 25 -1 25 -1 -1 -1| Report Duplicate | Flag | PURGE
Lunatic Server Solutions Java Developer Data Structures
Interview Type: In-Person
come on, it's straightforward - just tests your coding skills..
- Anonymous May 26, 2012