Cracking The Coding Interview Together – Problem 6.7: The Apocalypse

Imagine you are the chief systems architect for a newly formed global government. The World Queen summons you to her chamber. She is deeply concerned about the post-apocalyptic birth rate and demographic balance. To address this, she has decreed a strict, highly unusual policy: every family must continue to have children until they have exactly one girl, at which point they must immediately stop.

The Queen’s advisors are split. Some claim this policy will flood the kingdom with girls, creating an extreme gender imbalance. Others argue that because some families will have long runs of boys before finally having a girl, the population will skew heavily male. Both sides sound highly convincing. They are relying on raw human intuition—and in complex systems, human intuition is a notoriously poor guide.

As a senior engineer, you don't guess. You model, you calculate, and you simulate. Today, we are going to tackle this classic problem together. We will demystify the mathematics behind this apparent paradox, write a production-grade simulation in Java to prove our findings, and discuss why this style of thinking is vital for real-world system architecture.

Problem Statement

Let's formalize the problem as presented in Cracking the Coding Interview (Problem 6.7):

In the new post-apocalyptic world, the world queen is desperately concerned about the birth rate. Therefore, she decrees that all families should ensure that they have one girl or else they face massive fines. If all families abide by this policy—that is, they continue to have children until they have one girl, at which point they immediately stop—what will the gender ratio of the new generation be? (Assume that the odds of someone having a boy or a girl on any given pregnancy is equal.)

Our operational goals are:

• Formulate a rigorous mathematical proof to determine the expected gender ratio.
• Design and implement a highly optimized, thread-safe simulation to empirically validate our mathematical model.
• Analyze the time and space complexity of our simulation.
• Translate these mathematical concepts into real-world software engineering design patterns.

Analyze the Problem Together

Let's start by breaking down the core conflict. Why is this problem so counter-intuitive?

The "Aha!" moment comes when we realize that every single birth is an independent event. The probability of having a boy or a girl on any given pregnancy is exactly 0.5, completely independent of the family's previous children. The Queen's decree dictates when a family stops having children, but it cannot alter the laws of biology and probability for any individual birth.

Let's look at the possible family structures and their associated probabilities:

Notice a critical pattern here: Every single family has exactly one girl. No more, no less. If we simulate N families, we are guaranteed to have exactly N girls in the next generation.

Now, let's calculate the expected number of boys. The expected value of a random variable is the sum of each possible value multiplied by its probability. Let B be the number of boys in a family:

E[B] = 0 * (1/2) + 1 * (1/4) + 2 * (1/8) + 3 * (1/16) + ... + k * (1/2)^k+1

This is an arithmetico-geometric series. Let's solve it step-by-step. Let the sum be S:

S = Sum_{k=0 to infinity} k * (1/2)^k+1 = (1/2) * Sum_{k=0 to infinity} k * (1/2)^k

Let's evaluate the inner sum X = Sum_{k=0 to infinity} k * (1/2)^k:

X = 0 + 1*(1/2) + 2*(1/4) + 3*(1/8) + 4*(1/16) + ...

Multiply both sides by 1/2:

(1/2)X = 0 + 1*(1/4) + 2*(1/8) + 3*(1/16) + ...

Subtract the second equation from the first:

X - (1/2)X = 1/2 + (2-1)*(1/4) + (3-2)*(1/8) + (4-3)*(1/16) + ...
(1/2)X = 1/2 + 1/4 + 1/8 + 1/16 + ...

The right side is a standard geometric series starting at 1/2 with a common ratio of 1/2. The sum of this infinite geometric series is:

Sum = (1/2) / (1 - 1/2) = 1

Therefore:

(1/2)X = 1 => X = 2

Now substitute X back into our original equation for E[B]:

E[B] = (1/2) * X = (1/2) * 2 = 1

The expected number of boys per family is exactly 1.

Since the expected number of girls per family is also exactly 1, the expected gender ratio is 1:1 (or 50% boys and 50% girls). The Queen's decree has absolutely no effect on the overall gender ratio of the population!

Questions for the Interviewer

In an interview setting, jumping straight into the math can make you look like a calculator rather than an engineer. A senior engineer clarifies constraints and edge cases first. Here are the questions you should ask:

• "Are we assuming biological constraints on family size?" (e.g., is there a maximum number of children a family can physically have? If a family is biologically capped at, say, 10 children, the ratio will slightly skew male or female depending on the cap. We will assume infinite fertility for the base mathematical model, but we should parameterize this in our code.)
• "Is the probability of having a boy or a girl exactly 50/50?" (In the real world, the natural birth ratio is roughly 105 boys to 100 girls. We will assume exactly 0.5 for this problem, but our code should support a configurable probability parameter.)
• "Are we modeling a finite population?" (With a small population, variance can lead to temporary imbalances. We should design our simulation to run over large sample sizes to demonstrate convergence.)

Think About the Solution

To prove this to the Queen (and our interviewer), we will build an empirical simulation engine. Let's design it with clean, production-grade principles:

• Modularity: We will separate the simulation logic from the execution runner.
• Performance: Generating millions of random numbers can be computationally expensive. We will use Java's ThreadLocalRandom to ensure high performance and avoid thread contention if we decide to parallelize.
• Memory Efficiency: Instead of instantiating millions of Family objects in memory (which would thrash the Garbage Collector), we will stream the simulation and maintain running counters. This keeps our space complexity at O(1).

Write Code and Explain

Let's implement a clean, highly configurable simulation in Java.

package com.thedevlearnings.apocalypse;

import java.util.concurrent.ThreadLocalRandom;

/**
 * Simulation engine to verify the gender ratio under the Queen's decree.
 * Designed with performance, memory efficiency, and clean code principles in mind.
 */
public class ApocalypseSimulator {

