Jobs

Interviews

Discussions

Water and Jug Problem

Medium

Google

4 views

Topics:

ArraysRecursionDynamic Programming

You are given two jugs with capacities x liters and y liters. You have an infinite water supply. Return whether the total amount of water in both jugs may reach target using the following operations:

Fill either jug completely with water.
Completely empty either jug.
Pour water from one jug into another until the receiving jug is full, or the transferring jug is empty.

For example:

If x = 3, y = 5, target = 4, return true.
If x = 2, y = 6, target = 5, return false.
If x = 1, y = 2, target = 3, return true.

What is the most efficient way to determine whether the target can be reached? Explain the time and space complexity. Can you provide code?

Water and Jug Problem

Medium

Google

4 views

Topics:

ArraysRecursionDynamic Programming

Fill either jug completely with water.
Completely empty either jug.
Pour water from one jug into another until the receiving jug is full, or the transferring jug is empty.

For example:

If x = 3, y = 5, target = 4, return true.
If x = 2, y = 6, target = 5, return false.
If x = 1, y = 2, target = 3, return true.

What is the most efficient way to determine whether the target can be reached? Explain the time and space complexity. Can you provide code?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Are the jug capacities (jug1Capacity and jug2Capacity) and the target capacity (targetCapacity) guaranteed to be non-negative integers?
If the targetCapacity is greater than the sum of jug1Capacity and jug2Capacity, should I return false? Or is there some other expected behavior?
If the targetCapacity is 0, should I return true if either jug1Capacity or jug2Capacity is non-zero, or should both be zero?
Can jug1Capacity or jug2Capacity be zero? If so, how should I handle the case where both are zero and the targetCapacity is non-zero?
Is there a practical upper bound on the jug capacities? (This might influence the choice of algorithm to avoid potential integer overflow issues in intermediate calculations.)

Brute Force Solution

Approach

The water and jug problem involves using two jugs of different sizes to measure out a specific amount of water. The brute force method explores all possible combinations of filling, emptying, and transferring water between the jugs. It continues until it either finds a solution or has exhausted every possibility.

Here's how the algorithm would work step-by-step:

Start with both jugs empty.
Try every possible action with each jug: fill it completely, empty it completely, or pour water from one jug into the other until either the receiving jug is full or the pouring jug is empty.
After each action, check if either jug contains the target amount of water. If so, we've found a solution.
Keep a record of every state (how much water is in each jug) we have already seen to avoid repeating combinations.
If we reach a state we've seen before, stop exploring that path and go back to try other possibilities.
Continue exploring all combinations of filling, emptying, and transferring until we find the target amount or we have explored all possible combinations without success.

Code Implementation

def can_measure_water_brute_force(jug_one_capacity, jug_two_capacity, target_capacity):
    visited_states = set()
    queue = [(0, 0)]

    while queue:
        current_jug_one, current_jug_two = queue.pop(0)

        if current_jug_one == target_capacity or current_jug_two == target_capacity or current_jug_one + current_jug_two == target_capacity:
            return True

        current_state = (current_jug_one, current_jug_two)
        if current_state in visited_states:
            continue

        visited_states.add(current_state)

        # Fill jug one
        queue.append((jug_one_capacity, current_jug_two))

        # Fill jug two
        queue.append((current_jug_one, jug_two_capacity))

        # Empty jug one
        queue.append((0, current_jug_two))

        # Empty jug two
        queue.append((current_jug_one, 0))

        # Pour jug one into jug two
        pour_amount = min(current_jug_one, jug_two_capacity - current_jug_two)
        queue.append((current_jug_one - pour_amount, current_jug_two + pour_amount))

        # Pour jug two into jug one
        pour_amount = min(current_jug_two, jug_one_capacity - current_jug_one)
        queue.append((current_jug_one + pour_amount, current_jug_two - pour_amount))

    return False

Big(O) Analysis

Time Complexity

O(m*n) – The brute force approach explores all possible states of the two jugs. The number of possible states is bounded by the product of the capacity of jug1 (m) and the capacity of jug2 (n), since each jug can have an amount of water from 0 to its full capacity. Each state might be visited once. Thus, the algorithm's time complexity is proportional to the number of possible states, making it O(m*n).

