Interview Question

Country: United States
Interview Type: In-Person

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

``````def FindMaxOperation(numbers):
le = len(numbers)
DynTab = [[0 for i in xrange(le)] for j in xrange(le)]
for i in xrange(le):
DynTab[i][i] = numbers[i]
for j in xrange(i-1, -1, -1):
diff = i - j
tmpmax = 0
for k in xrange(diff):
tmpmax = max(tmpmax, DynTab[i][i-k]+DynTab[i-k-1][j], DynTab[i][i-k]*DynTab[i-k-1][j])
DynTab[i][j] = tmpmax
print DynTab[-1][0]``````

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

It doesn't consider negative numbers.

-1,-2,-3 should give (-1-2)*(-3) = 9. This algorithm gives 5 instead.

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

``````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)``````

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

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)``````

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

Your way even can not pass the example given.
2,1,1,2 should get max = 9.

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

what about zero? The idea is to print the operations, not obtain the result.

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

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];
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);
}
}

return Maximize(possibles);
}
}

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

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;
}

}``````

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

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) {

}

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) {
} else if (digitList.get(i) > 1) {
}
}

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;
}
}``````

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

you are not allowed to change positions of elements in ur solution

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

``````static void Main(string[] args)
{
int[] a ={2,1,1,2};
Console.WriteLine(GetMax(a,0,a.Length-1));
}
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;

}``````

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

static void Main(string[] args)
{
int[] a ={2,1,1,2};
Console.WriteLine(GetMax(a,0,a.Length-1));
}
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;

}

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

``````static void Main(string[] args)
{
int[] a ={2,1,1,2};
Console.WriteLine(GetMax(a,0,a.Length-1));
}
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;

}``````

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

``````static void Main(string[] args)
{
int[] a ={2,1,1,2};
Console.WriteLine(GetMax(a,0,a.Length-1));
}
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;

}``````

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

static void Main(string[] args)
{
int[] a ={2,1,1,2};
Console.WriteLine(GetMax(a,0,a.Length-1));
}
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;

}

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

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

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

I guess the way the question is worded, that zero would not be a valid input....since zero is not positive.

Seems that overflow could come into play....?

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

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;
}``````

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

fails on 1,1,1,5

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

``````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);
}

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
{
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)``````

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

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])``````

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

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))')``````

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

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;
}``````

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

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

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

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.

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

Dear Mr. Gamble

I shall be highly obliged if you could explain the details of the solution... Kindly reply

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

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.

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

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;
}``````

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

I realize it does not provide some cases.
Sorry.

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

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

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

Replace Add operator in place of multiply.

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

(2*1) * (1*2) = 4 < (2+1)*(2+1) = 9

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.