## Amazon Interview Question

Country: India

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

Just a little modification to the dynamic approach..I used a LISindex array to keep track of the element that comes before the current element.If any doubts ,Give a reply

``````#include<stdio.h>
#include<stdlib.h>

int lis( int arr[], int n )
{
int *lisindex=(int *)malloc(sizeof(int) * n);
int *lis, i, j, max = 0;
lis = (int*) malloc ( sizeof( int ) * n );
int lastLISindex;
int check,k=0;

for ( i = 0; i < n; i++ )
lis[i] = 1;

for ( i = 1; i < n; i++ )    {
for ( j = 0; j < i; j++ ) {
if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)   {
lis[i] = lis[j] + 1;
lisindex[i]=j;
}
}
}
/* Pick maximum of all LIS values */
for ( i = 0; i < n; i++ )    {
if ( max < lis[i] )
max = lis[i];
lastLISindex=i;
}

int *arrSeq=(int *)malloc(sizeof(int) * max);

for(int index=max-1;index>=0;index--) {
arrSeq[index]=arr[lastLISindex];
lastLISindex=lisindex[lastLISindex];
}

for(int index=0;index<max;index++)   {
printf("%d ",arrSeq[index]);
}

/* Free memory to avoid memory leak */
free( lis );

return max;
}

/* Driver program to test above function */
int main()
{
int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
int n = sizeof(arr)/sizeof(arr);
lis( arr, n );

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

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

Beautiful solution! The use of a predecessor array and the way the solution is coded up is quite instructive.

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

@Dumbo:Thanx

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

There is another way to find LIS, similar to patient sort, where you keep piles (stacks) to keep the increasing sequences. Here is the link and explanation of the algorithm: wordaligned.org/articles/patience-sort.

By using this method, you can not only print the longest increasing sequence, but also print all the longest subsequences, if there are more than one maximum subsequence.

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

Good one!

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

There is another clean and neat DP solution based on DAG in the book cs.berkeley.edu/~vazirani/algorithms/all.pdf.

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

Yea that's a great algorithm book too.

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

@Dumbo:cs.berkeley.edu/~vazirani/algorithms/all.pdf. this approach coded below but i guess making DAG is taking O(n^2).

``````#include <stdio.h>

#define SIZE(x) (sizeof(x)/sizeof(x))
int maxi(int a,int b)
{
return a>b?a:b;
}

int a[] = {10,5,2,5,2,13,17,15,16,19,20,21};

/* LIS using constructing a DAG */
void DAG()
{
int i, j, max=0,index;
int d = {0};
int dag = {0};
int prev = {0};

for(i=0;i<SIZE(a);i++) {
d[i]=1;prev[i]=0;
}
for(i=0;i<SIZE(a);i++)
for(j=0;j<SIZE(a);j++)
dag[i][j] = 0;
for(i=0;i<SIZE(a);i++)
for(j=i+1;j<SIZE(a);j++)
if(a[i] <= a[j])
dag[i][j] = 1;

d=1;
for(i=0;i<SIZE(a);i++)
for(j=0;j<SIZE(a);j++) {
if(dag[i][j] == 1) {
if(d[j] <= 1+d[i]) {
d[j] = 1+d[i];
prev[j] = i;
}
}
}
for(i=0;i<SIZE(a);i++)
if(max < d[i]) {
index = i;
max = d[i];
}
printf("max index %d and greatest total elements %d\n", index, max);
printf("%d\n", a[index]);
while(--max){
index = prev[index];
printf("%d\n", a[index]);
}
}

int main()
{
DAG();
}``````

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

@Nascent, is it consecutive numbers or just order in the given sequence should be considered ?

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

Its not consecutive. Its an increasing sequence. This is the tricky part else the problem is simple.

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

``````int longstr(int val[],int size)
{
int arr[size];
int i=0,j=1,count1=1,max=0,temp,index;
for( i = 0 ; i < size ; i++)
{
if(val[i] < val[j])
{
//printf(" in if The array is:%d ",val[j]);
j++;
count1++;
}
if(max < count1)
{
max = count1;
temp = j-(max);
index = 0;
while( temp <= j)
{
arr[index] = val[temp];
temp ++;
//printf("The array is: %d",arr[index]);
index++;
}
}

if(val[i] >= val[j-1])
{
// printf("in else The array is:%d ",val[j]);
count1 = 1;
j++;
}

}
for( index = 0; index < max; index++)
printf("%d ",arr[index]);
printf("The max number is:%d",max);
return max;
}
int main()
{
int val = 0;
int arr[]={1,5,7,8,9,45,78,2,4,1,7,12,23,34,6,23,45};
int size = sizeof(arr)/sizeof(arr);
val=longstr(arr,size-1);
return 1;
}``````

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

The following code prints a longest "strictly" increasing subsequence.
For example for {7, 7, 7, 7} it prints {7}. Only a little modification is required to print a longest non-decreasing subsequence.

Dynamic Programming. Time complexity O(n^2).

``````//lisLen[i] stores the length of longest increasing subsequence starting at index i.
//next[i] stores the index of next element in the longest increasing
//subsequence starting at index i.
int lisLen[SIZ], next[SIZ];

void printLIS(int a[], int len){
int i, j, max, index;

lisLen[len-1] = 1;
next[len-1] = -1;	//-1 indicates that there is no next number after this one.

for(i=len-2 ; i>=0 ; i--){
lisLen[i] = 1;
next[i] = -1;
for(j=i+1 ; j<=len-1 ; j++){
if(1+lisLen[j] > lisLen[i] && a[i]<a[j]){
lisLen[i] = 1 + lisLen[j];
next[i] = j;
}
}
}

max = 0;
for(i=0 ; i<len ; i++){
if(lisLen[i] > max){
max = lisLen[i];
index = i;
}
}
while(next[index] != -1){
cout<<a[index]<<" ";
index = next[index];
}
cout<<a[index]<<"\n\n";
}``````

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

Use dynamic programming approach.

Maintain a 2D array.
ith row will store the longest increasing sequence for ith number in the original array.
For optimization purpose, you can use another array to maintain the length of each row. Call it lengthArray.

Use DP approach to find longest increasing sequence for all the numbers from 0 to nth elements. Each time update the lengthArray.

at the end, iterate through lengthArray and find the largest element.
Lets say its jth.

Now print jth row from 2D array.

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

time complexity O(n)
space complexity O(n^2)

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

i defined a separate datastructure such that it keeps track of the indexex forming the LIS

``````#include<iostream>
using namespace std;
struct lis
{
int count;
int index;
};

void display(int a[],lis t[],int n,int pos)
{
if(t[pos].index!=pos)
{
display(a,t,n,t[pos].index);
}
cout<<a[pos]<<"  ";
return;
}

int lisnum(int a[],int n)
{
lis t[n];
for(int i=0;i<n;i++)
{
t[i].count=1;
t[i].index=i;
}
for(int i=0;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(a[i]>a[j]&&1+t[j].count>t[i].count)
{
t[i].count=1+t[j].count;
t[i].index=j;
}
}
}
int max=-10,pos=-1;
for(int i=0;i<n;i++)
{
if(t[i].count>max)
{
max=t[i].count;
pos=i;
}
}
display(a,t,n,pos);
return max;
}

