## Amazon Interview Question for Software Engineer / Developers

• 0
of 0 votes

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

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

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

@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
of 0 votes

@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
of 0 votes

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

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

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
of 0 votes

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
of 0 votes

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
of 0 votes

whats wrong with chennavarri's soln ??

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

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 and a. 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

Add a Comment
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.

Learn More

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

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More