## Linkedin Interview Question for Software Engineer / Developers

Country: United States

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

For the maximum product CONTINUOUS SUBSEQUENCE problem: it's little bit more complicated.

We can do it by DP:

Let define two arrays Ne[] and Po[] as follow:

``````Ne[i] = minimum negative product of continuous subsequence that finishes at i-th number;

Po[i] = maximum positive product of continuous subsequence that finishes at i-th number;``````

Initial values:

``````Ne[0] = min(-1,arr[0]);
Po[0] = max(1,arr[0]);``````

Recursive formula:

``````Ne[i] = min  ( arr[i], arr[i] * Po[i-1], arr[i] * Ne[i-1]);
Po[i] = max  ( arr[i], arr[i] * Po[i-1], arr[i] * Ne[i-1]);``````

``res = max(Po[i]);``

To avoid integer representation overflow when multiplying, we can store the (+,-) sign separately, and working on logarithmic values of positive numbers only, with note: log (a*b) = log a + log b;

``Please correct me if I am wrong, thanks!``

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

What would be the run time complexity for this? Linear/O(n) right?

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

Do you really need the logarithms? Would the product not be at its maximum if the absolutes of the values are at their maximum values, given that the product is positive? Therefor, could we not simply work with the sums?

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

Ne[0] should be Math.min(1, inputArr[0]); or otherwise it will alter the result
for example { 2, -3, -2, -2, -40,-5};
Po[1] = 3 instead of just -3 as it takes the max of { -1*-3, -3, 2*-3} if Ne[0] =1
This will cause the result to be 2400 {3,-2, -2, -40, -5} instead of 960 {2, -3, -2, -2, -40}

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

It says product subset not subsequence!

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

Include all positive numbers in the product subset. Suppose there are n negative integers in the input set. If n is even, then include all of the negative numbers in the product set. If n is odd, then include (n-1) with the maximum absolute values.

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

Bingo!

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

Let K be the number of negative elements in the array, and x be the largest negative number.

If K is even: keep all.
if K is odd: eliminate x, keep all remaining.

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

I think x should be smallest negative number

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

Oh, so you are going to keep all those nice zeroes, too? :D Still, I was thinking along those lines, too.

I am kind of in a LINQ mood today. Maybe I should start writing solutions like those in Haskell or Python.

``````static void LargestProductSet()
{
IEnumerable<int> a = new int[] { -9, -8, -1, 4, 9, -9, 0, -2 };

var zero = a.Where(i => i != 0);
var prod = zero.Aggregate((i, j) => i * j);
var maxs = prod > 0 ? zero : zero.Except(new[] { a.Where(i => i < 0).Max() });
}``````

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

However, how about we reduce this even a bit more?

What are we really interested in when deciding which elements to keep? Answer: if the product of the subset without zeroes is negative or not.

When is that subset's product negative? When the count of negative elements is odd!

So why don't we just write that?

``````static void LargestProductSet()
{
IEnumerable<int> a = new int[] { -9, -8, -1, 4, 9, -9, 0, -2 };

var nz = a.Where(i => i != 0);
var neg = a.Where(i => i < 0);
var maxs = neg.Count() % 2 == 0 ? nz : nz.Except(new[] { neg.Max() });
}``````

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

{{
public static int[] findMax(int[] values) {
int bestProduct = 0;
int bestStart = 0;
int bestEnd = 0;
int currProduct = 0;
int currStart = 0;
int bestSmallestNegIdx = 0;
int currSmallestNeg = Integer.MIN_VALUE;
int currSmallestNegIdx = 0;
for (int i = 0; i < values.length; ++i) {
if (currProduct == 0) {
currProduct = 1;
currStart = i;
currSmallestNeg = Integer.MIN_VALUE;
currSmallestNegIdx = 0;
}
if (values[i] < 0 && values[i] > currSmallestNeg) {
currSmallestNeg = values[i];
currSmallestNegIdx = i;
}
currProduct *= values[i];
if (Math.abs(currProduct) > Math.abs(bestProduct)) {
bestProduct = currProduct;
bestSmallestNegIdx = currSmallestNegIdx;
bestStart = currStart;
bestEnd = i;
}
}
if (bestProduct < 0) {
int left = 1;
int right = 1;
int i;
int j;
for (i = bestSmallestNegIdx - 1; i >= bestStart; --i) {
left *= values[i];
}
for (j = bestSmallestNegIdx + 1; j <= bestEnd; ++j) {
right *= values[j];
}
if (left > right) {
bestEnd = bestSmallestNegIdx - 1;
}
else {
bestStart = bestSmallestNegIdx + 1;
}
}
return new int[] { bestStart, bestEnd };
}
}}
O(n), O(1)

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

