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

Hiring now

Flexport has 115 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Software Engineer II, Autonomous Freight Technology
Bellevue, Washington, United States
Software Engineer II, DevEx
Amsterdam, Netherlands
Staff Software Engineer, DevEx
Amsterdam, Netherlands

Or practice this question first

Next question