Amazon Interview Question Software Engineer in Tests
it will be O(lon n) because you would be comparing only half the elements becasue the smallest element would be present in the leaf node only.
searching in for min in n/2 elements is log(n/2) which is O(log n). log n looks to be correct
Let number of elements to be checked is n which is 16 = 2^4; m=4
dividing the long list in the following list of smaller elements.
With first scan (1st comparison ) - 2 * 16/2 = 2 list of 8 elements
With first scan (1st comparison ) - 4 * 16/4 = 4 list of 4 elements
With first scan (1st comparison ) - 8 * 16/8 = 8 list of 2 elements
With first scan (1st comparison ) - 16 * 16/16 = 16 list of 1 elements
In the fourth scan we will get the number.
Summing them together. 2*n/2+4*n/4+8*n/8+16*n/16 = n(1+1+1+1)= n * m (m =4)
Total scan needed = m . 2^m=16 taking log to the base 2, we have m = log (16)=log(n)
Conclusion- log(n) seems to be correct.
there is n/2 leafs and they are not sorted we make a linear search in these n/2 elements ....O(n)
there is n/2 leafs and they are not sorted we make a linear search in these n/2 elements ....O(n)
In a max heap every node is the minimum of its 2 children. So the minimum has to be a leaf. If we exchange any leaf(f) with this minimum leaf(mf), mf will never bubble up though f may bubble up. This suggests that mf can occur as any leaf(no pirticular position can be fixed for mf). Unlike BST we have no way of searching for an element in a binary heap. So we will have to do a delete_max() operation n times(may be n-1) to find the mf. Which means time taken to find mf is O(n). Is my argument correct.
there is n/2 leafs in a heap ...among which min exists...these are not sorted ..so we make a linear search among these leafs hence complexity O(n)
complexity will be log(n) below is my algo.
if(root->left==0 and root->right==0) return root->data;
else if(root->left && !root->right) root=root->left;
else if(root->right && !root->left) root=root->right;
else
{
rData=root->right->data;
lData=root->left->data;
if(rData<lData) root=root->rData;
else root=root->lData;
}
O(1)
- AL July 21, 2011