Space Complexity

O(jug1Capacity * jug2Capacity) – The algorithm maintains a record of every state visited (the amount of water in each jug) to avoid cycles. This record is stored to check previously visited states, representing all possible combinations of water levels in both jugs. The maximum number of states occurs when we have all possible combinations of water levels, ranging from 0 to jug1Capacity in the first jug and 0 to jug2Capacity in the second jug. Thus, we need to store up to jug1Capacity * jug2Capacity states, which dominates the space complexity.

Optimal Solution

Approach

The water and jug problem asks if you can measure a specific amount of water using only two jugs of different sizes. The trick is to realize that the problem can be solved using math focused on the greatest common divisor, avoiding exploring all possible filling and emptying combinations.

Here's how the algorithm would work step-by-step:

First, calculate the greatest common divisor (GCD) of the two jug sizes. Think of it as the largest volume that both jugs can measure evenly.
Then, check if the target volume you need to measure is a multiple of the GCD. If it's not, you can't measure it, no matter how you fill and empty the jugs.
If the target volume is a multiple of the GCD, then it is possible to measure the required water.

Code Implementation

def can_measure_water(jug1_capacity, jug2_capacity, target_capacity):
    def greatest_common_divisor(first_number, second_number):
        while second_number:
            first_number, second_number = second_number, first_number % second_number
        return first_number

    # If the target is larger than the sum, it is impossible.
    if target_capacity > jug1_capacity + jug2_capacity:
        return False

    # Calculate the GCD to determine measurable volumes.
    common_divisor = greatest_common_divisor(jug1_capacity, jug2_capacity)

    # Check if the target capacity is a multiple of the GCD.
    if target_capacity % common_divisor == 0:
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

O(log(min(jug1Capacity, jug2Capacity))) – The dominant operation in this solution is calculating the greatest common divisor (GCD) of the two jug capacities. The Euclidean algorithm, commonly used to find the GCD, has a time complexity of O(log(min(a, b))), where a and b are the two numbers. Since our inputs are jug1Capacity and jug2Capacity, the time complexity is O(log(min(jug1Capacity, jug2Capacity))). The other operations, such as checking if the target capacity is a multiple of the GCD, take constant time and do not affect the overall time complexity.

Space Complexity

O(1) – The provided solution calculates the greatest common divisor (GCD) of the two jug sizes and then checks if the target volume is a multiple of the GCD. The GCD calculation typically involves iterative steps, storing only a few variables to keep track of intermediate values. Since the space needed for these variables does not depend on the input jug sizes or the target volume, the auxiliary space used is constant, regardless of the input. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Jug1 capacity or Jug2 capacity is zero	If either jug capacity is zero, check if the target capacity is zero or equal to the non-zero capacity.
Target capacity is greater than the sum of Jug1 and Jug2 capacities	Return false immediately, as it's impossible to measure a capacity larger than the combined jug capacities.
Jug1 and Jug2 capacities are equal and the target is not a multiple of their capacity.	Return false since the target cannot be measured with the given jug sizes when they are equal and target isn't a multiple.
Jug1 and Jug2 capacities are relatively prime (GCD is 1) and the target is within the capacity limit.	Return true because any amount within the range can be measured.
Integer overflow during capacity calculations (sum of jugs or GCD calculations)	Use a wider integer type (e.g., long) or modular arithmetic to prevent overflow during calculations, or check before calculations whether an overflow can occur.
Target capacity is negative	Return false immediately, as negative capacities are not physically meaningful in this context.
Both jug capacities are zero, but the target capacity is not zero.	Return false, as it is impossible to measure any non-zero amount with zero capacity jugs.
The greatest common divisor (GCD) of Jug1 and Jug2 does not divide the target capacity.	Return false, as only multiples of the GCD can be measured; check 'targetCapacity % GCD(jug1Capacity, jug2Capacity) == 0'.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Are the jug capacities (jug1Capacity and jug2Capacity) and the target capacity (targetCapacity) guaranteed to be non-negative integers?
If the targetCapacity is greater than the sum of jug1Capacity and jug2Capacity, should I return false? Or is there some other expected behavior?
If the targetCapacity is 0, should I return true if either jug1Capacity or jug2Capacity is non-zero, or should both be zero?
Can jug1Capacity or jug2Capacity be zero? If so, how should I handle the case where both are zero and the targetCapacity is non-zero?
Is there a practical upper bound on the jug capacities? (This might influence the choice of algorithm to avoid potential integer overflow issues in intermediate calculations.)

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with both jugs empty.
Try every possible action with each jug: fill it completely, empty it completely, or pour water from one jug into the other until either the receiving jug is full or the pouring jug is empty.
After each action, check if either jug contains the target amount of water. If so, we've found a solution.
Keep a record of every state (how much water is in each jug) we have already seen to avoid repeating combinations.
If we reach a state we've seen before, stop exploring that path and go back to try other possibilities.
Continue exploring all combinations of filling, emptying, and transferring until we find the target amount or we have explored all possible combinations without success.

