## Google Interview Question for SDE-3s

• 0

Country: United States

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

My solution N^3 top down dynamic programming approach but I believe there is an O(n) algorithm that solves it. Anyone have any ideas?

``````public static long max(int[] nums) {

Long[][] memo = new Long[nums.length][nums.length];
return max(nums, 0, nums.length - 1, memo);

}

public static long max(int[] nums, int i, int j, Long[][] memo) {

if (memo[i][j] != null) return memo[i][j];

if (i == j) {
return nums[i];
}

long max = Integer.MIN_VALUE;

for (int k = i; k < j; k++) {

long left = max(nums, i, k, memo);
long right = max(nums, k + 1, j, memo);

for (char c : "*-+".toCharArray()) {
long res = apply(c, left, right);
max = Math.max(max, res);
}
}

memo[i][j] = max;

return max;
}``````

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

``````def find_max_value(numbers)
one_count = 0
two_count = 0
max_val = 1
numbers.each do |number|
next if number == 0
number *= -1 if number < 0
if number == 1
one_count += 1
elsif number == 2
two_count += 1
else
max_val *= number
end
end
if two_count == 0 && one_count == 1
min = numbers.sort[1]
return (max_val/min)*(min+1)
end
get_final_max_value(one_count, two_count, max_val)
end

def get_final_max_value(one_count, two_count, max_val)
if one_count == 0 && two_count == 0
max_val = max_val
elsif one_count == 0
max_val *= 2**two_count
elsif two_count == 0
max_val *= get_max_val_from_ones_count(one_count)
else
if two_count >= one_count
max_val *= (3**one_count)*(2**(two_count-one_count))
else
max_val *= (3**two_count)*get_max_val_from_ones_count(one_count-two_count)
end
end
max_val
end

def get_max_val_from_ones_count(one_count)
quotient, reminder = get_quotient_and_reminder(one_count, 3)
if reminder == 0
3**quotient
elsif reminder == 1
3**(quotient-1)*4
else
3**quotient*2
end
end

def get_quotient_and_reminder(number, dividend)
quotient = number / dividend
reminder = number % dividend
return quotient, reminder
end``````

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

Works for positive and negative numbers.

``````pair<double, double> Extremes(double v1, double v2)
{
double min_val = min(v1 + v2, v1 - v2);
min_val = min(min_val, v1 * v2);
double max_val = max(v1 + v2, v1 - v2);
max_val = max(max_val, v1 * v2);
return pair<double, double>(min_val, max_val);
}

pair<double, double> MinMax(vector<double> const &a, int idx, int size,
map<pair<int, int>, pair<double, double>> &memo)
{
if (size == 0 ||
idx < 0 ||
idx >= a.size())
{
return pair<double, double>(0, 0);
}
if (size == 1) {
return pair<double, double>(a[idx], a[idx]);
}

pair<int, int> key = pair<int, int>(idx, size);
auto it = memo.find(key);
if (it != memo.end()) {
return it->second;
}

double min_v = numeric_limits<double>::max();
double max_v = numeric_limits<double>::lowest();

for (int i = 1; i < size; ++i) {
pair<double, double> left = MinMax(a, idx, i, memo);
pair<double, double> right = MinMax(a, idx + i, size - i, memo);

pair<double, double> p1 = Extremes(left.first, right.first);
pair<double, double> p2 = Extremes(left.first, right.second);
pair<double, double> p3 = Extremes(left.second, right.first);
pair<double, double> p4 = Extremes(left.second, right.second);

min_v = min(min_v, p1.first);
min_v = min(min_v, p2.first);
min_v = min(min_v, p3.first);
min_v = min(min_v, p4.first);
max_v = max(max_v, p1.second);
max_v = max(max_v, p2.second);
max_v = max(max_v, p3.second);
max_v = max(max_v, p4.second);
}

memo[key] = pair<double, double>(min_v, max_v);
return memo[key];
}``````

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

List<double> allPossibleNum = new List<double>();
double[] array = { 5, 4, 3, 1 };
Array.Sort(array);
Array.Reverse(array);
for (int i=array.Length-1;i > -1; i--)
{
double maxMultiNum = 1;
for (int j = 0; j <= i; j++)
{
maxMultiNum *= array[j];
}

for (int j = i+1; j < array.Length; j++)
{
}
}

