Google Interview Question


Country: United States




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

What matters is the number of negative values. If it's even return the entire array.

If it's odd keep track of: first negative (position, value, product of positive subarray before it) and last negative (position, value, product of positive array after it).

If the product of first negative value and the positive subarray before it is smaller than the product of last negative value and the positive subarray after it the maximum product subarray is from 0 to last negative value (not included.)

Otherwise the maximum product subarray is from first negative (not included) to the end.

Edge case: positive subarray has zero length (original array starts and/or ends with negative value.) In this case the product of subarray is zero and we only need to look at the negative value itself.

- gxg March 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void calcProd(int [] ints)
        {
            int posStart = 0;
            int postEnd = ints.Length;
            if(ints.Length < 2)
            {
                Console.WriteLine(ints[0]);
                return;
            }
            if(ints.Length == 0)
            {
                Console.WriteLine(0);
                return;
            }


            // int [] iList = {1,5,-6,88,5,-47,9,-65,6 };
            int max = 0;
            int runningTotal = 0;
            int subArrayStart = 0;
            int subArrayEnd = 0;
            while (posStart < ints.Length)
            {
                runningTotal = calcSubArray(posStart, postEnd, ints);
                if (runningTotal > max)
                {
                    max = runningTotal;
                    subArrayStart = posStart;
                    subArrayEnd = postEnd;
                }
                posStart = posStart + 1;
            }
            posStart = 0;
            while (postEnd > posStart)
            {
                runningTotal = calcSubArray(posStart, postEnd, ints);
                if (runningTotal > max)
                {
                    max = runningTotal;
                    subArrayStart = posStart;
                    subArrayEnd = postEnd;
                }
                    
                postEnd = postEnd - 1;
            }
            Console.WriteLine($"Max is {max}");
            Console.WriteLine($"start of subarray {subArrayStart} and end of subarray {subArrayEnd} ");

        }
        public static int calcSubArray(int posStart, int posEnd, int  [] ints)
        {
            int runningtotal = 1;
            for(int i = posStart; i < posEnd; i++)
            {
                runningtotal = runningtotal * ints[i];
            }
            Console.WriteLine(runningtotal);
            return runningtotal;
        }

- waged7 March 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MaxSubArrayProduct {

	static class Data{
		int product;
		int startIndex;
		int endIndex;
		Data(){
			super();
			this.product = Integer.MIN_VALUE;
			this.startIndex = -1;
			this.endIndex = -1;
		}

		public Data(int product, int startIndex, int endIndex) {
			super();
			this.product = product;
			this.startIndex = startIndex;
			this.endIndex = endIndex;
		}

		@Override
		public String toString() {
			return "Data [product=" + product + ", startIndex=" + startIndex + ", endIndex=" + endIndex + "]";
		}
	}

	static Data ProcessSubArray(int[] arr, int startIndex, int endIndex){
		if (startIndex == endIndex){
			return new Data(arr[startIndex], startIndex, endIndex);
		}else{
			int val = 1;
			int firstNegativeIndex = -1;
			int lastNegativeIndex = -1;

			for (int i=startIndex; i<=endIndex; i++){
				val *= arr[i];
				if (arr[i] <0){
					if (firstNegativeIndex == -1){
						firstNegativeIndex = i;
					}
					lastNegativeIndex = i;
				}
			}

			if (val < 0){
				int multiplierFirst = 1;
				for (int j=startIndex; j<=firstNegativeIndex; j++){
					multiplierFirst*=arr[j];
				}
				int multiplierLast = 1;
				for (int j=lastNegativeIndex; j<=endIndex; j++){
					multiplierLast*=arr[j];
				}
				if (val/multiplierFirst > val/multiplierLast){
					startIndex = firstNegativeIndex+1;
					val = val/multiplierFirst;
				}else{
					endIndex = lastNegativeIndex -1;
					val = val/multiplierLast;
				}
			}
			Data data = new Data(val, startIndex, endIndex);
			return data;
		}
	}

	private static void ProcessArr(int[] arr) {
		if (arr == null || arr.length <=0){
			System.out.println(new Data(Integer.MIN_VALUE, -1, -1));
			return;
		}
		Data maxData = new Data();
		int startIndex = -1;
		for (int i=0; i<arr.length; i++){
			if (arr[i] == 0){
				if (startIndex != -1){
					Data data = ProcessSubArray(arr, startIndex, i-1);
					if (data.product>maxData.product){
						maxData = data;
					}
					startIndex =-1;
				}
				if (0>maxData.product){
					maxData = new Data(0, i, i);
				}
			} else {
				if (startIndex == -1){
					startIndex = i;
				}
			}
		}

		if (startIndex!=-1){
			Data data = ProcessSubArray(arr, startIndex, arr.length-1);
			if (data.product>maxData.product){
				maxData = data;
			}
		}

		System.out.println(maxData.toString());
	}

	public static void main(String[] args){
		int arr[] = {0, 1, 2, -6, 8, 10, -9, -5, 1, 0, 8, 6, 5, 0};
		ProcessArr(arr);
		arr = new int[]{};
		ProcessArr(arr);
		arr = new int[]{0};
		ProcessArr(arr);
		arr = new int[]{-1};
		ProcessArr(arr);
		arr = new int[]{2};
		ProcessArr(arr);
		arr = new int[]{-3, 2};
		ProcessArr(arr);
		arr = new int[]{3, -2};
		ProcessArr(arr);
		arr = new int[]{-3, 2, 0, 0 , 3, -2};
		ProcessArr(arr);
		arr = new int[]{0, 0, -3, 2, 0, 0 , 3, -2, 0, 0};
		ProcessArr(arr);
	}
}

