## Facebook Interview Question for Software Engineers

Country: United States

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

Hey @ChrisK,
I would assume that you can't put a "-" before that first element.

If given the array [-1,2,3], your code produces the value 6, implying that the code added a "-" before the first "-1" and then multiplied it with 2 and 3.

I would just start the sub_problem function from the first element to begin with.

def max_number2(arr):
def sub_problem(prod, i):
if i == len(arr):
return prod

c = max(prod + sub_problem(arr[i], i + 1), prod - sub_problem(arr[i], i + 1), sub_problem(prod * arr[i], i + 1))
if arr[i] != 0:
return max(c, sub_problem(prod / arr[i], i + 1))
else:
return c

return sub_problem(arr[0], 1)

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

Hey ChrisK,

I would assume that you can't add a "-" before the first element.

Under that assumption, for the array [-1,2,3], your code would return 6 (-(-1)*2*3), while I would expect it to return 5 (-1+(2*3)).

I would add a simple modification to the code, starting the sub problem method on the first element of the array.

def max_number2(arr):
def sub_problem(prod, i):
if i == len(arr):
return prod

c = max(prod + sub_problem(arr[i], i + 1), prod - sub_problem(arr[i], i + 1), sub_problem(prod * arr[i], i + 1))
if arr[i] != 0:
return max(c, sub_problem(prod / arr[i], i + 1))
else:
return c

return sub_problem(arr[0], 1)

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

@lizka.k I'd share your assumption :-) thanks, that's correct

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

I am assuming, the question meant use +-*/ among the numbers in the array and return the max number.
Case1: if number > 1 multiply
Case 2: If number ==1 or number ==0, add
Case 3: if number < 0, multiply the negative numbers and see the final outcome is negative or positive, If negative divide the last number and subtract it to get the maximum number. if positive, that is the maximum number.

Let me know if my solution is correct.
private static int maxNumber(int[] nums) {
if(nums.length == 0) return 0;
Arrays.sort(nums);
int maxNumber = nums[nums.length - 1];
boolean containsNegative = false;
for(int i = nums.length -2; i >=0; i--){
if(nums[i] > 1) maxNumber *= nums[i];
else if(nums[i] == 0 || nums[i] == 1) maxNumber += nums[i];
else
{
containsNegative = true;
break;
}
}
if(containsNegative) {
int i = 0;
int negativeNum = nums[0];
while (nums[i] < 0) {
maxNumber *= nums[i];
negativeNum = nums[i];
i++;
}
if(maxNumber < 0){
maxNumber /= negativeNum;
maxNumber -= negativeNum;
}
}
return maxNumber;
}

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

Assumptions:
- add a single {+,-,*,/} between two numbers forming an algebraic expression that should be maximized: (n-1) choices
- *,/ takes precedence over +,-
- the order in which the numbers occur is given by the array, no re-ordering
- positive and negative numbers occur

Solution:
First, I just write down the recursion, by assumeing x/0 as not defined and
thus not valid in integer space (one could also argue x/0 = + infinite...)

rec(prod, i) =
max [
prod + rec(array[i], i + 1),
prod - rec(array[i], i + 1),
rec(prod * array[i], i + 1),
rec(prod / array[i], i + 1),  if array[i] != 0, can help
] if i < n
prod if i = n

this will do it... it's exponential: O(4^n).

Greedy choice won't help because e.g.:
-5 * 5 * 5 * -1 > -5 + 5 + 5 + -1
but
-5 * 5 < -5 + 5
etc...
or
2 * 1 * 4 > 2 + 1 + 4
but
2 * 1 * 2 < 2 + 1 + 2
etc...

now one can go and chase down cases where fewer
choices will do it in the recursion. For example, it's not right away
obvious when division helps at all and there might cases one doesn't
need to explore the division part of the branch.

the recursion has two arguments, so, I'd create a table like the one
below and further analyze...

