Evaluate a Parsed Expression for Many Values of x
Updated
Problem statement
An arithmetic expression such as 1 + (x) + 5 is given as a binary tree that was built beforehand, so there is no text to read. Compute what the tree evaluates to.
The tree has n nodes numbered 0 to n - 1, and node 0 is the root. Node i holds tokens[i]:
"+","-"or"*": an operator node with childrenleft[i]andright[i]. Its value is the left child's value combined with the right child's value. For"-", the right child's value is subtracted from the left child's value."x": the variable.- A whole number such as
"5": a constant.
Leaf nodes have left[i] == right[i] == -1. A child's number can be smaller or larger than its parent's number.
For each value in xs, set x to that value and return the value of the whole expression. Return the results in the same order as xs.
Function
evaluateParsedExpression(tokens: String[], left: int[], right: int[], xs: int[]) → long[]Examples
Example 1
tokens = ["+","+","1","x","5"]left = [1,2,-1,-1,-1]right = [4,3,-1,-1,-1]xs = [0,2,-4]return = [6,8,2]The tree holds (1 + x) + 5. Node 0 adds node 1 and node 4. Node 1 adds the leaves 1 and x. For x = 0 the value is 1 + 0 + 5 = 6, for x = 2 it is 8, and for x = -4 it is 2.
Example 2
tokens = ["-","*","x","x","-","x","3"]left = [1,2,-1,-1,5,-1,-1]right = [4,3,-1,-1,6,-1,-1]xs = [3,-2]return = [9,9]The tree holds x * x - (x - 3). The left operand is subtracted by the right one. For x = 3: 9 - 0 = 9. For x = -2: 4 - (-5) = 9.
Example 3
tokens = ["7"]left = [-1]right = [-1]xs = [5]return = [7]A single number node is the whole expression, so the value is 7 no matter what x is.
Constraints
1 <= tokens.length <= 999left.length == right.length == tokens.length- Each
tokens[i]is"+","-","*","x", or a whole number from 0 to 1000 written without leading zeros. -1 <= left[i], right[i] <= tokens.length - 1- The arrays describe one tree rooted at node 0: every operator node has two different children, every other node has
left[i] == right[i] == -1, and every node except node 0 is the child of exactly one node. 1 <= xs.length <= 100-1000 <= xs[k] <= 1000- For every value in
xs, the value of every node is between-10^15and10^15.
More Google Onsite Interview questions
- Delete Nodes and Return Forest RootsONSITE INTERVIEW · Seen Nov 2026
- Dice-Walk Winning ProbabilityPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- First and Last Target Position in a Mountain ArrayONSITE INTERVIEW · Seen Nov 2026
- Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- 0/1 Knapsack with Weight and Volume LimitsONSITE INTERVIEW · Seen Nov 2026
- Batched Subsequence Word MatchesONSITE INTERVIEW · Seen Nov 2026
- Course Schedule Cycle DetectionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Filesystem Entity Total SizeONSITE INTERVIEW · Seen Nov 2026
- Longest Subarray Within an Absolute-Difference LimitONSITE INTERVIEW · Seen Nov 2026
- Reach a Destination Through Scheduled FlightsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- N-ary Index-Path Encoder and DecoderBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Serialize and Deserialize an N-Ary TreeUber · ONSITE INTERVIEWUber interview questions
- Nested Todo ListNotion · PHONE SCREEN · ONSITE INTERVIEWNotion interview questions
- Uniformly Sample a Node from a Large TreeMeta · ONSITE INTERVIEWMeta interview questions
- N-Ary Tree Codec OperationsLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- Serialize and Deserialize a Binary TreeMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Count Prime Values in SubtreesVisa · OAVisa interview questions
- Throne Inheritance Without an Initial KingSnowflake · PHONE SCREENSnowflake interview questions
- Frog Position After T SecondsInMobi · PHONE SCREENInMobi interview questions
- Render a Task Tree from CSV RowsStripe · PHONE SCREEN · ONSITE INTERVIEWStripe interview questions
Google interview experiences
- Google L4 SWE Phone Screen: 1 Experience
- Google ML Engineering Manager Onsite: 1 Experience
- Google Experienced SWE First Round and Onsite: 1 Experience
- Google AI Coding Interview and AI OA: 2 Experiences
- Google SWE Intern Interview Results Timeline: 13 Experiences
- Google L4 SWE Phone Screen and Kirkland Onsite: 1 Experience