## Facebook Interview Question

Software Engineers**Country:**United States

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

add

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

add

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

add

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

"look ahead" etc.

in python 3

output:

- Chris July 09, 2017