## Linkedin Interview Question for Software Engineer / Developers

Country: United States

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

1. To find maximum sum SUBSET: eliminate all negative integers, keep only positive ones. If all numbers are negative, choose the empty subset.

2. To find maximum sum of continuous subsequence: keep summing up numbers and record maximum sum. If the sum is negative, reset it to be 0.

``````sum = 0;
maxSum = 0;
for i = 1..n
sum += array[i];
maxSum = max (maxSum, sum);
if (sum<=0) sum = 0;``````

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

I think this question wants you to keep track of the range that those numbers constituting that sum occupy. It can easily be added into your solution. I would give a candidate bonus points if they also knew that this algorithm is commonly known as "Kadane's Algorithm" and maybe even that a linear time algorithm was found in 1984. To me it shows someone treats computer science as more than just being a machine for coding interviews, in order to become a widget at big corp. :D

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

Does it have to be a continuous subsequence?
If so, there is a linear time solution to this. You might want to lookup max subarray/ Kadane's algo

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

If it does not have to be a continuous subsequence,
just pick out all the positive integers in the array and add them up, this is your answer

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

This is apparently computing max continuous subsequence. Nobody would actually think LinkedIn pays you 130K for picking out all the positive numbers in an array right?

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

haha, agreed.

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

The maximum subset with negative set of integers can be found out by first eliminating negative numbers and then finding out maximum subset using Kadane's algorithm. If all the numbers are negative that is the sum <= 0 then return 0 as described above

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

This was pretty much copied and pasted from the wikipedia page for Maximum_subarray_problem:

``````private int LargestSum(int[] numbers)
{
if (numbers == null || numbers.Length == 0)
{
return 0;
}

int max_so_far = numbers;
int max_ending_here = numbers;

for (int i = 1; i < numbers.Length; i++)
{
if (max_ending_here < 0)
{
max_ending_here = numbers[i];
}
else
{
max_ending_here += numbers[i];
}

if (max_ending_here >= max_so_far)
{
max_so_far = max_ending_here;
}
}

return max_so_far;
}``````

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

int max_sum(int a[],int n)
{
int max=a, curr=0;
for(int i=0;i<n;i++){
if(curr<0)
curr=a[i];
else
curr+=a[i];
if(max<curr)
max=curr;
}
return curr;
}

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

``````int max_sum(int a[],int n)
{
int max=a, curr=0;
for(int i=0;i<n;i++){
if(curr<0)
curr=a[i];
else
curr+=a[i];
if(max<curr)
max=curr;
}
return curr;
}``````

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

``````static int maxSubArraySum(int[] data){
int p1 = 0;
int max_so_far = Integer.MIN_VALUE;
int sum  = 0;
for(int i = 0; i < data.length; i++) {
int temp = sum + data[i];
if(temp > max_so_far)   max_so_far = temp;
if(temp < 0) {
sum = 0;
} else {
sum = temp;
}
}
return max_so_far;
}``````

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

``````public int maxSubArray(int[] prices) {
if (prices == null || prices.length < 1) {
return 0;
}

int currentMax = prices, max = prices;
for (int i=1; i < prices.length; i++) {
currentMax = Math.max(prices[i], currentMax+prices[i]);
max = Math.max(max, currentMax);
}
return 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.