Adobe Interview Question
Computer ScientistsCountry: United States
I think this fails on: 2 1 1 1 1 2.
you want to group the ones with their neighbor, /as evenly as possible/: (2+1+1) * (1+1+2) = 16;
(2 + 4) * 2 = 12
2 1 1 1 1 1 1 1 1 2
4 * 2 * 2 * 4 = 64
8 * 8 = 64.
2 * 2 * 2 * 2 * 2 * 2 = 64. Hum; so far this seems to hold up.
2 1 1 1 2 = 12
3 4 = 12 -- k, really seems to hold up.
edit: also, '(' and ')' are free - they don't take up a space between numbers. They couldn't - what would eg 1(2) mean?
Hi JeffD,
(i) For example 2 1 1 1 1 2 the algorithm will work as follows:
2 1 1 1 1 2
2 (1+1) (1+1) 2
2*2*2*2 = 16
However we can do better:
2 1 1 1 1 2
(2+1) 1 1 ( 1+2)
(2+1) (1+1) (1+2)
3*2*3 = 18
Hence you are right Jeff, the algorithm is NOT correct.
(ii) In sake of braces, you never get something like 1(2) since the while loop inserts '*'.
So the question is, how to fix the algorithm and is it feasible to slove this task in O(N) linear time?
Dynamic Programming:
Let's call the array of numbers, num
dp[i,j] = maximum value we could get from numbers num[i] to num[j]
base case: dp[i,i] = num[i]
dp[i,j] = max (dp[i,k]*dp[k+1,j] , dp[i,k]+dp[k+1,j] ) for all i<=k<j
and the final answer is dp[0,N-1]
Time Complexity O(N^3)
Hey why are you using the dp[i,k]-dp[k+1,j] ?? I am missing something? Is only multiply and sum
Brackets will be inserted at the position of k which gives max in
dp[i,j] = max (dp[i,k]*dp[k+1,j] , dp[i,k]+dp[k+1,j] ) for all i<=k<j
.
To reconstruct the expression, we can use another table (dp_op) which will store operation and value of k. Expression will be constructed working backward from dp_op[0,N-1].
Brackets will be inserted at the position of k which gives max in
dp[i,j] = max (dp[i,k]*dp[k+1,j] , dp[i,k]+dp[k+1,j] ) for all i<=k<j
.
To reconstruct the expression we can use another table(dp_op), which will store operation and value of k. Reconstruction can be done working backward from dp_op[0,N-1].
Dynamic programming
dpmn[i][j] is minimum value of [i,j] interval.
dpmx[i][j] is maximum value of [i,j] interval.
How to find dpmn[i][j], dpmx[i][j] these value.
given integers a[1],a[2],...,a[n]
for(int i=1; i<=n; i++)
{
dpm[i][i]=dpmx[i][i]=a[i];
for(int j=i-1; j>0; j--)
{
for(int k=j+1; k<i; k++)
{
dpmx[j][i] = max(dpmx[i][j], dpmn[j][k]*dpmn[k+1][i]);
dpmx[j][i] = max(dpmx[i][j], dpmx[j][k]*dpmn[k+1][i]);
dpmx[j][i] = max(dpmx[i][j], dpmn[j][k]*dpmx[k+1][i]);
dpmx[j][i] = max(dpmx[i][j], dpmx[j][k]*dpmx[k+1][i]);
...
etc
}
}
}
answer dp[1][n]
Solution is O(N^3)
value of expression will be maximum when multiplying. Special case will be value 1 where we need to first make it plus with max of +1 or -1 index value (which ever is maximum). Simple use of auxilary DS and one iteration of array will do it. special check will be if i+1 ==1 then get max of i and i+2 and put a plus between i+1 and max value index in () else keep using * between values
Solution O(n)
int[] arr={1,1,1,1,1};
char[] aux=new char[20];
int i=0;
int j=0;
for(;i<arr.length-1;i++){
if(arr[i]+arr[i+1]>arr[i]*arr[i+1]){
aux[j++]='(';
aux[j++]=Character.forDigit(arr[i],10);
aux[j++]='+';
aux[j++]=Character.forDigit(arr[++i],10);
if(i==arr.length-2 && arr[arr.length-1]==1 && arr.length>2){
aux[j++]='+';
aux[j++]=Character.forDigit(arr[++i],10);
}
aux[j++]=')';
}else{
aux[j++]=Character.forDigit(arr[i],10);
aux[j++]='*';
if(i==arr.length-2 && arr[arr.length-1]==1 && arr.length>2){
aux[j++]='(';
aux[j++]=Character.forDigit(arr[++i],10);
aux[j++]='+';
aux[j++]=Character.forDigit(arr[++i],10);
aux[j++]=')';
}else
aux[j++]=Character.forDigit(arr[++i],10);
}
if(i<arr.length-1)
aux[j++]='*';
}
if(i==arr.length-1){
aux[j++]=Character.forDigit(arr[i],10);
System.out.println("One Left");
}
for(i=0;i<j;i++){
System.out.print(aux[i]);
}
I haven't work it out yet, but got some idea. Hope someone could help me move forward from this point.
Observation1: for any two integers grater than one, their product is no smaller than their summation. And the product is equal to the summation iff the two integers are both two.
Observation2: for any positive integer X, (X+1)>X*1
Hence in the sequence, for any two consecutive non-one integers, * should be inserted rather than +.
Allowing sorting makes the maximum different (and easier): (1,3,1) vs (1,1,3). We assume that the original order should be kept.
So + and () are only involved when 1 appears.
For the case a,b,1,c,d, where a,b,c,d are greater than one, we should add 1 with min(b,c).
For the case ..,1,a,1,b,1,c,.. what shall we do?
For sequence 1,1,...,1,1, we know from arithmetic that splitting them equally could get maximum product. Assume we partition them into k groups, we'd like to maximize function (n/k)^k, calculus suggests that k=n/e achieves maximum. So we only need to try k=ceil(n/e) and k=floor(n/e). Eg. for [1]*10, n=10, k=3,4. for k=3, we have (3*3*4=36); for k=4, we have (2*2*3*3=36);
For sequence ..,a,1,1,...,1,1,b,.. what shall we do?
Multiplying is always better than adding, except in the case of 1's. In any string of consecutive ones, they should be paired up into *(1+1), except that if there is an odd numbers of 1's, then the last should be grouped in with the previous two as *(1+1+1). If there is just a single 1, then it should be added in with its smaller neighbor, so that ...2,1,3... would become *(2+1)*3
#include<bits/stdc++.h>
using namespace std;
int Multiply(int p[], int n)
{
int m[n][n];
int i, j, k, L;
for (i = 0; i < n; i++)
m[i][i] = p[i];
for (L=2; L<=n; L++)
{
for (i=0; i<n-L+1; i++)
{
j = i+L-1;
m[i][j] = INT_MIN;
for (k=i; k<=j-1; k++)
{
m[i][j] = max(m[i][j],max(m[i][k]*m[k+1][j], m[i][k] + m[k+1][j]));
}
}
}
return m[0][n-1];
}
int main()
{
int arr[] = {2, 1, 1,1,1,2};
int size = sizeof(arr)/sizeof(arr[0]);
printf("Maximum is %d ",
Multiply(arr, size));
getchar();
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int Multiply(int p[], int n)
{
int m[n][n];
int i, j, k, L;
for (i = 0; i < n; i++)
m[i][i] = p[i];
for (L=2; L<=n; L++)
{
for (i=0; i<n-L+1; i++)
{
j = i+L-1;
m[i][j] = INT_MIN;
for (k=i; k<=j-1; k++)
{
m[i][j] = max(m[i][j],max(m[i][k]*m[k+1][j], m[i][k] + m[k+1][j]));
}
}
}
return m[0][n-1];
}
int main()
{
int arr[] = {2, 1, 1,1,1,2};
int size = sizeof(arr)/sizeof(arr[0]);
printf("Maximum is %d ",
Multiply(arr, size));
getchar();
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int Multiply(int p[], int n)
{
int m[n][n];
int i, j, k, L;
for (i = 0; i < n; i++)
m[i][i] = p[i];
for (L=2; L<=n; L++)
{
for (i=0; i<n-L+1; i++)
{
j = i+L-1;
m[i][j] = INT_MIN;
for (k=i; k<=j-1; k++)
{
m[i][j] = max(m[i][j],max(m[i][k]*m[k+1][j], m[i][k] + m[k+1][j]));
}
}
}
return m[0][n-1];
}
int main()
{
int arr[] = {2, 1, 1,1,1,2};
int size = sizeof(arr)/sizeof(arr[0]);
printf("Maximum is %d ",
Multiply(arr, size));
getchar();
return 0;
}
The problem can be solved recursively or iteratively, there are two problems to solve:
(i) How to reduce the problem to smaller one
(ii) In which order to pick operand couples
(iii) How to chose between multiplication and addition
First, notice that without loss of generlity we can pick any two adjacent numbers, perform desired operation and replace the two numbers with the result, which forms a new reduced problem. For instance, let have a sequence of bumbers "a,b,c,d,e", let pick a couple b,c, hence the new reduced problem is a, x, d, e where x=(b '*' or '+' c).
Second, notice that since interers are positive, the only case when an addition is benefical is only when at least one member of the couple equals '1', otherwise multiplication yields the same or greater result.
Third, notice tha we wont to first get rid of '1' using addition, than it remains only to perform multiplication. If the '1' has two neighbours, it is benefical to sum it with the lower neighbour. To illustrate this consider example below:
Correct: 3,1,2 -> 3*(1+2)=9
Incorrect: 3,1,2->(3+1)*2 = 8
The algorithm sketch may look like this:
What remains is to print the expression to the standart output. The sample code may look like as follows:
Notice that the Node class is a custom doubly linked list datastructure.
- autoboli August 27, 2015