Coding

Pour Water Between Buckets to Make Water Levels Equal

Asked at

Flexport

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

You have n buckets each containing some gallons of water in it, represented by a 0-indexed integer array buckets, where the ith bucket contains buckets[i] gallons of water. You are also given an integer loss.

You want to make the amount of water in each bucket equal. You can pour any amount of water from one bucket to another bucket (not necessarily an integer). However, every time you pour k gallons of water, you spill loss percent of k.

Return the maximum amount of water in each bucket after making the amount of water equal. Answers within 10-5 of the actual answer will be accepted.

Input: buckets = [1,2,7], loss = 80 **Output: **2.00000 Explanation: Pour 5 gallons of water from buckets[2] to buckets[0]. 5 * 80% = 4 gallons are spilled and buckets[0] only receives 5 - 4 = 1 gallon of water. All buckets have 2 gallons of water in them so return 2.

Input: buckets = [2,4,6], loss = 50 **Output: **3.50000 **Explanation: **Pour 0.5 gallons of water from buckets[1] to buckets[0]. 0.5 * 50% = 0.25 gallons are spilled and buckets[0] only receives 0.5 - 0.25 = 0.25 gallons of water. Now, buckets = [2.25, 3.5, 6]. Pour 2.5 gallons of water from buckets[2] to buckets[0]. 2.5 * 50% = 1.25 gallons are spilled and buckets[0] only receives 2.5 - 1.25 = 1.25 gallons of water. All buckets have 3.5 gallons of water in them so return 3.5.

Consider the array **buckets = [5, 5, 5] **and loss = 30. What is the maximum possible water level after balancing?

1 <= buckets.length <= 105
0 <= **buckets[i] **<= 105
0 <=** loss** <= 99

cpp

class Solution {
public:
    double equalizeWater(vector<int>& buckets, int loss) {
        // Your code goes here
    }
};

java

class Solution {
    public double equalizeWater(int[] buckets, int loss) {
        // Your code goes here
    }
}

python

class Solution:
    def equalizeWater(self, buckets, loss):
        # Your code goes here

javascript

class Solution {
    equalizeWater(buckets, loss) {
        // Your code goes here
    }
}

csharp

public class Solution
{
    public double EqualizeWater(int[] buckets, int loss)
    {
        // Your code goes here
    }
}

func equalizeWater(buckets []int, loss int) float64 {

}

Stuck? Show a way to structure it+

01Binary-search a candidate final level x between zero and the maximum bucket.
02Buckets above x donate their surplus.
03Buckets below x need their deficit divided by the retained fraction.
04Check whether total donor surplus covers required poured volume.
05Run enough iterations for the requested precision.

Reference answer

For a proposed equal level x, do not compare total water directly because some disappears in transit. A bucket above x can pour bucket minus x gallons. A bucket below x needs x minus bucket gallons delivered, so the donor must pour that deficit divided by one minus loss over 100. Sum available poured gallons from high buckets and required poured gallons for low buckets; x is feasible when available is at least required. Feasibility is monotonic: lowering x cannot make it harder, so binary search from zero through the largest bucket. Use about 60 iterations with doubles, avoiding equality comparisons. This directly handles loss zero and loss near 100; with 100 percent loss, no deficit can be supplied, so the answer cannot exceed the minimum initial bucket. Each feasibility check is O(n), giving O(n times I) time for I fixed precision iterations and O(1) extra space.

Then expect these follow-ups

How would different loss rates per transfer change the model?
Tests: constraint adaptation
Why are 60 iterations sufficient for 1e-5 accuracy?
Tests: correctness reasoning

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question