Largest Minus Smallest Value of a Parenthesized Expression
Updated
Problem statement
You are given a string expression made of single digits joined by + and * signs, such as "2*2+2". There are no spaces.
Add parentheses to decide the order in which the signs are applied. The digits and signs stay in their order, and each sign combines the values on its two sides. The usual rule that * goes before + does not apply here: only the parentheses decide the order, and every way of grouping is allowed.
Different groupings can give different results. Let maxValue be the largest result over all groupings and minValue the smallest. Return maxValue - minValue.
Function
maxMinusMinValue(expression: String) → longExamples
Example 1
expression = "2*2+2"return = 2There are two groupings:
2*(2+2) = 8(2*2)+2 = 6
The largest value is 8 and the smallest is 6, so the answer is 8 - 6 = 2.
Example 2
expression = "1+2*3+4"return = 10There are five groupings:
((1+2)*3)+4 = 13(1+2)*(3+4) = 21(1+(2*3))+4 = 111+((2*3)+4) = 111+(2*(3+4)) = 15
The largest value is 21 and the smallest is 11, so the answer is 21 - 11 = 10.
Example 3
expression = "1+1*0"return = 1The groupings are (1+1)*0 = 0 and 1+(1*0) = 1.
Here doing the + first gives the smaller value, because the result is then multiplied by 0. The answer is 1 - 0 = 1.
Constraints
1 <= expression.length <= 37expression.lengthis odd. The characters at even indexes (0, 2, 4, ...) are digits from0to9, and the characters at odd indexes are+or*.
More Nutanix Onsite Interview questions
- Design Hit CounterONSITE INTERVIEW · Seen Oct 2026
- Peak Process MemoryONSITE INTERVIEW · Seen Aug 2026
- Minimum Operations to Transform ArrayONSITE INTERVIEW · Seen Jun 2026
- Count Connected Components in an Undirected GraphONSITE INTERVIEW · Seen Aug 2025
- LRU CacheONSITE INTERVIEW · Seen Aug 2025
- Running Median of a Multilevel Linked List in Level OrderONSITE INTERVIEW · Seen Aug 2025
- Custom Array IteratorONSITE INTERVIEW · Seen Dec 2024
- Collapse Runs of Repeated CharactersONSITE INTERVIEW · Seen Nov 2022
- Anagram Words in a SentenceONSITE INTERVIEW · Seen Apr 2022
- Sudoku SolverONSITE INTERVIEW · Seen Feb 2022
Similar questions at other companies
- Every Result of Grouping an ExpressionC3.ai · ONSITE INTERVIEWC3.ai interview questions
- Prime StringSnowflake · OASnowflake interview questions
- Sum of All ValuesFlexport · OAFlexport interview questions
- Without WhitespacesPostman · OAPostman interview questions
- Dice-Walk Winning ProbabilityGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Integer BreakAmazon · ONSITE INTERVIEW
- Knight Probability in ChessboardGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- Maximum Bouquet ValueOracle · ONSITE INTERVIEWOracle interview questions
- Count Staircases with Strictly Increasing StepseBay · ONSITE INTERVIEWeBay interview questions
- Calculate a Token-List ExpressionCollege Vine · ONSITE INTERVIEW