Microsoft Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

You can simply run a Length product through the array in O(n) time. Each time you have two pointers one which points at location i and the other one at i+L-1. The new product is previous_product*element[i+L]/element[i], assuming element[i] is non-zero. You compare this product with your current max value. Every time you encounter a zero you can simply skip L locations including the one containing zero.

- Ruchin Shah February 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can have to arrays, one for positive numbers and one for negative numbers. Sorting the two arrays as the absolute values decreasing. Setting two pointers at the beginning of two arrays. Comparing the absolute value at the two pointers. Each time get the bigger absolute value one , doing the multiplication and move the corresponding pointer ahead. After K moves we can get the product. If the product is positive then done. If it is negative, dividing the number at the pointer of negative array, multiplying the number at the pointer of positive array.

- spy February 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This assumes that there is a way to get a positive answer - suppose we have odd k and only negative numbers (among an infinite number of situations yielding a negative result), this does not work at all since we would actually want to choose with k numbers with smallest magnitude.

- anon February 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Here is the solution (there is probably a faster way)

pretty simple to code but here is the idea:

there are two cases.
1. best result positive
2. best result negative (meaning every possible result is negative)

Here is how we decide which case we have:
IF (K - # of positive elements) is odd and positive, we have case 2
ELSE case 1
simple to determine this, go through array and count number of positive elements in time O(n)

IF case 1:
follow the algorithm provided by spy

IF case 2:
we want to minimize total magnitude, so sort array from smallest magnitude to largest magnitude (ignore +/-) and choose K smallest elements of sorted array

- anon February 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks a lot, anon. I think the negative result only has one situation: odd number n and all negative numbers. In this situation we just sort the array as increasing order and get the first n numbers to get the product.

- spy February 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sort array in absolute values (Highest first)
Traverse array for first L elements
- 1. Keep track of number of negative integers
- 2. Keep track of last negative and last positive number.

If the number of negative integers is odd,
look for next positive and next negative number in array.
Multiply Next positive with current last positive and same with negatives. Check which gives higher value. Select that combination.

- Ryan April 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

sort the array
chose the biggest of a[0]*a[1]*a[N] and a[N-2]*a[N-1]*a[N]

- anonymous February 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry, that only works for N=3. please disregard the post.

- Anonymous February 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

subarray here must be contiguous, what if it's not?

- samuel February 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algorithm:
Find all the sub-arrays of length = input length and compute the product of each. Sub-arrays can be generated by generating all binary numbers from 0 to 2^arrays.length.

For example:
all subarrays of an array {2,5} can be generated in binary as:
00 = {}
01 = {,5}
10 = {2,}
11 = {2,5}
in below code: 1 << array.Length = 1 << 2 = 2 ^ 2 = 4 max subsets can be generated
Now, get all subsets of input length and find the max product.

public static void MaxProductOfSubArray(int[] array, int length)
        {
            if (array == null || array.Length == 0 || length < 0 || length > array.Length)
                throw new ArgumentException();

            int maxProduct = int.MinValue;
            int[] output = new int[length];
      
            int maxSubsets = 1 << array.Length;

            for (int i = 0; i < maxSubsets; ++i)
            {
                List<int> set = new List<int>();

                for (int j = 0, k = i; k > 0; j++, k >>= 1)
                    if ((k & 1) > 0) set.Add(array[j]);

                if (set.Count() == length)
                {
                    int product = 1;
                    set.ForEach(n => product *= n);
                    if (product > maxProduct)
                    {
                        maxProduct = product;
                        output = set.ToArray();
                    }
                }
            }

            output.ToList().ForEach(n => Console.Write(n + " "));
            Console.WriteLine(":" + maxProduct);
        }

- RKD February 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Since this is a subset rather than a subsequence. I think this can be solved in O(n) for the following case

Scenario 1: no zeros in the array

1. Count the number of negative numbers in the array
2. if there are no negative numbers in the array
a) We just need to ignore the leading and trailing 1s.
i) Run from the index 0 to n-2 . and start multiplying the elements. if there are leading 1 increase the start counter. if there are trailing 1 dont increase the end counter. store the multiplication to max1 and well the start and end index
ii) Run the index from n-1 to 1 follow the above step and store it in max2 and start and end index
iii) print the index of highest multiplication value.

3. if there are odd number of negative numbers. we need to multiply upto negCount-1 at the minimum and handle if there are any leading and trailing 1s
a) We can multiply from index 0 upto negCount-1 followed by positive numbers until we reach last negative number. if there are any leading and trailing 1s adjust the start and end index.
b) start from n-1 and multiply upto negCount-1 and any positive numbers following that until we reach the first negative number. Ignore the leading or traling 1s.
c.) compare the products and print the index of the largest product.

