FastPrepEvaluate a Parsed Expression for Many Values of x
Problems/Evaluate a Parsed Expression for Many Values of x

Evaluate a Parsed Expression for Many Values of x

Google logoGoogle● MediumFULLTIMEONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: One round in a 2022 Google onsite report was about evaluating an arithmetic expression that contains a variable, with 1 + (x) + 5 as the example. The expression arrived already parsed, and the candidate chose how to hold it in memory.

The report does not give the operators, how the structure is passed in, or which value of x to use. We read its wording as asking for the value. Here, you get the parsed tree as arrays. The operators are +, - and *. Subtraction takes the right child's value from the left child's value. Constants are whole numbers from 0 to 1000. You evaluate the tree once for each value in a list of x values. The class design itself is covered in the editorial and is not checked. The limits are our choice.

Our version is about 70% the same as the reported question.

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 children left[i] and right[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 <= 999
  • left.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^15 and 10^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
All Google interview questionsSee Google hiring insights
Saved
class Solution {
    public long[] evaluateParsedExpression(String[] tokens, int[] left, int[] right, int[] xs) {
        // Write your code here.
    }
}
Checking account…