I tried your solution on {-9,-8,-1,4,9,-9,-2} and its giving that {4,9,-9,-2} as result [3,6]
. Shouldn't it be {-9,-8,-1,4,9,-9} [0,5]

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

No, the answer should be {-9, -9, -8, -2, 4, 9}

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

1. Just ignore anything between -1 and 1.
2. Multiply everything else.
3. If product less than 0, divide the product by the negative number with least absolute value.

Example 1 :- 4 8 3 -5 -9 0.5 -0.5 12
1. Ignore 0.5 and -0.5
2. Product = 4*8*3*-5*-9*12
3. Product > 0, so return product

Example 2 :- 4 8 3 -5 -9 0.5 -0.5 12 -14
1. Ignore 0.5 and -0.5
2. Product = 4*8*3*-5*-9*12*-14
3. Product > 0, so return (product divided by -5)

This is O(n) time and O(1) space complexity.

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

I just realized it is only integers. In that case we can even skip step 1.

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

This Java code works, at least for the cases that I have tried:

``````private static void maxProduct(int[] input) {
int max = input[0];
int curPos = input[0];
int curNeg = input[0];
int posStart = 0;
int posEnd = 0;
int negStart = 0;
int negEnd = 0;
int maxStart = 0;
int maxEnd = 0;

for (int i=1; i<input.length;i++) {
curPos *= input[i];
curNeg *= input[i];
if (curPos > max) {
max = curPos;
posEnd = i;
maxStart = posStart;
maxEnd = posEnd;
} else if (curPos < 1 && i < input.length - 1) {
curPos = input[i] > 0 ? input[i]:1;
posStart = input[i] > 0 ? i : i+1;
}
negEnd = i;
if(curNeg > max) {
max = curNeg;
maxStart = negStart;
maxEnd = negEnd;
}

if (curNeg == 0 && i < input.length - 1) {
curNeg = 1;
negStart = i+1;
}
}
System.out.println(max);
System.out.println(maxStart + "," + maxEnd);
}``````

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

doesn't work on {-2, -3, -6} - returns 6 but actually 18 is answer

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

Below is an O(n) solution with O(1) space complexity:

``````public int maxProd2(int[] a) throws Exception{
if (a == null || a.length == 0)
throw new Exception("Invalid input");
int prod = 1;
int firstNegIdx=-1;
int firstNegProd=1;
int lastNegIdx=-1;
int lastNegProd=1;
int negCnt=0;
for (int i=0;i<a.length;i++) {
prod*=a[i];
if (a[i] < 0) {
negCnt++;
if (firstNegIdx < 0) {
firstNegIdx = i;
firstNegProd=prod;
}
lastNegIdx = i;
lastNegProd=prod/a[i];
}
}
if ( (negCnt & 1) == 0)
return prod;
else {
int p1 = prod / firstNegProd;
int p2 = lastNegProd;
return (p1 > p2 ? p1 : p2);
}
}``````

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

doesn't work with {0, 2, 5, 0} - should give 10 but gives 0

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

How about this? Arrange the numbers such that all positive numbers are in the beginning and all the negative numbers are in the end or vice versa. Include all the positive numbers in the resulting subset (if there are any). Sort the negative numbers and keep adding the negative numbers to the result in pairs, starting from the smallest until there are no or just 1 negative number(s) left.

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

Does the result subset allow duplicate elements? If yes, below is a linear solution.
Scan all numbers, skip 0 and keep track of the largest negative number and count of negative numbers. Add the numbers into a vector. If count is even, the vector is the result. Else remove the first occurance of the largest negative number for the vector.

If the subset does not allow duplicate numbers(as the mathematical definition of a "set" specs), dedupe the numbers in input then apply the above algorithm. The complexity is still O(n), but need O(n) space for a hash table.

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

plz tell me if i am wrong

``````int msx_sum(int a[],int n)
{
int max=a[0], curr[n];
curr[0]=a[0];
curr[1]=a[0]*a[1] > a[1] ? a[0]*a[1] : a[1];
max= max>curr[1]? max:curr[1];
for(int i=2;i<n;i++)
{
if(a[i]<0)
{
if(a[i-1]<0)
curr[i]=curr[i-2]*a[i]*a[i-1];
else curr[i]=a[i];
}
else
curr[i]= curr[i-1]*a[i]> a[i] ?curr[i-1]*a[i]: a[i];
if(max<curr[i])
max=curr[i];
}
return max;``````

}

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

