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

- lizka.k July 16, 2017 | Flag Reply
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

- ChrisK July 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 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)

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

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

- ChrisK July 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 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;
}

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

I am little confused here .. what is prod?

- Anonymous July 18, 2017 | 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