## Amazon Interview Question for SDE1s

Country: India
Interview Type: In-Person

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

Algo - Greedy Algorithm
Add smallest two ropes first and push the change back to min heap
Java Implementation

``````public class MinimunRopeJoiningCost {
static public void main(String[] args) throws Exception{
PriorityQueue<Integer> pq = new PriorityQueue<>();
for ( String s: temp){
}
Integer result = new Integer(0);
while(pq.size()>1){
Integer a = pq.remove();
Integer b = pq.remove();
result = result + a+b;
}
System.out.println(result);
}
}``````

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

You'll have to use min-heap. Extract the two smallest ropes Li and Lj from minheap and add back (Li + Lj) back to min-heap. Repeat the process until there is only one element in minheap and its length will be L1 to LN

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

Isn't the solution greedy ? We store rope array in min heap and join the two less expensive ( the less expensive with current rope) each time till there is one rope

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

O(n log n) - choose 2 smallest lengths for joining first - minHeap, put result back to heap, repeat till only one element in heap remains (the final length)

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

c++, priority_queue, O(n log n)

``````#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int minCost(vector<int>& arr) {
priority_queue< int, vector<int>, greater<int> > pq;
int i, cost;

cost = 0;
for (i = 0; i < arr.size(); i++) {
pq.push(arr[i]);
}

while (pq.size() > 1) {
i = pq.top();
pq.pop();
i += pq.top();
pq.pop();
pq.push(i);
cost += i;
}

return cost;
}

int main (int argc, char* argv[]) {
vector<int> arr;

cout << minCost(arr) << endl;

arr.push_back(1);
arr.push_back(2);
arr.push_back(3);
arr.push_back(5);
arr.push_back(7);

cout << minCost(arr) << endl;

return 0;
}``````

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

you are miss-interpreting the question.
1st : you have to join all the ropes available
2nd: total length should be sum of all ropes.

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

I think what you want it is an arithmetic progression.
So you should use this formula: Sn = ((L1+Ln) x n) / 2
C++ example:

``````int main() { int ropes[]{2,4,6,8,10}; //5 =n, the number of the ropes
int Sn=0;  Sn=((2+10)*5)/2;  cout<<"Ropes Length: "<<Sn; return 0; }``````

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

public class Test {

public static void main(String[] args) {

int swap;
int[] arr = {5,6,2,4,3};
int j = arr.length;

for( int i = j ; i > 1 ; i--){
for(int k = 0 ; k < 2 ; k++){
for(int m = k+1 ; m < i ; m++){
if(arr[k] > arr[m]){
swap = arr[k];
arr[k] = arr[m];
arr[m] = swap;
}
} // sorting first two elements.

}

arr[0] = arr[0] + arr[1];
System.out.print(arr[0]);
for(int n=1 ; n < i-1 ; n++){
arr[n] = arr[n+1];
System.out.print(","+arr[n]);
}
System.out.println("");
}
System.out.println("Total Cost : "+ arr[0]);
}

}

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

Dynamic Programming: for 3 ropes

min = min(l1 + 2 * (l2+l3), (l1+l2)*2 + l3, (l1+l3)*2 + l2)

Also, one more thing I noticed, if we sort them and join them

1 2 3 4 5 6

Join 1 and 2 : 3 3 4 5 6 : 3
Join 3 and 3: 6 4 5 6: 6
Join 6 and 4: 10 5 6 : 10
Join 10 and 5: 15 6 : 15
Join 15 and 6: 21

total : 55

Can we use this algorithm

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

Can you please add an example i.e. sample input and an output?

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

It does not matter - whatever order you choose the code is same - because when you join two ropes the next join would require joining ropes of larger length.

Final cost would be sum(L1, ,,, , LN) in whatever order

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

I don't get the confusion ?? Total cost of joining is L1 + 2*(L2+L3+L4...) + Ln. So you actually need to find the maximum and 2nd max make them the end of the rope and just join others. In my example I assumed L1,Ln are max. This will be the minimum cost.

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

this is Hoffman encoding in disguise

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

``````/* re-arrange the list of rope in sorted order
then get the cost of first two biggest rope joining
with the smallet rope from both the end.
so the cost will be
L1 + 2S1 + L2*/
int minCost(int *arr, int size){
int f = 0;
for (int s = 1, l = size - 1; arr[s] != INT_MIN; f++, s++, l--){
arr[s] = arr[f] + 2 * arr[l] + arr[s];
arr[l] = INT_MIN;
arr[f] = INT_MIN;
}
return arr[f];
}``````

input rope array :: 15 14 8 37 20
isorted rope passed to minCost() :: 37 20 15 14 8
minimum cost = 116

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

I think he program needs clarification, seems that the sum is always the same, can you provide more detail on it?

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

lets say we have ropes of 5, 6, 8, 9, total cost of joining is always going to 56, no matter what combination we take.
5+6=11
8+9=17
11+17=28
Final cost = 11+17+28=56

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

Total cost is always going to be the same irrespective of the combination -
example lets say we have ropes of length 5,6,8,9.
1) 5+6=11
2) 8+9=17
3) 11+17=28
4) 28+17+11=56

Total cost is always 56

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

``````package com.company;

import java.lang.*;
import java.util.*;

public class Main {

public static void main(String[] args) {
int a[] = {4, 3, 2, 6};
int n = a.length;
PriorityQueue<Integer> p = new PriorityQueue<>(n);
for (int i = 0; i < n; i++) {
}
int r = 0;
while(p.size()>1){
int b = p.remove();
int c = p.remove();
r = r + (c+b);
}
System.out.print(r);
}
}``````

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

I think what you want it is an arithmetic progression.
So you should use this formula: Sn = ((L1+Ln) x n) / 2
C++ example:
#include <iostream>

using namespace std;

int main()
{
int ropes[]{2,4,6,8,10}; //5 =n, the number of the ropes
int Sn=0;
Sn=((2+10)*5)/2;
cout<<"Ropes Length: "<<Sn;
return 0;
}

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

I think what you want it is an arithmetic progression.
So you should use this formula: Sn = ((L1+Ln) x n) / 2
C++ example:

``````#include <iostream>

using namespace std;

int main()
{
int ropes[]{2,4,6,8,10}; //5 =n, the number of the ropes
int Sn=0;
Sn=((2+10)*5)/2;
cout<<"Ropes Length: "<<Sn;
return 0;
}``````

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

As all the ropes lengths have to be considered no matter what, can't we directly sort the lengths and compute its sum? in any case, it seems like there is no minimum sum as the sum amount is always going to be same for any combination of lengths. I might be missing something here, if so please let me know.

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

Is it only me who notices that the cost is given L1 + L2, no matter what. So even if we join any random pieces of rope the cost is still gonna be fixed. So the cost might be (n-1)*(L1+L2). Thoughts on this?

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.