Jobs

Interviews

Discussions

Toss Strange Coins

Medium

Twitch

0 views

Topics:

ArraysDynamic Programming

You have n coins. Each coin has a probability of being heads. Each coin is biased towards heads such that when tossed the probability of getting heads is prob[i].

Return the probability that the number of heads is exactly target if you toss every coin one time.

Example 1:

Input: prob = [0.4], target = 1
Output: 0.40000

Example 2:

Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0
Output: 0.03125

Constraints:

1 <= prob.length <= 1000
0 <= prob[i] <= 1
0 <= target <= prob.length
Answers will be accepted as correct if they are within 10^-5 of the correct answer.

Toss Strange Coins

Medium

Twitch

0 views

Topics:

ArraysDynamic Programming

You have n coins. Each coin has a probability of being heads. Each coin is biased towards heads such that when tossed the probability of getting heads is prob[i].

Return the probability that the number of heads is exactly target if you toss every coin one time.

Example 1:

Input: prob = [0.4], target = 1
Output: 0.40000

Example 2:

Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0
Output: 0.03125

Constraints:

1 <= prob.length <= 1000
0 <= prob[i] <= 1
0 <= target <= prob.length
Answers will be accepted as correct if they are within 10^-5 of the correct answer.

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:

What are the constraints on the length of the `probs` array and the value of `target`? Could either be zero?
Can the probabilities in the `probs` array be outside the range of [0, 1]? If so, how should I handle probabilities that are negative or greater than 1?
If `target` is greater than the number of coins (length of `probs`), what should I return? Should I return 0, or is an exception expected?
Is the input array `probs` guaranteed to be valid (e.g., not null or malformed)?
Are we looking for an exact float comparison for the probability, or is a certain tolerance acceptable? If a tolerance is expected, what is an acceptable epsilon value for floating-point comparisons?

Brute Force Solution

Approach

The brute force approach to this coin problem is like trying every single combination of coin flips to see which one gets us the right number of heads. We essentially simulate all possible sequences of flips and count the successful outcomes. This means we'll explore every branch of possibility.

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

Consider all possible sequences of coin flips. Each coin has a chance of landing heads or tails.
For each sequence, determine if it results in the desired number of heads.
If a sequence has the desired number of heads, count it as a success.
After checking all possible sequences, determine the total number of successful sequences.
Calculate the probability by dividing the number of successful sequences by the total number of sequences we tested.

Code Implementation

def toss_strange_coins_brute_force(probabilities, target_heads):
    number_of_coins = len(probabilities)
    total_sequences = 2 ** number_of_coins
    successful_sequences = 0

    for i in range(total_sequences):
        heads_count = 0
        
        # Iterate through the coins, determining heads or tails based on the binary representation of i
        for coin_index in range(number_of_coins):
            if (i >> coin_index) & 1:

                # If the bit is set, consider it heads and add the probability.
                heads_count += 1

        #Check if current sequence results in desired heads.
        if heads_count == target_heads:
            successful_sequences += 1

    # Calculate the probability of achieving the target number of heads
    probability = successful_sequences / total_sequences
    return probability

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach involves considering all possible sequences of coin flips for n coins. Each coin flip has two possibilities (heads or tails). Therefore, the total number of possible sequences is 2 * 2 * ... * 2 (n times), which equals 2^n. For each of these 2^n sequences, we determine if it results in the desired number of heads, requiring O(n) work, but this is dominated by the 2^n sequences. Consequently, the overall time complexity is O(2^n).

Space Complexity

O(1) – The brute force approach described explores all possible sequences of coin flips without explicitly storing each sequence. It counts successful outcomes and calculates probability but doesn't require auxiliary data structures that scale with the input size, N (number of coins). Therefore, the space used is constant, mainly for storing a few counters and temporary variables. This means the space complexity is O(1) as it does not depend on N.

Optimal Solution

Approach

This problem is about figuring out the chance of getting exactly a certain number of heads when you flip some coins, but these coins aren't fair. We'll use a technique that builds up the answer piece by piece, looking at one coin at a time and storing the probabilities as we go.

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

