Google Interview Question
SDE-3sCountry: United States
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
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];
}
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];
}
double MaxAddNum = 0;
for (int j = i+1; j < array.Length; j++)
{
MaxAddNum += array[j];
}
allPossibleNum.Add(maxMultiNum * (MaxAddNum>0 ? MaxAddNum : 1));
}
Console.WriteLine("Maximum produced number is " + allPossibleNum.Max());
Console.Read();
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];
}
double MaxAddNum = 0;
for (int j = i+1; j < array.Length; j++)
{
MaxAddNum += array[j];
}
allPossibleNum.Add(maxMultiNum * (MaxAddNum>0 ? MaxAddNum : 1));
}
Console.WriteLine("Maximum produced number is " + allPossibleNum.Max());
Console.Read();
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)
{
case 0: //add
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);
}
}
}
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)
{
case 0: //add
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);
}
}
}
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
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> ();
addNumbersReplaceOnes (a, arr);
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 {
arr.add(n);
}
}
}
ArrayList<Integer> temp = new ArrayList<Integer> ();
while (numOfOnes >= 2) {
temp.add(2);
numOfOnes--;
}
if (numOfOnes == 1) {
if (temp.size() > 0) {
temp.set(0, 3);
} else {
min++;
}
}
arr.add(min);
arr.addAll(temp);
}
}
// 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;
}
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];
}
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))
return totals[-1]
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"
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))
return totals[-1]
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"
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();
}
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;
}
}
}
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);
}
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;
}
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;
}
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?
- talal.nabulsi5 August 27, 2017