- havefun March 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def get_max_indices(nums):
    after_first_negative = 1
    before_last_negative = 1
    total = 1

    first_negative_idx = None
    last_negative_idx = None

    for idx, num in enumerate(nums):
    	if num < 0:
            last_negative_idx = idx
            before_last_negative = total

            if not first_negative_idx:
                first_negative_idx = idx

            if first_negative_idx and first_negative_idx != idx:
                after_first_negative *= num

            total *= num

    if total > 0:
        print(0, len(nums))

    elif after_first_negative > before_last_negative:
        print(first_negative_idx + 1, len(nums))

    else:
        print(0, last_negative_idx - 1)
    
    print(max(total, after_first_negative, before_last_negative))

- zhebrak March 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def get_max_indices(nums):
    after_first_negative = 1
    before_last_negative = 1
    total = 1

    first_negative_idx = None
    last_negative_idx = None

    for idx, num in enumerate(nums):
        if num < 0:
            last_negative_idx = idx
            before_last_negative = total

            if not first_negative_idx:
                first_negative_idx = idx

        if first_negative_idx and first_negative_idx != idx:
            after_first_negative *= num

        total *= num

    if total > 0:
        print(0, len(nums))

    elif after_first_negative > before_last_negative:
        print(first_negative_idx + 1, len(nums))

    else:
        print(0, last_negative_idx - 1)
    
    print(max(total, after_first_negative, before_last_negative))

- zhebrak March 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

* This solution assumes extra iteration to calculate the array product first time.
1. Iterate over array.
2. Calculate the prod to the left of current element or right of current element.
3. Update the result with max.

int MaxProdSum::find(int *a, int n, int p, int &resI, int &resJ) {
    int mxProd = INT_MIN;
    int mxI = -1, mxJ = -1;
    int curProd = 1;

    for (int i = 0; i < n; i++) {
        curProd *= a[i];
        if (curProd > mxProd) {
            mxProd = curProd;
            mxI = 0;
            mxJ = i;
        }
        if (p > mxProd) {
            mxProd = p;
            mxI = i;
            mxJ = n - 1;
        }

        p /= a[i];
    }

    resI = mxI;
    resJ = mxJ;
    return mxProd;
}

- amit March 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def maxProduct(self, nums):
        min_product_till_now = float('inf')
        max_product_till_now = -float('inf')
        max_so_far = -float('inf')
        for item in nums:
            if item < 0:
                t1 = max(min_product_till_now * item, item)
                t2 = min(max_product_till_now * item, item)
            elif item > 0:
                t1 = max(max_product_till_now * item, item)
                t2 = min(min_product_till_now * item, item)
            else:
                t1, t2 = 0, 0
            min_product_till_now, max_product_till_now = t2, t1
            max_so_far = max(t1, t2, max_so_far)
        return max_so_far

This solution is a modification of Kadane's algorithm which maintains two different sums namely max_till_now and min_till_now which are maximum and minimum till the current index.
This could easily be changed to find the indices.

- abhishek6498 June 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

pair<int, int> MaxProductSubarray(const vector<int>& a)
{
    if (a.empty())
    {
        return pair<int, int>(-1, -1);
    }
    if (a.size() == 1)
    {
        return pair<int, int>(0, a.size());
    }
    int neg_num_count = 0;
    int64_t l_prod = 1;
    int l = 0;
    for (; l < a.size(); ++l)
    {
        if (a[l] < 0)
        {
            ++neg_num_count;
            break;
        }
        l_prod *= a[l];
    }
    if (neg_num_count == 0)
    {
        return pair<int, int>(0, a.size());
    }
    int64_t r_prod = 1;
    int r = a.size() - 1;
    for (; r >= 0; --r)
    {
        if (a[r] < 0)
        {
            ++neg_num_count;
            break;
        }
        r_prod *= a[r];
    }
    if (l == r)
    {
        if (l == 0) {return pair<int, int>(l + 1, a.size());}
        if (l == a.size() - 1) {return pair<int, int>(0, l);}
        return l_prod > r_prod ? pair<int, int>(0, l) : pair<int, int>(l + 1, a.size());
    }
    for (int i = l + 1; i < r; ++i)
    {
        if (a[i] < 0)
        {
            ++neg_num_count;
        }
    }
    if (neg_num_count % 2 == 0)
    {
        return pair<int, int>(0, a.size());
    }
    return l_prod * -a[l] > r_prod * -a[r] ? pair<int, int>(0, r) : pair<int, int>(l + 1, a.size());
};

- Alex October 31, 2018 | 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