## Amazon Interview Question

Software Engineer / DevelopersCould 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