Console.WriteLine("Maximum produced number is " + allPossibleNum.Max());

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

``````List<double> allPossibleNum = new List<double>();
double[] array = { 5, 4, 3, 1 };
Array.Sort(array);
Array.Reverse(array);
for (int i=array.Length-1;i > -1; i--)
{
double maxMultiNum = 1;
for (int j = 0; j <= i; j++)
{
maxMultiNum *= array[j];
}

for (int j = i+1; j < array.Length; j++)
{
}
}

Console.WriteLine("Maximum produced number is " + allPossibleNum.Max());

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

if you wonder how the dp solutions are built, here the recursion:

``````term(i,j) = max(term(i,k)+term(k,j), term(i,k)*term(k,j)) if j-i > 1, for all k where i<k<j
abs(array[i]), if j-i == 1
result = term(0, len(array))``````

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

MaxOutput(vector<int> arry, int &maxout)
{
if (arry.size() == 1)
{
maxout = max(maxout, arry[0]);
return;
}
for (int i = 0; i < arry.size()-1; i++)
{
int temp;
for (int k = 0; k < 3; k++)
{
switch (k)
{
temp = arry[i] + arry[i + 1];
break;
case 1: //sub
temp = arry[i] - arry[i + 1];
break;
case 2: //mul
temp = arry[i] * arry[i + 1];
}

vector<int> subarry;
for (int j = 0; j < arry.size(); j++)
{
if (i == j)
subarry.push_back(temp);
else if (i + 1 != j)
subarry.push_back(arry[j]);
}
MaxOutput(subarry, maxout);
}
}
}

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

``````MaxOutput(vector<int> arry, int &maxout)
{
if (arry.size() == 1)
{
maxout = max(maxout, arry[0]);
return;
}
for (int i = 0; i < arry.size()-1; i++)
{
int temp;
for (int k = 0; k < 3; k++)
{
switch (k)
{
temp = arry[i] + arry[i + 1];
break;
case 1: //sub
temp = arry[i] - arry[i + 1];
break;
case 2: //mul
temp = arry[i] * arry[i + 1];
}

vector<int> subarry;
for (int j = 0; j < arry.size(); j++)
{
if (i == j)
subarry.push_back(temp);
else if (i + 1 != j)
subarry.push_back(arry[j]);
}
MaxOutput(subarry, maxout);
}
}
}``````

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

``````C++ Code
========
#include <iostream>
#include <algorithm>
using namespace std;

void PrintArray(int *a, int n);

int main(void) {
int n=0, r=0, a[100]={0};

cout << "Enter number of array elements:";
cin >> n;
for(int i=0; i<n; i++ ){
cout << "a[" << i << "]=";
cin >> a[i];
}

sort(a, a+n);
PrintArray(a, n);

for(int i=0; i<n; i++){
if(a[i]==1){
for(int j=0; j<n; j++){
if(a[j]!=0 && i != j){
a[j]+=a[i];
a[i]=0;
break;
}
}
PrintArray(a, n);
}
}

for(int i=0; i<n; i++){
if(a[i]!=0){
r = (r==0)? a[i]:r*a[i];
}
}

cout << "Max=" << r << endl;
return 0;
}

