Adobe Interview Question
Software Engineer / Developers1) First find the maximum element, that will be the root of the heap.
2) This element divides the array in two half. Recursively, keep finding the largest element and making it root.
Time Complexity: O(n^2)
I think we can do it in n time
start from the first element. Keep track of the maximum element seen till now.
At each point, maximum element at that point will be one of roots and the elements seen before that will be part of its left subtree. (it could also be a leaf element)
elements after this max element and before any other element found in the list which is greater than this max element will be in its right subtree.
so you have to go through the list. Keep forming left subtrees. Once you reach to any right subtree. form it separately and attach it to main tree.
in this example
- 2
- 8
/
2
- 8 4
/
2
-
14
/
8
/ \
2 4
and so on
Code for hard coded heap, getting its inorder traversal and then restoring heap back from in-order traversal. Hint is how you get the in-order traversal, then just reverse the assignment in in-order traversal to get the heap back.
- Anonymous July 12, 2011