Amazon Interview Question
SDE1sCountry: India
Interview Type: In-Person
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;
}
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]);
}
}
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
/* 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
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++) {
p.add(a[i]);
}
int r = 0;
while(p.size()>1){
int b = p.remove();
int c = p.remove();
r = r + (c+b);
p.add(c+b);
}
System.out.print(r);
}
}
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;
}
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;
}
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.
Algo - Greedy Algorithm
Add smallest two ropes first and push the change back to min heap
Java Implementation
- onFingers February 24, 2016