## Amazon Interview Question for SDE1s

Country: India
Interview Type: Written Test

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

I believe this simple nlogn solution with O(n) space should work: sort an array of pairs that include (value, index). Find the largest consecutive subsequence sum such that index_1 < index_2 < index_3 ... < index_n.

Works for your test case as well as adding [-1] to the beginning. However, I didn't fully test it out. If anyone could give a counter example, or give a faster algorithm I would like to know.

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

And how would you find the largest index-increasing subsequence?

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

We have to traverse the array by summing up till we reach an element that is smaller than the previous element.

Then we have to put it in a struct {int lastnum,int sum};
lastnum is the last greatest no in the sequence and sum is the sum of the sequence.
Then after finding the element that is smaller, create another structure and do the same. Now for each element compare with all the structure if the lastnum is smaller than the current no, then update sum and lastnum.
Finally iterate through the structure and return the structure with largest sum.

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

Bug Found. Will Edit.

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

``````public class SumData//Helper class that will store largest sum and its length
{
private int sum;
private int length;
}

public class LisSumFinder
{
public int findLisSum(int[] a)
{
if(a==null)
{
throw new InvalidInputException("input array cannot be null");
}
ArrayList<SumData> allSums=new ArrayList<SumData>();
findLisAndSums(allSums,0,a);
SumData max=allSums.get(0);
for(SumData x:allSums)
{
max=x.length>=max.length?x:max;

}
return max.sum;
}

public void findLisAndSums(ArrayList<SumData> allSums,int idx,int[] a)
{
SumData curr;
if(idx==a.length)
{
return;
}
if(idx==0)
{
curr=new SumData();
}else
{
for(int i=0; i<idx;i++)
{
if(a[i]<a[idx])
{
curr=findLongestSum(curr,allSums.get(i));
}
}
}
curr.length++;
curr.sum+=a[idx];
findLisAndSums(allSums,idx+1,a)

}
public SumData findLongestSum(SumData x,SumData y)
{
if(x==null)
{
return y;
}
if(x.length>y.length)
{
return x;
}
return y;
}

}``````

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

Time complexity: O(n^2), Space: O(n)

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

``````def maxValue(listValue):
Value = sorted(listValue)
Sum = Value
if len(Value)==0:
return
maxValue = Value
for index in range(1,len(listValue)):
pre = Value[index-1]
curr = Value[index]
# Sum = pre
if curr-pre ==1:
Sum +=curr
maxValue = max(Sum,maxValue)
else:
Sum = curr

return maxValue
print maxValue([1,2,8,3])``````

Time(nlogn), space:O(n)

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

It's a Classical LIS problem.. with a simple addition that we also have to store the LIS so that later we can return it's sum..
Time complexity: O(n^2), Space Complexity: O(n)

``````static int lisSum(int[] ar){
int[] prev = new int[ar.length];	//to store the path
int[] lis  = new int[ar.length];		//to store the lis
Arrays.fill(prev, -1);
Arrays.fill(lis, 1);

int max = 0;		//to store the max lis
int maxIndex = -1;		//to store the indx of max LIs.. so that we can sum it later

for(int i=1; i<ar.length; i++){
for(int j = 0; j<i; j++){
if(ar[i] > ar[j] && lis[i] < lis[j] + 1){
lis[i] = lis[j] + 1;
prev[i] = j;
}
}

if(max < lis[i]){
max = lis[i];
maxIndex = i;
}
}
int sum = 0;
while(maxIndex != -1){
sum = sum + ar[maxIndex];
maxIndex = prev[maxIndex];
}

return sum;
}``````

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

public static void longestinsubsequence(int[] arr)
{
int lengtharr = arr.length;
int[] t = new int [lengtharr];
int[] sum = new int[lengtharr];
int larges = 1;
int value =1;
for(int i=0;i<lengtharr;i++)
{
t[i]=1;
sum[i] = arr[i];
}
for(int i = 1;i<lengtharr;i++)
{
for (int j=0;j<i;j++)
{
if(arr[j]<arr[i])
{
t[i] = Math.max(t[i], t[j]+1);
sum[i] = arr[i]+sum[j];
if(value < t[i]){
larges = i;
value = t[i];
}
}
}
}

System.out.print(sum[larges]);

}

public static void main(String [] args)
{

int[] arr = new int;
arr = 1;
arr = 8;
arr = 2;
arr = 3;

longestinsubsequence(arr);

}

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

