Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
i thought about combining heap and BST properties, but didnt knew it was a standard thing... :)
Insert a heap itself is an O(logn) operation, and a binary tree traversal is also an O(logn) operation. So first pass, travel the heap to see if theres a duplicate. If not, insert it. That is O(2*logn). Don't know its allowed.
Its not clear how the traversal will be of O(logn) because this is not a binary search tree. the number could be in either subtree. Thanks
@artemis - heap is also full binary tree, in other words tree representation of array
check chapter 6 in CLRS book
@siva: Artemis is right in saying that searching an element would be a O(n) operations. Though its a binary tree (normally), but heap node's subtrees won't have BST property of being > than left and less than the right subtree. Hence Binary search won't happen. One optimization which can be done is to check for n-1/2 elem value (assuming its implemented as array), and going to leaves or internal nodes hence. Other can be (assuming max heap), to stop going in the subtree if the node's values is less than the element being searched. But, still it'll be O(n)....
@Prashant..yes, exactly what I meant.
@siva..searching in binary tree and binary search tree are different, because BST has the property of left node<root and right node>root, whereas in case of heap we if the element we are searching for < root then it can be in either left/right subtree.
Also, I will add..this was a theory question, so it may not be possible...but I am not sure.
You need some sort of supplementary data structure. It can't be done if all you have is a heap.
@Artemis: we can in fact show that this is so. Consider a heap whose bottom most layer is full (about n/2 elements there). Suppose that all the elements in all levels except the bottom level are larger than the number we're looking for. Then, the element we're looking for can be anywhere in the bottom-most level. We have to search in the bottom-most level, but checking any position in the bottom-most level reveals no information about any other element in the bottom-most level. In other words, if there's any position in the bottom-most level that you don't check in this particular situation, the element you're looking for could be hiding there. So in the worst case here, you must check every one of n/2 positions in the bottom-most level, which takes O(n) time.
we can take an extra array which stores the index of heap elements (heap is implemented using array) in sorted order,it will be kind of hashing concept. now applying binary search in this array taking the indices for the heap array - O(logn). and then, if not present, insertion in heap - O(logn)..
Huh?
You also need to update the sorted array on a heap insert, which makes insert Omega(n).
There was a reason others were talking about trees/hashtables.
during heap insertion, when the elements need to be shifted, then there only, the index-array elements will also be shifted
for example..
max-heap : 99(0), 77(1), 88(2), 11(3), 33(4), 22(5), 55(6)
correspoding index array : 3(0), 5(1), 4(2), 6(3), 1(4), 2(5), 0(6)
why you guys are making the problem too difficult. take an avl tree, and insert element both in heap and avl tree, now before inserting an element in heap, find out(in (logn)) weather the element is present or not, if not, insert in into both(require O(logn))
@sonesh... Do u even know the difference between HEAP and AVL???
Please find out more about AVL before making such random statements.
@Parixit: Now when you insert say 50 into the heap, how will you update the index array?
after inserting 50
max-heap : 99(0), 77(1), 88(2), 50(3), 33(4), 22(5), 55(6), 11(7)
correspoding index array : 7(0), 5(1), 4(2), 3(3), 6(4), 1(5), 2(6), 0(7)
add the element at the end of heap and increment the size of heap
check if it is great than its parent, if no, break
if yes, swap the element with its parent, repeat the above procedure until the element is already at the root or less than its parent
@lfenjoy9: you've described the normal heapify process. You haven't discussed the key aspect here of how you would ensure the element is not already in the heap.
in the web, i seen a new DS called Heap Structured Search Trees. I don't know this is the right answer. you can check if interested.
- Anonymous November 26, 2012