## Amazon Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

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

Dynamic Programming
Largest_Increasing_Sequence( n ) = Max { Largest_Increasing_Sequence Excluding first element( n-1 ) , Largest_Increasing_Sequence Including first element(n-1) }

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

and how is this recursion working?
what you are putting is very abstract.

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

basicalgos.blogspot.com/2012/03/37-longest-increasing-sequence-lis.html

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

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

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

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

}

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

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;

}

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

sorry missed the part where it is mentioned that it is not necessarily adjacent

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

We can just do a Quick Sort on the numbers and perform the earlier program written

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

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;

}``````

}

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

You misunderstood the problem. This is not a maximum-subarray problem.

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

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``````

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

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.

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

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 ?

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

okok got it.
its sub-sequence not subset :P

My proposed algo will be:
A=original array
1) B=A
2) sort T
3) find longest common subsequence between A and B

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

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

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

// 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");
}

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

this contains both nlogn as well as n^2 time algos

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

``````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();``````

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

o(n^2) time and O(n) extra space .

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

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

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

and yes.. it is succesfully running on my visual studio..

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.