Adobe Interview Question
Developer Program EngineersCountry: India
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
I thought of this approach initially and found bug.
try with this example
{10, -3, -4, 7, 6, 5, -4, -1}
@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.
#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;
}
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);
}
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: 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 - 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.
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)
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;
}
}
Append all the elements except last one into end of buffer and then apply LIS problem(With Dynamic Programming on it).
- Mitesh September 09, 2013For 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