int main()
{
cout<<"enter the program. \n";
int n,*a;
cout<<"Enter the size. \n";
cin>>n;
a=new int[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int t=lisnum(a,n);
cout<<"Length="<<t;
return 0;
}``````

i hope this could serve the purpose...
tell me if any doubts... regarding the program..

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

i defined a separate datastructure such that it keeps track of the indexex forming the LIS

``````#include<iostream>
using namespace std;
struct lis
{
int count;
int index;
};

void display(int a[],lis t[],int n,int pos)
{
if(t[pos].index!=pos)
{
display(a,t,n,t[pos].index);
}
cout<<a[pos]<<"  ";
return;
}

int lisnum(int a[],int n)
{
lis t[n];
for(int i=0;i<n;i++)
{
t[i].count=1;
t[i].index=i;
}
for(int i=0;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(a[i]>a[j]&&1+t[j].count>t[i].count)
{
t[i].count=1+t[j].count;
t[i].index=j;
}
}
}
int max=-10,pos=-1;
for(int i=0;i<n;i++)
{
if(t[i].count>max)
{
max=t[i].count;
pos=i;
}
}
display(a,t,n,pos);
return max;
}

int main()
{
cout<<"enter the program. \n";
int n,*a;
cout<<"Enter the size. \n";
cin>>n;
a=new int[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int t=lisnum(a,n);
cout<<"Length="<<t;
return 0;
}``````

i hope this could serve the purpose...
tell me if any doubts... regarding the program..

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

Can we use LCS here?

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

You need to use LIS dynamic approach..LCS is used when two arrays are given.

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

This was a great (and tricky) question. I challenged myself to implement a single pointer traversal, instead of using a leading/trailing pointer. The running time of this algorithm should be O(n) as it simply scans each element and copies to the new array. In the worst case it would scan and copy each element once if this was a sorted (ascending) array of integers.

This problem also required that I make special consideration for the last element in the array, should it be part of the largest ascending sequence, thus the use of the ternary operators evaluating on i==a.length.

Assumption: Duplicates are not considered "increasing", so they are not counted as such and cause the 'count' to start over.

I also incorporated Java's ArrayList class so that I could account for increasing sequences that have the same length, and subsequently print all of them.

I hope this proves helpful =)