    private final double girlProbability;
    private final int maxFamilySize;

    /**
     * Constructor to initialize simulation parameters.
     * 
     * @param girlProbability Probability of having a girl (0.0 to 1.0)
     * @param maxFamilySize   Maximum children a family can have due to biological limits (use Integer.MAX_VALUE for unlimited)
     */
    public ApocalypseSimulator(double girlProbability, int maxFamilySize) {
        if (girlProbability <= 0.0 || girlProbability >= 1.0) {
            throw new IllegalArgumentException("Probability must be strictly between 0 and 1");
        }
        if (maxFamilySize <= 0) {
            throw new IllegalArgumentException("Max family size must be greater than 0");
        }
        this.girlProbability = girlProbability;
        this.maxFamilySize = maxFamilySize;
    }

    /**
     * Runs the simulation for a given number of families.
     * 
     * @param totalFamilies Number of families to simulate
     * @return A SimulationResult containing the aggregated metrics
     */
    public SimulationResult runSimulation(int totalFamilies) {
        long totalBoys = 0;
        long totalGirls = 0;
        ThreadLocalRandom random = ThreadLocalRandom.current();

        for (int i = 0; i < totalFamilies; i++) {
            int familyBoys = 0;
            int familyGirls = 0;
            int childrenCount = 0;

            while (familyGirls == 0 && childrenCount < maxFamilySize) {
                childrenCount++;
                if (random.nextDouble() < girlProbability) {
                    familyGirls++;
                } else {
                    familyBoys++;
                }
            }
            totalBoys += familyBoys;
            totalGirls += familyGirls;
        }

        return new SimulationResult(totalFamilies, totalBoys, totalGirls);
    }

    /**
     * Immutable record to hold simulation results.
     */
    public static class SimulationResult {
        private final int totalFamilies;
        private final long totalBoys;
        private final long totalGirls;

        public SimulationResult(int totalFamilies, long totalBoys, long totalGirls) {
            this.totalFamilies = totalFamilies;
            this.totalBoys = totalBoys;
            this.totalGirls = totalGirls;
        }

        public double getGirlRatio() {
            long totalChildren = totalBoys + totalGirls;
            if (totalChildren == 0) return 0.0;
            return (double) totalGirls / totalChildren;
        }

        public double getAverageChildrenPerFamily() {
            return (double) (totalBoys + totalGirls) / totalFamilies;
        }

        @Override
        public String toString() {
            return String.format(
                "Simulation Results for %d families:\n" +
                "- Total Boys: %d\n" +
                "- Total Girls: %d\n" +
                "- Gender Ratio (Girls/Total): %.6f (Expected: %.6f)\n" +
                "- Avg Children per Family: %.4f",
                totalFamilies, totalBoys, totalGirls, getGirlRatio(), 0.5, getAverageChildrenPerFamily()
            );
        }
    }

    public static void main(String[] args) {
        // Run simulation with 10,000,000 families, 50/50 probability, and no biological limit
        ApocalypseSimulator simulator = new ApocalypseSimulator(0.5, Integer.MAX_VALUE);
        
        System.out.println("Starting simulation...");
        long startTime = System.currentTimeMillis();
        
        SimulationResult result = simulator.runSimulation(10_000_000);
        
        long endTime = System.currentTimeMillis();
        
        System.out.println(result);
        System.out.printf("Simulation completed in %d ms\n", (endTime - startTime));
    }
}

Code Walkthrough

Let's look at the key architectural decisions in this code:

1. ThreadLocalRandom: Instead of using java.util.Random, we use ThreadLocalRandom.current(). This is a best practice in modern Java. It avoids internal synchronization overhead and is significantly faster in high-throughput loops.
2. Memory Footprint: Notice that we do not instantiate a Family object inside the loop. Creating 10 million objects would trigger frequent Garbage Collection pauses. Instead, we maintain primitive counters (totalBoys, totalGirls) and accumulate them. This is an O(1) space complexity approach.
3. Defensive Programming: The constructor validates input parameters, ensuring that we don't allow invalid probabilities or negative family sizes.

Time & Space Complexity

Let's analyze the efficiency of our simulation engine:

• Time Complexity: O(N), where N is the number of families. For each family, the expected number of iterations of the inner loop is 2 (since the expected family size is 2 children). Thus, the total number of random number generations is 2N on average, which scales linearly.
• Space Complexity: O(1) auxiliary space. We only store a few primitive variables to track the running totals, making this extremely memory efficient and friendly to the CPU cache.

Why This Problem Matters (The Senior Perspective)

Why do tech companies ask this question? It's not just a brain teaser; it tests your ability to think about system dynamics and emergent behavior.

In software engineering, we often design systems where individual components follow simple rules, but the aggregate system behaves in unexpected ways. For example:

• Microservices and Retry Storms: If every microservice retries a failed request up to 3 times, it seems like a safe local policy. However, at scale, this simple rule can trigger a catastrophic "retry storm" that completely takes down your database.
• Load Balancing: Choosing the "least loaded" server can cause all clients to simultaneously herd to the same server, creating a cyclic bottleneck.

This problem teaches us to separate local stopping conditions (when a family stops having children) from global probability distributions (the independent 50/50 chance of each birth). As a senior engineer, you must always look past local rules to understand the global invariants of your system.

Final Thoughts

We have successfully proven—both mathematically and empirically—that the Queen's decree will result in a perfect 1:1 gender ratio. The laws of probability remain undefeated.

If you want to take this a step further, try modifying the simulation code to introduce a biological limit (e.g., maxFamilySize = 4). How does limiting family size affect the ratio? (Hint: It will skew the ratio slightly, but which way? Run the code and find out!)

Thanks for reading, and happy coding! Let us know your thoughts in the comments below.