Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Take example 1,9,6,2,5
If Cost in given input order is : 10+16+18+23 = 67
If cost is sorted then : 3+8+14+23 = 48
minHeap is : 3+9+14+23 = 49
1
/ \
2 6
/\
9 5
So min heap wont give the least result sorting will.Please correct me if I am wrong
Sorting won't work. If you look at 4, 5, 6, 7
Sorting will give you a cost of 9 + 15 + 22 = 46
Huffman/minheap above will give you a cost of 9 + 13 + 22 =44
In the example 1,9,6,2,5, the minheap algorithm will do the following steps:
1 with 2, cost 3
3 with 5, cost 8
6 with 8, cost 14
9 with 14, cost 23
which is 48 overall.
EDITED: there is flaw in my post! The order of sticks matters!
Re-formulate the problem:
Given n sticks of length L_1, L_2, ..., L_n, with total length of L.
Only combination of two sticks into one is allowed each time. Every combination costs the sum of the two sticks.
Calculate the minimum cost to combine all n sticks into a stick of length L.
This can be solved by recursive/DP as following.
Let C(u,v) be the minimum cost to join sticks from number u to number v.
The recursive formula will be:
C(u,v) = min { C(u,k) + C(k+1,v) }, for k = u+1 to v-1;
The answer will be C(1,n).
My pseudo code implementation using recursive with memoization:
joinSticks(u,v):
if (u == v) return L[u];
if (Mem[pair(u,v)] != 0 ) return Mem[pair(u,v)];
minCost = maxInt;
for k = u to v-1
minCost = min { minCost, joinSticks(u,k) + joinSticks(k+1,v) };
Mem[pair(u,v)] = minCost;
return minCost;
My solution may work for the constraint that:
"Only combination of two CONSECUTIVE sticks is allowed"
Sorry!
@ninhnnsoc : Your approach will fail for the following scenario
Consider Lengths as {1,4, 2}. According to your approach, it will consider the following cases
Case 1 : minCost(1) + minCost(4,2)
minCost(4,2) is 6 and joining it with 1 will cost 7 so total is 13
Case 2: minCost(1,4) + minCost(2)
minCost(1,4) will be 5 and joining with 2 will be 7 so total will be 12
But the optimal solution is MinCost(1,2) and Join with 4
Total Cost = 3 + 7 = 10
Recursively pick the two sticks of minimum length, merge it (e.g. sum value) and add it back to the collection.
The reason why you should always pick the minimum 2 length is:
1, suppose you have two sticks, a1 and a2
the cost is a1 + a2
2, suppose you have three sticks, a1 < a2 < a3
the answer is you pick a1, a2 first, the cost is 2*(a1 + a2) + a3
why if you choose a3 first? the cost would be higher than above by:
2 * (a3 - a2) - (a3 - a2) = a3 - a2, which is a positive value.
So you should always pick the minimum 2 sticks.
1, Sort the array
2, pick the first two
3, insert the sum of first two to the sorted array (log n)
repeat that steps until done
total cost is nlogn
I think the problem can be better explained with an example as many people are thinking that the total cost will be sum of all the lengths. Suppose there are 3 sticks of length 1, 2, 4
You can do the combination in this way,
Step 1: 1+2 (cost=3) Now we have two sticks of length 3 and 4
Step 2: 3+4(cost=7) Now we have one stick of length 7
Total cost 7+3=10
But if you do it in this way,
Step 1: 4+2 (cost=6) Now we have two sticks of length 6 and 1
Step 2: 6+1 (cost=7) Now we have one stick of length 7
Total cost 6+7=13
So we can see that if we add the smaller ones first, we will minimize the cost. We can solve it with a min heap. We will add all the lengths in the min heap. We will pop two from the min heap and add them and put them back in the heap. We will continue this process till there is no more stick.
I think the key is:
1. sort the sticks in ascent order, L1 <= L2 <= L3 <=...Ln
2. each time when combined 2 sticks, then put it back to the pool, and sort it again as 1)
3. we can see if the each time combination is smallest, the summary of all costs number is smallest.
As there is no restrictions on the order of sticks mentioned so perhaps sorting them in ascending order and start combining from the least one will give the minimum cost.
suppose the length of sticks are x1,x2,x3,x4.........,xn then the total cost will be given by (x1 + x2) + (x1+x2+x3) + (x1+x2+x3+x4)+...........+(x1+x2+x3+..........+xn)
So to have the minimum value x1,x2,x3......,xn must be in increasing order.
#include <stdio.h>
#include <stdlib.h>
#define INF (~0)
/* This can be optimized by caching */
unsigned int stick_length(int sticks[], int s, int e)
{
unsigned int i, ans = 0;
for (i = s; i <= e; i++) {
ans += sticks[i];
}
return ans;
}
unsigned int join_sticks(int sticks[], int s, int e, unsigned int **cache)
{
int k, p1, p2, tmp;
if (s > e) return INF;
if (s == e) return sticks[s];
if (cache[s][e] != INF) {
return cache[s][e];
}
for (k = s; k < e; k++) {
p1 = join_sticks(sticks, s, k, cache);
p2 = join_sticks(sticks, k+1, e, cache);
/* adding stick lengths, not same as making cost */
tmp = stick_length(sticks, s, k) + stick_length(sticks, k+1, e);
/* adding making cost */
if (k > s) tmp += p1;
if (k+1 < e) tmp += p2;
if (tmp < cache[s][e]) {
cache[s][e] = tmp;
}
}
return cache[s][e];
}
int main()
{
int i, j;
int sticks[] = {24, 25, 28, 4, 6, 10, 9};
// int sticks[] = {2, 3, 4, 6};
// int sticks[] = {2, 3, 4, 6, 7};
// int sticks[] = {13, 4, 6};
int n = sizeof(sticks)/sizeof(sticks[0]);
unsigned int ans;
unsigned int **cache;
cache = (unsigned int **)calloc(n, sizeof(int *));
for (i = 0; i < n; i++) {
cache[i] = (unsigned int *)malloc(n*sizeof(int));
}
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
cache[i][j] = INF;
}
}
ans = join_sticks(sticks, 0, n-1, cache);
printf("ans: %u\n", ans);
return 0;
}
I can come up with a NlogN complexity algo if lengths given are in random order.
Incase the lengths are sorted then complextity would be O(N)
Lengths = Array.Sort(Lengths)
int [] IncrementalLength = new int[Lengths.length + 1]
for(int i=1;i<=Lengths.length;i++)
incrementalLength[i] = incrementalLength[i-1] + Lengths[i-1]
TotalSum = SumArray(incrementalLength)
return TotalSum
Dude, thx for your solution, do you mind to explain why it is the minimum cost solution?
The "Huffman coding" solution is the same as the one by anshul14ranjan above. The common point between Huffman coding and this problem is that in Huffman, you always start by combining the two characters with the smallest frequency, and you repeat that same step until you build the whole tree, which is very similar to anshul14ranjan 's solution
Suppose there are n(>0) sticks of length {L1, L2, ... , Ln}, where L1<=L2<=...<=Ln, I think the answer is:
cost =
(1) 0, if n=1;
(2) L1+L2, if n=2;
(3) L1 + 2 * (L2 + L3 +...+Ln-1) + Ln, if n>2;
Prove:
Each time we combine 2 sticks to 1, there remains n-1 sticks, until there is only 1 stick. So we need to combine n-1 times. To minimize each combine cost, we should choose the shortest 2 sticks all the time.
So, the 1st combine cost is L1+L2, left n-1 sticks of lenght {L2, L3, ... , Ln};
the 2nd combine cost is L2+L3, left {L3, L4, ..., Ln};
the 3rd combine cost is L3+L4, left {L4, L5, ..., Ln};
...
the total cost is L1+2*(L2 + L3 +...+Ln-1)+Ln.
I don't get it?
The answer is always sum of overall stick
It's independent of choices leading to the final sum.
It's not even a minimization problem.
for loop in any order over the sticks, and return the accumulated sum.
no its not.
ie. you have sticks length 1,2,3
case 1:
you put 1 and 2 together first, cost1 = 1+2 = 3, and you have sticks length 3,3
then you put 3 in, cost2 = 3+3=6;
so the total cost = cost1+cost2 = 3+6 = 9;
case 2"
you put 2 and 3 together first, cost1 = 2+3 =5, and you have sticks length 1,5
then you put 1 in, cost2 = 1+5=6;
so the total cost =cost1+cost2 = 5+6 = 11;
Ridiculous. At least try the problem first. It has an obvious solution! There was a similar question, search for it. The answer there was dynamic programming.
You have an array of stick lengths,
sLen = {1, 4, 6, 10, 11 }.
If you remember your math, Addition is Commutative and Associative, i.e.
((1 + 4) + (6 + 10) + 11) == ((1 + 4) + (6 + (10 + 11)). The minimum cost is the same no matter how you do it. Unless you multiply two lengths that make up one piece and add the cost of each piece. Only in the latter case the answer will be different.
Suppose L1,L2,...Ln are length of the sticks with L1 <= L2 <= L3 <= ... <=Ln.
No matter how you form the final stick, each stick is used twice except for the outer ones, which are used only once. Hence, any combination which puts the largest two sticks at the left & right ends will be an optimal one.
Minimal cost = 2*[ L1 + L2 + ... + L(n-2)] + L(n-1) + Ln
An arrangement having this cost: Ln,L1,L2,L3,...L(n-1)
Each time, you combine two sticks of min length, you have (N-2) + 1 (the new stick) = N-1 left in system. So now you re-calculate and choose 2 min sticks and combine those and continue.
- anshul14ranjan March 17, 2014Implementation:
Use a min-heap, remove min and next min = combine, insert the new length into the heap.
worst case Per operation runtime: 2*log (N) (remove 2 mins) + log (N) (insert new value)
Operation repeated N times = 3N*log(N) = O(N log(N))
However, if you notice, the height of min-heap goes on decreasing in each step and a more tighter analysis would yield a log(N!) worst case complexity (which ofcourse is O(N*log(N))