NOTE: I use a file with 100,000 randomly generated integers to test, that is the reason for the scanner at the start to load my test case.

``````Scanner scanner = new Scanner(new File("IntegerArray.txt"));
int [] a = new int ;
int k = 0;
while(scanner.hasNextInt()){
a[k++] = scanner.nextInt();
}

ArrayList<int[]> resultSet = new ArrayList<>();
int[] result = new int;
int i, j;
int count = 1;  //first element in sequence always counted

for(i=1; i < a.length; i++){
if(a[i-1] < a[i]){
count++;  //increase the current count when increasing element found
}
else
if(count >= result.length && (a[i-1] >= a[i] || i == a.length -1) ){
if(count > result.length){resultSet.clear();}
result = new int[count];
for(j = 0; j < result.length; j++){
result[j] = (i == a.length-1) ?  a[i-count+j+1] : a[i - count + j];
//edge case (End) - to make sure we capture the last element
//if it is part of the largest increasing sequence
}
count = 1;
}
else{count = 1;}
}

for(i=0; i < resultSet.size(); i++){
int[] temp = resultSet.get(i);
for(int x = 0; x < temp.length; x++){
System.out.println(temp[x] + " ");
}
System.out.println();
}``````

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

Just to understand the question,
if the input is {1,5,7,8,9,45,78,2,4,1,7,12,23,34,6,23,45};
The increasing sub-arrays are
{1,5,7,8,9,45,78} -> Longest and should be the result.
{2,4}
{1,7,12,23,34}
{6,23,45}

The output should be {1, 5, 7, 8, 9, 45, 78}

Can someone confirm?

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

Yes it should be the longest..

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

I'm not able to get hang on need for an algorithm with complexity > O(n).

I'm thinking of the below algorithm. Let me know if I missed something in the question.

1. Loop from i = 1 to length
2. In each iteration, if Array[i] <= Array[i -1]
2.a. Set the start index of result to i;
2.b else: Increment the temp. size counter.
2.b: If the result size < temp size counter, update the result start index and the result size.
3. Iterate through result start index for result size and print the numbers from the given array.
Time complexity is O(n) and its in-place algorithm.

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

``````public static void PrintIncreasingSubArray(int[] iarInput)
{
int iTmpStart = 0; 		// Temp. Start Index.
int iTmpLength = 0;		// Temp. Length.
int iResStart = 0;		// Result Start Index.
int iResLength = 0;		// Result Length.
// Loop from index 1 to the end of list.
for(int iIndex=1; iIndex < iarInput.length; iIndex++)
{
// Check if the sequence is increasing/decreasing-flat.
if(iarInput[iIndex] <= iarInput[iIndex-1])
{
// Flat or decreasing trend.
iTmpStart = iIndex;
iTmpLength = 0;
}else{
// Increasing Trend.
iTmpLength++;
// As the new found sequence is bigger, update the old result values.
if(iTmpLength > iResLength)
{
iResStart = iTmpStart;
iResLength = iTmpLength;
}
}
}
// Print the longest increasing sub-array using start index and length of result.
for(int iCount = 0; iCount <= iResLength; iCount++)
{
System.out.print(iarInput[iResStart + iCount]);
System.out.print(", ");
}
}``````

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

The elements in the subsequence do not have to be adjacent, they just have to appear in order in the input array. So for example {1, 5, 7, 8, 9, 12, 23, 34, 45} is longer than your proposed answer.

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

@Steven.Tallia: Thanks for clarifying. Now that sounds interesting.

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

#include <iostream>
#include <vector>
using namespace std;

