InMobi Interview Question


Country: India
Interview Type: Phone Interview




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

.....geeksforgeeks.org/maximum-product-subarray/

- basskeyz July 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- Anonymous June 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- Anonymous June 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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 ..........

- aka June 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- Anonymous June 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- aka June 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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;
   }

- shaktiman June 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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])

- whatevva' June 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- Cheran June 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

sites.google.com/site/spaceofjameschen/home/array/find-the-maximum-contiguous-subsequence-product----inmobi

- Anonymous June 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));

}

- as November 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- PKT June 12, 2013 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More