Cracking The Coding Interview Together – Problem 6.2: Basketball

As software engineers, we are constantly bombarded with the illusion that "more is better." More servers, more retries, more redundancy, more data. We instinctively believe that adding a safety net always improves our chances of success. But as senior engineers, we must look past our intuition and let rigorous analysis guide our architectural decisions.

Today, we are diving into Problem 6.2: Basketball from Cracking the Coding Interview. On the surface, it looks like a simple high school probability puzzle about shooting hoops. But beneath this playful exterior lies a fundamental truth about system reliability, quorum consensus, and retry policies in distributed systems. By the end of this post, we will not only solve the mathematical puzzle together, but we will also build a production-ready simulation engine and explore how this exact math dictates whether your microservices survive a network partition or collapse under a retry storm. Let's get started.

Problem Statement

The problem is defined as follows:

You have a basketball hoop and someone says that you can play one of two games:

• Game 1: You get one shot to make the hoop.
• Game 2: You get three shots and you have to make at least two of them.

If p is the probability of making a particular shot, for which values of p should you pick one game or the other?

Our operational goals are to mathematically derive the threshold for p, build a simulation tool to verify our mathematical model, and translate these findings into concrete system design patterns.

Analyze the Problem Together

Let's break down the mechanics of both games. We want to find the probability of winning each game as a function of p, where 0 <= p <= 1.

For Game 1, the probability of winning is straightforward:

P(Game 1) = p

For Game 2, we win if we make at least two out of three shots. This means we win if we make exactly 2 shots OR exactly 3 shots. Because each shot is an independent event, we can model this using binomial probability.

Let's list the winning scenarios for Game 2:

• Making exactly 3 shots: The probability is p * p * p = p^3.
• Making exactly 2 shots: There are three ways this can happen (Make-Make-Miss, Make-Miss-Make, Miss-Make-Make). The probability for each sequence is p^2 * (1 - p). Since there are 3 such sequences, the total probability is 3 * p^2 * (1 - p).

Adding these together gives us the total probability of winning Game 2:

P(Game 2) = p^3 + 3 * p^2 * (1 - p)
P(Game 2) = p^3 + 3p^2 - 3p^3
P(Game 2) = 3p^2 - 2p^3

Now, we need to compare P(Game 1) and P(Game 2) to determine when we should choose one over the other. We want to find when Game 1 is better than Game 2:

P(Game 1) > P(Game 2)
p > 3p^2 - 2p^3

Let's solve this inequality together:

2p^3 - 3p^2 + p > 0
p(2p^2 - 3p + 1) > 0
p(2p - 1)(p - 1) > 0

This polynomial has roots at p = 0, p = 0.5, and p = 1. Since p is a probability, its domain is strictly bounded by [0, 1]. Let's analyze the intervals:

• If 0 < p < 0.5: The term p is positive, (2p - 1) is negative, and (p - 1) is negative. The product of (positive) * (negative) * (negative) is positive. Thus, P(Game 1) > P(Game 2).
• If 0.5 < p < 1: The term p is positive, (2p - 1) is positive, and (p - 1) is negative. The product of (positive) * (positive) * (negative) is negative. Thus, P(Game 1) < P(Game 2).
• If p = 0, p = 0.5, or p = 1: The probabilities are equal (P(Game 1) == P(Game 2)).

Here is a quick comparative summary of our options:

Questions for the Interviewer

In an actual interview, a senior engineer doesn't just jump into writing equations. They clarify the boundaries of the problem. Here are the questions we should ask:

• Are the shots truly independent? In real life, physical fatigue or psychological pressure (the "hot hand" fallacy or choking under pressure) can affect subsequent shots. We will assume strict independence for this mathematical model.
• Is the probability p constant across all shots? We assume p does not change between shot 1, 2, and 3.
• Are there any resource or latency costs associated with taking more shots? In a pure math puzzle, shots are free. In a distributed system, extra network calls cost time, bandwidth, and compute. We should keep this distinction in mind for our architectural discussion.

Think About the Solution

To prove our mathematical derivation, we will build a clean, production-ready Java application. Our solution will feature:

1. An Analytical Solver: A method that uses our derived formula to instantly recommend the best strategy.
2. A Monte Carlo Simulator: A simulation engine that runs thousands of simulated games to empirically verify our mathematical proofs. This is a highly valued skill in engineering, as real-world systems are often too complex for closed-form equations, making simulation our primary tool for validation.

Let's design our classes with clean separation of concerns, proper encapsulation, and clear documentation.

Write Code and Explain

Here is our complete, production-grade Java implementation:

package com.thedevlearnings.basketball;

import java.util.Random;

/**
 * StrategyEvaluator determines the optimal game strategy based on shot success probability.
 * It provides both analytical solutions and empirical Monte Carlo simulations.
 */
public class StrategyEvaluator {

    private static final Random RANDOM = new Random();

    public enum GameChoice {
        GAME_1, // 1 shot, need 1 make
        GAME_2, // 3 shots, need at least 2 makes
        ANY     // Both games yield identical odds
    }

    /**
     * Analytically determines the best game to play based on mathematical derivation.
     * 
     * @param p The probability of making a single shot (0.0 <= p <= 1.0)
     * @return The optimal GameChoice
     */
    public static GameChoice getOptimalStrategy(double p) {
        if (p < 0.0 || p > 1.0) {
            throw new IllegalArgumentException("Probability must be between 0.0 and 1.0 inclusive.");
        }
        
        if (p == 0.0 || p == 0.5 || p == 1.0) {
            return GameChoice.ANY;
        }
        
        return (p > 0.5) ? GameChoice.GAME_2 : GameChoice.GAME_1;
    }

