Interview Question
Country: United States
Interview Type: In-Person
def maximize(seq):
if len(seq) == 1:
return seq[0]
elif len(seq) == 2:
return max((seq[0] * seq[1]), (seq[0] + seq[1]))
n = len(seq)
possibles = []
for i in xrange(n - 1):
plus = seq[i] + seq[i + 1]
mult = seq[i] * seq[i + 1]
cand1 = seq[:i] + [plus] + seq[i+2:]
cand2 = seq[:i] + [mult] + seq[i+2:]
possibles.append(maximize(cand1))
possibles.append(maximize(cand2))
return max(possibles)
Solution is pretty simple:
#assuming an array of positive numbers
array = [1,1,2,1,1,1,2,2,3,4]
#1. parse through the array and remove all '1's
#2. find the minimum number in the array apart from 1
#3. multiply the remaining numbers
numberOfOnes = 0
minimumOfArray = 0
count = 0
for each in array:
if count==0 and not each==1:
minimumOfArray = each
count = count + 1
if each == 1:
numberOfOnes = numberOfOnes + 1
elif not each == 1 and each < minimumOfArray:
minimumOfArray = each
#we now have the number of ones and
#the smallest number other than 1 from array
print(numberOfOnes)
print(minimumOfArray)
#maxOutput has the product of numbers in array
#with or without considering 1s, the product will be the same
maxOutput = 1
for each in array:
maxOutput = maxOutput * each
#now we need to find how to maximise the output using 1s
#say we have five 1s in the array i.e., 1+1+1+1+1 = 5;
#max output of ones can be obtained by always adding them to 2s and if there
#is 1 remaining, then add that one to one of the 2s we got from summing 1s.
#so here we get : (1+1)*(1+1+1)
#the maximum output from 1s can be obtained as follows
maxOutputFromOnes = 1
if numberOfOnes%2 == 0:
#2**3 implies 2 cubed i.e., 2*2*2
maxOutputFromOnes = 2**int(numberOfOnes/2)
elif numberOfOnes%2 == 1:
maxOutputFromOnes = (2**(int(numberOfOnes/2)-1))*(2+1)
print(maxOutputFromOnes)
#now multiply output of product of arrays and maxoutputfromones
print(maxOutput*maxOutputFromOnes)
int Maximize(IList<int> numbers)
{
if (numbers.Count == 1) return numbers[0];
if(numbers.Count == 2)
{
var add = numbers[0] + numbers[1];
var mul = numbers[0] * numbers[1];
if (add > null) return add;
return mul ;
}
var possibles = new List<int>();
int i;
for(i = 0; i< numbers.Count ; i = i+2)
{
if (i + 1 < numbers.Count)
{
var plus = numbers[i] + numbers[i + 1];
var mul = numbers[i]*numbers[i + 1];
possibles.Add(plus > mul ? plus : mul);
}
else possibles.Add(numbers[i]);
}
return Maximize(possibles);
}
}
Please tell me how to improve this code..
import java.util.*;
public class DPDemos
{
public static void main(String rags[])
{
System.out.println("Enter the choice");
System.out.println("1. For maxminising the by adding * or + ");
Scanner sc=new Scanner(System.in);
int choice = sc.nextInt();
switch(choice)
{
case 1 : System.out.println(max());
break;
}
}
public static int max()
{
int[] a=ipt1DArray();
int m=a[0];
int count=0;
for(int i=0;i<a.length;i++)
{
if(a[i]==1)
count++;
}
System.out.println(count);
int[] ones=new int[count];
int onesidx=0;
print(a);
for(int i=1;i<a.length;i++)
{
if(a[i]!=1)
a[i]=a[i-1]*a[i];
else
{
ones[onesidx]=i;
onesidx++;
}
}
print(ones);
print(a);
for(int i=0;i<ones.length-1;i++)
{
int o=a[ones[i]-1];
int n=a[ones[i+1]-1];
if((o+1)*n > o*(n+1))
{
a[ones[i+1]-1]=(o+1)*n;
}
else
a[ones[i+1]-1]=o*(n+1);
}
int i=ones[ones.length-1];
int p=a[i-1];
int q=a[a.length-1];
if((p+1)*q > p*(q+1))
a[a.length-1]=(p+1)*q;
else
a[a.length-1]= p*(q+1);
print(a);
return a[a.length-1];
}
public static void print(int[] a)
{
for(int i=0;i<a.length;i++)
System.out.print(a[i]+" ");
System.out.println();
}
public static int[] ipt1DArray()
{
System.out.println("Enter the no of elements");
Scanner sc1=new Scanner(System.in);
int m=sc1.nextInt();
int[] a=new int[m];
System.out.println("Enter elements");
for(int i=0;i<m;i++)
{
Scanner s=new Scanner(System.in);
a[i]=s.nextInt();
}
return a;
}
}
Solution in Java:
package com.learn;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
public class FindMaximumResult {
/**
* @param args
*/
public static void main(String[] args) {
System.out.println("Enter the no of elements");
Scanner sc1 = new Scanner(System.in);
int m = sc1.nextInt();
int[] initArray = new int[m];
System.out.println("Enter elements");
for (int i = 0; i < m; i++) {
Scanner s = new Scanner(System.in);
initArray[i] = s.nextInt();
}
List<Integer> digitList = new ArrayList<Integer>(initArray.length);
for (int digit : initArray) {
digitList.add(digit);
}
System.out.println("FindMaximumResult.main()- " + maxValue(digitList));
}
private static int maxValue(List<Integer> digitList) {
/*System.out.println("Intial List size in FindMaximumResult.maxValue()- "
+ digitList.size() + " List- " + digitList);*/
List<Integer> onesList = new ArrayList<Integer>();
List<Integer> moreThanTwoList = new ArrayList<Integer>();
for (int i = 0; i < digitList.size(); i++) {
if (digitList.get(i) == 1) {
onesList.add(digitList.get(i));
} else if (digitList.get(i) > 1) {
moreThanTwoList.add(digitList.get(i));
}
}
Collections.sort(moreThanTwoList);
/*System.out.println("Final List size in FindMaximumResult.maxValue()- "
+ moreThanTwoList.size() + " List- " + moreThanTwoList);*/
// System.out.println("FindMaximumResult.maxValue()- " + onesList);
for (Integer oneDigit : onesList) {
moreThanTwoList.set(0, moreThanTwoList.get(0) + oneDigit);
Collections.sort(moreThanTwoList);
}
int maxResult = 1;
for (Integer digit : moreThanTwoList) {
maxResult = maxResult * digit;
}
return maxResult;
}
}
static void Main(string[] args)
{
int[] a ={2,1,1,2};
Console.WriteLine(GetMax(a,0,a.Length-1));
Console.ReadLine();
}
static int GetMax(int[] a, int start, int end)
{
if (start == end)
{
return a[start];
}
int maxVlaue = 0;
for (int i = start; i < end; i++)
{
int l1 = GetMax(a, start, i);
int l2 = GetMax(a, i + 1, end);
maxVlaue = Math.Max(maxVlaue, Math.Max(l1 + l2, l1 * l2));
}
return maxVlaue;
}
static void Main(string[] args)
{
int[] a ={2,1,1,2};
Console.WriteLine(GetMax(a,0,a.Length-1));
Console.ReadLine();
}
static int GetMax(int[] a, int start, int end)
{
if (start == end)
{
return a[start];
}
int maxVlaue = 0;
for (int i = start; i < end; i++)
{
int l1 = GetMax(a, start, i);
int l2 = GetMax(a, i + 1, end);
maxVlaue = Math.Max(maxVlaue, Math.Max(l1 + l2, l1 * l2));
}
return maxVlaue;
}
static void Main(string[] args)
{
int[] a ={2,1,1,2};
Console.WriteLine(GetMax(a,0,a.Length-1));
Console.ReadLine();
}
static int GetMax(int[] a, int start, int end)
{
if (start == end)
{
return a[start];
}
int maxVlaue = 0;
for (int i = start; i < end; i++)
{
int l1 = GetMax(a, start, i);
int l2 = GetMax(a, i + 1, end);
maxVlaue = Math.Max(maxVlaue, Math.Max(l1 + l2, l1 * l2));
}
return maxVlaue;
}
static void Main(string[] args)
{
int[] a ={2,1,1,2};
Console.WriteLine(GetMax(a,0,a.Length-1));
Console.ReadLine();
}
static int GetMax(int[] a, int start, int end)
{
if (start == end)
{
return a[start];
}
int maxVlaue = 0;
for (int i = start; i < end; i++)
{
int l1 = GetMax(a, start, i);
int l2 = GetMax(a, i + 1, end);
maxVlaue = Math.Max(maxVlaue, Math.Max(l1 + l2, l1 * l2));
}
return maxVlaue;
}
static void Main(string[] args)
{
int[] a ={2,1,1,2};
Console.WriteLine(GetMax(a,0,a.Length-1));
Console.ReadLine();
}
static int GetMax(int[] a, int start, int end)
{
if (start == end)
{
return a[start];
}
int maxVlaue = 0;
for (int i = start; i < end; i++)
{
int l1 = GetMax(a, start, i);
int l2 = GetMax(a, i + 1, end);
maxVlaue = Math.Max(maxVlaue, Math.Max(l1 + l2, l1 * l2));
}
return maxVlaue;
}
I think the two special cases are zero and 1. Of course, if they are missing from the list, then it is just a straight multiplication of all the numbers.
Usually expressions are implemented using tree & stack, depending on what you need to do. Push & pop values & expressions onto the stack to build up the final string. It seems the final expression string, more so than the max value, was the point of the question...?
Gonna tune this up, switch it to iterative version.
int maxout(vector<int> input, int first, int last)
{
if (last <= first)
return 0;
vector<int> values(6,0);
values[0] = (input[first] + input[first+1]) + maxout(input, first+2, last);
values[1] = (input[first] + input[first+1]) * maxout(input, first+2, last);
values[2] = (input[first] * input[first+1]) + maxout(input, first+2, last);
values[3] = (input[first] * input[first+1]) * maxout(input, first+2, last);
values[4] = input[first] + maxout(input, first+1, last);
values[5] = input[first] * maxout(input, first+1, last);
vector<int>::iterator best = max_element(values.begin(), values.end());
return *best;
}
class Program
{
static int max;
static string strMax;
// this will find the maximum result and print the string with parenthesis
static void Main(string[] args)
{
max = 0;
int[] vals = { 2, 1, 1, 2 };
int nops = vals.Length - 1;
// ops will contain 0 for mult, 1 for add
int[] ops = new int[nops];
// 3 operators will result in 2^3 possible combinations
long count = (long)Math.Pow(2, nops);
// loop through all possible combinations using binary math
for (long i = 0; i < count; i++)
{
// loop through each operator, to see if should be mult or add
for (int j = 0; j < nops; j++)
{
// use binary AND to set the operator at each location
long flag = (long)Math.Pow(2, j);
ops[j] = ((flag & i) == flag) ? 1 : 0;
}
CalcTerms(vals, ops);
}
Console.WriteLine("************");
Console.WriteLine("max={0}, str = {1}", max, strMax);
Console.ReadKey();
}
static void CalcTerms(int[] vals, int[] ops)
{
StringBuilder sb = new StringBuilder();
Stack<int> stackProd = new Stack<int>();
int nops = ops.Length, index = 0;
bool bLastTermSummed = false;
while (index < nops)
{
// if current term is mult
if (ops[index] == 0)
{
if (bLastTermSummed == false)
{
stackProd.Push(vals[index]);
sb.Append(vals[index]);
}
sb.Append("*");
bLastTermSummed = false;
index++;
}
else
{
// current term is addition
var sum = GetSum(ref index, vals, ops, sb);
stackProd.Push(sum);
bLastTermSummed = true;
}
}
if (bLastTermSummed == false)
{
stackProd.Push(vals[index]);
sb.Append(vals[index]);
}
// calc the prod stack
int prod = 1;
while (stackProd.Count > 0)
{
prod *= stackProd.Pop();
}
Console.Write(sb.ToString());
Console.Write(" ");
Console.WriteLine(prod);
// save the max
if (prod > max)
{
max = prod;
strMax = sb.ToString();
}
}
static int GetSum(ref int index, int[] vals, int[] ops, StringBuilder sb)
{
int sum = 0, nops = ops.Length;
sb.Append("(");
while (index < nops && ops[index] == 1)
{
sum += vals[index];
sb.Append(vals[index]);
sb.Append("+");
index++;
}
// get last number
sum += vals[index];
sb.Append(vals[index]);
sb.Append(")");
return sum;
}
}
// produces the following output
2*1*1*2 4
(2+1)*1*2 6
2*(1+1)*2 8
(2+1+1)*2 8
2*1*(1+2) 6
(2+1)*(1+2) 9
2*(1+1+2) 8
(2+1+1+2) 6
************
max=9, str = (2+1)*(1+2)
Decision tree again. The key is to generate the right options.
def maxComb(nums):
total = len(nums)
largest = 0
solution = ''
options = [{'sofar':[], 'remain':[x for x in reversed(nums)], 'opening':0}]
while len(options):
option = options.pop()
sofar = option['sofar']
remain = option['remain']
used = total - len(remain)
opening = option['opening']
if len(remain):
prefixes = [ '' ]
if used:
prefixes = ['+','*']
for prefix in prefixes:
for toopen in range(0, total-used-opening):
options.append({
'sofar': sofar[:] + [prefix, '('*toopen, str(remain[-1])],
'remain': remain[:-1],
'opening': opening + toopen
})
for toclose in range(max(0, opening-(total-used)+1), min(opening, used)+1):
options.append({
'sofar': sofar[:] + [prefix, str(remain[-1]), ')'*toclose],
'remain': remain[:-1],
'opening': opening - toclose
})
else:
current=''.join(sofar)
val = eval(current)
if val > largest:
largest = val
solution = current
return largest, solution
print maxComb([2,1,1,2])
print maxComb([2,1,1,2,3,4,5])
Fixed for negative numbers
def maxComb(nums):
total = len(nums)
largest = 0
solution = ''
options = [{'sofar':[], 'remain':[x for x in reversed(nums)], 'opening':0}]
while len(options):
option = options.pop()
sofar = option['sofar']
remain = option['remain']
used = total - len(remain)
opening = option['opening']
if len(remain):
prefixes = [ '' ]
if used:
prefixes = ['+','*']
for prefix in prefixes:
nextNum = remain[-1]
if (nextNum >= 0):
nextNum = str(nextNum)
else:
nextNum = "(" + str(nextNum) + ")"
for toopen in range(0, total-used-opening):
options.append({
'sofar': sofar[:] + [prefix, '('*toopen, nextNum],
'remain': remain[:-1],
'opening': opening + toopen
})
for toclose in range(max(0, opening-(total-used)+1), min(opening, used)+1):
options.append({
'sofar': sofar[:] + [prefix, nextNum, ')'*toclose],
'remain': remain[:-1],
'opening': opening - toclose
})
else:
current=''.join(sofar)
val = eval(current)
if val > largest:
largest = val
solution = current
return largest, solution
print maxComb([2,1,1,2])
print maxComb([2,1,1,2,3,4,5])
print maxComb([-1, -2, -3])
Result
(9, '(2+1)*(1+2)')
(540, '((((2+1)*(1+2)))*3)*4*5')
(9, '(((-1)+(-2))*(-3))')
The problem is just a variation of Matrix Chain Multiplication Dynamic Programming.Here is a working code working on all given test cases.
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <climits>
#include <queue>
#include <algorithm>
#include <cassert>
#define INF INT_MAX
#define NIL -1
#define PR(A) cout<<endl<<#A<<" = "<<A;
#define INF INT_MAX
using namespace std;
typedef vector<vector<int>> matrix;
typedef vector<int> arr;
typedef unsigned int ui;
vector<vector<int>> & make_matrix(int m,int n,int r=0){
vector<vector<int>>&q=*(new vector<vector<int>>);
q.resize(m);
for(auto &i:q){
i.resize(n);
fill(i.begin(),i.end(),r);
}//edn fr
return q;
}//end vector
void printarr(arr &a,int low=0,int high=INT_MAX){
if(high==INT_MAX){
high=a.size()-1;
}//END IF
cout<<endl;
for(int i=low;i<=high;i++){
cout<<a[i]<<' ';
}//end for
}//end [rint
void printmatrix(matrix &a){
for(auto i:a){
cout<<endl;
for(auto j:i){
cout<<j<<" ";
}//end fo
}//end for
}//end [rint
int solve(vector<int>&a){
matrix dp=make_matrix(a.size(),a.size(),INT_MIN);
for(int i=0;i<a.size();i++){
dp[i][i]=a[i];
}//end for
for(int i=0;i<a.size()-1;i++){
dp[i][i+1]=max(a[i]*a[i+1],a[i]+a[i-1]);
}//end for
for(int len=3;len<=a.size();len++){
for(int i=0;i<=a.size()-len;i++){
int j=i+len-1;
for(int k=i;k<j;k++){
dp[i][j]=max(dp[i][j],max(dp[i][k]+dp[k+1][j],dp[i][k]*dp[k+1][j]));
}//end for
}//end for
}//end for
return dp[0][a.size()-1];
}//end solve
int main(){
vector<int>a{-1,-2,-3};
cout<<endl<<solve(a);
return 0;
}
Since position is fixed and both + and * are binary operators, this is a tournament style maximisation. Visualise the problem as a binary tree where the leaves are the values (and they're all a the same depth). For each parent of these leaves you just need to make the decision should I combine them with the + or the * and store the arithmetic result at that node? Then for the parents of them do the same, and recurse that to the root. This method takes O(n^2) operations. Caveat: if the array is of odd length, there are 2 ways to build the tree
Should you please show the details? I cannot image that how does it goes with O(n^2). For example, for leaves "2, 1, 2", you have to see whether the mid 1 should combine the left or right 2 to construct the parent node.
Dear Mr. Gamble
I shall be highly obliged if you could explain the details of the solution... Kindly reply
This for sure should not take O(n^2).
You can tell what you need in an item at that specific item. There is just a few extra edge cases. Runtime O(n). Algo should go like this.
For all numbers:
- check if the number is "1" if not, always use multiply.
- if number is "1", our goal is to minimize a sum >= 3. So check previous and next items.
- If no ones, pick the smallest of the two, to put in brackets and add.
- If there is a one in next, go to next->next.
- If next->next still a one, put the 3 in brackets (you have your golden 3 ideal). and move your pointer.
- Otherwise check for twos. If on both sides of both ones there are twos, then and only then your wanna seperate the ones with the twos. (as the example above). Otherwise, couple the two ones together and move the pointer.
For negative.
- Do same as above, while keeping track of number of negatives. (note negatives will be treated as non-ones! Keep track of the smallest negative number position.
- If number of negatives is even, do nothing.
- If number of negatives is odd, get the smallest negative number and change its signs from multiply to addition on the side for which the first sum > 0, is smaller.
- For 0 remember you have to always add on both sides, no matter what.
Solution in C#
public static int MaxResult(List<int> listOfNumbers)
{
int countOfList = listOfNumbers.Count;
int valueOfReturn = 1;
int previousNumber = 1;
for (int i = 0; i < countOfList; i++)
{
if (listOfNumbers.Max()>1)
{
valueOfReturn *= listOfNumbers.Max();
}
else if(listOfNumbers.Max()<=1 && i%2==0)
{
valueOfReturn *= Convert.ToInt32(Math.Pow(2, (countOfList - i) / 2));
break;
}
else
{
valueOfReturn /= previousNumber;
valueOfReturn *= (previousNumber + 1) * Convert.ToInt32(Math.Pow(2, (countOfList - i ) / 2));
break;
}
previousNumber = listOfNumbers.Max();
listOfNumbers.Remove(listOfNumbers.Max());
}
return valueOfReturn;
}
we need to Identify biggest numbers and associate the next number with Multiply opertion to maximze the result. Very simple.
Example in 2112 , 2 is the biggest number . Assosiate 2 with Multiply operator with the next closest value 1. so (2*1) + (1*2) .
- use DP O(n^3) time complexity August 20, 2014