Google Interview Question Senior Software Development Engineers
Country: India
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.
*/
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!
- scotthazlett December 05, 2020import 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)