Linkedin Interview Question Software Engineer / Developers
Country: United States
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?
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}
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.
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.
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.
How about this?
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() });
}
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() });
}
{{
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)
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]
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.
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);
}
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);
}
}
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.
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.
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;
}
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));
}
}
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;
}
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.
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));
}
}
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;
}
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;
}
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;
}
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);
}
}}
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);
}
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);
}
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);
}
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);
}
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:
Initial values:
Recursive formula:
The answer is
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;
- ninhnnsoc April 23, 2014