## Adobe Interview Question for Developer Program Engineers

• 0

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

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

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

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

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

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

sorry try with this

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

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.

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.

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

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;

k = 0;
x = 0;
while(x++ < 2) {  // Run through regular LIS twice.
for (i = 0; i < ((x == 1)?n:l); 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);
}``````

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.

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

@Vin: doesn't work.
check for this input
1,2,3,0,6
becomes
1,2,3,0,6,1,2,3,0,6

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

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

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

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)

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

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.

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) {
set LIS (for arr) == LIS[arr.length-1] + 1;
invoke step 1 (this time we start from LIS == 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 > arr[arr.length - 1]) {
L = 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 += 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;
}
}``````

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.