Google Interview Question for Senior Software Development Engineers


Country: India




Comment hidden because of low score. Click to expand.
0
of 0 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)

- scotthazlett December 05, 2020 | Flag Reply
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]

- Abhi December 14, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 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

- abhigupta4981 December 14, 2020 | Flag Reply
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. 


*/

- Sheshu December 28, 2020 | Flag Reply
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. 


*/

- skumaringuva December 28, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 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)

- Yorik January 03, 2021 | Flag Reply


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