Goldman Sachs Interview Question
Java DevelopersCountry: India
Interview Type: In-Person
The goal should be , put empty the biggest jar into biggest jar in another set so that you dnt hv to pour a jar from initial container set twice.
To Achieve this , make a max heap of both container sets ,
pop out 1 container from each heap.
pour the water from a to b.
Now if both empty , discard them or if either of them has some water left , put them back in heap again. Increase a counter to C.
Complexity - X*(Logx+ LogY)
I think question is saying
we have two type of containers
let x and y,
let total are 5 containers in each type
x type has 1,2,3,4,5 capacities containers
y has 1,2,3,4,5 capacities containers
let cost to transfer from x to y is given as
y1 y2 y3 y4 y5
x1 3 4 2 1 0
x2 * 2 3 1 4
x3 * * 1 3 2
x4 * * * 2 1
x5 * * * * 3
* indicates that transfer from bigger container to smaller not possible
Answer:-
i think we can solve it by using dp
that transfer content of X1 into Y1 and proceed further, find total cost, then x1 to y2 for each such case find total cost and find min of these total costs.
i didnt get your question what is the capacity of Y containers? and what is fixed cost C is it directly proportional to something??
- Joey September 02, 2013