Adobe Interview Question for Computer Scientists


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[0]);
		return a[0];		
	}
	Node<Integer> la = new Node<Integer>();
	Node<String>   sa = new Node<String>();
	for (int k=0; k<a.length; k++) {
		la.add(a[k]);
		sa.add(""+a[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
			if(curra.prev.val>curra.next.val) 	addWithNext(curra, currs);
			else 							addWithPrev(curra, currs);
		}
		else if (curra.isFirst() && !curra.isLast()) 		// has only right neighbour
			addWithNext(curra, currs)
		else if (curra.isLast() && !curra.isFirst()) 		// has only left neighbour
			addWithPrev()
		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;
}

private void addWithPrev(Node ...) {...}

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

- autoboli August 27, 2015 | Flag Reply
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?

- JeffD August 28, 2015 | Flag
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?

- autoboli August 28, 2015 | Flag
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)

- MehrdadAP August 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Vlad August 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- JeffD August 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Gaurav September 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Gaurav September 08, 2015 | Flag
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)

- Anonymous August 26, 2015 | Flag Reply
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[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)

- adiya.tb August 26, 2015 | Flag Reply
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

- Vinay August 26, 2015 | Flag Reply
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[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]);
		}

- Vinay August 26, 2015 | Flag Reply
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 [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?

- Pyramid August 27, 2015 | Flag Reply
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

- yehadut August 27, 2015 | Flag Reply
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[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;
}

- Ayush October 01, 2015 | Flag Reply
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[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;
}

- Ayush October 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{fdfd}

- Anonymous October 20, 2015 | Flag Reply
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[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;
}

- dddd October 20, 2015 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More