Boolean Expression Results After Leaf Flips
Reported by candidates from Google's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
The tree is the whole game in this Google OA question, reported in October 2026. You get a Boolean expression encoded as parallel arrays, tokens and parent, and you have to rebuild the structure before you can evaluate anything. Then you answer: what does the root become if you flip one leaf? If you've got an assessment coming up, expect to spend half your time on parsing the arrays and the other half on not recomputing everything. StealthCoder is the hedge if you blank mid-OA, but the pattern here is clean enough to walk in with.
The problem
A Boolean expression tree is encoded by parallel arrays tokens and parent. Node 0 is the root. Operator tokens are AND, OR, XOR, and NOT; leaf tokens are 0 and 1. Children appear in increasing node-index order. NOT has one child, each other operator has two children, and leaves have none. Examples Example 1 tokens = ["AND","OR","1","0","NOT","0"] parent = [-1,0,1,1,0,4] return = [true,false,true,false] The original expression is (1 OR 0) AND NOT 0, which is true. Flipping leaves 1, 0, and the child of NOT independently produces false, true, and false.
Reported by candidates. Source: FastPrep
Pattern and pitfall
Build children lists from the parent array. Since children appear in increasing index order, a single pass that appends each node to its parent's list keeps the order right. Then evaluate with a DFS and store each node's value. The naive approach flips each leaf and re-evaluates the whole tree, which is O(leaves times n). The better trick is to compute, for every node, whether flipping a given leaf would change the root. Push a sensitivity flag down from the root. NOT always passes it through. AND passes it to a child only if the sibling is 1. OR passes it only if the sibling is 0. XOR always passes it. A leaf with the flag set flips the root, so its answer is the negated original value. Watch the recursion depth on skewed trees. Use an iterative traversal if the tree can be deep. If you blank on the propagation rules during the live OA, StealthCoder can give you the skeleton.
If this hits your live OA and you blank, StealthCoder solves it in seconds, invisible to the proctor.
You can drill Boolean Expression Results After Leaf Flips cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Built by an Amazon engineer who would have shipped this the night before his JPMorgan OA if he'd had it.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Google's OA.
Google reuses patterns across OAs. Built by an Amazon engineer who would have shipped this the night before his JPMorgan OA if he'd had it. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Boolean Expression Results After Leaf Flips FAQ
What's the trick in the Google Boolean expression tree OA?+
Don't re-evaluate the tree for every leaf flip. Evaluate once, then pass down whether a change at each node would reach the root. AND, OR, and NOT each have a simple rule based on the sibling's value, and XOR always propagates. That gives linear time.
How do I build the tree from the tokens and parent arrays?+
Make an empty child list for each node. Loop i from 1 to n-1 and append i to the list of parent[i]. Because children appear in increasing index order, the lists end up in the right order without sorting. Node 0 is the root, and its parent is -1.
Is the brute-force flip-and-reevaluate approach good enough?+
It's correct but costs O(leaves times n), which can be quadratic. It's fine as a fallback to check your logic on small cases like the example. If the input sizes are large, the sensitivity-propagation approach is the safer bet, so write that one.
Should I use recursion or iteration for the tree walk?+
A skewed tree can make recursion deep, so an iterative post-order pass for values and a top-down pass for sensitivity is safer. Since parents are given by index, you can often process nodes by explicit stack. Recursion is fine only if you know the depth is small.
How do I prepare for this in 48 hours?+
Practice building a tree from a parent array, then evaluating it with DFS. Next, hand-derive the flip rules for AND, OR, NOT, and XOR on small cases. Trace the example by hand until you get [true,false,true,false]. Then code it once from scratch and test an edge case with a single leaf root.