Facebook Interview Question for Software Engineers


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

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

- Chris July 09, 2017 | Flag Reply
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;
	}

- Vikram Gupta July 09, 2017 | Flag Reply
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);
    }

- niki July 10, 2017 | Flag Reply
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);
    }

- niki July 10, 2017 | Flag Reply
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);
    }

- niki July 10, 2017 | Flag Reply
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

- vzyarko July 10, 2017 | Flag Reply
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)

- adrock July 10, 2017 | Flag Reply
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));
}

- Anonymous July 10, 2017 | Flag Reply
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?

- muchosretardos July 11, 2017 | Flag Reply
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

- vikalpveer July 11, 2017 | Flag Reply
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

- Anonymous July 12, 2017 | Flag Reply
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

- Anonymous July 12, 2017 | Flag Reply
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

- Anonymous July 12, 2017 | Flag Reply
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

- anonymous July 12, 2017 | Flag Reply
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 :-)

- Chris July 16, 2017 | Flag Reply
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;
	}

- vikramgupta20.7 July 09, 2017 | Flag Reply
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;
	}

- Anonymous July 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- niki July 10, 2017 | Flag


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