Google Interview Question
Senior Software Development EngineersCountry: 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.
*/
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));
}
}
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, 2020