## Amazon Interview Question for SDE-2s

Team: Robotics
Country: United States

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

This is very famous problem asked by Amazon thousand number of times. It is a min-heap problem.
They also presented once to me like this:
We have a strcat(s1,s2) that is 3rd party function. Every time you run this function, you need to pay cost s1.length()+s2.length() to 3rd party. You have to minimize this cost.
Suppose you have arrayp[ = {3,4,6,9},
If you start adding bigger numbers first, the cost is (9+6) + ((9+6)+4) + ((9+6+4)+3). You can see that 9 occurred most number of times. So, cost is more. Instead, if you start with 2 smallest numbers, cost will be calculated like this:
1. (3+4=7), now we have {7,6,9}
2. Take min 2 from these (6+7)=13, now we have (13,9)
3. Take min. 2 from these. and final sum is 22.
--------------
So, every time it is about taking minimum 2 numbers, adding them and putting the resultant sum back in set (or array). Again find 2 min. numbers, add them...
Repeat this process until you have a single element (or let's say you have 2 elements and sum them.).
So, algo goes like this:

``````int getMinCost(int a[], int n)
{
1. Create min heap (lets say pq) and push all elements of array into min heap (STL priority queue acts like min heap so you can use that).
2. int sum=0;
// heap size is n initially (number of array elements)
while(n>1) {

top1= pq.top(); top2 =pq.top();
sum+=top1+top2;
pq.push_back(top1+top2);
// priority queue runs heapify() itself.
n--;
}
return sum;
}``````

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.