## Amazon Interview Question for Consultants

• 0

Country: United States
Interview Type: Phone Interview

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

Greedy Algorithm DOES NOT work for the 0-1 Knapsack problem, where items are not divisible; you either take an item or not. However, fractional Knapsack (where items are divisible) problem can be solved with Greedy Algorithm.

DP can solve both 0-1 and Fractional Knapsack problems.

Comment hidden because of low score. Click to expand.
-2

I think we can use greedy approach for 0-1 knapsack as after sorting by value of items, you should keep moving to i+1 item if i th does not fit in knapsack.

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

@Raj: that would not result in an optimal solution. Try to give an argument for why the greedy approach would be correct, and you will probably come to realize why it doesn't work.

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

@eugene,
yes you are right.the following will not work in greedy

value : 20 8 9 5.6 5.5
weight : 5 2 3 2 2
Knapsack capacity is 11

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

Greedy algorithm produce optimized solution in each step, but it cannot ensure global optimized solution. Where as Dynamic Programming always produce global optimized solution.

Comment hidden because of low score. Click to expand.
-2

I think local optimized is also global optimized in case of knapsack

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

I've also answered this in the other post. Basically the solution depends on the problem. If the problem is the 0-1 Knapsack problem, where items are not divisible; you either take an item or not, then you can ONLY use DP. However, fractional Knapsack (where items are divisible) problem can only be solved BOTH with the Greedy Algorithm and DP.

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

if you use greedy approach for 0-1 knapsack problem you will not get the optimal solution.
In this case greedy will give an approximate answer and why we are going for DP is yet another story.Here we will get subpriblems which will have to solve more than one time in the reccursion, So in order to reduce this overhead of solving a problem more than one time we are going for DP

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

greedy algo is for fractional knapsack
dp is for 0-1 knapsack

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.