Cracking The Coding Interview Together – Problem 8.14: Boolean Evaluation

Have you ever stared at a complex conditional statement in a legacy codebase and wondered how many different evaluation paths actually exist? Today, we are tackling a classic combinatorial puzzle that bridges the gap between discrete mathematics and high-performance system design. We will look at Problem 8.14: Boolean Evaluation from Cracking the Coding Interview. By the end of this post, you will understand how to break down recursive subproblems, spot overlapping states, and apply dynamic programming with memoization to solve a combinatorial explosion.

Problem Statement

Given a boolean expression consisting of the symbols 0 (false), 1 (true), & (AND), | (OR), and ^ (XOR), and a desired boolean result value result (true or false), we need to implement a function to count the number of ways of parenthesizing the expression such that it evaluates to result.

For example, given the expression 1^0|0|1 and the desired result false (0), our function should return the total number of valid parenthesization configurations that produce false.

Analyze the Problem Together

When we first look at this problem, it screams recursion. Every binary operator in the expression represents a split point. If we place parentheses around a sub-expression, we divide our string into a left sub-expression and a right sub-expression, joined by an operator.

The "Aha!" conflict here lies in the subproblem dependency. To know whether the overall expression evaluates to true or false, we don't just need to know if the left side is true. Depending on the operator (&, |, or ^), we might need the left side to be true or false, and the right side to be true or false, to achieve our target.

If we use a naive recursive approach without memoization, we recalculate the exact same sub-expressions over and over again. This leads to an exponential time complexity of $O(3^N)$, which will melt your CPU for anything longer than a handful of characters. To optimize this, we must use dynamic programming with memoization, caching the results of evaluating sub-expressions from index i to j for both true and false outcomes.

Questions for the Interviewer

Before we write a single line of code, as senior engineers, we must clarify the boundaries of the problem:

• Can we assume the input expression is always well-formed? (i.e., alternating operands and operators, starting and ending with digits).
• What is the maximum length of the expression? This helps us decide between top-down memoization and bottom-up tabulation.
• How should we handle integer overflow? Given the combinatorial nature of parenthesizing, could the number of ways exceed Integer.MAX_VALUE?

Think About the Solution

Our top-down dynamic programming solution will use a recursive function, say countEval(String exp, boolean result, int start, int end, Map<String, Integer> memo). However, string slicing and map lookups can be slow. Instead, we can use a three-dimensional memoization table: memo[start][end][resultIndex], where resultIndex is 1 for true and 0 for false.

For a given range from start to end:

• Base case: If start == end, we evaluate the single character (0 or 1) and compare it with the desired result.
• Recursive step: Iterate through every operator at index k between start + 1 and end - 1. Split the expression into left (start to k-1) and right (k+1 to end). Compute the ways to get true and false for both sides, then combine them based on the operator at index k.

Write Code and Explain

Here is the production-ready, clean Java implementation using memoization to ensure optimal performance.

import java.util.HashMap;

public class BooleanEvaluation {

    public int countEval(String expr, boolean result) {
        // A cache key can be represented cleanly, but for performance,
        // a 3D array or a composite key object is preferred. Here we use a HashMap with a string key for clarity.
        return countEvalHelper(expr, result, 0, expr.length() - 1, new HashMap<String, Integer>());
    }

    private int countEvalHelper(String expr, boolean result, int start, int end, HashMap<String, Integer> memo) {
        // Base case: single character
        if (start == end) {
            char c = expr.charAt(start);
            boolean val = (c == '1');
            return val == result ? 1 : 0;
        }

        String key = result + "_" + start + "_" + end;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        int ways = 0;

        // Iterate through all operators
        for (int i = start + 1; i < end; i += 2) {
            char operator = expr.charAt(i);
            
            // Evaluate left and right sub-expressions for both true and false outcomes
            int leftTrue = countEvalHelper(expr, true, start, i - 1, memo);
            int leftFalse = countEvalHelper(expr, false, start, i - 1, memo);
            int rightTrue = countEvalHelper(expr, true, i + 1, end, memo);
            int rightFalse = countEvalHelper(expr, false, i + 1, end, memo);

            int totalWays = (leftTrue + leftFalse) * (rightTrue + rightFalse);

            int trueWays = 0;
            if (operator == '&') {
                trueWays = leftTrue * rightTrue;
            } else if (operator == '|') {
                trueWays = leftTrue * rightTrue + leftTrue * rightFalse + leftFalse * rightTrue;
            } else if (operator == '^') {
                trueWays = leftTrue * rightFalse + leftFalse * rightTrue;
            }

            ways += result ? trueWays : (totalWays - trueWays);
        }

        memo.put(key, ways);
        return ways;
    }
}

Step-by-Step Walkthrough:

• We check if our range contains a single character. If so, we return 1 if it matches our target result, 0 otherwise.
• We generate a unique memoization key incorporating our target result, start index, and end index.
• We loop through every operator in the current window. For each operator, we calculate the number of ways the left and right sub-expressions evaluate to true or false.
• Using boolean algebra rules, we calculate how many combinations result in true for the current operator. Finally, we accumulate either trueWays or totalWays - trueWays depending on our target result.

Time & Space Complexity

Let's break down the computational footprint of our solution:

• Time Complexity: $O(N^3)$. There are $O(N^2)$ possible sub-expressions defined by pairs of (start, end) indices. For each sub-expression, we iterate up to $O(N)$ times to test split points. With memoization, each state is computed only once.
• Space Complexity: $O(N^3)$. Our memoization map stores entries for every combination of start, end, and result boolean state. Since there are $N^2$ pairs of indices and 2 possible boolean results, the total number of unique states is $2 imes N^2$, leading to an auxiliary space complexity of $O(N^2)$ for the cache, plus $O(N)$ for the recursion call stack.

Why This Problem Matters (The Senior Perspective)

Problems like Boolean Evaluation are not just interview hurdles; they model real-world scenarios in compiler design, AST (Abstract Syntax Tree) optimization, and expression evaluation engines in databases. When building query optimizers or dynamic rule engines, understanding how to parse, memoize, and evaluate combinatorial logic expressions efficiently separates senior engineers from junior ones. Thread safety and immutability also become critical here if multiple threads evaluate expressions concurrently against shared memoization caches.

Final Thoughts

Dynamic programming is your superpower when dealing with overlapping subproblems and combinatorial explosions. By breaking down the expression into manageable left and right segments and caching our results, we transformed an intractable problem into an elegant, highly performant solution. Take this code, refactor it to use a 3D primitive array instead of a string-keyed HashMap to reduce garbage collection overhead, and drop a comment below if you have any questions. Happy coding!