Enumerate Results of Every Binary Parenthesization

Quick Overview

Enumerate Results of Every Binary Parenthesization. Insert parentheses in every possible full binary way into expression and return the resulting values. Keep the operands and operators in their existing order. D

Enumerate Results of Every Binary Parenthesization

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Other

### Problem Insert parentheses in every possible full binary way into expression and return the resulting values. Keep the operands and operators in their existing order. Different parenthesizations producing equal values still contribute separate output occurrences. The output order is unrestricted. ```cpp vector<int> diffWaysToCompute(string expression); ``` ### Examples ```text expression = "2*3+4" -> [14,10] expression = "5-2-1" -> [4,2] ``` ### Constraints - Expression length is 1 through 20. - Tokens are decimal integers from 0 through 99 and binary +, - or * operators. - All completed results fit signed 32-bit; at most 10000 result occurrences are generated. ### Follow-up Questions Explain how the permitted output freedom is preserved without losing required values or occurrences. ### What a Strong Answer Covers Memoize each operand interval. Choose each operator as its final operation and combine every result from the left and right intervals. Explain why every produced result satisfies the source contract and why no required result is omitted.

Overview: Enumerate Results of Every Binary Parenthesization. Insert parentheses in every possible full binary way into expression and return the resulting values. Keep the operands and operators in their existing order. D

Amazon logo
Amazon
Date not reported
mediumSoftware EngineerOtherCoding & Algorithms
0
0

Problem

Insert parentheses in every possible full binary way into expression and return the resulting values. Keep the operands and operators in their existing order. Different parenthesizations producing equal values still contribute separate output occurrences. The output order is unrestricted.

vector<int> diffWaysToCompute(string expression);

Examples

expression = "2*3+4" -> [14,10]
expression = "5-2-1" -> [4,2]

Constraints

  • Expression length is 1 through 20.
  • Tokens are decimal integers from 0 through 99 and binary +, - or * operators.
  • All completed results fit signed 32-bit; at most 10000 result occurrences are generated.

Follow-up Questions Guidance

Explain how the permitted output freedom is preserved without losing required values or occurrences.

What a Strong Answer Covers Guidance

Memoize each operand interval. Choose each operator as its final operation and combine every result from the left and right intervals. Explain why every produced result satisfies the source contract and why no required result is omitted.