## Bloomberg LP Interview Question for Software Engineers

• 1
of 1 vote

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

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

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 * array * 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.

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.

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

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

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

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, m2 = v , m3 = v;
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;
}``````

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

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

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, a);
int max_prod2 = a * a;
int min_val = min(a, a);
int min_prod2 = a * a;
max_prod3 = a * a * a;
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;
}``````

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 = { INT_MIN, INT_MIN, INT_MIN }; // keep sorted ascending
while (count--) {
if (values[count] > highest) { // First check against lower value in highest[].
if (values[count] >= highest) {
highest = highest;
highest = highest;
highest = values[count];
} else if (values[count] >= highest) {
highest = highest;
highest = values[count];
} else {
highest = values[count];
}
}
}
return highest * highest * highest;
}``````

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

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

Isn't is just a two lines thing ...?

``````nums.sort()
return max(nums[-1] * nums[-2] * nums[-3], nums[-1] * nums * nums)``````

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.

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