``````public static void longestinsubsequence(int[] arr)
{
int lengtharr = arr.length;
int[] t = new int [lengtharr];
int[] sum = new int[lengtharr];
int larges = 1;
int value =1;
for(int i=0;i<lengtharr;i++)
{
t[i]=1;
sum[i] = arr[i];
}
for(int i = 1;i<lengtharr;i++)
{
for (int j=0;j<i;j++)
{
if(arr[j]<arr[i])
{
t[i] = Math.max(t[i], t[j]+1);
sum[i] = arr[i]+sum[j];
if(value < t[i]){
larges = i;
value = t[i];
}
}
}
}

System.out.print(sum[larges]);

}

public static void main(String [] args)
{

int[] arr = new int;
arr = 1;
arr = 8;
arr = 2;
arr = 3;

longestinsubsequence(arr);

}``````

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

``````function increasing_sum(\$list){
\$longest_path = 0;
\$longest_path_sum = 0;

\$curr_path = 1;
\$curr_path_sum = \$list;

\$breakdown_idx = 0;

for(\$i=1; \$i<count(\$list); \$i++){
if((\$list[\$i] < \$list[\$breakdown_idx] && \$i < \$breakdown_idx) || (\$list[\$i] > \$list[\$i-1] && \$i > \$breakdown_idx) || \$i == \$breakdown_idx){
\$curr_path++;
\$curr_path_sum += \$list[\$i];
}else if(\$i > \$breakdown_idx){
if(\$curr_path > \$longest_path){
\$longest_path = \$curr_path;
\$longest_path_sum = \$curr_path_sum;
}

\$breakdown_idx = \$i;
if(\$list < \$list[\$breakdown_idx]){
\$curr_path = 1;
\$curr_path_sum = \$list;
}else{
\$curr_path = 0;
\$curr_path_sum = 0;
}
\$i=1;
}
}

if(\$curr_path > \$longest_path){
\$longest_path = \$curr_path;
\$longest_path_sum = \$curr_path_sum;
}
return \$longest_path;
}``````

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

``````int array = {1,8,2,3,77};
sort(array, array+5);

for(int i = 0; i <5; i ++)
{
}
for(int i = 0 ; i < 5 ; i ++)
{
if(i != 0)
{
if(array[i] == array[i-1]+1)
{
}
}
}

int max = 0;
for(int i = 0; i <5; i ++)
{
{
{
}
}
}

cout<<max;``````

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

How about transforming the problem into a directed graph (larger numbers with an array index greater and value greater would have a connection) and then searching the graph using a DFS for the longest path until a deadend? This approach would take O(n^2) complexity and O(n^2) memory to construct the graph and O(n) for the DFS tracking.

``````public static int longestIncreasingSubsequenceSum(int[] arr){
//construct the graph
ArrayList<Integer>[] connections = new ArrayList<Integer>[arr.length];
for(int i = 0; i < arr.length; i++){
connections[i] = new ArrayList<Integer>();
for(int j = 0; j < i; j++){
if(arr[j] < arr[i]){
}
}
}

//find the best sum
int bestLength = -1;
int bestSum = Integer.MIN_VALUE;
int[] localBestLength = new int[arr.length];
int[] localBestSum = new int[arr.length];
for(int i = 0; i < arr.length; i++){
dfs(i, arr, connections, localBestLength, localBestSum);
if(localBestLength[i] > bestLength){
bestLength = localBestLength[i];
bestSum = localBestSum[i];
}
}
return bestSum;
}

private static void dfs(int i, int[] arr, ArrayList<Integer>[] connections, int[] localBestLength, int[] localBestSum){
int childBestSum = 0;
int childBestLength = 0;
for(Integer child : connections[i]){
if(localBestLength[child] == 0){
dfs(child, arr, connections, localBestLength, localBestSum);
}
if(localBestLength[child] > childBestLength){
childBestLength = localBestLength[child];
childBestSum = localBestSum[child];
}
}
localBestLength[i] = childBestLength + 1;
localBestSum[i] = childBestSum + arr[i];
}``````

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

How about a non-searching approach. Here's one for traversing the list. Unfortunately it's still O(n^2) complexity, but now O(n) memory:

``````public static int longestIncreasingSubsequenceSum(int[] arr){
if(arr == null){
throw new NullPointerException("\"arr\" may not be null");
}

//populate the lists of lengths
int[] lengths = new int[arr.length];
int[] sums = new int[arr.length];
int bestLength;
int bestSum;
for(int i = 0; i < arr.length; i++){
for(int j = i-1; j > -1; j--){
if(arr[j] < arr[i] && lengths[j] > lengths[i]){
lengths[i] = lengths[j];
sums[i] = sums[j];
}
}
lengths[i] ++;
sums[i] += arr[i];
if(length[i] > bestLength){
bestLength = length[i];
bestSum = sums[i];
}
}

return bestSum;
}``````

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.