case |prod | array[i] | {operations}, comment
----------------------------------------------------------
1.a  |= 0  | = 0      | {+}, doesn't matter, + will do it
b  |     | = 1      | {+,-}, +: e.g. 0+1*8, -: e.g. 0-1*-8
c  |     | = -1     | {+,-}, see above
d  |     | > 1      | {+,-}, see above
e  |     | < -1     | {+,-}, see above
----------------------------------------------------------
2.a  |= 1  | = 0      | {+}, (see case 1.a)
b  |     | = 1      | {+,-}, +: e.g. 1+1*8, -: e.g. 1-1*-8
c  |     | = -1     | {+,-}, see above
d  |     | > 1      | {+,-}, see above
e  |     | < -1     | {+,-}, see above
----------------------------------------------------------
3.a  |= -1 | = 0      | {+} (see case 1.a)
b  |     | = 1      | etc.
c  |     | = -1     | ..
d  |     | > 1      |
e  |     | < -1     |
----------------------------------------------------------
4.a  |> 1  | = 0      |
b  |     | = 1      |
c  |     | = -1     |
d  |     | > 1      |
e  |     | < -1     |
----------------------------------------------------------
5.a  |< -1 | = 0      |
b  |     | = 1      |
c  |     | = -1     |
d  |     | > 1      |
e  |     | < -1     |

there are many cases, not sure this leads to an elegant solution. How ever
one would figure out if '/' is useful at all...

or, when I was more familiar with existing NP complete and NP hard problems
I would start a discussion to prove the thing is NP complete or NP hard.

or I would ask for a hint, but I'm quite not sure it exists

or I'd start to add constraints, like no 0, no negative numbers, no 1s etc... to
simplify the problem

anyway, here the exponential, recursive version in python 3 with an incomplete
list of tests.

def max_number(arr):
def sub_problem(prod, i):
if i == len(arr):
return prod

c = max(prod + sub_problem(arr[i], i + 1), prod - sub_problem(arr[i], i + 1), sub_problem(prod * arr[i], i + 1))
if arr[i] != 0:
return max(c, sub_problem(prod / arr[i], i + 1))
else:
return c

return sub_problem(0, 0)

print(max_number([2,1,1,1])) #2+1+1+1 = 5
print(max_number([2,1,1,1,9])) # 2*1*1*1*9 = 18
print(max_number([2,1,-2])) #2+1--2 = 5
print(max_number([2,0,2])) # 2+0+2 = 4
print(max_number([-5,1,1,1,1,-3])) # 15

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

I am little confused here .. what is prod?

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

int[] arr = {-4, -3, -2, -1, 1, 1, 2, 3};
int[] newarr = new int[arr.length];
int j = 0, i = 0;
for (i = 0; i < arr.length - 2; i++) {
if (arr[i] < 0 && arr[i + 1] < 0) {
newarr[j++] = arr[i] * arr[i + 1];
i++;
} else {
newarr[j++] = arr[i];
}
}
while (i < arr.length) {
newarr[j++] = arr[i++];
}
System.out.println("ans: new: " + Arrays.toString(newarr));
Arrays.sort(newarr);
int leftover = 0, startIndex = 0,count_ones=0;
int k = 0;
for (int q = 0; q < newarr.length; q++) {
if (newarr[q] <= 0) {
startIndex++;
leftover += newarr[q];
}
if (newarr[q]==1){
count_ones++;
}
}
System.out.println("ans: startIndex: " + startIndex+" |left="+leftover+" |count_ones="+count_ones);
int[] input = new int[newarr.length - startIndex-count_ones];
System.arraycopy(newarr, startIndex+count_ones, input, 0, newarr.length - startIndex-count_ones);
System.out.println("ans: input: " + Arrays.toString(input));
//int maxsum= findsum(arr,0,arr[0]);
while(count_ones!=0){
input[0]+=1;
Arrays.sort(input);
count_ones--;
}
System.out.println("ans: new input: " + Arrays.toString(input));
int ans=input[0];
for(int m = 1;m<input.length;m++){
ans*=input[m];
}
ans-=leftover;
System.out.println("ans:"+ans);

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

Assuming it has no zero, if it has zero, remove zeroes in O(n). Should be simple to implement.