int main()
{
std::vector<int>vec;
int arr={1,9,2,4,7,2,3};
int matrix;

for(int i=0;i<7;i++)
for(int j=0;j<8;j++)
matrix[i][j]=99;

matrix=arr;

for(int i=1;i<7;i++)
for(int j=1;j<8;j++)
{
if(arr[i]>matrix[i-1][j-1]&&arr[i]<matrix[i-1][j])
matrix[i][j]=arr[i];
else
matrix[i][j]=matrix[i-1][j];
}

int k=6;
int j;
for(j=1;j<8;j++)
{
if(matrix[k][j]==99)
{
break;
}
}
j--;
while(matrix[k][j]!=99)
{
cout<<matrix[k][j];
vec.push_back(matrix[k][j]);
k--;
j--;
}

int m=vec.size();
for (int i=m;i>0;i--)
{
cout<<vec[i];
}
return 0;
}

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

``````#include <iostream>
#include <vector>
using namespace std;

int main()
{
std::vector<int>vec;
int arr={1,9,2,4,7,2,3};
int matrix;

for(int i=0;i<7;i++)
for(int j=0;j<8;j++)
matrix[i][j]=99;

matrix=arr;

for(int i=1;i<7;i++)
for(int j=1;j<8;j++)
{
if(arr[i]>matrix[i-1][j-1]&&arr[i]<matrix[i-1][j])
matrix[i][j]=arr[i];
else
matrix[i][j]=matrix[i-1][j];
}

int k=6;
int j;
for(j=1;j<8;j++)
{
if(matrix[k][j]==99)
{
break;
}
}
j--;
while(matrix[k][j]!=99)
{
cout<<matrix[k][j];
vec.push_back(matrix[k][j]);
k--;
j--;
}

int m=vec.size();
for (int i=m;i>0;i--)
{
cout<<vec[i];
}
return 0;
}``````

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

``````#include <iostream>
#include <vector>
using namespace std;

int main()
{
std::vector<int>vec;
int arr={1,9,2,4,7,2,3};
int matrix;

for(int i=0;i<7;i++)
for(int j=0;j<8;j++)
matrix[i][j]=99;

matrix=arr;

for(int i=1;i<7;i++)
for(int j=1;j<8;j++)
{
if(arr[i]>matrix[i-1][j-1]&&arr[i]<matrix[i-1][j])
matrix[i][j]=arr[i];
else
matrix[i][j]=matrix[i-1][j];
}

int k=6;
int j;
for(j=1;j<8;j++)
{
if(matrix[k][j]==99)
{
break;
}
}
j--;
while(matrix[k][j]!=99)
{
vec.push_back(matrix[k][j]);
k--;
j--;
}

int m=vec.size();
for (int i=m-1;i>=0;i--)
{
cout<<vec[i];
}
return 0;
}``````

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

Here all the solutions are O(n^2); nlogn solution is given on algoritihmist site using binary search.

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

``````what about radix sort approach:
1.given *a, create b[],c[],d[] = {0} string/int arrays and exp =1 , m= a, int count =0; and other declarations
2. while (m/exp>0)
for (i=0:n-1)
b[i] = a[i]/exp %10;
for(i=0:n-1)
count++;
a[i] = b[i];

if(count != 1)
for(i=0:n-1)
c[i]>b[i]
d[i]++

c[i] = b[i]

3. then d[i] will have the maximum increasing sequence for each entry.
4. then check the longest from the d array and return it.``````

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

don't forget to get the bigest/longest number and assign to m at the beginning and do exp *= 10 at the end of step 2.

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

Traverse Array and keep track of current AscSequenceStartIndex, AscSequenceLength and AscSequenceEndIndex.
At the end print elements from index AscSequenceStartIndex to AscSequenceEndIndex

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

It is not necessary to be sorted array

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

@PKTSOngChen:

Just to understand the question,
if the input is {1,5,7,8,9,45,78,2,4,1,7,12,23,34,6,23,45};
The increasing sub-arrays are
{1,5,7,8,9,45,78} -> Longest and should be the result.
{2,4}
{1,7,12,23,34}
{6,23,45}

The output should be {1, 5, 7, 8, 9, 45, 78}

Wt else you got from qus ???

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

To me it looks as per your example there are two sub-arrays
1. {1,5,7,8,9,45,78}
2. {2,4,,7,12,23,34,45}

guys correct me if my understanding is wrong

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.