Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Written Test
The problem here is that you are not making the use of heap.
This is the generalized solution to convert an array[random] into heap.
@shondik: then can we use binary tree to find the duplicate and remove them from heap? But it needs extra space..
The heap can be implemented either in array or by making the nodes refer to each other.
the approaches are either keep travelling the nodes and when a duplicate is found , replace the duplicate with the last node and apply trickle down ..... or what i find more simpler is keep applying remove method of heap to fill the array in a sorted manner... then it would be much easier to find the duplicates
I think it's not even clear whether we can modify the heap directly, or whether we are only exposed to its API such as insert() and extractMin(). I suspect this is an easy problem where we are just supposed to extract them all into another data structure then add them back into the heap while de-duping.
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)
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.
// 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;
}
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
- codingAddicted July 14, 2012