``````int maxProductSubset(int input[],int len){
int prod = 1;
int negMin=9999;
for(int i=0;i<len;i++){
if(input[i]!=0)
prod = prod*input[i];
}
if(prod>0) //all positives or even number of negatives
return prod;
else{ //odd number of negative numbers
for(int i=0;i<len;i++){
if(input[i]<0){
if(((input[i])*(-1)) < negMin)
negMin = ((input[i])*(-1));
}
}
return prod/((negMin)*(-1));
}
}``````

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

This solution uses O(1) space and has O(n) time complexity

``````public int maxProduct(int[] A) {
if (A==null || A.length==0) {
return 0;
}

int pCurrentMax = A[0],
pMaxSoFar=A[0],
pCurrentMin = A[0],
pTempMin, pTempMax;
for (int i =1; i < A.length; i++) {
pTempMax = Math.max(Math.max(A[i]*pCurrentMax, A[i]*pCurrentMin), A[i]);
pTempMin = Math.min(Math.min(A[i]*pCurrentMax, A[i]*pCurrentMin), A[i]);
pMaxSoFar = Math.max(pTempMax, pMaxSoFar);
pCurrentMin = pTempMin;
pCurrentMax = pTempMax;

}
return pMaxSoFar;
}``````

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

Why downvote ?

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

With same definition as above, P[i] --> maximum positive product ending at i, N[i] --> minimum negative product ending at i.

if (a[0] != 0) {
P[0] = max(1, a[0]);
N[0] = min(1, a[0]);
} else {
P[0] = 0;
N[0] = 0;
}

if (a[i] < 0) {
P[i] = max (1, N(i-1) * a[i]);
N[i] = min (1, P(i-1) * a[i]);
}
else if (a[i] > 0) {
P[i] = max(1, P[i-1] * a[i]);
N[i] = min(1, N[i-1] * a[i]);
} else {
P[i] = 1;
N[i] = 1;
}

Note that it has not be 1 not -1 for N[i] .. run via an example.

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

``````public class MaximumProduct {

public static int getMaximumProduct(int[] input) {
int max = input[0];
int min = input[0];

int maxResult = input[0];

for(int i=1; i<input.length; i++) {
int temp = max;
max = Math.max(Math.max(input[i], temp*input[i]), min*input[i]);
if(max > maxResult) {
maxResult = max;
}

min = Math.min(Math.min(input[i], temp*input[i]), min*input[i]);
}

return maxResult;
}

public static void main(String args[]) {
int[] input = {-3,0,-4};
System.out.println(MaximumProduct.getMaximumProduct(input));
}

}``````

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

``````public static int maxProductSubset(int[] array) {
int retVal = 1;
int count=0;
int max = Integer.MIN_VALUE;
boolean allPositiveAreZero = true;

for(int i : array) {
if(i!=0)
retVal *= i;

if(i<0) {
count++;
max = (i>max) ? i : max;
}

if(i>0) {
allPositiveAreZero = false;
}
}

if(count%2==0) {
return retVal;
}

if(count==1 && allPositiveAreZero) {
return 0;
}

return retVal / max;
}``````

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

``````public static int maxProductSubset(int[] array) {
int retVal = 1;
int count=0;
int max = Integer.MIN_VALUE;
boolean allPositiveAreZero = true;

for(int i : array) {
if(i!=0)
retVal *= i;

if(i<0) {
count++;
max = (i>max) ? i : max;
}

if(i>0) {
allPositiveAreZero = false;
}
}

if(count%2==0) {
return retVal;
}

if(count==1 && allPositiveAreZero) {
return 0;
}

return retVal / max;
}``````

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

``````public static int maxProductSubset(int[] array) {
int retVal = 1;
int count=0;
int max = Integer.MIN_VALUE;
boolean allPositiveAreZero = true;

for(int i : array) {
if(i!=0)
retVal *= i;

if(i<0) {
count++;
max = (i>max) ? i : max;
}

if(i>0) {
allPositiveAreZero = false;
}
}

if(count%2==0) {
return retVal;
}

if(count==1 && allPositiveAreZero) {
return 0;
}

return retVal / max;``````

}

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

My main idea is sort, rotate, and sublist for right k element.

After sort, max product for positive integer is most right of list.
But this question can have negative integer.
Product of two negative integer can be greater than product of any positive integer.

So I did two left rotate. It can move two negative integer on the right most of list.
Then I calculated product of right most K integers.
I did repeat left rotate until finding max product.