void PrintArray(int *a, int n){
for(int i=0; i<n; i++)
cout << a[i] << " ";
cout << endl;``````

``````Python Code
==========
a = [int(x) for x in input().split()]
print(a)
a.sort()
print(a)

for i in range(0, len(a)):
if a[i] == 1:
for j in range(0, len(a)):
if i != j and a[j] != 0:
a[j] += a[i]
a[i] = 0
break
print(a)

r = 0
for i in a:
if a[i] != 0:
r = a[i] if r == 0 else r*a[i]

print("max=%d", r)

Bug:
if a[i] != 0:
IndexError: list index out of range``````

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

My solution in O(n) only for positive numbers.

``````import java.util.ArrayList;

public class ArrayOfNumbersMax {

public static void main (String[] args) {
int[] a = {1,3,4,5};
System.out.println(max(a));

}

public static int max (int[] a) {

ArrayList<Integer> arr = new ArrayList<Integer> ();

int result = 1;
for (int num : arr) {
result *= num;
}
return result;
}

private static void addNumbersReplaceOnes(int[] a, ArrayList<Integer> arr) {
int numOfOnes = 0;
int min = Integer.MAX_VALUE;
for (int n : a) {

if (n == 1) {
numOfOnes ++;
} else {
if (n < min) {
min = n;
} else {
}
}
}
ArrayList<Integer> temp = new ArrayList<Integer> ();
while (numOfOnes >= 2) {
numOfOnes--;
}
if (numOfOnes == 1) {
if (temp.size() > 0) {
temp.set(0, 3);
} else {
min++;
}
}
}``````

}

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

Does this work for all?

``````public static int max(int[] a)
{
Arrays.sort(a);
int max=a[0];

for(int i=1; i< a.length; i++)
{
max = Math.max(max*a[i], Math.max(max+a[i], max-a[i]));
}
return max;
}``````

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

// Input:
// p : array of integers
// n : number of elements in array
//
// Question:
// use operators {+,-,*} along with () to get the maximum value from the list of integers, assuming they are positive
//
// Solution
// for negative numbers, they are prefixed with (-?) in order to make them positive & increase result. after that, its the same is first solution
// all values of 1 needs to be added to the smallest numbers. as we pick the smallest & add 1, it might no longer be smallest, hence we add the next '1' to the next smallest.
// so in fact, we sort all numbers & then add the '1' values to the smallest numbers. this can be done in loops on array bcz as we add the '1', the values increase & match values that were previously larger.
// logic: if we have K times 5 & K times 1 then the max valule is obviously (1+5)^K - nothing can beat that.
// p.s.: if 0 is a valid input value, it'll need to be added so it wont zero everything.

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <math.h>

int comp_int(const void *_p1, const void *_p2)
{
const int p1 = *((int*)_p1);
const int p2 = *((int*)_p2);
if (p1 < p2)
return -1;
else if (p1 == p2)
return 0;
else
return 1;
}

int max_from_set(int *p, int n)
{
int count_1;
int start_1, start;
int res;
int i;

if (n == 0)
return 0;
#ifdef SUPPORT_NEGATIVE
// convert negative values to positive. this can also be done withn the sorting comparison routine bcz it must compare all values for sorting.
for (i=0; i<n ; i++) {
if (p[i] < 0)
p[i] = -p[i];

}
#endif
// sort all values.
qsort(p, n, sizeof(*p), comp_int);
// skip zeros & count
for (i=0; (i<n) && (p[i] == 0); i++);
if (i == n) {
// only zeroes in input
return 0;
}
start_1 = i;
// counting instances of value '1' & find index of first value > 1.
for (count_1=0; i<n && (p[i] == 1); i++, count_1++);
// compute the max value of 1's (after we dropped 0). so we add the '1' to themselves, to get '2' that will multiply
// go for 2*2*2*2....*2 with optional single '3' incase we have odd number of '1'
if ((count_1 >= 1) && (count_1 <= 3)) {
res = count_1;
} else if (count_1 % 2) {
// even number (>= 5) of '1' - go for 2*2*2...*2 = 2 ^ (count_1/2)
res = 3*pow(2, (count_1-3)/2);
} else {
// odd number (>= 4) of '1' - go for 3*2*2...*2 = 3 * 2 ^ (count_1/2)
res = pow(2, count_1/2);
}
if (i == n) {
// only '1' values
return res;
} else {
// we add into number(s) greater than 1
start = i;
}
// we now have a sorted array with count_1 times the value '1' & p[start] > 1 unless no such value exist (i.e.: i == n)
// for the sorted array : [0,....0,1,...1,(x>1), ....]
// | |
// start_1----/ |
// start ------------/
if (count_1 == 1)
p[start] ++; // add '1' to the smallest value
// multiply all values in range [start .. n)
for (i=start; i<n ; i++) {
res *= p[i];
}
return res;
}

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

O(n) soln. -

``````public static void main(String[] args) {
int[] arr = {1,1,1,5};
int n = max(arr);
System.out.println(n);
}

public static int max(int[] arr){

int n = arr.length;
int[] dp = new int[n];

dp[0] = arr[0];
dp[1] = Math.max(arr[0] + arr[1], arr[0] * arr[1]);
dp[1] = Math.max(dp[1], arr[1] != 0 ? arr[0] / arr[1] : 0);
dp[1] = Math.max(dp[1], arr[0] - arr[1]);

int prev = -1;

for(int i = 2; i < n; i++){
prev = dp[i-2];
dp[i] = Math.max(dp[i-1] + arr[i], dp[i-1] * arr[i]);
dp[i] = Math.max(dp[i], arr[i] != 0? dp[i-1] / arr[i]: 0);
dp[i] = Math.max(dp[i], dp[i-1] - arr[i]);

dp[i] = Math.max(dp[i], prev*(arr[i-1] * arr[i]));
dp[i] = Math.max(dp[i], prev*(arr[i-1] + arr[i]));
dp[i] = Math.max(dp[i], prev*(arr[i] != 0? arr[i-1] / arr[i] : 0));
dp[i] = Math.max(dp[i], prev*(arr[i-1] - arr[i]));

dp[i] = Math.max(dp[i], prev+(arr[i-1] * arr[i]));
dp[i] = Math.max(dp[i], prev+(arr[i-1] + arr[i]));
dp[i] = Math.max(dp[i], prev+(arr[i] != 0? arr[i-1] / arr[i]: 0));
dp[i] = Math.max(dp[i], prev+(arr[i-1] - arr[i]));

dp[i] = Math.max(dp[i], prev-(arr[i-1] * arr[i]));
dp[i] = Math.max(dp[i], prev-(arr[i-1] + arr[i]));
dp[i] = Math.max(dp[i], prev-(arr[i] != 0? arr[i-1] / arr[i]: 0));
dp[i] = Math.max(dp[i], prev-(arr[i-1] - arr[i]));

if(arr[i-1] * arr[i] != 0)
dp[i] = Math.max(dp[i], prev/(arr[i-1] * arr[i]));
if(arr[i-1] + arr[i] != 0)
dp[i] = Math.max(dp[i], prev/(arr[i-1] + arr[i]));
if((arr[i] != 0? arr[i-1] / arr[i]: 0) != 0)
dp[i] = Math.max(dp[i], prev/(arr[i] != 0? arr[i-1] / arr[i]: 0));
if(arr[i-1] - arr[i] != 0)
dp[i] = Math.max(dp[i], prev/(arr[i-1] - arr[i]));
}
return dp[n-1];
}``````

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

in Python, though I think there is a bug when the first number is a negative.

``````def get_arithmetics(v1, v2):
return [
v1 * v2,
v1 + v2,
v1 - v2,
v1 % v2,
]

def get_max(input):
totals = [1, input[0]]

for index, num in enumerate(input[1:]):
index = index+1
rhs = max(get_arithmetics(input[index-1], num))
max_potentials = [max(get_arithmetics(totals[index], num))]
max_potentials.append(totals[index-1] * rhs)

if (len(totals)>2):
max_potentials += get_arithmetics(totals[index-1], rhs)
totals.append(max(max_potentials))

assert get_max([3, 4, 5, 1]) == 72, "[3, 4, 5, 1] == 72"
assert get_max([1, 1, 1, 5]) == 15, "[1, 1, 1, 5] == 15"
assert get_max([8, 5, -1]) == 48, "8, 5, -1] == 48"``````

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

``````def get_arithmetics(v1, v2):
return [
v1 * v2,
v1 + v2,
v1 - v2,
v1 % v2,
]

def get_max(input):
totals = [1, input[0]]

for index, num in enumerate(input[1:]):
index = index+1
rhs = max(get_arithmetics(input[index-1], num))
max_potentials = [max(get_arithmetics(totals[index], num))]
max_potentials.append(totals[index-1] * rhs)

if (len(totals)>2):
max_potentials += get_arithmetics(totals[index-1], rhs)
totals.append(max(max_potentials))

assert get_max([3, 4, 5, 1]) == 72, "[3, 4, 5, 1] == 72"
assert get_max([1, 1, 1, 5]) == 15, "[1, 1, 1, 5] == 15"
assert get_max([8, 5, -1]) == 48, "8, 5, -1] == 48"``````

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

``````public static void main(String args[]) throws Exception {
int arr[] = { 1, 1, 1, 5 };
System.out.println(maxValue(arr));
}

public static int maxValue(int arr[]) {
int matr[][] = new int[arr.length][arr.length];
for (int index = 0; index < arr.length; index++)
matr[index][index] = arr[index];
for (int len = 2; len <= arr.length; len++) {
for (int i = 0; i < arr.length - len + 1; i++) {
int j = i + len - 1;
for (int k = i + 1; k <= j; k++) {
matr[i][j] = max(matr[i][j], matr[i][k - 1] + matr[k][j], matr[i][k - 1] - matr[k][j], matr[i][k - 1] * matr[k][j]);
}
}
}
return matr[0][arr.length - 1];
}

public static int max(int... arr) {
return Arrays.stream(arr).max().getAsInt();
}``````

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

72 for first Ex. is not Max.
See this (1+3)*4*5=80

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

easy solution

``````package com.indus.training.persist.impl;

import java.util.Arrays;

public class MaxArray {

public static void main(String[] args) {
max mObj = new max();
int[] a = { 1, 3,5,1,1};
System.out.println(mObj.maxval(a));

}

}

class max {
public int maxval(int[] ex) {
int j = 0;

for (int i = 0; i < ex.length; i++) {
if (ex[i] == 1) {
j++;
}

}
if (j == 1) {
Arrays.sort(ex);
int[] mex = Arrays.copyOfRange(ex, 1, ex.length);
mex[0] = mex[0] + 1;
int m = 1;
for (int k = 0; k < mex.length; k++) {
m = m * mex[k];
}
return m;

} else {
Arrays.sort(ex);
int[] nEx = Arrays.copyOfRange(ex, j, ex.length);
int m = 1;
for (int k = 0; k < nEx.length; k++) {
m = m * nEx[k];
}
m = m * j;
return m;
}

}
}``````

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

``````int max(int t[])
{
int max = 0;
int tmp = 0;
sort(t);
for(int i=0;i<len;i++) {
for(int j=0;j<=i;j++)
tmp+=t[j]
for(int j=i+1;j<len;j++)
tmp=tmp*t[j];
if (tmp > max)
max = tmp;
}
return max;
}``````

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

Following code works for positive and negative numbers in O(n) time.

``````public static long getMaxValue(int[] nums) {
int length = nums.length;
long leftVal = nums[0];
long rightVal = nums[length - 1];

for (int leftIndex = 1, rightIndex = length - 2; leftIndex < length; leftIndex++, rightIndex--) {
long left = leftVal * nums[leftIndex];
if (!(Math.max(left, leftVal + nums[leftIndex]) == left)) {
left = leftVal + nums[leftIndex];
}
if (!(Math.max(left, leftVal - nums[leftIndex]) == left)) {
left = leftVal - nums[leftIndex];
}
leftVal = left;

long right = rightVal * nums[rightIndex];
if (!(Math.max(right, rightVal + nums[rightIndex]) == right)) {
right = rightVal + nums[rightIndex];
}
if (!(Math.max(right, rightVal - nums[rightIndex]) == right)) {
right = rightVal - nums[rightIndex];
}
rightVal = right;
}

return Math.max(leftVal, rightVal);
}``````

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

public static long maxOutput(int[] in, int start, int end)
{
if(end < start || end >= in.length)
{
return Long.MIN_VALUE;
}

if(end == start)
{
return in[end];
}

long result = Long.MIN_VALUE;

for(int i = start; i < end; i++)
{
long left = maxOutput(in, start, i);
long right = maxOutput(in, i+1, end);
long mul = left * right;
long add = left + right;
long sub = left - right;

result = Math.max(result, Math.max(mul, Math.max(add, sub)));
}
return result;
}

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

public static long maxOutput(int[] in, int start, int end)
{
if(end < start || end >= in.length)
{
return Long.MIN_VALUE;
}

if(end == start)
{
return in[end];
}

long result = Long.MIN_VALUE;

for(int i = start; i < end; i++)
{
long left = maxOutput(in, start, i);
long right = maxOutput(in, i+1, end);
long mul = left * right;
long add = left + right;
long sub = left - right;

result = Math.max(result, Math.max(mul, Math.max(add, sub)));
}
return result;
}

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.

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