## Amazon Interview Question for Software Engineer / Developers

Country: India
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
2
of 4 vote

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

Comment hidden because of low score. Click to expand.
0

good idea!

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

a heap is nothing but an array with heap conditions right?

Comment hidden because of low score. Click to expand.
0

right! But are you making use of those conditions?

Comment hidden because of low score. Click to expand.
0

@shondik: then can we use binary tree to find the duplicate and remove them from heap? But it needs extra space..

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

1. Create a vector.
2. Extract Min-heap element from the heap.
3. If this element is same as last inserted then simply discard the element, otherwise insert the element.
4. Create the min-heap using the elements in the array.

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````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)``````

Comment hidden because of low score. Click to expand.
0

Good one !

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

Doubt ? u r deleting the non duplicates nodes also rite?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````//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);

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````//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);

}``````

Comment hidden because of low score. Click to expand.
-1
of 3 vote

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.

Comment hidden because of low score. Click to expand.
0

duplicates need not be the child of the parent having same value..
duplicates can be at the same level of the heap.. are you getting my point?

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

congrats sri..help me i am about to appear for amazon interview

Comment hidden because of low score. Click to expand.
0

Then share ur questions here . It will be useful for others.

Comment hidden because of low score. Click to expand.
0

then pls share with us the details like your Current CTC, CTC you expected, CTC offered, Exp in No.of years etc.,

Comment hidden because of low score. Click to expand.
-2
of 2 vote

``````// 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;
}``````

Comment hidden because of low score. Click to expand.
0

will this code work for 3 4 5 7 9 9 10. I dont think so it is

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

how can you say that the element in a node is duplicate?

Comment hidden because of low score. Click to expand.
0

First you need to find a duplicate.

Comment hidden because of low score. Click to expand.
0

I don't understand what you're proposing.

Comment hidden because of low score. Click to expand.
0

@manan, how you are finding the duplicate in the heap?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.