Imagine you have no coins. The chance of getting zero heads is 100%, because you didn't flip anything.
Now, consider the first coin. There are two possibilities: either you get heads, or you get tails. The chance of each is given to you.
Next, consider the second coin. Now for each possibility you figured out before, we need to see what happens if we flip this new coin. If we had zero heads before, and this coin lands heads, we now have one head. If it lands tails, we still have zero heads. Do the probability calculation for each outcome.
Keep going for each coin: each time you add a coin, you double the number of possibilities to consider, because the new coin can land either heads or tails. The probabilities of each outcome must be updated accordingly.
After considering all coins, we will know the probabilities of getting 0 heads, 1 head, 2 heads, and so on, up to the total number of coins we had.
Finally, look up the probability of getting exactly the number of heads you wanted (the target) which will be one of the probabilities you just calculated.

Code Implementation

def toss_strange_coins(probabilities, target_heads):
    number_of_coins = len(probabilities)
    # Initialize the DP table; dp[i][j] = probability of j heads with first i coins
    dp_table = [[0.0] * (number_of_coins + 1) for _ in range(number_of_coins + 1)]
    dp_table[0][0] = 1.0

    for i in range(1, number_of_coins + 1):
        # The probability of the current coin landing heads.
        head_probability = probabilities[i - 1]
        # The probability of the current coin landing tails.
        tail_probability = 1.0 - head_probability

        for j in range(i + 1):
            # If we get tails, the number of heads doesn't change
            dp_table[i][j] = dp_table[i - 1][j] * tail_probability

            # If we get heads, the number of heads increases by one
            if j > 0:
                dp_table[i][j] += dp_table[i - 1][j - 1] * head_probability

    # The result is the probability of getting 'target_heads' after tossing all coins.
    return dp_table[number_of_coins][target_heads]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n*target) – The algorithm iterates through each of the n coins. For each coin, it updates probabilities for 0 to target heads. This update involves calculations that depend on the previous probabilities. Therefore, for each of the n coins, we perform target operations to compute the new probabilities. The total number of operations approximates n * target, thus giving us a time complexity of O(n*target).

Space Complexity

O(N) – The algorithm uses a dynamic programming approach to store probabilities for each coin considered. It maintains a table (implicitly) to store the probabilities of obtaining 0 to i heads after considering the first i coins. This table requires space proportional to the number of coins (N) because it needs to store probabilities for 0 heads, 1 head, 2 heads,... up to N heads. Thus, the auxiliary space used is proportional to N. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
probs is null or empty	Return 1.0 if target is 0, otherwise return 0.0 as no heads can be achieved with no coins.
target is negative or greater than the number of coins	Return 0.0 as it's impossible to have a negative number of heads or more heads than coins.
probs contains probabilities outside the range [0, 1]	Filter out probabilities that are not within [0, 1] or clamp them to the interval.
probs contains extreme probabilities (very close to 0 or 1)	The DP approach should handle this gracefully, but consider potential floating-point precision issues; use double for calculations.
target is 0 (we want no heads)	Multiply all (1 - prob) values together to get the probability of all tails.
target is equal to the number of coins (we want all heads)	Multiply all prob values together to get the probability of all heads.
Large input size for probs (affects time and space complexity)	Dynamic programming approach should scale reasonably well, but memoization is crucial to avoid redundant calculations and optimize time complexity.
Floating-point precision errors can accumulate with large n	Be aware of the potential for errors and consider using a higher precision data type if necessary or techniques to minimize error propagation.

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:

What are the constraints on the length of the `probs` array and the value of `target`? Could either be zero?
Can the probabilities in the `probs` array be outside the range of [0, 1]? If so, how should I handle probabilities that are negative or greater than 1?
If `target` is greater than the number of coins (length of `probs`), what should I return? Should I return 0, or is an exception expected?
Is the input array `probs` guaranteed to be valid (e.g., not null or malformed)?
Are we looking for an exact float comparison for the probability, or is a certain tolerance acceptable? If a tolerance is expected, what is an acceptable epsilon value for floating-point comparisons?

