## Adobe Interview Question for Computer Scientists

• 2

Country: United States

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

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:

``````1) Reduce problem by geting rid of '1's by addition with lower neighbour
2) Multiply all remaining elements.``````

What remains is to print the expression to the standart output. The sample code may look like as follows:

``````public int findMax(int[] a) {
if (a.length>1) {
System.out.println(a);
return a;
}
Node<Integer> la = new Node<Integer>();
Node<String>   sa = new Node<String>();
for (int k=0; k<a.length; k++) {
}
getRidOfOnes(la, sa);

/* Multiplication - no '1's left */
res = 1;
while(true) {
res *= la.val;
System.out.print(ls.val);
if(!la.isLast()) 	System.out.print("*");
else 			break;
la = la.next;
ls = ls.next;
}
System.out.println();
return res;
}
private void getRidOfOnes(Node<Integer> curra, Node<String> currs) {
while(curra != NULL) {
if(curra.val != 1) {
curra = curra.next;
currs = currs.next;
continue;
}
if (!curra.isFirst() && !curra.isLast()) { 		// has both neighbours
}
else if (curra.isFirst() && !curra.isLast()) 		// has only right neighbour
else if (curra.isLast() && !curra.isFirst()) 		// has only left neighbour
curra = curr.next;
}
}

private void addWithNext(Node<Integer> curra, Node<String> currs) {
curra.val += curr.next.val;
curra.next = curra.next.next;
currs.val += "("+curr.val+"+"+curr.next.val+")";
currs.next = curra.next.next;
}

Notice that the Node class is a custom doubly linked list datastructure.

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

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?

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

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?

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

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)

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

Hey why are you using the dp[i,k]-dp[k+1,j] ?? I am missing something? Is only multiply and sum

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

you don't use '(' or ')' at all.

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

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

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

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

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

Sort the array,and put + for numbers up to 1 and assign to a var.
if the var value <= 1, add the next number in the sorted array to it.
Continue the above step, till the var becomes > 1, then for the remaining numbers put * (multiply)

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

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,a,...,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
}
}
}
Solution is O(N^3)

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

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

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

Solution O(n)

``````int[] arr={1,1,1,1,1};
char[] aux=new char;
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]);
}``````

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

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

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

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

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

#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[n-1];
}

int main()
{
int arr[] = {2, 1, 1,1,1,2};
int size = sizeof(arr)/sizeof(arr);

printf("Maximum is %d ",
Multiply(arr, size));

getchar();
return 0;
}

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

``````#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[n-1];
}

int main()
{
int arr[] = {2, 1, 1,1,1,2};
int size = sizeof(arr)/sizeof(arr);

printf("Maximum is %d ",
Multiply(arr, size));

getchar();
return 0;
}``````

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

{fdfd}

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

#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[n-1];
}

int main()
{
int arr[] = {2, 1, 1,1,1,2};
int size = sizeof(arr)/sizeof(arr);

printf("Maximum is %d ",
Multiply(arr, size));

getchar();
return 0;
}

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.