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 Technical Screen rounds at Waymo.

What role is this question designed for?

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

Serialize Expression Tree Minimizing Parentheses

Company: Waymo

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given a binary expression syntax tree, serialize it into an infix string using the minimum number of parentheses required to preserve the tree's evaluation semantics. Each node is one of: - A variable leaf, represented by a non-empty identifier such as `a`, `x`, or `foo` - A binary operator node whose operator is one of `+`, `-`, `*`, `/` and whose left and right children are valid expression nodes Use standard arithmetic precedence: 1. `*` and `/` have higher precedence than `+` and `-` 2. Operators are evaluated left to right when precedence is the same Return a string representation of the expression with unnecessary parentheses removed, but do not change the meaning of the original expression tree. Examples: - Tree for `(a + b) * c` should serialize as `(a+b)*c` - Tree for `a + (b * c)` should serialize as `a+b*c` - Tree for `a - (b + c)` should serialize as `a-(b+c)` - Tree for `(a - b) - c` should serialize as `a-b-c` - Tree for `a / (b * c)` should serialize as `a/(b*c)` Implement a function such as: `string serialize(Node root)` where `Node` contains either a variable name or an operator with left and right children.

Quick Answer: This question evaluates proficiency with binary expression trees, operator precedence and associativity, and the ability to serialize an abstract syntax tree into an infix string using the minimum necessary parentheses.

You are given a binary expression syntax tree and must serialize it into an infix string with no spaces, using the minimum number of parentheses needed to preserve its mathematical meaning. The inorder sequence of operands and operators must stay the same as in the tree. You may only decide whether a child subexpression should be wrapped in parentheses. Each node is either: - a variable leaf, or - a binary operator node using one of `+`, `-`, `*`, `/` Use normal mathematical arithmetic rules: - `*` and `/` have higher precedence than `+` and `-` - operators with the same precedence are read left to right - `/` is ordinary mathematical division, not programming-language integer division For this problem, the tree is encoded with arrays: - `types[i]` is either `'var'` for a leaf or one of `'+', '-', '*', '/'` for an operator node - if `types[i] == 'var'`, then `values[i]` is the variable name and `left[i] = right[i] = -1` - otherwise, `left[i]` and `right[i]` are the indices of the left and right child, and `values[i]` is ignored - `root` is the index of the root node Examples: - `(a + b) * c` -> `(a+b)*c` - `a + (b * c)` -> `a+b*c` - `a - (b + c)` -> `a-(b+c)` - `(a - b) - c` -> `a-b-c` - `a / (b * c)` -> `a/(b*c)`

Constraints

1 <= n == len(types) == len(values) == len(left) == len(right) <= 1000
Each `types[i]` is either `'var'` or one of `'+', '-', '*', '/'`
If `types[i] == 'var'`, then `values[i]` is a non-empty identifier and `left[i] = right[i] = -1`
The input describes a valid binary tree rooted at `root`

Examples

Input: (['var'], ['foo'], [-1], [-1], 0)

Expected Output: 'foo'

Explanation: A single variable leaf needs no parentheses.

Input: (['var', 'var', '+', 'var', '*'], ['a', 'b', '', 'c', ''], [-1, -1, 0, -1, 2], [-1, -1, 1, -1, 3], 4)

Expected Output: '(a+b)*c'

Explanation: The `+` subtree has lower precedence than `*`, so it must stay parenthesized.

Input: (['var', 'var', 'var', '*', '+'], ['a', 'b', 'c', '', ''], [-1, -1, -1, 1, 0], [-1, -1, -1, 2, 3], 4)

Expected Output: 'a+b*c'

Explanation: Multiplication already binds tighter than addition, so no extra parentheses are needed.

Input: (['var', 'var', 'var', '+', '-'], ['a', 'b', 'c', '', ''], [-1, -1, -1, 1, 0], [-1, -1, -1, 2, 3], 4)

Expected Output: 'a-(b+c)'

Explanation: Without parentheses, `a-b+c` would mean `(a-b)+c`, which changes the value.

Input: (['var', 'var', '-', 'var', '-'], ['a', 'b', '', 'c', ''], [-1, -1, 0, -1, 2], [-1, -1, 1, -1, 3], 4)

Expected Output: 'a-b-c'

Explanation: Because operators of the same precedence are read left to right, `(a-b)-c` can be written as `a-b-c`.

Input: (['var', 'var', 'var', '*', '/'], ['a', 'b', 'c', '', ''], [-1, -1, -1, 1, 0], [-1, -1, -1, 2, 3], 4)

Expected Output: 'a/(b*c)'

Explanation: Dropping the parentheses would produce `a/b*c`, which means `(a/b)*c`, not `a/(b*c)`.

Input: (['var', 'var', 'var', '-', '+'], ['a', 'b', 'c', '', ''], [-1, -1, -1, 1, 0], [-1, -1, -1, 2, 3], 4)

Expected Output: 'a+b-c'

Explanation: For the right child of `+`, same-precedence subtraction does not need parentheses: `a+(b-c)` can be written as `a+b-c`.

Input: (['var', 'var', 'var', '-', '-'], ['a', 'b', 'c', '', ''], [-1, -1, -1, 1, 0], [-1, -1, -1, 2, 3], 4)

Expected Output: 'a-(b-c)'

Explanation: Here the right child of `-` must stay wrapped. `a-b-c` would mean `(a-b)-c`, which is different.

Input: (['var', 'var', 'var', '/', '*'], ['x', 'y', 'z', '', ''], [-1, -1, -1, 1, 0], [-1, -1, -1, 2, 3], 4)

Expected Output: 'x*y/z'

Explanation: For ordinary arithmetic, `x*(y/z)` can be written as `x*y/z` without changing meaning.

Input: (['var', 'var', 'var', '/', '/'], ['a', 'b', 'c', '', ''], [-1, -1, -1, 1, 0], [-1, -1, -1, 2, 3], 4)

Expected Output: 'a/(b/c)'

Explanation: The right child of `/` with the same precedence must keep parentheses. `a/b/c` means `(a/b)/c`.

Input: (['var', 'var', '+', 'var', '/'], ['foo', 'bar', '', 'baz', ''], [-1, -1, 0, -1, 2], [-1, -1, 1, -1, 3], 4)

Expected Output: '(foo+bar)/baz'

Explanation: Multi-character identifiers are allowed. The sum must stay parenthesized because it is the left child of division.

Hints

Compare a child node's operator precedence with its parent's. Lower precedence children usually need parentheses; higher precedence children do not.
The tricky case is when parent and child have the same precedence. The left child is safe without parentheses, but the right child depends on the parent operator. Compare `a+(b-c)` with `a-(b-c)`, and `x*(y/z)` with `x/(y/z)`.

Quick Overview

This question evaluates proficiency with binary expression trees, operator precedence and associativity, and the ability to serialize an abstract syntax tree into an infix string using the minimum necessary parentheses.