How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Boolean Expression Tree with Leaf Flips

Quick Overview

This question evaluates a candidate's ability to work with tree data structures and apply efficient update propagation techniques. It tests practical understanding of recursive tree evaluation, logical operator semantics, and incremental recomputation by traversing ancestor paths rather than re-evaluating the full tree.

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

# Boolean Expression Tree with Leaf Flips You are given a boolean expression represented as a tree. - Each **leaf** node holds a boolean value: `true` or `false`. - Each **internal** node holds a logical operator and combines the values of its children: - `NOT` is unary (exactly one child). - `AND`, `OR`, `XOR` are n-ary over their children (evaluate left to right; for `XOR`, the result is `true` iff an odd number of children evaluate to `true`). The **value of the tree** is the value computed at the root by evaluating recursively. You will then perform a sequence of **leaf flips**. Each flip toggles one leaf from `true` to `false` (or vice versa). The flips are given as a list of leaf references in flip order. After **each** flip, report the new value of the root. Return a list of booleans: the root value after the 1st flip, after the 2nd flip, and so on. ## Interface Define your own node type. A node has an operator (or is a leaf), and a list of children. **Nodes do not store a parent pointer** — you must derive any parent/path information yourself. ``` TreeNode: is_leaf: bool op: one of {"AND", "OR", "XOR", "NOT"} # only when not a leaf value: bool # only when a leaf children: list[TreeNode] # only when not a leaf ``` ## Input - `root`: the root `TreeNode` of the expression tree. - `flips`: a list of leaf nodes to toggle, applied in order. Flips are cumulative (each builds on the previous tree state). ## Output - A list of booleans of length `len(flips)`: the root value after each successive flip. ## Example ``` Expression: XOR( OR(false, true), AND(true, NOT(true)) ) Initial root value: XOR( true, false ) = true flips = [ <the leaf currently `false` inside OR> ] After flipping it to true: OR(true, true) = true, AND branch still false New root: XOR(true, false) = true Output: [true] ``` ## Requirements - Evaluate the **initial** root value first. - For each flip, recompute the affected values. A flip can only change ancestors of the flipped leaf, so an efficient solution recomputes **only along the path from the flipped leaf up to the root**, stopping early if a node's value does not change. Avoid re-evaluating the entire tree on every flip. ## Constraints - `1 <= number of nodes <= 10^5` - `1 <= len(flips) <= 10^5` - Operators are exactly `AND`, `OR`, `XOR` (n-ary, at least one child) and `NOT` (exactly one child). - Leaves are pure boolean constants. ## Follow-up to consider in your design - Discuss how you would precompute structure once so that each of the many flips is handled in time proportional to the leaf's depth (path length) rather than the full tree size, and how early termination helps when a flip does not propagate.

Quick Answer: This question evaluates a candidate's ability to work with tree data structures and apply efficient update propagation techniques. It tests practical understanding of recursive tree evaluation, logical operator semantics, and incremental recomputation by traversing ancestor paths rather than re-evaluating the full tree.

You are given a boolean expression represented as a tree. - Each **leaf** node holds a boolean value: `true` or `false`. - Each **internal** node holds a logical operator and combines the values of its children: - `NOT` is unary (exactly one child). - `AND`, `OR`, `XOR` are n-ary over their children (for `XOR`, the result is `true` iff an odd number of children evaluate to `true`). The **value of the tree** is the value computed at the root by evaluating recursively. You then perform a sequence of **leaf flips**; each flip toggles one leaf. After **each** flip, report the new root value. ## Serializable encoding (used by this console) So the tree can be passed as data, it is encoded as a nested list: - **Leaf:** `["LEAF", <bool>]` - **Internal node:** `[<op>, <child>, <child>, ...]` where `<op>` is one of `"AND"`, `"OR"`, `"XOR"`, `"NOT"` and each `<child>` is itself an encoded node. Example tree `XOR( OR(false, true), AND(true, NOT(true)) )` becomes: ``` ["XOR", ["OR", ["LEAF", false], ["LEAF", true]], ["AND", ["LEAF", true], ["NOT", ["LEAF", true]]]] ``` ## Inputs - `tree`: the encoded root node. - `flips`: a list of **paths**. Each path is a list of child-indices that locates a leaf — start at the root and, for each index `i` in the path, descend into the `i`-th child; the node you land on is the leaf to toggle. (An empty path `[]` refers to the root itself, which is only valid when the root is a leaf.) Flips are cumulative: each builds on the tree state left by the previous flip. ## Output Return a list of booleans of length `len(flips)`: the root value after the 1st flip, after the 2nd flip, and so on. ## Example Tree `["XOR", ["OR", ["LEAF", false], ["LEAF", true]], ["AND", ["LEAF", true], ["NOT", ["LEAF", true]]]]` evaluates to `true` initially. With `flips = [[0, 0]]` (the `false` leaf inside the OR), the OR becomes `OR(true, true) = true`, the AND branch stays `false`, so the root is `XOR(true, false) = true`. Output: `[true]`. ## Efficiency requirement Evaluate the initial root value once. For each flip, recompute only along the path from the flipped leaf up to the root, stopping early if a node's value does not change — do not re-evaluate the whole tree per flip. With this, each flip costs time proportional to the leaf's depth.

