FastPrepBoolean Expression Results After Leaf Flips
Problems/Boolean Expression Results After Leaf Flips

Boolean Expression Results After Leaf Flips

Google logoGoogle● MediumFULLTIMENEW GRADINTERNONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: The report defines the Boolean operators, initial evaluation, and per-leaf root updates. Array serialization and independent single-leaf flips are specified for practice; the judged task matches at about 95%.

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.

Return an array containing the original root value followed by the root value obtained when each leaf is flipped independently. Process leaves in increasing node-index order, and restore the original tree before considering the next leaf.

Function

rootValuesAfterLeafFlips(tokens: String[], parent: int[]) → boolean[]

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.

Example 2

tokens = ["XOR","0","0"]parent = [-1,0,0]return = [false,true,true]

The original equal inputs XOR to false. Flipping either input alone makes the inputs different.

Constraints

  • 1 <= tokens.length == parent.length <= 200000.
  • parent[0] == -1 and 0 <= parent[i] < i for i > 0.
  • The arrays encode one valid rooted expression tree with the required operator arities.
  • Every token is 0, 1, AND, OR, XOR, or NOT.

More Google problems

  • Apartment Housemate PreferencesPHONE SCREEN · Seen Nov 2026
  • Price at Query TimestampsPHONE SCREEN · Seen Nov 2026
  • 0/1 Knapsack with Weight and Volume LimitsONSITE INTERVIEW · Seen Nov 2026
All Google interview questionsSee Google hiring insights
Saved
class Solution {
    public boolean[] rootValuesAfterLeafFlips(String[] tokens, int[] parent) {
        // Write your code here.
    }
}
Checking account…