Combinations of adding operators and parentheses

DFS (Depth first search) with memoization has been introduced in the post of word break using memoization. It uses one of dynamic programming technique “memoization” to save previous results and used for the following recursive steps. This will avoid overlapping and improve complexity. This interview question is another example to use DFS and memoization – the combinations of adding operators and parentheses and find the max possible value.

The trick here is adding parentheses. If you read Gayle McDowell’s “Cracking the Coding Interview” book, you probably have known the “combinations of n-pairs parentheses” problem. The easiest approach is to use DFS recursion. The solution is to split the operation into 2, left and right recursion calls. The left recursion puts “(” to output string; and right recursion puts “)” to the output string. The time complexity is Cn. Cn is Catalan number. Catalan numbers are sequence of natural numbers, often involving recursively defined objects. The first Catalan numbers for n = 0, 1, 2, 3 … are 1, 1, 2, 5, 14…

In the case of combinations of adding operators and parentheses, we use a hashmap<List, List> to store partial results. The keys of the map are the combinations of operands in the array. The values are the results after applying four operators (+ – * /). Since there are parentheses involved, we split the operation to left and right to call recursion as well. Once we have all the possible results, we can find the max possible one. The hashmap actions as the memoization to avoid the overlapping. The time complexity reduces from exponential to (Cn)^2.

Google Interview Question (CareerCup):
Your input is an array, and you can use *, +, -, and () parenthesis anywhere to create and output the maximum possible value.
Ex: input is {3,4,5,1} –> output: 72
input is {1,1,1,5} –> output: 15
Follow up, if there are numbers <0

Java Code:

Input: [3, 4, 5, 1]
Max possible value is: 72

O Notation:
Time complexity:O(Cn^2), Cn is Catalan number, n is array length
Space complexity: Space O(Cn^2)

Java Coding Interview Pocket Book (2nd Edition)

Comments are closed