InMobi Interview Question
Country: India
Interview Type: Phone Interview
A O(n^2) time and space solution seems straightforward:
- make a NxN table where [i][j] is the product between number at i-th and j-th position. If you calculate it in the right order the calculations will take O(n^2) time and than you traverse the matrix to find the maximum (or you store it during matrix filling!).
Let's try O(n) with O(1) time!
- let's notice 2 things:
-- if we know our product is + and the next number is - than the remaining product will be only smaller
-- 0 helps us only if our current product is - (which should never happen when we take into account the previous observation)
So maybe:
- count the number of - numbers
- count the product from index 0 until the next number is 0 in the array or our current product is + and the next number is the only "-" number ahead (we keep track of - numbers remaining)
- when we hit such a condition we store our current product in "max" if it is bigger than previous max
- we need to start counting the product again from the index of the 2nd "-" number we found if the next number is the last "-" or from our current number plus 2 positions if the next number in the array is 0.
Following the above example [7,-3,-1,2,-40,0,3,6]
- minuses = 3
- we go from 7 up to 2 (next number is -40, the last minus) and we store as product=42
- we go back to -1 (second - number we saw) and compute the product till we hit -40 (next number is 0) and store new max as 80 since 80>42
- we start from 3 (-40 plus 2 positions) and go to the end but we skip this product as it is only 18
We do skip quite a few places back but notice we will skip only at most once so there will be 2n traversals in the worst case.
Opinions welcome.
@Up: well cannot edit as anonymous, but I just realized that when we have to back up (because the next number would change our product permanently to a - number) we don't need to traverse the same elements again, we just need to divide our current product by the first number in our current subarray and continue.
@up: would you mind explaining O(n^2) approach?
-3 7 2 0 -5 7 -2 -2 2, the maximum subsequence product = -5 * 7 * -2 = 70
You are just taking into account only two numbers so ..........
@Up: as I see the O(n^2) approach:
- create a NxN matrix of doubles (or whatever the range of our values can be)
- on the diagonal put the i-th number of our array
- [0][0] is simply the first value in the array (the product in the range (0,0) inclusive)
- product [i][j] will be [i][j-1]*A[j], right?
- find the max in the array
There are ((n^2)/2)+n values in the array which given us O(n^2) time and space complexity.
But as I said I think the O(n) time and O(1) solution works fine. Basically we partition the array around 0s and find the max product of each subarray as I described.
P.S. I already flagged the double post I did below, hope someone will delete it.
@up: just to make it better.
- create a NxN matrix of doubles (or whatever the range of our values can be)
- on the diagonal put the i-th number of our array
- [0][0] is simply the first value in the array (the product in the range (0,0) inclusive)
- product [i][j] will be [i][j-1]*A[j]
- after the first row is populated.For second row start from 1,1 and do the same things as done for row 0.For third row start from 2,2 and so on....
In the end find the maximum by searching in the entire N*N matrix or when you are multiplying keep the max found till now in a variable and print it in the end.
o(n^2) solution
static int maximumSubArrayProductBad(int[] array) {
int maxprod = 0;
for (int i = 0; i < array.length; i++) {
int localProd = 1;
for (int j = i; j < array.length; j++) {
localProd = localProd * array[j];
if (localProd > maxprod) {
maxprod = localProd;
}
}
}
return maxprod;
}
Following is the code in python. Conceptually, we can think of the array being split into sub-arrays by elements that are "0" since the resulting max subarray will not straddle a "0" (unless the max product is < 0). So, [7 -3 -1 2 -40 0 3 6 ] => [7 -3 -1 2 -40], [3 6]
Now we try to find the max contiguous subarrays in each of the split subarrays. In order to do this we keep track of three products in each split subarray. For split subarray [7 -3 -1 2 -40]:
1. total product = product( [7, -3, -1, 2, -40] )
2. product after first negative element = product([-1, 2, -40])
3. product before the last negative element = product( [7, -3, -1, 2])
max product of split sub-array is = max( product#1, product#2, product#3)
max product = max(max products of all split sub-arrays)
The code below implements the above logic in a single pass of the array, so it is not exactly as described above
def max_subarray_prod(num_list):
num_list.append(0)
number_of_allnums = 0
max_prod = None
prod_total = None
prod_to_last_negnum = None
prod_from_first_negnum = None
first_negative_num_encountered = False
for num in num_list:
if num == 0:
if number_of_allnums == 0:
continue
max_prod = max(max_prod, prod_total,\
prod_to_last_negnum, \
prod_from_first_negnum)
number_of_allnums = 0
prod_total = None
prod_to_last_negnum = None
prod_from_first_negnum = None
first_negative_num_encountered = False
else:
number_of_allnums += 1
prod_to_last_negnum = prod_total if num < 0 \
else prod_to_last_negnum
prod_total = num if prod_total is None else prod_total*num
if first_negative_num_encountered:
prod_from_first_negnum = num if prod_from_first_negnum \
is None else prod_from_first_negnum*num
if num < 0:
first_negative_num_encountered = True
return max_prod
print max_subarray_prod([ 7, -3, -1, 2, -40, 0, 3, 6])
print max_subarray_prod([ -3, 7, 2, 0, -5, 7, -2, -2, 2])
#include <stdio.h>
#include <assert.h>
#include <algorithm>
#include <iostream>
enum direction_t{
LEFT,
RIGHT
};
int
find_directional_max(direction_t type, int *array, int size)
{
if (size == 0) {
assert(false);
}
if (size == 1) {
return array[0];
}
int start = 0, end = 0;
int prev_max = 0;
if (type == RIGHT) {
start = 0;
end = size - 1;
} else if (type == LEFT) {
start = size - 1;
end = 0;
} else {
assert(false);
}
int pos = start;
int max = 0;
while ( pos != end) {
max += array[pos];
if (max > prev_max) {
prev_max = max;
}
if (start > end) {
pos--;
} else {
pos++;
}
}
return prev_max;
}
int
find_sequence_max(int *array, int size)
{
if (size == 0) {
assert(false);
}
if (size == 1) {
return array[0];
}
int start = 0;
int mid = size/2;
int left_max = find_sequence_max(array+start, mid);
int right_max = find_sequence_max(array+(mid), size - mid);
int left_end_max = find_directional_max(LEFT, array+start, mid);
int right_begin_max = find_directional_max(RIGHT, array+(mid), size - mid);
int max = std::max(left_max, right_max);
if ((left_end_max + right_begin_max) > max) {
return (left_end_max + right_begin_max);
}
return max;
}
int main()
{
int array[10] = { 1, -1, 3,4,5,-6,7,8, -9, 10};
std::cout << "value is " << find_sequence_max(array, 10) << std::endl;
return 0;
}
Use dynamic programming. Store minimum product subsequence as well as the maximum product contiguous subsequence;
#include<stdio.h>
int min (int a,int b);
int max (int a,int b);
int smallestproduct(int A[] ,int size)
{int big[100], small[100],i,greatest;
big[0]=A[0];
small[0]=A[0];
for(i=1;i<size;i++)
if(A[i]<0)
{big[i]=max(A[i],A[i]*small[i-1]);
small[i]=min(A[i],A[i]*big[i-1]);
}
else
{big[i]=max(A[i],A[i]*big[i-1]);
small[i]=min(A[i],A[i]*small[i-1]);
}
greatest=big[0];
for(i=1;i<size;i++)
if(big[i]>greatest)
greatest=big[i];
return greatest;
}
int min (int a,int b)
{if (a<b)
return a;
else
return b;
}
int max(int a,int b)
{if(a>b)
return a;
else
return b;
}
int main()
{int A[1000];int size,i;
scanf("%d",&size);
for(i=0;i<size;i++)
scanf("%d",&A[i]);
printf("\n %d",smallestproduct(A,size));
}
Logic:
1) Have all the subset of array separated by 0 for analysis. [because having zero in ant subset will make product 0]
2) Now in all subset of non-zero numbers follow below steps:
2.1) In case number of negative element is even find product of all numbers and keep this product in a global variable to compare with other products
2.2) In case odd numbers of negative elements divide subset into two more subset separated by first negative element
Parallely divide subset into two more subset separated by last negative element
---In this way we will get 4 possible products for a subset get the Max and proceed for further sub-set analysis.
.....geeksforgeeks.org/maximum-product-subarray/
- basskeyz July 21, 2013