Brute Force Solution

Approach

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

Consider all possible sequences of coin flips. Each coin has a chance of landing heads or tails.
For each sequence, determine if it results in the desired number of heads.
If a sequence has the desired number of heads, count it as a success.
After checking all possible sequences, determine the total number of successful sequences.
Calculate the probability by dividing the number of successful sequences by the total number of sequences we tested.

Code Implementation

def toss_strange_coins_brute_force(probabilities, target_heads):
    number_of_coins = len(probabilities)
    total_sequences = 2 ** number_of_coins
    successful_sequences = 0

    for i in range(total_sequences):
        heads_count = 0
        
        # Iterate through the coins, determining heads or tails based on the binary representation of i
        for coin_index in range(number_of_coins):
            if (i >> coin_index) & 1:

                # If the bit is set, consider it heads and add the probability.
                heads_count += 1

        #Check if current sequence results in desired heads.
        if heads_count == target_heads:
            successful_sequences += 1

    # Calculate the probability of achieving the target number of heads
    probability = successful_sequences / total_sequences
    return probability

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine you have no coins. The chance of getting zero heads is 100%, because you didn't flip anything.
Now, consider the first coin. There are two possibilities: either you get heads, or you get tails. The chance of each is given to you.
Next, consider the second coin. Now for each possibility you figured out before, we need to see what happens if we flip this new coin. If we had zero heads before, and this coin lands heads, we now have one head. If it lands tails, we still have zero heads. Do the probability calculation for each outcome.
Keep going for each coin: each time you add a coin, you double the number of possibilities to consider, because the new coin can land either heads or tails. The probabilities of each outcome must be updated accordingly.
After considering all coins, we will know the probabilities of getting 0 heads, 1 head, 2 heads, and so on, up to the total number of coins we had.
Finally, look up the probability of getting exactly the number of heads you wanted (the target) which will be one of the probabilities you just calculated.

Code Implementation

def toss_strange_coins(probabilities, target_heads):
    number_of_coins = len(probabilities)
    # Initialize the DP table; dp[i][j] = probability of j heads with first i coins
    dp_table = [[0.0] * (number_of_coins + 1) for _ in range(number_of_coins + 1)]
    dp_table[0][0] = 1.0

    for i in range(1, number_of_coins + 1):
        # The probability of the current coin landing heads.
        head_probability = probabilities[i - 1]
        # The probability of the current coin landing tails.
        tail_probability = 1.0 - head_probability

        for j in range(i + 1):
            # If we get tails, the number of heads doesn't change
            dp_table[i][j] = dp_table[i - 1][j] * tail_probability

            # If we get heads, the number of heads increases by one
            if j > 0:
                dp_table[i][j] += dp_table[i - 1][j - 1] * head_probability

    # The result is the probability of getting 'target_heads' after tossing all coins.
    return dp_table[number_of_coins][target_heads]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
probs is null or empty	Return 1.0 if target is 0, otherwise return 0.0 as no heads can be achieved with no coins.
target is negative or greater than the number of coins	Return 0.0 as it's impossible to have a negative number of heads or more heads than coins.
probs contains probabilities outside the range [0, 1]	Filter out probabilities that are not within [0, 1] or clamp them to the interval.
probs contains extreme probabilities (very close to 0 or 1)	The DP approach should handle this gracefully, but consider potential floating-point precision issues; use double for calculations.
target is 0 (we want no heads)	Multiply all (1 - prob) values together to get the probability of all tails.
target is equal to the number of coins (we want all heads)	Multiply all prob values together to get the probability of all heads.
Large input size for probs (affects time and space complexity)	Dynamic programming approach should scale reasonably well, but memoization is crucial to avoid redundant calculations and optimize time complexity.
Floating-point precision errors can accumulate with large n	Be aware of the potential for errors and consider using a higher precision data type if necessary or techniques to minimize error propagation.