Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
1. If A[i] is smallest among all end candidates of active lists, we will start new active list of length 1.
2. If A[i] is largest among all end candidates of active lists, we will clone the largest active list, and extend it by A[i].
3. If A[i] is in between, we will find a list with largest end element that is smaller than A[i]. Clone and extend this list by A[i]. We will discard all other lists of same length as that of this modified list.
Note that at any instance during our construction of active lists, the following condition is maintained.
“end element of smaller list is smaller than end elements of larger lists”.
This is my first thought on being able to decide between discarding all (or subset of) a sequence that you are already considering. It's recursive but I believe it is O(n^2).
private static int longestSequence(int[] array, int index,
int largestValue, int length)
{
if (array.length == 1)
return 1;
if (index >= array.length)
return length;
int currentLargestValue;
int excludeLength = length, includeLength = length;
if (length == 0 || array[index] > largestValue)
currentLargestValue = array[index];
else
currentLargestValue = largestValue;
includeLength = longestSequence(array, index + 1, currentLargestValue, length + 1);
excludeLength = longestSequence(array, index + 1, largestValue, length);
if (includeLength >= excludeLength)
return includeLength;
else
return excludeLength;
}
public static int findSequence(int[] a) {
int max =0, j =1, val = 0;
for (int i =0; i< a.length; i++) {
if (a[i] == val +1) {
j ++;
}
else {
if (j > max) {
max = j;
}
j = 1;
}
val = a[i];
}
if (j > max) {
max = j;
}
return max;
}
After viewing the wiki page "Maximum subarray problem", I find out this problem can be solved by "Kadane's algorithm".
Note: before DP, we have to traverse the int array in case all elements are negative.
This algorithm runs at O(n).
Below is my implementation which has a minor difference from the original algo on that mine also return the star and end indices of this max sub sequence.
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <algorithm>
using namespace std;
int longestSeq(int *arr, int size, int &start, int &end)
{
// check if all elements are negative
int k = 0;
for (k=0; k<size; k++)
if (arr[k]>0) break;
if (k==size-1) return arr[0];
start = 0, end = 0;
int ret = 0, sum = 0;
for (int i=0; i<size; i++) {
if (sum==0 && arr[i]>0) start = i;
sum = max(0, sum+arr[i]);
if (sum > ret) {
ret = sum;
end = i;
}
}
return ret;
}
void printArray(int *arr, int l, int r)
{
for (int i=l; i<=r; i++)
cout<<arr[i]<<" ";
cout<<endl;
}
int main(int argc, char **argv)
{
int N = atoi(argv[1]);
int *a = new int[N];
srand(time(0));
for (int i=0; i<N; ++i)
a[i] = rand() % 100 - 49;
cout<<"intput: ";
printArray(a, 0, N-1);
int start, end;
int max = longestSeq(a, N, start, end);
cout<<"max subarray: ";
printArray(a, start, end);
cout<<"max value: "<<max<<endl;
return 0;
}
}
Here is a tested solution in Python that returns the longest length as well as the actual array using dynamic programming:
def findSeq(array):
temp = [1] * len(array)
rv = 0
for i in range(len(array) - 1, -1, -1):
for j in range(i + 1, len(array)):
if array[i] < array[j]:
temp[i] = max(temp[i], 1 + temp[j])
rv = max(rv, temp[i])
# at this point rv has the answer we need, but we can use temp to reconstruct a potential subarray
subarray = []
rvc = rv
for i, t in enumerate(temp):
if t == rvc:
rvc -= 1
subarray.append(array[i])
return rv, subarray
The loop invariant is that if we are processing the item at index i then array temp has in it the longest lengths for items at indices i + 1, i + 2, i + 3, ... We iterate through the input array from right to left, and given the assumption we simply consider the current element A, scan rightwards, and for every element B greater than it we test if A followed by the sequence starting at B produces a longer subsequence than the one whose length we have recorded in temp.
to be noted : non-necessarily-adjacent
if you sort the entire given array, won't it become increasing ?
{1.-1.3.-3}
sorted : -3 -1, 1, 3 .
isn't it increasing ?
so isn't the ans = entire array ?
this is a O(nlogn) solution. It is like the usual DP solution just keep the smallest element in the specified idx(order) in the DP[]. So instead of checking all the elements in dp we just do binary search if the element is smaller than the last one or increment the size if it is bigger. here is the code bellow:
public int LIS(int[] arr) {
int[] dp = new int[arr.length];
dp[0] = Integer.MIN_VALUE;
int size = 1;
for (int i = 0; i < arr.length; i++) {
if (arr[i] < dp[0])
dp[0] = arr[i];
else if (arr[i] > dp[size - 1])
dp[size++] = arr[i];
else {
int k = binSearchNextOrEqual(dp, arr[i]);
dp[k] = arr[i];
}
}
return size;
}
// longest_inc_subseq.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<iostream>
using namespace std;
void find_subseq_n2_time(int *input,int n)
{
int *temp=new int[n];
int i,j;
int *path=new int[n];
for(i=0;i<n;i++)
{
temp[i]=1;
path[i]=i;
for(j=i-1;j>=0;j--)
{
if(input[j]<input[i] && temp[j]+1>temp[i])
{
path[i]=j;
temp[i]=temp[j]+1;
}
}
}
int max=temp[0];
for(i=0;i<n;i++)
{
if(temp[i]>max)
{
max=temp[i];
j=i;
}
}
cout<<"length of longest increasing subsequence is : "<<max<<" and path is : ";
cout<<j<<" ";
while(path[j]!=j)
{
cout<<path[j]<<" ";
j=path[j];
}
//cout<<path[j]<<endl;
cout<<endl;
}
template<class T>
int binsearch(T *input,int n,int index,int len,int *subseq_so_far)
{
int start=1;
int end=len;
int mid;
while(start<=end)
{
mid=start+((end-start)/2);
//cout<<"mid : "<<mid<<endl;
//if(mid==0)
//return ((input[index]>input[subseq_so_far[1]])?1:0);
if(input[subseq_so_far[mid]]==input[index])
return 0;
else if(input[subseq_so_far[mid]]>input[index])
end=mid-1;
else
start=mid+1;
}
return (start-1);
}
template<class T>
void find_subseq_nlogn(T *input,int n)
{
int *subseq_so_far;
int *path;
int i,j;
int length;
path=new int[n+1];
subseq_so_far=new int[n+1];
subseq_so_far[0]=-1;
subseq_so_far[1]=0;
length=1;
for(i=1;i<n;i++)
{
j=binsearch(input,n,i,length,subseq_so_far);
cout<<"index : "<<j<<endl;
path[i]=subseq_so_far[j];
if(j==length || input[i]<input[subseq_so_far[j+1]])
{
subseq_so_far[j+1]=i;
if(length<j+1)
length=j+1;
}
}
cout<<"length of the longest subsequence found is : "<<length<<endl;
cout<<"The path from end is : \n";
i=subseq_so_far[length];
while(i>=0)
{
cout<<input[i]<<" at index : "<<i<<endl;
i=path[i];
}
}
int main()
{
int input[]={99,100,100,100,101,3,4,5,6,7,8};
find_subseq_n2_time(input,11);
find_subseq_nlogn(input,11);
system("pause");
}
int a[]={0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15};
int n=sizeof(a)/sizeof(int);
int *occ=new int[n];
for(int i=0;i<n-1;i++)
{
int count=0;
for(int j=i+1;j<n;j++)
if(a[j]>a[i])
count++;
occ[i]=count;
}
int buf[10];
int no=-1;
int max,pos;
i=0;
while(i<n)
{
int flag=0;
for(int j=i;j<n;j++)
{
if(a[j]>buf[no] || no==-1)
{
if(flag==0)
{
flag=1;
max=occ[j];
pos=j;
}
if(occ[j]>max)
{
max=occ[j];
pos=j;
}
}
}
cout<<"\n "<<a[pos]<<" "<<pos;
buf[++no]=a[pos];
i=pos+1;
}
getch();
this is a simple c code.. O(n) solution.. people mite confuse if its O(n^2) but its O(n)
#include<stdio.h>
#include<conio.h>
void main()
{
int j;
int arr[10]={5,6,0,1,2,3,4,7,22,11};
int localstrt=0;int localend=0;
int longeststart=0;int longestend=0;
int i=0;
for(i=0;i<10;i++)
{
if(arr[i]<arr[i+1])
{
j=i;
localstrt=i;localend=i;
while((arr[j]<arr[j+1])&&(j<10))
{
j++;
}
localend=j;
if((longestend - longeststart)<(localend - localstrt))
{
longestend=localend;longeststart=localstrt;
}
i=j;
}
}
printf("%d %d",longeststart,longestend);
getch();
}
Dynamic Programming
- Rishi June 10, 2012Largest_Increasing_Sequence( n ) = Max { Largest_Increasing_Sequence Excluding first element( n-1 ) , Largest_Increasing_Sequence Including first element(n-1) }