Google Interview Question for Senior Software Development Engineers

Country: India

Comment hidden because of low score. Click to expand.
2
of 2 vote

You can use matrix chain multiplication dp
Dp[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

Comment hidden because of low score. Click to expand.
0
of 0 votes

I guess it does not work with negative inputs (e.g.: [-5, 1, -2]).

Comment hidden because of low score. Click to expand.
1
of 1 vote

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)``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

I guess it does not work with negative inputs (e.g.: [-5, 1, -2]).

Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry, I meant to answer the comment below

Comment hidden because of low score. Click to expand.
1
of 1 vote

It's a recursive problem, which can be solved with DP.

There is a simple way to solve a problem for {a1, a2, a3, a4} if you have solutions for:

(a1), (a2, a3, a4)
(a1, a2), (a3, a4)
{a1, a2, a3), (a4)

Comment hidden because of low score. Click to expand.
0
of 0 vote

You can use matrix chain multiplication dp to find the maximum value
dp[l...r] = max(dp[l...k]opdp[k+1...r]) for op in [+,-,*] for k in [l..r-1]

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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.

*/``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

We dont need to worry about negative numbers I guess..-(-3) for example is positive..so we can treat everything as positive

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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.

*/``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

I guess you can't change order of numbers that's why in first example max is 72

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 votes

Definitely not a correct solution for this case {3,4,1,5,1}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def maxx(l):
mmax=l[0]

mx=0
for i in l[1::]:
if mmax*i>mmax+i:
mmax*=i
else:
mmax+=i
l=l[::-1]
amax=l[0]
for x in l[1::]:
if amax*x>amax+x:
amax*=x
else:
amax+=x
if mmax>amax:
return mmax
else:
return amax``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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));
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Since you can use + and - anywhere you can use absolute values. if two adjacent numbers are both bigger than or equal to 2 their multiplication is always bigger. For any adjacent a,b If a < 2 multiplication is bigger if a / (a-2) < b / (b-2). to avoid division by zero change it to a*(b-2)/(a-2)
when there is a number less than 2 you should check both neighbors and first do the addition with the smaller one .
First do all additions than multiply remaining.

``````# find max result
# Engin Yegnidemir
# 8 March 2022

testCases = [
[[3,4,5,1],72],
[[1,1,1,5],15],
[[1,0,2,3],9],
[[-1,-2,-3,-4,2],72],
[[1,0.5,0.6,0.9,10,-2],60],
[[0.5,0.5,0.5],1.5],
[[1,1],2],
[[-1,-1],2],
[[3,3],9],
[[3,1.5,3],13.5],
[[3,1.5,2.5],12],
[[3,0,1.5,0,2.5],12],
[[0],0]
]

def findMaxResult(arr):

if len(arr)  < 1:
raise TypeError
elif len(arr) < 2:
return abs(arr[0])
elif len(arr) > 2:
i = 1
while i < len(arr)-1: #look at a window of three numbers
current = abs(arr[i])
left = abs(arr[i-1])
right = abs(arr[i+1])
if current < 2:
if left < right:
if current * (left - 2) / (2 - current) < left:
add = left+current
arr.pop(i-1)
arr.pop(i-1)
arr.insert(i-1,add)
continue
else:
if current * (right - 2) / (2 - current) < right:
add = right+current
arr.pop(i)
arr.pop(i)
arr.insert(i,add)
continue
i += 1 #if there is nothing to add advance to next window
if len(arr) > 1:
current = abs(arr[0])
if current < 2:
right = abs(arr[1])
if current * (right - 2) / (2 - current) < right :
add = current+right
arr.pop(0)
arr.pop(0)
arr.insert(0,add)

if len(arr) > 1:
lastIndex = len(arr) - 1
current = abs(arr[lastIndex])
if current < 2:
left = abs(arr[lastIndex - 1])
if current  * (left - 2) / (2 - current) < left:
add = arr[lastIndex - 1]+current
arr.pop(lastIndex - 1)
arr.pop(lastIndex - 1)
arr.insert(lastIndex - 1,add)

res = arr[0]
for i in range(1,len(arr)):
res = abs(arr[i] * res)

return res

for testCase in testCases:
#testCase = testCases[6]
print(str(findMaxResult(testCase[0])) + '=' + str(testCase[1]))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````# find max result
# Engin Yegnidemir
# 8 March 2022

testCases = [
[[3,4,5,1],72],
[[1,1,1,5],15],
[[1,0,2,3],9],
[[-1,-2,-3,-4,2],72],
[[1,0.5,0.6,0.9,10,-2],60],
[[0.5,0.5,0.5],1.5],
[[1,1],2],
[[-1,-1],2],
[[3,3],9],
[[3,1.5,3],13.5],
[[3,1.5,2.5],12],
[[3,0,1.5,0,2.5],12],
[[0],0]
]

def findMaxResult(arr):

if len(arr)  < 1:
raise TypeError
elif len(arr) < 2:
return abs(arr[0])
elif len(arr) > 2:
i = 1
while i < len(arr)-1: #look at a window of three numbers
current = abs(arr[i])
left = abs(arr[i-1])
right = abs(arr[i+1])
if current < 2:
if left < right:
if current * (left - 2) / (2 - current) < left:
add = left+current
arr.pop(i-1)
arr.pop(i-1)
arr.insert(i-1,add)
continue
else:
if current * (right - 2) / (2 - current) < right:
add = right+current
arr.pop(i)
arr.pop(i)
arr.insert(i,add)
continue
i += 1 #if there is nothing to add advance to next window
if len(arr) > 1:
current = abs(arr[0])
if current < 2:
right = abs(arr[1])
if current * (right - 2) / (2 - current) < right :
add = current+right
arr.pop(0)
arr.pop(0)
arr.insert(0,add)

if len(arr) > 1:
lastIndex = len(arr) - 1
current = abs(arr[lastIndex])
if current < 2:
left = abs(arr[lastIndex - 1])
if current  * (left - 2) / (2 - current) < left:
add = arr[lastIndex - 1]+current
arr.pop(lastIndex - 1)
arr.pop(lastIndex - 1)
arr.insert(lastIndex - 1,add)

res = arr[0]
for i in range(1,len(arr)):
res = abs(arr[i] * res)

return res

for testCase in testCases:
#testCase = testCases[6]
print(str(findMaxResult(testCase[0])) + '=' + str(testCase[1]))``````

Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More