How should I practice Stack Formula Interpreter?

Start by reading the full statement, solve the visible examples, then compare the pattern against related TypeSafe AI phone screen problems in FastPrep.

Is Stack Formula Interpreter associated with TypeSafe AI?

FastPrep tags this as a TypeSafe AI phone screen coding practice problem when the problem catalog has that company and stage context.

Stack Formula Interpreter

TypeSafe AI● EasyFULLTIMEPHONE SCREEN

Problem statement

Source note: This was a full-time technical phone screen at TypeSafe AI, and the code was written by hand. The report names the task in a line or two: an interpreter, built around a stack, that works out the value of arithmetic formulas. The author found it easier than the common calculator exercises. The report gives no formula syntax, operator list, rounding rule, output form, limits or examples.

Practice choices: each formula is a line of space-separated tokens in postfix order. A number is pushed, including a negative one such as -3; a token is an operator only when it is exactly one of the four characters +, -, * and /. An operator pops the top value as its right operand and the value below it as its left operand, then pushes the result, and division truncates toward zero. Every formula is valid, never divides by zero, and every value fits in a 32-bit integer. You get many formulas at once and return one value per formula, in order. The size limits and the examples are ours too.

The judged task matches the report at about 55%.

You are building a small stack interpreter that evaluates formulas. A formula is a string of tokens separated by single spaces. The interpreter starts with an empty stack and reads the tokens from left to right:

An integer literal, such as 12 or -3, pushes its value onto the stack.
An operator +, -, * or / pops the top value as the right operand, then pops the next value as the left operand, and pushes left op right.
Division truncates toward zero, so -7 / 2 is -3.

A token is an operator only when it is exactly one of those four characters. A token such as -3 is a negative literal, not a minus sign. After the last token, exactly one value is left on the stack, and that value is the formula's value.

Given an array formulas, evaluate each formula on its own, starting from an empty stack every time. Return an array with the value of each formula, in the same order.

Function

evaluateFormulas(formulas: String[]) → int[]

Examples

Example 1

formulas = ["3 4 +","10 2 8 * -","7"]return = [7,-6,7]

Each formula starts with an empty stack.

"3 4 +": push 3 and 4; + pops them and pushes 3 + 4 = 7.
"10 2 8 * -": push 10, 2 and 8; * pops 8 and 2 and pushes 2 * 8 = 16; - pops 16 (right) and 10 (left) and pushes 10 - 16 = -6.
"7": a single literal; its value is 7.

Example 2

formulas = ["-7 2 /","7 -2 /","5 -3 -"]return = [-3,-3,8]

"-7 2 /" computes -7 / 2 = -3.5, which truncates toward zero to -3 (not -4). "7 -2 /" also gives -3.

In "5 -3 -", the token -3 is a negative literal and the last - is the operator, so the value is 5 - (-3) = 8.

Example 3

formulas = ["6 2 3 + * 8 4 / -"]return = [28]

6, 2, 3 are pushed; the stack is [6, 2, 3].
+ replaces 2, 3 with 5: [6, 5].
* replaces 6, 5 with 30: [30].
8 and 4 are pushed: [30, 8, 4]; / replaces 8, 4 with 2: [30, 2].
- replaces 30, 2 with 30 - 2 = 28, the only value left.

Constraints

1 <= formulas.length <= 100
1 <= formulas[i].length <= 1000
Each formulas[i] consists of tokens separated by single spaces, with no leading or trailing space.
Each token is +, -, *, /, or an integer literal: an optional - followed by decimal digits with no leading zeros. Zero is written 0, never -0.
Every formula is well-formed: each operator finds at least two values on the stack, and exactly one value is left after the last token.
No formula divides by zero.
Every literal and every intermediate value is in the range [-2^31, 2^31 - 1].

See TypeSafe AI hiring insights