Code Implementation

def can_measure_water_brute_force(jug_one_capacity, jug_two_capacity, target_capacity):
    visited_states = set()
    queue = [(0, 0)]

    while queue:
        current_jug_one, current_jug_two = queue.pop(0)

        if current_jug_one == target_capacity or current_jug_two == target_capacity or current_jug_one + current_jug_two == target_capacity:
            return True

        current_state = (current_jug_one, current_jug_two)
        if current_state in visited_states:
            continue

        visited_states.add(current_state)

        # Fill jug one
        queue.append((jug_one_capacity, current_jug_two))

        # Fill jug two
        queue.append((current_jug_one, jug_two_capacity))

        # Empty jug one
        queue.append((0, current_jug_two))

        # Empty jug two
        queue.append((current_jug_one, 0))

        # Pour jug one into jug two
        pour_amount = min(current_jug_one, jug_two_capacity - current_jug_two)
        queue.append((current_jug_one - pour_amount, current_jug_two + pour_amount))

        # Pour jug two into jug one
        pour_amount = min(current_jug_two, jug_one_capacity - current_jug_one)
        queue.append((current_jug_one + pour_amount, current_jug_two - pour_amount))

    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, calculate the greatest common divisor (GCD) of the two jug sizes. Think of it as the largest volume that both jugs can measure evenly.
Then, check if the target volume you need to measure is a multiple of the GCD. If it's not, you can't measure it, no matter how you fill and empty the jugs.
If the target volume is a multiple of the GCD, then it is possible to measure the required water.

Code Implementation

def can_measure_water(jug1_capacity, jug2_capacity, target_capacity):
    def greatest_common_divisor(first_number, second_number):
        while second_number:
            first_number, second_number = second_number, first_number % second_number
        return first_number

    # If the target is larger than the sum, it is impossible.
    if target_capacity > jug1_capacity + jug2_capacity:
        return False

    # Calculate the GCD to determine measurable volumes.
    common_divisor = greatest_common_divisor(jug1_capacity, jug2_capacity)

    # Check if the target capacity is a multiple of the GCD.
    if target_capacity % common_divisor == 0:
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Jug1 capacity or Jug2 capacity is zero	If either jug capacity is zero, check if the target capacity is zero or equal to the non-zero capacity.
Target capacity is greater than the sum of Jug1 and Jug2 capacities	Return false immediately, as it's impossible to measure a capacity larger than the combined jug capacities.
Jug1 and Jug2 capacities are equal and the target is not a multiple of their capacity.	Return false since the target cannot be measured with the given jug sizes when they are equal and target isn't a multiple.
Jug1 and Jug2 capacities are relatively prime (GCD is 1) and the target is within the capacity limit.	Return true because any amount within the range can be measured.
Integer overflow during capacity calculations (sum of jugs or GCD calculations)	Use a wider integer type (e.g., long) or modular arithmetic to prevent overflow during calculations, or check before calculations whether an overflow can occur.
Target capacity is negative	Return false immediately, as negative capacities are not physically meaningful in this context.
Both jug capacities are zero, but the target capacity is not zero.	Return false, as it is impossible to measure any non-zero amount with zero capacity jugs.
The greatest common divisor (GCD) of Jug1 and Jug2 does not divide the target capacity.	Return false, as only multiples of the GCD can be measured; check 'targetCapacity % GCD(jug1Capacity, jug2Capacity) == 0'.