Bloomberg LP Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




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

@aonecoding,
if you look into your own algorithm, I can see there is a solution in exact n. I dislike O, I like Theta. So yes, in Theta(n).

- NoOne May 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Let's assume that the array has at *least three entries* and that we pick numbers from the array *without replacement*.

The solution is trivial if the array only contains positive numbers. In fact even if there's one negative number in the array, the solution is:

case_0 = prod( nlargest( 3, array ) )

Here, nlargest can be implemented using a heap. In case there are two or more negative numbers in the array, we need to handle two distinct cases (due to the fact that two negative numbers can yield a large positive product).

case_1 = prod( nlargest( 3, array ) )
case_2 = prod( max( array ) * nsmallest( 2, array ) )

Thus, the final solution that handles all cases (including case_0 which is identical to case_1) in linear time is:

max( case_1, case_2 )

A specific implementation in Python might be:

from heapq import nsmallest, nlargest
from numpy import prod
from itertools import combinations


def max_prod3(arr):
    case_1 = prod(nlargest(3, arr))
    case_2 = max(arr) * prod(nsmallest(2, arr))
    return max(case_1, case_2)


def test_max_prod3(arr):
    # compare with brute-force solution
    correct = max(prod(triplet) for triplet in combinations(arr, 3))
    assert max_prod3(arr) == correct, "incorrect result for input {}".format(arr)

- Kristian Holsheimer May 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int largestProduct3(int[] array) {

        Arrays.sort(array);

        int n = array.length;
        int maxProduct;

        //case> pick the last 3 numbers(when the array has only negative, or only positive numbers)
        maxProduct = array[n - 1] * array[n - 2] * array[n - 3];

        //case> pick 2 numbers from the left end and 1 number from the right end
        maxProduct = Math.max(maxProduct, array[0] * array[1] * array[n - 1]);

        return maxProduct;
    }

Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.

Given by experienced engineers/interviewers from FB, Google and Uber,
our ONE TO ONE courses cover everything in an interview including
latest interview questions sorted by companies,
SYSTEM DESIGN Courses (highly recommended for people interviewing with FLAG)
ALGORITHMS (conquer DP, Graph, Greedy and other advanced algo problems),
and mock interviews.

Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.

Welcome to email us aonecoding@gmail.com with any questions. Thanks for reading.

- aonecoding May 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The solution isn't that good.Complexity is O(nlogn) as you sort. we can do better.

- Goutham May 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if the array is only positive integers you can do it in O(n)
int max1 = int.MinValue;
int max2 = int.MinValue;
int max3 = int.MinValue;

for(int i = 0; i <A.Length;i++)
{
if(A[i] > max1)
{
max3 = max2;
max2 = max1;
max1 = A[i];
}
if(A[i] > max2)
{
max3 = max2;
max2 = A[i];
}
if (A[i] > max3)
max3 = A[i];
}

Console.WriteLine(max1 * max2 * max3);

- techbits May 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if the array is only positive integers, you can do it in O(n)

int max1 = int.MinValue;
            int max2 = int.MinValue;
            int max3 = int.MinValue;

            for(int i  = 0; i <A.Length;i++)
            {
                if(A[i] > max1)
                {
                    max3 = max2;
                    max2 = max1;
                    max1 = A[i];                    
                }
                if(A[i] > max2)
                {
                    max3 = max2;
                    max2 = A[i];
                }
                if (A[i] > max3)
                    max3 = A[i];
            }

            Console.WriteLine(max1 * max2 * max3);

- techbits May 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If the array contains only positive integers then one can do it in O(n) ...

int max1 = Integer.MIN_VALUE;
        int max2 = Integer.MIN_VALUE;
        int max3 = Integer.MIN_VALUE;

        for(int i  = 0; i <A.length;i++)
        {
            if(A[i] > max1)
            {
                max3 = max2;
                max2 = max1;
                max1 = A[i];                    
            }
            else if(A[i] > max2)
            {
                max3 = max2;
                max2 = A[i];
            }
            else if (A[i] > max3)
                max3 = A[i];
        }
        System.out.println("Maximum product : " + (max1 * max2 * max3));

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