{{
public int getProduct(List<Integer> list){
int product = 1;

for(Integer num : list){
product = product * num;
}

return product;
}

public List<Integer> getMostRight(List<Integer> input, int k){
int right = input.size();
int left = input.size() - k;
return input.subList(left, right);
}

public List<Integer> getMaxProduct(List<Integer> input, int k){

Collections.sort(input);

int maxProduct = Integer.MIN_VALUE;
for(int shift = 0; Math.abs(shift) < input.size(); shift=shift-2){

List<Integer> subList = getMostRight(input, k);

if( maxProduct < getProduct(subList) ){
maxProduct = getProduct(subList);
}else{
Collections.rotate(input, 2);
break;
}

Collections.rotate(input, -2);
}

return getMostRight(input, k);
}
}}

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

My main idea is sort, rotate, and sublist for right k element.

After sort, max product for positive integer is most right of list.
But this question can have negative integer.
Product of two negative integer can be greater than product of any positive integer.

So I did two left rotate. It can move two negative integer on the right most of list.
Then I calculated product of right most K integers.
I did repeat left rotate until finding max product.

``````public int getProduct(List<Integer> list){
int product = 1;

for(Integer num : list){
product = product * num;
}

return product;
}

public List<Integer> getMostRight(List<Integer> input, int k){
int right = input.size();
int left = input.size() - k;
return input.subList(left, right);
}

public List<Integer> getMaxProduct(List<Integer> input, int k){

Collections.sort(input);

int maxProduct = Integer.MIN_VALUE;
for(int shift = 0; Math.abs(shift) < input.size(); shift=shift-2){

List<Integer> subList = getMostRight(input, k);

if( maxProduct < getProduct(subList) ){
maxProduct = getProduct(subList);
}else{
Collections.rotate(input, 2);
break;
}

Collections.rotate(input, -2);
}

return getMostRight(input, k);
}``````

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

``````public int getProduct(List<Integer> list){
int product = 1;

for(Integer num : list){
product = product * num;
}

return product;
}

public List<Integer> getMostRight(List<Integer> input, int k){
int right = input.size();
int left = input.size() - k;
return input.subList(left, right);
}

public List<Integer> getMaxProduct(List<Integer> input, int k){

Collections.sort(input);

int maxProduct = Integer.MIN_VALUE;
for(int shift = 0; Math.abs(shift) < input.size(); shift=shift-2){

List<Integer> subList = getMostRight(input, k);

if( maxProduct < getProduct(subList) ){
maxProduct = getProduct(subList);
}else{
Collections.rotate(input, 2);
break;
}

Collections.rotate(input, -2);
}

return getMostRight(input, k);
}``````

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

``public void``

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

``````public int getProduct(List<Integer> list){
int product = 1;

for(Integer num : list){
product = product * num;
}

return product;
}
public List<Integer> getMostRight(List<Integer> input, int k){
int right = input.size();
int left = input.size() - k;
return input.subList(left, right);
}
public List<Integer> getMaxProduct(List<Integer> input, int k){

Collections.sort(input);

int maxProduct = Integer.MIN_VALUE;
for(int shift = 0; Math.abs(shift) < input.size(); shift=shift-2){

List<Integer> subList = getMostRight(input, k);

if( maxProduct < getProduct(subList) ){
maxProduct = getProduct(subList);
}else{
Collections.rotate(input, 2);
break;
}

Collections.rotate(input, -2);
}

return getMostRight(input, k);
}``````

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

HH

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

My main idea is sort, rotate, and sublist for right k element.

After sort, max product for positive integer is most right of list.
But this question can have negative integer.
Product of two negative integer can be greater than product of any positive integer.

So I did two left rotate. It can move two negative integer on the right most of list.
Then I calculated product of right most K integers.
I did repeat left rotate until finding max product.

``````public int getProduct(List<Integer> list){
int product = 1;

for(Integer num : list){
product = product * num;
}

return product;
}
public List<Integer> getMostRight(List<Integer> input, int k){
int right = input.size();
int left = input.size() - k;
return input.subList(left, right);
}
public List<Integer> getMaxProduct(List<Integer> input, int k){

Collections.sort(input);

int maxProduct = Integer.MIN_VALUE;
for(int shift = 0; Math.abs(shift) < input.size(); shift=shift-2){

List<Integer> subList = getMostRight(input, k);

if( maxProduct < getProduct(subList) ){
maxProduct = getProduct(subList);
}else{
Collections.rotate(input, 2);
break;
}

Collections.rotate(input, -2);
}

return getMostRight(input, k);
}``````

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.