Adobe Interview Question for Developer Program Engineers


Country: India




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

Append all the elements except last one into end of buffer and then apply LIS problem(With Dynamic Programming on it).
For ex-5 4 3 2 1 would be converted to 5 4 3 2 1 5 4 3 2 - LIS would be 1 5
5 6 7 1 2 3 would be converted to 5 6 7 1 2 3 5 6 7 1 2 - LIS would be 1 2 3 5 6 7

- Mitesh September 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

In fact there is no need append the array to the array, all we have to do is find the smallest element, now stretch out the array taking the smallest element as position 0 and going round to come back to the position of the smallest element, now find the LIS on this array, it will be the longest LIS for the circular array

- Praveen August 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I thought of this approach initially and found bug.
try with this example

{10, -3, -4, 7, 6, 5, -4, -1}

- rajdeeps.iitb October 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry try with this

-1, 40, -14, 7, 6, 5, -4, -1

- rajdeeps.iitb October 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Do the compassion and check boundary condition see if it can be merged.

- Tuotuo August 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Praveen: I don't think your approach works.
Consider 1,2,3,0,6,7

As is, 1,2,3,6,7 is the longest subsequence

If we go with your approach,

0,6,7,1,2,3 - 0,1,2,3 will be the longest subsequence

So, looks like we have to do evaluate the longest subsequence with every element as the starting one and maintain the current longest at any point.

But, it will be O(n^2). Need to think of further optimizing it.

- matrix August 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream.h>

using namespace std;

int longestConsecutive(vector<int> &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
map<int,bool>mp;
for ( unsigned int i=0;i<num.size();i++){
mp[num[i]]=true;
}

int res=0;
for (unsigned int i=0;i<num.size();i++){
int mx=1;
int fd = num[i];

mp.erase(num[i]);
while (mp.find(fd+1)!=mp.end()){
mx++;
mp.erase(fd+1);
fd++;
}

fd = num[i];
while (mp.find(fd-1)!=mp.end()){
mx++;
mp.erase(fd-1);
fd--;
}

if (mx>res){res=mx;}
}

return res;
}

int main() {
vector<int> num;
num.push_back(5);
num.push_back(4);
num.push_back(3);
num.push_back(2);
num.push_back(1);

cout << longestConsecutive(num);
return 0;
}

- Nishant Pandey August 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void liss(int* a, int n)
{
    int *l;
    int i, j, k, x;
    l = (int*) a_malloc(sizeof(int) * (n + 1), sizeof(int));

    l[0] = 0;

    k = 0;
    x = 0;
    while(x++ < 2) {  // Run through regular LIS twice.
        for (i = 0; i < ((x == 1)?n:l[1]); i++) {
            for (j = k; j > 0 && a[l[j]] >= a[i]; j--); // Replace with BSearch for log n performance.

            if (j == k) {
                k += 1;
            }

            l[j+1] = i;
        }
    }

    // output
    for (i = 1; i <= k; i++) {
        printf("%d, ", a[l[i]]);
    }
    printf("\n");

    a_free(l);
}

- c0der September 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

i would say, append the input array to the end of input array. Now the input array becomes a bigger array of size is 2n.
5 4 3 2 1 becomes 5 4 3 2 1 5 4 3 2 1.
Now apply LIS algo. it would give the circular LIS 1 5 .

5 6 7 1 2 3 becomes 5 6 7 1 2 3 5 6 7 1 2 3 and gives the result - 1 2 3 5 6 7.

- Vin August 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Vin: doesn't work.
check for this input
1,2,3,0,6
becomes
1,2,3,0,6,1,2,3,0,6
answer will be 5(0,1,2,3,6) but actual answer is 4.

- aka August 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

@aka - yes, you are correct, i dint thought of all the possible cases. I think we can consider the same approach after little modifications. for every element we should consider only a window size of n only.
so for 1,2,3,0,6,1,2,3,0,6, if we considers first 0 as the start point, consider elements only up to second zero(window size 5). this will resolve the issue.

- Vin August 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

I think you're almost there. What about concatenating the the array with same array minus the last element?
1, 2, 3, 0, 6 becomes 1,2,3,0,6,1,2,3,0 and LIS is 4 (0,1,2,3)
5, 4, 3, 2, 1 becomes 5,4,3,2,1,5,4,3,2 and LIS is 2 (1,5) or 2(4,5)
5, 6, 7, 1, 2, 3 becomes 5,6,7,1,2,3,5,6,7,1,2 and LIS is 6(1,2,3,5,6,7)

- oOZz August 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

1,2,3,0,5,6 becomes 1,2,3,0,5,6,1,2,3,0,5 and LIS is 5(0,1,2,3,5), however, actually the answer should still be 4.

- Anon October 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

1) Compute LIS for the whole array using a standard DP approach -> You will find LIS for the last element.
2) Check if there is a circle:
if (arr[length-1] < arr[0]) {
set LIS[0] (for arr[0]) == LIS[arr.length-1] + 1;
invoke step 1 (this time we start from LIS[0] == LIS[arr.length-1] + 1 instead of 1 like during the first invocation);
}

3) Find max value of LIS

Code:

public static void main(String[] args) {

	// int[] arr = { 10, 22, 9, 33, 21, 50, 41, 60, 80 };
	// int[] arr = { 5, 6, 7, 1, 2, 3 };
	// int[] arr = { 5, 6, 7, 1, 2, 3 };
	int[] arr = { 5, 4, 3, 2, 1 };
	int[] L = new int[arr.length];
	increasingSubsequence(arr, L);
	if (arr[0] > arr[arr.length - 1]) {
	    L[0] = L[arr.length - 1];
	    increasingSubsequence(arr, L);
	}

	int max = 0;
	for (int i = 0; i < L.length; i++) {
	    if (L[i] > max) {
		max = L[i];
	    }
	}
	System.out.println(Arrays.toString(arr));
	System.out.println(Arrays.toString(L));
	System.out.println(max);
    }

    public static void increasingSubsequence(int[] arr, int[] L) {

	L[0] += 1;
	for (int i = 1; i < L.length; i++) {
	    int maxn = 0;
	    for (int j = 0; j < i; j++) {
		if (arr[j] < arr[i] && L[j] > maxn) {
		    maxn = L[j];
		}
	    }
	    L[i] = maxn + 1;
	}
    }

- thelineofcode August 20, 2013 | 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