void max3(int& m1, int& m2, int& m3){
		int max = max(max(m1,m2),m3);
             	int min = min(min(m1,m2),m3);
                m2 = (m1+m2+m3) - max - min;
                m1 = max;
 		m3 = min; 
	}

	int findMaxProduct(const vector<int>& v1){
	        int sz = v.size();
        	int m1 = v[0], m2 = v[1] , m3 = v[2];
        	max3(m1, m2, m3);


	        for(int i=3; i<sz; i++){
        	        if(v[i] > m3){
                	        m3 = v[i];
                        	max3(&m1, &m2, &m3);
                	}
        	}

        	cout << m1 * m2 * m3;	
	}

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

Actually, since the question is about multiplying the three maximum numbers we can still achieve a O(n) for whatever numbers beings used by using additional data structure such as hash map which contains a maximum numbers as a key and frequency of that number as a value. Basically, the idea would be to insert maximums in a hash map with their frequency. if that frequency is greater than or equal 3, then we are done. If it is 2, we are missing the third maximum, if only 1, that means we are missing the other 2 maximums. So, the idea here is to iterate over the array 3 times which is O(3n).

- Ahmed.Ebaid July 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if all is positive: a*b*c is largest if you pick the largest three numbers
if negative numbers are alowed, you have two cases, the product of the two smallest and the largest or the product the three largest

to find the three largest and two smallest numbers iterate over the array and pick this numers out (as if you would only scan for max or min). The thing is k-Selection and leads to O(n*k), but if k is constant, it's O(n) and if k is small it's reasonable efficient (among others due to caches on the CPU)

then calculate the two cases and return the max of them.

done.

if you need coaching... ;-)

- Chris July 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Time complexity: O(N)

int MaxProd3(vector<int> const &a)
{
    int max_prod3 = 0;
    if (a.size() >= 3) {
        int max_val = max(a[0], a[1]);
        int max_prod2 = a[0] * a[1];
        int min_val = min(a[0], a[1]);
        int min_prod2 = a[0] * a[1];
        max_prod3 = a[0] * a[1] * a[2];
        for (int i = 2; i < a.size(); ++i) {
            max_prod3 = max(max_prod3, a[i] * max_prod2);
            max_prod3 = max(max_prod3, a[i] * min_prod2);
            max_prod2 = max(max_prod2, max_val * a[i]);
            max_prod2 = max(max_prod2, min_val * a[i]);
            min_prod2 = min(min_prod2, max_val * a[i]);
            min_prod2 = min(min_prod2, min_val * a[i]);
            max_val = max(max_val, a[i]);
            min_val = min(min_val, a[i]);
        }
    }
    return max_prod3;
}

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

C++ solution

int product3highest(const int values[], size_t count) {
  int highest[3] = { INT_MIN, INT_MIN, INT_MIN }; // keep sorted ascending
  while (count--) {
    if (values[count] > highest[0]) { // First check against lower value in highest[].
      if (values[count] >= highest[2]) {
        highest[0] = highest[1];
        highest[1] = highest[2];
        highest[2] = values[count];
      } else if (values[count] >= highest[1]) {
        highest[0] = highest[1];
        highest[1] = values[count];
      } else {
        highest[0] = values[count];
      }
    }
  }
  return highest[0] * highest[1] * highest[2];
}

- Luc November 04, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For all positive elements in the array:

def prodThreeLargest(arr):
    max1 = max2 = max3 = float('-inf')
    for i in range(len(arr)):
        if arr[i] > max1:
            max3 = max2
            max2 = max1
            max1 = arr[i]
        elif arr[i] > max2:
            max3 = max2
            max2 = arr[i]
        elif arr[i] > max3:
            max3 = arr[i]
    #print("max1 {} max2 {} max3 {}".format(max1, max2, max3))

    return max1*max2*max3

For positive and negative elements:

import heapq


def prodThreeLargest(arr):
    n1, n2 = heapq.nsmallest(2, arr)
    print(n1, n2)
    p1, p2, p3 = heapq.nlargest(3, arr)
    print(p1, p2, p3)

    return max(n1*n2*p1, p1*p2*p3)

- Ron June 23, 2019 | 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