Constraints

1 <= number of nodes <= 10^5
1 <= len(flips) <= 10^5
Operators are exactly AND, OR, XOR (n-ary, at least one child) and NOT (exactly one child).
Leaves are pure boolean constants.
Each flip path locates an existing leaf; an empty path [] is valid only when the root itself is a leaf.

Examples

Input: (["XOR", ["OR", ["LEAF", false], ["LEAF", true]], ["AND", ["LEAF", true], ["NOT", ["LEAF", true]]]], [[0, 0]])

Expected Output: [true]

Explanation: Initial root = XOR(OR(false,true)=true, AND(true, NOT(true)=false)=false) = true. Flip path [0,0] is the false leaf inside OR -> OR(true,true)=true, AND branch unchanged false, root XOR(true,false)=true.

Input: (["AND", ["LEAF", true], ["LEAF", true]], [[0], [1], [0]])

Expected Output: [false, false, false]

Explanation: Start AND(true,true)=true. Flip child 0 -> AND(false,true)=false. Flip child 1 -> AND(false,false)=false. Flip child 0 back -> AND(true,false)=false.

Input: (["LEAF", true], [[], []])

Expected Output: [false, true]

Explanation: Root is a leaf. Empty path [] toggles the root leaf: true->false, then false->true.

Input: (["OR", ["LEAF", false], ["LEAF", false]], [[0], [1], [0]])

Expected Output: [true, true, true]

Explanation: Start OR(false,false)=false. Flip child 0 -> OR(true,false)=true. Flip child 1 -> OR(true,true)=true. Flip child 0 back -> OR(false,true)=true.

Input: (["NOT", ["LEAF", false]], [[0], [0]])

Expected Output: [false, true]

Explanation: Start NOT(false)=true. Flip the single child false->true -> NOT(true)=false. Flip back true->false -> NOT(false)=true.

Input: (["XOR", ["LEAF", true], ["LEAF", false], ["LEAF", true], ["LEAF", false]], [[1], [3], [0]])

Expected Output: [true, false, true]

Explanation: n-ary XOR = parity of true children. Start [T,F,T,F] -> 2 trues -> false. Flip idx1 F->T: 3 trues -> true. Flip idx3 F->T: 4 trues -> false. Flip idx0 T->F: 3 trues -> true.

Input: (["AND", ["OR", ["LEAF", false], ["LEAF", false]], ["NOT", ["LEAF", false]]], [[0, 1], [0, 1], [1, 0]])

Expected Output: [true, false, false]

Explanation: Start AND(OR(false,false)=false, NOT(false)=true)=false. Flip [0,1] (2nd OR leaf) F->T: OR=true, AND(true,true)=true. Flip [0,1] back T->F: OR=false, AND=false. Flip [1,0] (NOT's leaf) F->T: NOT(true)=false, AND(false,false)=false.

Hints

Build the tree once and keep, per node, its current boolean value plus a pointer to its parent. Nodes have no parent pointer in the raw encoding, so set parents yourself while building.
Do a single recursive post-order evaluation to fill every node's initial value before processing any flips.
A flip can only affect ancestors of the flipped leaf. Toggle the leaf, then recompute each ancestor in turn walking up to the root.
Early termination: if recomputing an ancestor yields the same value it already had, none of its own ancestors can change either, so stop and record the current root value.
For AND, short-circuit thinking helps reason about it, but you must recompute from the actual current child values; for XOR the result is the parity (odd count) of true children.

Quick Overview