PPractick

The problem

You're building a rule-engine for a fraud-detection system at a fintech company. Analysts write boolean rules like "1&0|1" (using 1/0 for true/false and &, |, ^ for AND/OR/XOR) but forget to specify operator precedence or parentheses in legacy rule files migrated from an old system. Since ambiguous expressions could evaluate differently depending on how they're grouped, your task is to compute every possible result obtainable by parenthesizing the expression in all valid ways — so the compliance team can audit whether the rule is ambiguous (multiple distinct outcomes) or safe (all groupings agree).

Given a string expression containing digits 0/1 and operators &, |, ^, return a list of all possible results from evaluating the expression by computing every possible way to parenthesize the operators.

Function signature

vector<int> diffWaysToEvaluate(string expression);

Test cases

Input expression	Output	Explanation
`"1&0	1"`	[0, 1]
`"0&0&0&1^1	0"`	[0, 1]
"1"	[1]	Single operand, no operators — trivial base case
"0"	[0]	Single operand
`"1^0	0	1"`

(Constraints typically: 1 <= expression.length <= 20, expression consists of digits 0/1 and operators &,|,^ only, no spaces, no unary operators)

(Note: since these are boolean 0/1 results, the output is just every distinct {0,1} value achievable — but the classic LeetCode version of this problem uses arithmetic +,-,* and returns ALL results including duplicates, not deduplicated. The boolean variant with &,|,^ is a common interview spin — clarify with interviewer whether to dedupe.)

How interviewers phrase it

• "Given a string with digits and operators, return all possible results from grouping the operators differently using parentheses."
• The classic version (LeetCode 241) uses arithmetic operators +, -, * on numbers — the boolean version (&, |, ^ on 0/1) is a common variant/follow-up. They may start with the arithmetic version and pivot to boolean as a follow-up, or vice versa.
• Key phrase that signals this problem: "all possible results of different parenthesizations" — this is the giveaway for the "split at every operator, recurse on both sides, combine" pattern (i.e., the MCM/Catalan-number recursion pattern).

Clarifying questions to ask

1. Should the output contain duplicate values, or should it be deduplicated to a set? (Arithmetic LC241 keeps duplicates since results are usually distinct numbers; the boolean variant naturally has many duplicates since there are only 2 possible values — confirm whether to dedupe.)
2. What operators are supported — just &, |, ^? Any operator precedence rules to ignore, or do we treat every split point equally regardless of operator type?
3. Can the expression contain multi-digit operands, or is it guaranteed single-digit (0/1) only? (Changes how you parse operands during recursion/splitting.)
4. What's the max expression length? (For length ~20, the number of parenthesizations follows Catalan number growth — without memoization this can blow up; confirm if memoization is expected.)

Follow-ups to expect

1. "Can you memoize to avoid recomputation?"
2. "What's the time complexity, and why does it grow so fast?"
3. *"Can you do this with arithmetic operators (+, -, ) instead?"
4. "What if you only wanted to know whether the expression is ambiguous (more than one distinct result), not list every result?"
5. "How would you extend this to support multi-digit numbers in the boolean version (e.g., bitwise AND on integers, not just 0/1)?"
6. "Can you do this iteratively with DP instead of top-down recursion?"

Related questions

• Frog Jump Medium
• Frog jump with K distances Medium
• Fibonacci Number Easy
• Matrix chain multiplication Hard
• Matrix Chain Multiplication | Bottom-Up Hard
• Minimum cost to cut the stick Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in