Facebook Interview Question
Software EngineersCountry: 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