Every Result of Grouping an Expression
Updated
Problem statement
You are given a string expression made of whole numbers joined by the operators +, - and *, such as "4-1-2+3".
Add parentheses to decide the order in which the operators are applied. A grouping is a way of adding parentheses so that every operator joins exactly two parts, each part being a single number or a group in parentheses. Only the parentheses decide the order; the usual rule that * goes before + and - does not apply.
Return the value of every grouping, sorted from smallest to largest. Different groupings can give the same value. List a value once for each grouping that gives it.
Function
allGroupingResults(expression: String) → long[]Examples
Example 1
expression = "7-2*5"return = [-3,25]Two operators give two groupings. (7-2)*5 = 5 * 5 = 25 and 7-(2*5) = 7 - 10 = -3. The first grouping applies - before *, which is allowed here. Sorted, the results are -3 and 25.
Example 2
expression = "4-1-2+3"return = [-2,2,4,8,8]Four numbers can be grouped in five ways: ((4-1)-2)+3 = 4, (4-(1-2))+3 = 8, (4-1)-(2+3) = -2, 4-((1-2)+3) = 2 and 4-(1-(2+3)) = 8. Two groupings give 8, so 8 appears twice.
Example 3
expression = "42"return = [42]A single number has exactly one grouping: the number itself.
Constraints
1 <= expression.length <= 20expressionholds between 1 and 7 numbers.- Each number is from
0to99and is written without leading zeros. - The only operators are
+,-and*. Numbers and operators alternate, and there are no spaces or parentheses.
More C3.ai interview questions
- Fewest Jumps to the Last IndexONSITE INTERVIEW · Seen Jan 2023
- Rotate a Square Grid ClockwiseONSITE INTERVIEW · Seen Jan 2023
- Movie Schedule for Maximum EnjoymentONSITE INTERVIEW · Seen Jan 2023
- Days Until a Warmer DayPHONE SCREEN · ONSITE INTERVIEW · Seen Apr 2022
- Can All Courses Be FinishedONSITE INTERVIEW · Seen Nov 2021
- Longest Arithmetic SubsequenceONSITE INTERVIEW · Seen Feb 2021
- Gas Station LoopONSITE INTERVIEW · Seen Dec 2020
- Drop Recent Duplicate MessagesOA · Seen Oct 2026
- Maximum K-Star SumOA · Seen Oct 2026
- Fewest Turns to Open a Wheel LockPHONE SCREEN · Seen Nov 2024
Similar questions at other companies
- Scramble StringExpedia · ONSITE INTERVIEWExpedia interview questions
- Validate a Palindrome After Limited DeletionsMeta · PHONE SCREEN · ONSITE INTERVIEWMeta interview questions
- Wildcard Pattern MatchingMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Largest Minus Smallest Value of a Parenthesized ExpressionNutanix · ONSITE INTERVIEWNutanix interview questions
- Integer to English Words: Up to 20 DigitsPeopleStrong · ONSITE INTERVIEWPeopleStrong interview questions
- Fibonacci with Input ValidationMorgan Stanley · ONSITE INTERVIEWMorgan Stanley interview questions
- Edit DistanceAstrotalk · PHONE SCREEN
- Minimum Dictionary SegmentsGoogle · PHONE SCREENGoogle interview questions
- Prime StringSnowflake · OASnowflake interview questions
- Sum of All ValuesFlexport · OAFlexport interview questions