4. If the negative count is even. Then we can max multiply n-1 elements on the both side ignoring leading and trailing 1s.

Scenario 2: If there are zeros.

1. all the above scenarios applicable but we have to consider that there are more than 1 array based on the number of zeros.

- Check February 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

the solution would be to sort the array in absolute value and pick the last n elements. If product comes out to be negetive, remove the smallest negetive and take the next smallest positive number from the array.

Example:
{4, 1, 7, -8, 9}, 3

sort it { 1, 4, 7, -8, 9}

take last n element {7, -8, 9}

If (product is negetive)
replace smallest -ve number (-8) with 4 -> {4, 7, 9}
else
You already have the answer

- CodeCraker March 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

just to clarify for readers
if product is negative, replace smallest negative by absolute value with maximum unused in set positive value

- Darkhan.Imangaliev March 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

input: {1,2,1,2}, L=2

output: ???

- S O U N D W A V E March 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
* ALGORITHM
* for i=1 to n
* find products of i to i+l array elements
* if product>maxproduct
* maxProduct=product and maxStartIndex=i
* return maxStartIndex
*/

public static int findmaxProductSubArray(int[] arr, int l)
{
int len=arr.length;
int maxProduct=Integer.MIN_VALUE;
int maxStartIndex=0,tempProduct=1;
for(int i=0;i<=len-l;i++)
{
for(int j=i;j<((i+l));j++)
{
tempProduct*=arr[j];
}
if(tempProduct>maxProduct)
{
maxProduct=tempProduct;
maxStartIndex=i;
}
tempProduct=1;
}
return maxStartIndex;
}

- Dany March 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This algorithm just linearly parses the array for l elements. Like this you ll miss many combinations.
eg. {-9,7,6,-2}, 3
for this your alg considers {{-9,7,6}, {7,6,-2} which doesn't have the correct combination of {-9,7,-2}.

I think the answer involves sorting the given input integers as absolute nos - ie., without considering their sign. Then within the first L integers if you find odd no. of -ve numbers you should check whether replacing the lowest -ve no with positive (if exists) or lowest positive no with -ve no(if exists) yields the maximum result.

- prav April 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

one more sceario is if you have no positve numbers in your input list and L is odd..You got to take the lowest absolute values in the sorted list.

- prav April 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sort the array based on the absolute value of each element of the array into a sorted array. The sorted array holds the original values not absolute values.
then (length of the array - L) to end of the sorted array. Multiply these numbers and you have absolute value of the biggest product.

- Kruz March 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I didn't understand the eg. output. Why {4,-7,-8,9} can't be the output?
Example:
Input: {4, 1, -7, -8, 9}, 3
Output: {-7,-8,9}

- Anonymous April 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I didn't understand the output. Why is it not {4,-7,-8,9}

Input: {4, 1, -7, -8, 9}, 3
Output: {-7,-8,9}

- prav April 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ignore this comment. I missed the point that the output sub array length 3 is given .

- prav April 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Implemented without sorting, just linear scan with floating scan window and with zero count monitoring within scanning range:

def find_max_subarray(vector, L):
    # Check inputs
    LV = len(vector)
    if LV < L:
        raise ValueError("Incorrect input data")
    elif LV == L:
        return vector
    # Do it!
    l = 0
    r = 0
    sum = 1
    result = (0, L)
    newSum = 0
    zerosCount = 0
    while r < LV:
        if vector[r] == 0:
            zerosCount += 1
        if r < L:
            sum *= vector[r]
        else:
            l += 1
            if 0 != zerosCount:
                if vector[l-1] == 0:
                    zerosCount -= 1
                    if 0 == zerosCount:
                        newSum = 1
                        for i in range(l , r+1):
                            newSum *= vector[i]
            else:
                newSum = sum / vector[l-1] * vector[r]

            if newSum > sum:
                result = (l, r)
                sum = newSum
        r += 1
    return vector[result[0]:result[1]+1:1]

print(find_max_subarray([0, 1, 0, 0, -7, 8, 9, 0, 1, 9, 8], 3))

>> [1, 9, 8]

- Pepper April 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Also, inner zero-scan loop can be optimizing to avoid rescan [l:r+1] interval.

- Pepper April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The out put for your input [0, 1, 0, 0, -7, 8, 9, 0, 1, 9, 8] should be [9,9,8]

- YJKim June 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

thought process:
1) since it is unsorted array, best we can do for complexity is O(n)

Algo

