CareerCup

sort the heap into an array and when a duplicate is found , replace ine of the duplicates will null and then make the heap from the array again

hash_map = { }
def removeDuplicate(root):
    if hash_map.get(root->data):
        print "Found duplicate"
        swap(root->data, heaps(last_element) )
        delete(heaps(last_element) )
        min_heapify(root)
    else:
        hash_map.put(root->data, True)
        removeDuplicate(root->left)
        removeDuplicate(root->right)

1. create a new array of same size
2. if heap not empty delete from heap
3. if last filled array element not equal to deleted heap element add it to array
4. repeat step 2
5. the new array is the new heap

0nlog 2n space
please comment

How about:
Creating another min-heap from the given in-heap + 2 variables to hold the last Element inserted into the 2nd min-heap and element just removed from 1st heap, V1 and V2 resp.
1) Set V1,V2 = null
2) Repeat the following steps till given min-heap - 1st is empty
3) Remove the element from 1st min-heap into 'V2'
4) Compare this with 'V1' for equality.
a) If both are not equal i.e. NOT duplicate, insert this into 2nd min-heap and update V1 to this element

In a min heap the value(parent) <= value(child) .

so, compare if value(root) = value(left_child) or value(root) = value(right_child)
if neither of the 2conditions are met remove the root and heapify to make the next smallest node as the root and again compare.

.....................1
............4................2
........5.....6........3.......4

1!=4 and 1!=2 hence remove 1 and make 2 as the root.

......................2
............4.................3
......5..........6.......4

2 != 4 and 2 != 3
remove 2 and make 3 as the root.

....................3
.............4...........4
.........5......6

here we can see the multiple occurrence of 4, and 1 entry of 4 can be removed while preserving the other.

//Start from the root, compare the root with left and right child and children with themselves,
//if a duplicate, replace with the last element and heapify.
//I haven't written a Heapify, it is general Heapify routine.

public void removeDupes(int arr[], int index, int len)
{
   if (len == 0)
        return;
    
    int left = 2*index + 1;
    int right= 2*index + 2;  
    int duplicate = -1;
    if(left < len && arr[index] == arr[left]))
        duplicate  = index;
    else if( right< len && arr[index] == arr[right])
        duplicate  = index;
    else (right <len && left <len && arr[right] == arr[left])
        duplicate  = left;
    
    if (duplicate != -1)
    {
        arr[duplicate] == arr[len-1];
        len  = len - 1;
        heapify(arr, duplicate, len);
    }
    
    
    if(left < len)
        removeDupes(arr, left, len);
    if(right < len)
        removeDupes(arr, right, len);
       
      
}

//Start from the root, compare the root with left and right child and children with themselves,
//if a duplicate, replace with the last element and heapify.
//I haven't written a Heapify, it is general Heapify routine.

public void removeDupes(int arr[], int index, int len)
{
   if (len == 0)
        return;
    
    int left = 2*index + 1;
    int right= 2*index + 2;  
    int duplicate = -1;
    if(left < len && arr[index] == arr[left]))
        duplicate  = index;
    else if( right< len && arr[index] == arr[right])
        duplicate  = index;
    else (right <len && left <len && arr[right] == arr[left])
        duplicate  = left;
    
    if (duplicate != -1)
    {
        arr[duplicate] == arr[len-1];
        len  = len - 1;
        heapify(arr, duplicate, len);
    }
    
    
    if(left < len)
        removeDupes(arr, left, len);
    if(right < len)
        removeDupes(arr, right, len);
       
      
}

I think it should work the following way:

Start from the root
1) Compare a node with Minimum of its two childs.
2) If it is equal to the child, delete the node, replace it with the last node and call heapify for this and the following node so that heap comes in order again. Go to step 1 for the same node again.
3) If it is not equal to the any of immediate children, repeat the step 1 for the children recursively.

Maintain another min heap h2 for the frontier of your BFS in which all elements are unique.
1. put root in h2.
2. compare the top of h2 with its two children, if one child has the same value, remove it from h1 and compare again. if not equal, put the child in h2. After two children being compared or there is not children any more, pop the parent out from h2.
3. Do step 2 until h2 is empty.

i got placed in amazon ,what should i do next?

// n is the size of the heap array
// a is the min heap array.
void f(int* a, int n)
{
    int k = n;
    int i = 0;

    while(i<k)
    {
       if(LeftExists(i, k) && a[i]==a[Left(i)])
       {
           Remove(a, Left(i), n);
           k--;
       }
       else if(RightExists(i, k) && a[i]==a[Right(i)])
       {
           Remove(a, Right(i), n);
           k--;
       }
       else if(LeftExists(i,k) && RightExists(i,k) && a[Left(i)]==a[Right(i)])       
       {
           Remove(a, Right(i), n);
           i++;
	   k--;
       }
       else
       {
           i++;
       }       
    }
}

void Remove(int* a, int i, int n)
{
    a[i] = a[n-1];

    // if the new node value is bigger than its children, heapify down.
    while(true)
    {
       if(LeftExits(i,n) && a[i]>a[Left(i)])
       {
           swap(a[i], a[Left(i)];
           i=Left(i);
       }
       else if(RightExists(i,n) && a[i]>a[Right(i)])
       {
           swap(a[i], a[Right(i)]);
           i=Right(i);
       }
       else
       {
           break;
       }
    }
  
    // if the new node value is smaller than its parent, heapify up. 
    while(true)
    {
       if(i!=0 && a[i]<a[Parent(i)])
       {
           swap(a[i], a[Parent(i)];
           i=Parent(i);
       }
       else
       {
           break;
       }
    }
}

int Left(int i)
{
    return (i+1)*2-1;
}

int Right(int i)
{
    return Left(i)+1;
}

int Parent(int i)
{
    if(i==0) return -1;
    return floor((i+1)/2)-1;
}

bool LeftExists(int i, int n)
{
    return Left(i)<n;   
}

bool RightExists(int i, int n)
{
    return Right(i)<n;   
}

1) When ever you find a duplicate replace it with root element
2) Now delete the last node in heap and replace its value with root element(which is actually duplicate)
3) Now run heapify.