Amazon Interview Question SDE1s
Country: India
Interview Type: Written Test
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.
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;
}
}
def maxValue(listValue):
Value = sorted(listValue)
Sum = Value[0]
if len(Value)==0:
return
maxValue = Value[0]
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)
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;
}
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[4];
arr[0] = 1;
arr[1] = 8;
arr[2] = 2;
arr[3] = 3;
longestinsubsequence(arr);
}
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[4];
arr[0] = 1;
arr[1] = 8;
arr[2] = 2;
arr[3] = 3;
longestinsubsequence(arr);
}
function increasing_sum($list){
$longest_path = 0;
$longest_path_sum = 0;
$curr_path = 1;
$curr_path_sum = $list[0];
$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[0] < $list[$breakdown_idx]){
$curr_path = 1;
$curr_path_sum = $list[0];
}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;
}
int array[5] = {1,8,2,3,77};
sort(array, array+5);
int answer[5];
for(int i = 0; i <5; i ++)
{
answer[i] = array[i];
}
for(int i = 0 ; i < 5 ; i ++)
{
if(i != 0)
{
if(array[i] == array[i-1]+1)
{
answer[i] = answer[i-1]+array[i];
}
}
}
int max = 0;
for(int i = 0; i <5; i ++)
{
if(answer[i] != array[i])
{
if(answer[i] > max)
{
max = answer[i];
}
}
}
cout<<max;
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]){
connections[i].add(j);
}
}
}
//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];
}
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;
}
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.
- SycophantEve June 18, 2015Works 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.