## Facebook Interview Question for Software Engineers

• 1
of 1 vote

Country: United States

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

cool problem, twist one's head a bit, specially after birthday party

Clarification:
- string with single digit numbers between 0 and 9, no negative numbers (no '-' in the string)
- algebraic interpretation is infix where * takes preceedence
- the order in which the numbers occure is given by the string sequence (no re-ordering)

Solution:
- 0: a * 0 = 0 but n + 0 = n, always pick '+' before and after a '0'
- 1: a * 1 < a + 1, but 9*1*5 > 9+1*5, assuming we give multiplication preceedence

Samples:
- 1*2 = 2
1+2 = 3
- 5+1+1+2 = 9
5*1*1*2 = 10

Therefore, the rules is not as easy as placing +-ses around 0 and 1s

the working recursion, supposing array[i] contains the 0 <= integer <= 9 is:
- sub_problem(prefix_prod, i) =
max [
prefix_prod + sub_problem(array[i], i + 1),
sub_problem(prefix_prod * array[i], i + 1)
] if i < n
prefix_prod if i = n

- this recursion works for 0's and 1's automatically, but it's inefficient
because for every number it will make the choice '+' or '*' which will
create two branches at each level, thus leading to O(2^n) runtime -
not good -

- special case 1:
if num is a '0' we do not need to explore the '*' branch because it will loose
prefix_prod + sub_problem(array[i], i + 1) if i < n and array[i] = 0
to the recursion to handle this special case more efficient

- special case 2:
if num is > 1 and prefix_prod > 1 it's clear that multiplication will win
sub_problem(prefix_prod * array[i], i + 1) if i < n and array[i] > 1 and prefix_prod > 1
to the recursion to handle that special case

- special case 3:
finally, if num is 1 and prefix_prod is 1 it's clear that multiplication will loose
because k*1 + anything > 1^k + anything
prefix_prod + sub_problem(array[i], i + 1) if i < n and array[i] = 1 and prefix_prod = 1

things like "3111111111111111111112" will still lead to exponential behaviour depending on
the length of the '1's sequence. Of course one can improve this with more sophisticated

in python 3

``````def max_number(str):
def sub_problem(prefix_prod, i):
# base case
if i == n:
return prefix_prod

# since input is a string, num = array[i] from above
num = ord(str[i]) - ord('0')

# special case 1 and 3 (see above)
if num == 0 or (num == 1 and prefix_prod == 1):
return prefix_prod + sub_problem(num, i + 1)
# special case 2 (see above)
if num > 1 and prefix_prod > 1:
return sub_problem(prefix_prod * num, i + 1)
# recursion if it's not decidable whether to add or multiply
return max(prefix_prod + sub_problem(num, i + 1), sub_problem(prefix_prod * num, i + 1))

n = len(str)
return sub_problem(0, 0)

print(max_number('2111')) #2+1+1+1 = 5
print(max_number('21119')) # 2*1*1*1*9 = 18 vs. 2+1+1+1+9 = 14
print(max_number('212')) # 2+1+2 = 5 vs. 2*1*2 = 4
print(max_number('202')) # 2+0+2 = 4 vs. 2*0*2 = 0 or 2+0*2 ...
print(max_number('89')) # 72``````

output:

``````5
18
5
4
72``````

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

The idea here is to parse through the input one number at a time and if the number is 0 or 1 then use + else use *.

n * 0 = 0 but n + 0 = n, which is greater
n * 1 = n but n + 1 = n + 1, which is greater

``````public int findMax(String input) {
if (input == null) return -1;
if (input.length() == 1) return Character.getNumericValue(input.charAt(0));

int a = Character.getNumericValue(input.charAt(0));
int result = a;

for(int i = 0; i < input.length() - 1; i++) {
int n = Character.getNumericValue(input.charAt(i));
int m = Character.getNumericValue(input.charAt(i + 1));

if (n == 0 || n == 1 || m == 0 || m == 1) {
result = result + m;
} else {
result = result * m;
}
}
return result;
}``````

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

``````public int maxNumber(String s) {
if (s == null || s.isEmpty()) {
return 0;
}
return rec(s);
}

private int rec(String s) {
int n = s.length();
if (n == 1) {
return s.charAt(0) - '0';
}
int current = s.charAt(n - 1) - '0';
int prev = rec(s.substring(0, n - 1));
int sum = current + prev;
int product = current * prev;
return Math.max(sum, product);
}``````

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

``````public int maxNumber(String s) {
if (s == null || s.isEmpty()) {
return 0;
}
return rec(s);
}

private int rec(String s) {
int n = s.length();
if (n == 1) {
return s.charAt(0) - '0';
}
int current = s.charAt(n - 1) - '0';
int prev = rec(s.substring(0, n - 1));
int sum = current + prev;
int product = current * prev;
return Math.max(sum, product);
}``````

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

``````public int maxNumber(String s) {
if (s == null || s.isEmpty()) {
return 0;
}
return rec(s);
}

private int rec(String s) {
int n = s.length();
if (n == 1) {
return s.charAt(0) - '0';
}
int current = s.charAt(n - 1) - '0';
int prev = rec(s.substring(0, n - 1));
int sum = current + prev;
int product = current * prev;
return Math.max(sum, product);
}``````

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

It's not clear if it's any two consecutive numbers or just any two random numbers.
in first case it's O(n) complexity - just a single scan.
in second brute force is C(n, 2) ~ n^2 but if we sort the string we just try last and last-1 elements.
P.S do not need the sort, just one scan for greatest and second greatest elements

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

wow thats a lot of coding. in r representing the string as an integer vector ie x_1x_2x_3... = c(x_1, x_2, x_3...) you could do

prod(ifelse(x <= 1, 1, x)) + sum(x == 1)

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

