## Amazon Interview Question for Software Engineer / Developers

• 0

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

Huffman coding

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

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

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

@Bogdan:Can you elaborate more?

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

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

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

@Irina: Your explanation is sound, but you are making an assumption here. The main solution depends upon
1. Do we need to tie all the ropes
Or
2. Do we need to tie a any two or more ropes

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

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.

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

You said it better... the Huffman coding idea... which is a greedy idea... :)

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

yes. I agree Huffman coding. You can use Min priority queue to insert values .

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

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)

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

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

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

Alright so sort them and do a merge on adjacent ones. Ex:

``````2,2,3,3,4,5
2+2, 3+3, 4+5. Cost: 19
Resultant array (4, 4, 9)
4+4. Cost. 8
Resultant array: 8,9
Resultant array: 8+9. Cost. 17
Total cost 19+8+17 = 44``````

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

It could be solved using dynamic algorithm. Some thing on lines of knapsack problem where you have to keep the sum min.

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

Was it a phone interview?

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

Use minheap.

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

its Dynamic programming problem

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

whats wrong with chennavarri's soln ??

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

Consider a= 1, b = 1, c = 1, d = 1.
tying a and b = 1 + 1 = 2
tying ab to c = 2 + 1 = 3
tying abc to d =3 + 1 = 4
Total cost = 2 + 3 + 4 = 9

IF u solve it as ab = 1 + 1 = 2
cd = 1 + 1 = 2
ab to cd = 2 + 2 = 4

Total cost = 2 + 2 + 4 = 8

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

the problem is like this one: merging optimal n arrays.
In each step you will tie the shortest 2 ropes.
ex: 1, 3, 6, 2, 8, 5
order: 1, 2, 3, 5, 6, 8
1 + 2 = 3 => 3, 3, 5, 6, 8
3 + 3 = 6 => 5, 6, 6, 8
5 + 6 = 11 => 6, 8, 11
6 + 8 = 14 => 11, 14
11 + 14 = 25

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

anybody can elaborate huffman algo to solve the problem

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

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
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

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.