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.
*/
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