Some quick pseudo-code

``````/** Assumptions:
* number will be non-negative
* number will parse to an int
**/
function findMaxCombo(String num){
int len = num.length();
if( len <= 1 ){
return 0;
}
int a = parseInt(num.substr(0,1));
num = num.substr(1,len-1);
int b = parseInt(num.substr(0,1));
return max( a*b, a+b, findMaxCombo(num));
}``````

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

For a string x_1x_2x_3... you should always add if x_i if its 0. However, is this also the case for x_i=1. For instance for 214, 2*1*4> 2+1+4. On the other hand for 21114 2+1+1+1+4 > 2*1*1*1*4. Have I misunderstood the question?

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

here is my Solution

``````int max_str(char *str, int i) {

int c  = *str - '0';
int p,m;
if(*str == '\0') {
return i;
}else {
p = i + max_str(str+1,c);
m = max_str(str+1,i*c);

return (p > m ? p:m);
}
}
void main() {
printf("\n sum of string = %d \n",max_str("2111", 0));
printf("\n sum of string = %d \n",max_str("21119", 0));
printf("\n sum of string = %d \n",max_str("212", 0));
printf("\n sum of string = %d \n",max_str("202", 0));
printf("\n sum of string = %d \n",max_str("419", 0));
printf("\n sum of string = %d \n",max_str("409", 0));
}``````

And output

``````sum of string = 5

sum of string = 18

sum of string = 5

sum of string = 4

sum of string = 36

sum of string = 13``````

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

def max_sum_mul(string1):
list_num = [int(x) for x in string1]
max_sum = 0
max_mul = 1
max_all = 0
for i in range(len(list_num)):

if (list_num[i] + max_sum) > max_sum:
max_sum = list_num[i] + max_sum
if (list_num[i]*max_mul) > max_mul:
max_mul = list_num[i]*max_mul
if max_mul > max_sum:
max_all = max_mul
else:
max_all = max_sum

return max_all

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

``````def max_sum_mul(string1):
list_num = [int(x) for x in string1]
max_sum = 0
max_mul = 1
max_all = 0
for i in range(len(list_num)):

if (list_num[i] + max_sum) > max_sum:
max_sum = list_num[i] + max_sum
if (list_num[i]*max_mul) > max_mul:
max_mul = list_num[i]*max_mul
if max_mul > max_sum:
max_all = max_mul
else:
max_all = max_sum

return max_all``````

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

``````def max_sum_mul(string1):
list_num = [int(x) for x in string1]
max_sum = 0
max_mul = 1
max_all = 0
for i in range(len(list_num)):

if (list_num[i] + max_sum) > max_sum:
max_sum = list_num[i] + max_sum
if (list_num[i]*max_mul) > max_mul:
max_mul = list_num[i]*max_mul
if max_mul > max_sum:
max_all = max_mul
else:
max_all = max_sum

return max_all``````

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

``````def max_sum_mul(string1):
list_num = [int(x) for x in string1]
max_sum = 0
max_mul = 1
max_all = 0
for i in range(len(list_num)):

if (list_num[i] + max_sum) > max_sum:
max_sum = list_num[i] + max_sum
if (list_num[i]*max_mul) > max_mul:
max_mul = list_num[i]*max_mul
if max_mul > max_sum:
max_all = max_mul
else:
max_all = max_sum

return max_all``````

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

@PraTrick:
1) how can you reply, I can't... pressing "submit" just doesn't do anything.
2) your question: well, 2+1+1+1*9 is not (2+1+1+1)*9 but (1*9)+2+1+1+1 because * takes precedence over + that's why it should use 2*1*1*1*9 ...
of course you can simplify by telling you ignore operator precedence, but that you really must state, it's a major simplification and a "broad" assumption

The whole thing was much easier when precedence wouldn't matter, but I thought, I'd want to stay with basic arithmetic's

@PraTrick: just saw, you removed your question ;-) never mind :-)

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

The idea here is to parse through the input one number at a time and if the number is 0 or 1 then use + else use *.

n * 0 = 0 but n + 0 = n, which is greater
n * 1 = n but n + 1 = n + 1, which is greater

EDIT: the previous solution doesn't work in all cases. The recursive one below is correct.

``````public int findMax(String input) {
if (input == null) return -1;
if (input.length() == 1) return Character.getNumericValue(input.charAt(0));

int a = Character.getNumericValue(input.charAt(0));
int result = a;

int n = Character.getNumericValue(input.charAt(0));
int m = Character.getNumericValue(input.charAt(1));

if (n == 0 || n == 1 || m == 0 || m == 1) {
result = result + findMax(input.substring(1));
} else {
result = result * findMax(input.substring(1));
}
return result;
}``````

Comment hidden because of low score. Click to expand.
-2
of 6 vote

0 and 1 should always be operated by a '+' as they won't help in multiplication.
n * 0 = 0 but n + 0 = 0
n * 1 = n but n + 1 = n + 1
So we can iterate through the input, multiplying the numbers and if the next number in the input is 0 or 1 then add them to the result instead of multiplying.

``````public int maxNumber(String input) {
if (input == null) return -1;
if (input.length() == 1) return Character.getNumericValue(input.charAt(0));

int a = Character.getNumericValue(input.charAt(0));
int result = a;

for(int i = 0; i < input.length() - 1; i++) {
int n = Character.getNumericValue(input.charAt(i));
int m = Character.getNumericValue(input.charAt(i + 1));

if (n == 0 || n == 1 || m == 0 || m == 1) {
result = result + m;
} else {
result = result * m;
}
}
return result;
}``````

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

That's not true. Let's say you have "11" as an input. In this case "1*1"=1, but "1+1"=2 which is greater than 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.