Google Interview Question Senior Software Development Engineers
Country: India
As a strawman solution, I went with an exhaustive traversal. Further optimizations is needed past 5 inputs due to horrendous runtime complexity.
QUESTION: Would my solution benefit from memoization? If not, would an alternate solution which permutes the tree (akin to how red-black trees stay balanced via permuting the tree during insertion) benefit from memoization? Perhaps a Merkle Tree?
Thank you in advance for your time and guidance!
import sys
import unittest
from enum import Enum
class BinaryOperation(Enum):
# Enum forbids descriptors as values, so use tuple as value instead and wrap function inside
ADD = (lambda left, right: left + right),
SUB = (lambda left, right: left - right),
MUL = (lambda left, right: left * right),
DIV = (lambda left, right: left / right),
def __call__(self, *args, **kwargs):
return self.value[0].__call__(*args, **kwargs)
def __repr__(self):
return self.value[0].__repr__()
def __str__(self):
return self.value[0].__str__()
class Direction(Enum):
L, R = range(2)
class IntegerOperations:
@staticmethod
def __find_maximum(numbers, index, operations, directions, running_max):
# check for return condition: only 1 number left in numbers
if len(numbers) == 1:
return max(running_max, int(numbers[0]))
# sanity checks
if index < 0 or index >= len(numbers):
assert False, "index out-of-bounds"
if len(operations) == 0:
assert False, "out of operations"
if len(directions) == 0:
assert False, "out of directions"
# remove out-of-bounds recursion
if index == 0:
directions.remove(Direction.L)
elif index == len(numbers) - 1:
directions.remove(Direction.R)
# may want to add additional short-curcuit logic here
# recurse along {all operations} X {all directions}
for direction in directions:
for operation in operations:
# generate inputs for next recursion call
# start with all operations, all directions
iter_operations = [op for op in BinaryOperation]
iter_directions = [di for di in Direction]
iter_index = index
# operate() presumes LTR operands, so for a RTL operation, we simply decr our index
if direction == Direction.L:
iter_index = iter_index - 1
# operate upon 2 elements in numbers, and return a list that is 1 element shorter
try:
iter_numbers = IntegerOperations.operate(numbers, iter_index, operation)
except ZeroDivisionError:
next
# can add code to handle other math exceptions
# recurse and overwrite running_max if larger tally found
running_max = IntegerOperations.__find_maximum(iter_numbers, iter_index, iter_operations, iter_directions, running_max)
# we must also consider skipping to the next index (R) without performing any binary operation,
# so that we can find solutions where the parantheses are not nested, eg ((1+1)+1)*(1+1).
# we can ignore skipping to the previous index (L) because that space has already been covered.
# code would be cleaner to fold the following into the main nested loops above, but that would require
# adding a skip operator into BinaryOperation which would require refactoring BinaryOperation into a more generalized class
if Direction.R in directions:
# R is still an option, ergo index+1 is valid index
iter_index = index + 1
iter_operations = [op for op in BinaryOperation]
iter_directions = [di for di in Direction]
running_max = IntegerOperations.__find_maximum(numbers, iter_index, iter_operations, iter_directions, running_max)
return running_max
@staticmethod
def find_maximum(numbers):
""" given a list of integers, finds the largest total by permuting math operations (*,/,-,+) and parentheses.
operations that result in NaN are ignored, eg 1 / 0 """
index = 0 # must be 0 as traversal algorithm is optimized to skip only rightwards but not leftwards
operations = [op for op in BinaryOperation]
directions = [di for di in Direction]
return IntegerOperations.__find_maximum(numbers, index, operations, directions, ~sys.maxsize)
@staticmethod
def operate(numbers, index, operation):
""" performs binary operation on 2 elements (numbers[index], numbers[index+1]) in a list of numbers,
and returns a copy of the list that preserves ordering as well as combines those 2 elements into 1 """
result = operation(numbers[index], numbers[index+1])
pre_numbers = numbers[:index]
post_numbers = numbers[index+2:]
return pre_numbers + [result] + post_numbers
class Test(unittest.TestCase):
# can add more test cases, just some sanity tests
def test_max_tally(self):
data = [
([2, 2, 2, 2, 2], 32),
([0.5, 0.5, 0.5, 0.5, 0.5], 8),
([1, 1, 1, 1, 1], 6),
([1, 0, 1, 0, 1], 3),
([-1, -5, 10, -5, 0], 300),
# ([1, 1, 1, 1, 1, 1], 9), # runtime becomes prohibitive for length >= 6
]
for d in data:
assert IntegerOperations.find_maximum(d[0]) == d[1]
print("[PASS] {} -> {}".format(d[0], d[1]))
return
if __name__ == "__main__":
unittest.main(verbosity=2)
testCases = {
[0]
[0,0]
[0.5,0.5,1,2]
[-1,-2,0,1,2]
[-0.25,-0.24,-100,-101,0.24,0.25,1,100,101]
[1,2,3,4,5]
[-1,-2,-3,-4]
[-1,-2,-3,-4,-5]
[-0.5,-0.4,-0.3]
[-0.5,-0.4]
}
/*
Group numbers into +ve -ve
Group numbers into decimal and non decimal
-ve
{
{ negative decimals -
ex: 0.5x0.5 - less number
0.5+0.5 - greater
0.5-0.5 - less of all.
}
{ -ve non decimal
odd count-
only one -ve - total max can be negative.
else -(least number)( multiply all numbers)
even count- * - max number
}
}
+ve
{
{
decimals
0.5+0.5 -- Max
0.5 - 0.5
0.5x0.5
}
{
Non decimals
multiplication will give max
}
}
if we calculate subgroups and try to make the final output, it will be best result.
*/
testCases = {
[0]
[0,0]
[0.5,0.5,1,2]
[-1,-2,0,1,2]
[-0.25,-0.24,-100,-101,0.24,0.25,1,100,101]
[1,2,3,4,5]
[-1,-2,-3,-4]
[-1,-2,-3,-4,-5]
[-0.5,-0.4,-0.3]
[-0.5,-0.4]
}
/*
Group numbers into +ve -ve
Group numbers into decimal and non decimal
-ve
{
{ negative decimals -
ex: 0.5x0.5 - less number
0.5+0.5 - greater
0.5-0.5 - less of all.
}
{ -ve non decimal
odd count-
only one -ve - total max can be negative.
else -(least number)( multiply all numbers)
even count- * - max number
}
}
+ve
{
{
decimals
0.5+0.5 -- Max
0.5 - 0.5
0.5x0.5
}
{
Non decimals
multiplication will give max
}
}
if we calculate subgroups and try to make the final output, it will be best result.
*/
First we should get ride of ones. To do so create a new array with the same size. Copy data from the old array. If there is one 1 then add it to the smaller neighbor. If there is more than one one write them as collection of 2 and 3s. Priority is with 3. This means you may have one or two 2s before 3s.
Solve the resulting array with matrix chain multiplication algorithm.
I found this question confusing.
It mentions a double array but the examples given don't look like a double array.
Also, in the example {3,4,5,1} the answer given is 72 but I think (1+3)(4)(5) will give an answer of 80. I think the logic goes like this - if in the list there are 1s all those ones need to go in a second array. If there's only 1 1 then that one gets added to the smallest number in the first array and you multiply out the results but if there are multiple ones in the second array you add them then multiply the the numbers so 3,4,5,1 becomes 2 arrays (3,4,5) and (1) since there is only 1 1 it gets added to the smallest number (1+3)*(4)*(5) = 80 but (1,1,1,5) becomes array (5) and array (1,1,1) the 3 ones get added and multiplied by the contents in the other array - giving you 15. I haven't yet thought about negatives.
A simple solution I could think for n>0 is, count all the 1s in the given array (if any are present), sum them together(represented by count) and multiply all the numbers (except ones) and then multiply it with the count of 1's (if count>0). That will be the maximum possible value for an array containing positive integers only.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.*;
public class OperatorCombinationsResults {
//Wrapper, Time O(Cn^2), Space O(Cn^2), Cn is Catalan number, n is array length
public static int operatorCombinations(List<Integer> tokens) {
List<Integer> res = helper(tokens, new HashMap<>());
Collections.sort(res, Collections.reverseOrder());
return res.get(0);
}
//DFS + memoziation, Time average O(Cn^2) when memoization takes places, Space O(Cn^2)
private static List<Integer> helper(List<Integer> t, Map<List<Integer>, List<Integer>> map) {
if (t.size() <= 1)
return t;
if (map.containsKey(t))
return map.get(t);
List<Integer> res = new ArrayList<>();
for (int i = 1; i < t.size(); i++) {
List<Integer> left = helper(t.subList(0, i), map);
List<Integer> right = helper(t.subList(i, t.size()), map);
for (int a : left) {
for (int b : right) {
res.add(a + b);
res.add(a - b);
res.add(a * b);
if (b != 0)
res.add(a / b);
}
}
}
map.put(t, res); //map stores (token, partial result) pair
return res;
}
public static void main(String[] args) {
List<Integer> list = Arrays.asList(3,4,5,1);
System.out.println("Input: " + list);
System.out.print("Max possible value is: ");
System.out.println(operatorCombinations(list));
}
}
You can use matrix chain multiplication dp
- abhigupta4981 December 14, 2020Dp[l...r] = max(dp[l..k]opdp[k+1...r]) for op in [+,-,*] for k in [l...r-1]
This will help you find max value in n^3
Let me know if there is some more optimal soln than this