## Deshaw Inc Interview Question for Software Engineer / Developers

• 1
of 1 vote

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

If you already know how to solve max subsequence problem, you already know a O(n) solution for this problem too
1. In the first iteration find the subsequence that has maximum sum
2. change sign of all the elements in the array
3. Now, find the maximum sum subsequence again

The absolute maximum should now be either of the sub-sequences computed from 1&3.
To be optimal, 2&3 can be combined.

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

first sequence will give 398 and second will give 2 so ans will be 398

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

Initialize:
max_so_far = 0
max_ending_here = 0

Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_ending_here < 0)
max_ending_here = 0
(c) if(max_so_far < max_ending_here)
max_so_far = max_ending_here
return max_so_far

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

how will you handle negative nos???

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

If we are just comparing the min and max subsequence, how would 398 come then??

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

int maxsequence(int a[], int size)
{
int current_max = 0;
int real_max = current_max;
for(i=0; i<size; i++)
{
current_max += a[i];
if(current_max <= 0)
current_max = 0;
else if(current_max > real_max)
real_max = current_max;
}
return real_max;
}

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

this one is nice and working

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

this will not work for following arrays:
{-9}
{-1,-2,-3}

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

Find max subsequence and min subsequence in one loop then compare the absolute value of max subsequence and min subsequence

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

correct!!

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

I guess the question wants a subarray rather than a subsequence .

Reasoning: Example 100,-2,300
In this case if we take the maximum subsequence it shall be just 100,300 which sums to 400
But the answer mentioned is 398 .

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

#include<iostream>
using namespace std;

int max_subarray(int a[],int n)
{
int i;
int sum_here=0;
int sum=0;
for(i=0;i<n;i++)
{
sum_here+=a[i];
if(sum_here<0)
sum_here=0;
if(sum_here>sum)
sum=sum_here;
}
return sum;
}

int main()
{
int i,n;
cin>>n;
int a[n];
for(i=0;i<n;i++)
cin>>a[i];
int a1,a2,max;
a1=max_subarray(a,n);
for(i=0;i<n;i++)
a[i]=-a[i];
a2=max_subarray(a,n);
max=a1>a2?a1:a2;
cout<<"\n"<<max;
}

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

#include<stdio.h>
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
int main()
{
int s[9],i,k,start;
int a[9]={0,-2,-3,4,-1,-2,1,5,-3};
s[0]=0;
for(i=1;i<9;i++)
{
s[i]=max(s[i-1]+a[i],a[i]);
if(s[i]==a[i])
start=i;
}
k=i-1;
printf("%d",s[k]);
return 0;
}
~

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

Kadane’s Algorithm, including sum for negative numbers:

``````public static void main(String[] args) {

int[] arr = { 1, 2, -3, -4, 5, -2, -4 };
int maxPositiveSum = 0;
int maxPositiveStart = 0;
int maxPositiveEnd = 0;
int currentPositiveStart = 0;
int currentPositiveSum = 0;

int maxNegativeSum = 0;
int maxNegativeStart = 0;
int maxNegativeEnd = 0;
int currentNegativeStart = 0;
int currentNegativeSum = 0;

for (int i = 0; i < arr.length; i++) {
currentPositiveSum += arr[i];
currentNegativeSum += arr[i];
if (currentPositiveSum < 0) {
currentPositiveSum = 0;
currentPositiveStart = i + 1;
} else if (currentPositiveSum > maxPositiveSum) {
maxPositiveSum = currentPositiveSum;
maxPositiveStart = currentPositiveStart;
maxPositiveEnd = i;
}
if (currentNegativeSum > 0) {
currentNegativeSum = 0;
currentNegativeStart = i + 1;
} else if (Math.abs(currentNegativeSum) > maxNegativeSum) {
maxNegativeSum = Math.abs(currentNegativeSum);
maxNegativeStart = currentNegativeStart;
maxNegativeEnd = i;
}
}
if (Math.abs(maxNegativeSum) > maxPositiveSum) {
System.out.println("Start: " + maxNegativeStart + ", Emd: " + maxNegativeEnd + ", Sum: "
+ Math.abs(maxNegativeSum));
} else {
System.out.println("Start: " + maxPositiveStart + ", Emd: " + maxPositiveEnd + ", Sum: " + maxPositiveSum);
}
}``````

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

``````int maxs(int a[],int n)
{
int sum=a[0],max=a[0],prev=a[0];
for(int i=1;i<n;i++)
{
sum=sum+a[i];
if (( prev < 0&& sum > 0 ) || ( prev > 0 && sum < 0 ))
{
sum=a[i];

}
if(max<abs(sum))
{
max=sum;
}
prev=sum;

}
return (abs(max));
}``````

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.