Maintain a window of 3 elements.
current prod= a[0]*a[1]*a[2]
max_prod= curr_prod
max_index=0;//no need to store high index
for( int i=3; i<array_length; i++)
if(a[i]==0) i=i+3;
else
curr_prod= (curr_prod/a[i-3] )*a[i];
if(curr_prod>max_prod) {max_prod=curr_prod; max_index=i}
}

- Yoda April 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Idea: 1. Calculate product of a[0]..a[L-1]. Mark it as maxProduct and prevProduct
//       2. If L = size, end the process. Otherwise go to p.3
//       3. Start from i = 1.
//       4. Check if arr[i - 1 + L] == 0 or arr[i - 1] == 0). If not, go to p.5
//          If arr[i - 1] == 0, traverse the array until you find 1st non-zero element.
//          If arr[i - 1 + L] == 0, we'll bypass it by making i = i + L.
//          If after those two index adjustments i + L <= size of array, calculate currentProduct as product
//          of arr[i]..arr[i - 1 + L] 
//          Go to p.6.
//       5. Calculate currentProduct as: prevProduct / arr[i - 1] * arr[i - 1 + L]. Go to p.6
//       6. If currentProduct > maxProduct, then assign currentProduct to maxProduct.
//       7. Increment i.
//       8. Repeat pp. 3-8 while i + L <= size of array
int Product(int *arr, size_t start, size_t end)
{
    int product = 0;

    if (arr && start <= end)
    {
        product = 1;
        for (size_t i = start; i <= end; i++)
        {
            product *= arr[i];
            if (product == 0)
            {
                break;
            }
        }
    }

    return product;
}

errno_t FindProduct(int *arr, size_t size, size_t L, int *pBegin, int *pEnd, int *pProduct)
{
    errno_t error = EINVAL;
    int maxProduct = 0;
    int currentProduct = 0;
    int prevProduct = 0;
    int begin = 0;
    int end = 0;

    if (arr && size && L && L <= size && pBegin && pEnd && pProduct)
    {
        error = 0;
        begin = 0;
        end = L - 1;
        maxProduct = prevProduct = Product(arr, 0, L - 1);
        if (L < size)
        {
            size_t i = 1;
            
            while (i + L <= size)
            {
                if (arr[i - 1 + L] == 0 || arr[i - 1] == 0)
                {
                    if (arr[i - 1] == 0)
                    {
                        while (arr[i] == 0 && i + L <= size)
                        {
                            i++;
                        }
                    }
                    else
                    {
                        i += L;
                    }

                    if (i + L <= size)
                    {
                        currentProduct = Product(arr, i, i - 1 + L);
                    }
                }
                else
                {
                    currentProduct = prevProduct / arr[i - 1] * arr[i - 1 + L];
                }
                if (currentProduct > maxProduct)
                {
                    maxProduct = currentProduct;
                    begin = i;
                    end = i - 1 + L;
                }
                prevProduct = currentProduct;
                i++;
            }
        }

        *pProduct = maxProduct;
        *pBegin = begin;
        *pEnd = end;
    }

    return error;
}

- AK October 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Keep track of min and max product, and multiply the next number with the min and max and update their values accordingly. If the next number is zero then we need to reset the min and max. Keep track of the final max in a separate variable. Here is the java code:

public static int maximumProductSubSequence(int[] array) {

		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		int tempMin = 0;
		int tempMax = 0;
		int currentMin = 1;
		int currentMax = 1;
		for (int i = 0; i < array.length; i++) {
			if (array[i] == 0) {
				currentMin = 1;
				currentMax = 1;
				System.out.println("Reset");
				continue;
			}
			tempMin = Math.min(array[i] * currentMin, array[i] * currentMax);
			tempMax = Math.max(array[i] * currentMin, array[i] * currentMax);

			currentMin = Math.min(array[i], tempMin);
			currentMax = Math.max(array[i], tempMax);
			min = Math.min(min, currentMin);
			max = Math.max(max, currentMax);
		}
		return max;
	}

- Bhumik November 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

In O(n) we can realize that do we have a positive number or not.

If not: 
	If there is a zero and L is odd, select it and done!
	If L is odd and no zero, sort in O(nlgn) and choose the L lowest absolute values.
	If L is even, sort in O(nlgn) and choose the L biggest absolute values.

If we do have positive numbers, we can sort the array based on the absolute values O(nlgn) and choose the L biggest absolute values.

If the result is negative we do have two options:
1. Remove a negative value and add a positive value
2. Remove a positive value and add a negative value
Based on the current selected lowest positive and negative absolute values and the next positive and negative values, we can decide which one is better.

- mahdi.oraei February 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.


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