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
Enumerate Results of Every Binary Parenthesization
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.
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.