Boolean Expression Results After Leaf Flips
Google● MediumFULLTIMEONSITE INTERVIEWProblem statement
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.
The problem statement continues
ProExamples
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.
FastPrep Pro
Reported in 1 Google interview this weekUnlock this recently reported problem
FastPrep Pro gives you full access to interview problems reported within the last week.
- Full problem statement and constraints
- 1 more worked example, explained
- Guided hints and editorial
- Run your code on real test cases
$8.25/month
$99 billed yearly — or $19 month-to-month. Cancel anytime.
Free plan — 2 of 2 free unlocks used this week