int[] arr = {-4, -3, -2, -1, 1, 1, 2, 3};
int[] newarr = new int[arr.length];
int j = 0, i = 0;
for (i = 0; i < arr.length - 2; i++) {
if (arr[i] < 0 && arr[i + 1] < 0) {
newarr[j++] = arr[i] * arr[i + 1];
i++;
} else {
newarr[j++] = arr[i];
}
}
while (i < arr.length) {
newarr[j++] = arr[i++];
}
System.out.println("ans: new: " + Arrays.toString(newarr));
Arrays.sort(newarr);
int leftover = 0, startIndex = 0,count_ones=0;
int k = 0;
for (int q = 0; q < newarr.length; q++) {
if (newarr[q] <= 0) {
startIndex++;
leftover += newarr[q];
}
if (newarr[q]==1){
count_ones++;
}
}
System.out.println("ans: startIndex: " + startIndex+" |left="+leftover+" |count_ones="+count_ones);
int[] input = new int[newarr.length - startIndex-count_ones];
System.arraycopy(newarr, startIndex+count_ones, input, 0, newarr.length - startIndex-count_ones);
System.out.println("ans: input: " + Arrays.toString(input));
//int maxsum= findsum(arr,0,arr[0]);
while(count_ones!=0){
input[0]+=1;
Arrays.sort(input);
count_ones--;
}
System.out.println("ans: new input: " + Arrays.toString(input));
int ans=input[0];
for(int m = 1;m<input.length;m++){
ans*=input[m];
}
ans-=leftover;
System.out.println("ans:"+ans);

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

@Lizozom forgive me if I'm wrong, but for

arr = [2, -3, 3]

the result would be 2 (2+(-3+3)), however, as far as I can tell, the maximum value is 11 (2--3*3)

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

@chrisK:

Wait why is it {{ rec(prod * array[i], i + 1) }} instead of {{ prod * rec(array[i], i+1 }} . Trying to think why the plus(+) and minus(-) recursion format differs from the divide and multiply.

Also as the for division and whether its useful or not, it would become more useful if the numbers can be floating point(although the function signature shows int), ex 0.1, then operations such as 2/0.1 could maximize its result.

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

@tnutty2k8:
because of operation precedence... you may want to write down the recursion tree, for array = [a,b,c], this should give you the insight.

right, there are all integers, so, I suppose the only advantage you get from division is in a situation like 1, -100, 50... in order to get rid of the -100, one could do: 1/-100+50... but actually 1--100+50 is still better...
but x/0 could lead to positive infinity which would be neat... ;-)

The thing is full of special cases one needs to consider in order to get an optimal solution. However, since the question got re-posted, I assume somebody has a hint ready...

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

Input array - return maximum number
The array elements can be re-order

#include <algorithm>
#include <vector>

int best_operator_result(int a, int b)
{
int tmp;
int opt1 = a * b;
int opt2 = a + b;
tmp = std::max(opt1, opt2);
int opt3 = a / b;
tmp = std::max(tmp, opt3);
int opt4 = b / a;
tmp = std::max(tmp, opt4);
int opt5 = a / b;
tmp = std::max(tmp, opt5);
int opt6 = a - b;
tmp = std::max(tmp, opt6);
int opt7 = b - a;
tmp = std::max(tmp, opt7);
return tmp;
}

int best_match(int n, const std::vector<int>& numbers, size_t& index)
{
int maxVal = 0;
for(size_t i = 0; i < numbers.size(); ++i) {
int tmp = best_operator_result(n, numbers[i]);
if(i == 0) {
maxVal = tmp;
index = 0;
} else if(tmp > maxVal) {
maxVal = tmp;
index = i;
}
}
return maxVal;
}

int getMaxNumber(const std::vector<int>& numbers)
{
int res = 0;

// Empty list - return 0
if(numbers.empty()) return 0;

// 1 element in the list, return that element
if(numbers.size() == 1) return numbers[0];

// Loop over the array trying every pair combination
std::vector<int> modNumbers = numbers;
while(!modNumbers.empty()) {
int n = modNumbers[0];
modNumbers.erase(modNumbers.begin());
size_t where = std::string::npos;
res = best_match(n, modNumbers, where);
modNumbers.erase(modNumbers.begin() + where);
if(modNumbers.empty()) break;
modNumbers.insert(modNumbers.begin(), res);
}
return res;
}

Examples:

getMaxNumber({ 2, 1, 1, 1, 9 }); // 21=2*9+1+1+1

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.