Amazon Interview Question Software Engineer / Developers
Could you please explain?
Becoz I think the cost is constant. For example: if I have w,x,y,z length of ropes and I have to tie them together. Then what ever is order of tying the ropes, cost is going to be w+x+y+z
if you have w, x, y, z length of ropes and you want to tie them together you can have multiple results. for instance:
if you choose to tie w to x (cost w + x), y to z (cost y + z), and then tie the results together the total cost will be 2 * (w + x + y + z)
but if you tie w to x (w + x), and tie the result with y (w + x + y) and then tie the result with z (w + x + y + z) the total cost will be 3 * w + 3 * x + 2 * y + z
Suppose you have 4 ropes with lengths 1 , 1 , 1 , 1. Initially , the cost C = 0. If I tie the first 2, I get 3 ropes with lengths 2, 1, 1 and C = 2.If i tie now the first 2 again, I get 2 ropes with 3 and 1 lengths and C = 5. Finally , I tie the last 2 and I get C = 9. But if I choose at every step the smallest 2 ropes as length, I get a better result, because the configuration would be 1 ,1,1,1 with C = 0 -> 2 ,1 ,1 with C = 2 -> 2 , 2 with C = 4 and finally the cost is C = 8.This is the Huffman coding idea.
Why not just sort and add ascendingly??
given 3,2,4,1. The minimal cost is 19 for sequence (((1+2) +3) +4).
And a generalized observation could be made, if lengths are sorted as s1,s2,s3...sn
minimal cost is given by, (n-1)*s1 + (n-1)*s2 + (n-2)*s3 +..+(n-k)*s(k+1)+..+ 1*sn
in the above example=> 3*1 + 3*2 + 2*3 + 1*4 = 19
Another example: given lengths: 7,5,6,5 then sort => 5,5,6,7
minimal cost = 3*5 + 3*5 + 2*6 = 1*7 = 49 , complexity is O(nlogn + n)
it's wrong. for (2,2,3,3) ur sol gives
2+2 = 4
4+3 = 7
7+3 = 10
total 21
however, optimal is 20
Order N^2 algo- iam sure there will be better.
sort the ropes according to their lengths. lets say we get array a.
add tow smallest one a[0] and a[1]. put this new rope in the array to a place which maintains the sorting order. repeat.
sorting - nlogn
each addition -0(1)
putting this rope to sorted array again for n ropes - 0(n)
for n itemes or ropes - n^2
so all in all n^2
Huffman coding
- Bogdan October 10, 2010