    /**
     * Simulates Game 1 (1 shot) for a given number of trials.
     */
    public static double simulateGame1(double p, int trials) {
        int wins = 0;
        for (int i = 0; i < trials; i++) {
            if (simulateShot(p)) {
                wins++;
            }
        }
        return (double) wins / trials;
    }

    /**
     * Simulates Game 2 (3 shots, need at least 2 makes) for a given number of trials.
     */
    public static double simulateGame2(double p, int trials) {
        int wins = 0;
        for (int i = 0; i < trials; i++) {
            int makes = 0;
            for (int shot = 0; shot < 3; shot++) {
                if (simulateShot(p)) {
                    makes++;
                }
            }
            if (makes >= 2) {
                wins++;
            }
        }
        return (double) wins / trials;
    }

    private static boolean simulateShot(double p) {
        return RANDOM.nextDouble() < p;
    }

    public static void main(String[] args) {
        double[] testProbabilities = {0.15, 0.50, 0.85};
        int trials = 1_000_000;

        System.out.println("=== BASKETBALL STRATEGY SIMULATION ===\n");
        for (double p : testProbabilities) {
            System.out.printf("Testing p = %.2f%n", p);
            System.out.println("------------------------------------");
            
            GameChoice recommended = getOptimalStrategy(p);
            System.out.println("Analytical Recommendation: " + recommended);

            double empiricalG1 = simulateGame1(p, trials);
            double empiricalG2 = simulateGame2(p, trials);

            System.out.printf("Empirical Win Rate Game 1: %.5f%n", empiricalG1);
            System.out.printf("Empirical Win Rate Game 2: %.5f%n", empiricalG2);
            
            String actualBest = (Math.abs(empiricalG1 - empiricalG2) < 0.001) ? "ANY" 
                               : (empiricalG1 > empiricalG2) ? "GAME_1" : "GAME_2";
            System.out.println("Empirical Best Choice:    " + actualBest);
            System.out.println();
        }
    }
}

Code Walkthrough

• getOptimalStrategy(double p): This is our analytical engine. It runs in O(1) time and uses our derived threshold of 0.5 to instantly return the mathematically optimal strategy.
• simulateShot(double p): Generates a pseudo-random double between 0.0 and 1.0. If it falls below p, the shot is successful. This is a standard way to model Bernoulli trials.
• simulateGame1 and simulateGame2: These methods run Monte Carlo simulations. By executing 1,000,000 trials, we leverage the Law of Large Numbers to ensure our empirical results converge closely to our theoretical probabilities.

Time & Space Complexity

Let's analyze the performance characteristics of our solution:

• Analytical Solver (getOptimalStrategy):
  • Time Complexity: O(1). It performs a constant number of basic comparisons.
  • Space Complexity: O(1). No extra memory is allocated.
• Simulation Engine (simulateGame1 / simulateGame2):
  • Time Complexity: O(T), where T is the number of trials. For Game 2, we perform up to 3 * T random number generations, which remains strictly linear.
  • Space Complexity: O(1). We only maintain a few primitive counters in memory, regardless of the number of trials.

Why This Problem Matters (The Senior Perspective)

Now, let's step back and look at this problem through the lens of a Senior Systems Architect. Why does a software engineering interviewer care about basketball shots?

Because this problem is a perfect mathematical model for Distributed Consensus and Retry Policies.

The Retry Storm and Downstream Failures

Imagine you have a microservice that calls a downstream database. The database is struggling under heavy load, and its success rate (our p) drops to 30% (0.30).

A junior engineer might say: "Let's implement a retry policy! If we try 3 times and need at least 2 successful writes to achieve quorum consensus, we will make our system more robust!"

Let's look at the math we just proved. If p = 0.30:

• Game 1 (No Retries / Single Attempt): Success rate is 30%.
• Game 2 (3 Attempts, Quorum of 2 needed): Success rate is 3 * (0.3)^2 - 2 * (0.3)^3 = 0.27 - 0.054 = 21.6%.

By adding retries and requiring a quorum of 2, you have actually reduced your system's overall success rate from 30% to 21.6%! Even worse, you have tripled the traffic hitting your already struggling database, likely triggering a cascading failure (a retry storm).

Quorum in Distributed Databases (Cassandra, DynamoDB)

In distributed databases, we write to multiple replica nodes. If we write to 3 nodes and require a quorum of 2 successful writes to acknowledge success to the client, we are playing Game 2.

If our network reliability or node health p drops below 0.5, our write success rate drops off a cliff compared to a single-node write (Game 1). This is why distributed systems use circuit breakers to stop traffic entirely when p drops below a critical threshold, rather than blindly retrying and exacerbating the failure.

Final Thoughts

What looked like a simple basketball puzzle is actually a profound lesson in system design. Redundancy and retries are powerful tools, but they are only effective when your baseline reliability p is above 0.5. When your system is severely degraded, adding more attempts without fixing the underlying bottleneck only accelerates your failure.

Next time you design a retry mechanism or configure a database quorum, remember the basketball problem. Run the math, check your baseline success rate, and design your systems to fail gracefully rather than thrashing.

Have you ever encountered a real-world retry storm where adding retries made things worse? Let's discuss in the comments below!

Until next time, keep building, keep learning, and keep cracking those systems!