Facebook Interview Question Software Engineers
Country: United States
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)
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;
}
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
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);
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);
@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.
@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...
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
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.
- Lizozom July 16, 2017