## Facebook Interview Question for Software Developers

Country: United States
Interview Type: In-Person

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

1. I think -1-2-3 should be equals to -6, not 6.
2. Some people mentioned the answer should be equals to ZERO. Let's take a look at the simplest number "12" Here are all the possible combinations:
12 = 12
1+2 = 3
1-2 = -1
+12 = 12
+1+2 = 3
+1-2 = -1
-12 = -12
-1+2 = 1
-1-2 = -3

Sum = 14, so it is not equal to zero. If you look carefully, the final sum equals to the sum of the first three (the first number without the +/- sign). Let's check the number "123":
123 = 123
12+3 = 15
12-3 = 9
1+23 = 24
1+2+3 = 6
1+2-3 = 0
1-23 = -22
1-2+3 = 2
1-2-3 = -4
+123 = 123
+12+3 = 15
+12-3 = 9
+1+23 = 24
+1+2+3 = 6
+1+2-3 = 0
+1-23 = -22
+1-2+3 = 2
+1-2-3 = -4
-123 = -123
-12+3 = -9
-12-3 = -15
-1+23 = 22
-1+2+3 = 4
-1+2-3 = -2
-1-23 = -24
-1-2+3 = 0
-1-2-3 = -6

sum = 153. The final sum is same as the sum of the first nine line. Also I see the pattern that for number "ab", the sum equals to ab+a*2, and for number "abc", the sum equals to abc+ab*2+a*6. I think you get the idea now. The time complexity should be O(n) where n is the length of the string.

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

First, solve it on the paper very carefully, you will see a pattern. 2/3 of the numbers cancel each other out, and you are only left with 9 numbers. Add up all the numbers that have either '+' or ' ' in the beginning depending on whichever you cancel. It will be 153.

Here is a solution using JavaScript. I believe it can be done without using this deep nested loops, but this works fine so far.

``````var signs = ["+","-",""],
numbers = [1, 2, 3],
total = 0,
string = "",
grandTotal = 0;

for (var i = 0; i < 3; i++) {
for (var j = 0; j < 3; j++) {
for (var k = 0; k < 3; k++) {
string = signs[i] + numbers[0] + signs[j] + numbers[1] + signs[k] + numbers[2];
total = eval(string)
console.log(string + "=" + total);
grandTotal += total;
}
}
}

console.log("Grand total: " + grandTotal);``````

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

``````package AmazonProbs;

import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;
import javax.script.ScriptException;

//You have a string of numbers, i.e. 123. You can insert a + or - sign in front of ever number, or you can leave it empty. Find all of the different possibilities, make the calculation and return the sum.
//For example;
//+1+2+3 = 6
//+12+3 = 15
//+123 = 123
//+1+23 = 24
//...
//-1-2-3 = 6
//...
//Return the sum of all the results.
//

public class PlusMinusNone {
public static void main(String[] args) {
String num= String.valueOf(123);
String val[]=new String[]{"+","-",""};
ScriptEngineManager s = new ScriptEngineManager();
ScriptEngine eng = s.getEngineByName("JavaScript");
for (int i = 0; i < val.length; i++) {
for (int j = 0; j < val.length; j++) {
for (int k = 0; k < val.length; k++) {
String str= (val[i] +num.charAt(0)+  val[j] +num.charAt(1) +val[k] + num.charAt(2));
try {
System.out.println(str + " = " +eng.eval(str));
} catch (ScriptException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}

}

}
}``````

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

``````def sumHelper(index, finalSum, currSum, prev):
if index == 4:
if prev == 0:
finalSum[0] = finalSum[0] + currSum
return
current = prev*10 + index
sumHelper(index+1, finalSum, currSum+current, 0)
sumHelper(index+1, finalSum, currSum-current, 0)
sumHelper(index+1, finalSum, currSum, current)

def sum():
finalSum = [0]                   #to pass by reference
sumHelper(1, finalSum, 0, 0)
return finalSum[0]``````

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

import itertools
def printSums(s):
total = 0
for j, m in enumerate(itertools.combinations_with_replacement('0+-', len(s))):
ress = ''
for i,d in enumerate(m):
nextD = '' if m[i] == '0' else m[i]
ress = ress + nextD + s[i]
ss = eval(ress)
print ress, '=', ss
total += ss
if j > 0:
ress = ress.replace('+', '-')
ss = eval(ress)
print ress, '=', ss
total += ss
return total
print printSums('123')

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

``````int parseStringNr(const string &str, unsigned int &idx)
{
int res = 0, len = str.length();
bool is_negative = false;
idx = 0;

if (str[0] == '+' || str[0] == '-')
{
res = str[1] - '0';
idx = 2;
is_negative = (str[0] == '-');
}
else if (str[0] - '0' >= 0 && str[0] - '0' <= 9)
{
res = str[0] - '0';
idx = 1;
}
else
return 0;

while (idx < len)
{
if (str[idx] - '0' >= 0 && str[idx] - '0' <= 9)
res = (res * 10) + (str[idx] - '0');
else if (str[idx] == '+' || str[idx] == '-')
break;
else
return 0;

idx++;
}

if (is_negative)
res *= -1;

return res;
}

int evalStringNr(const string &str)
{
unsigned int i = 0, count = 0, len = str.length();
int nr, tot_nr = 0;

while (i < len)
{
nr = parseStringNr(str.substr(i), count);
if (nr == 0)
return 0;

tot_nr += nr;
i += count;
}

return tot_nr;
}

int computeString(char *num_str)
{
char *signs[] = { "+", "-", "" };
int tot = 0;
string build_str;

if (strlen(num_str) != 3)
return 0;

for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
for (int k = 0; k < 3; k++)
{
build_str.clear();

build_str.append(signs[i]);
build_str.append(num_str, 1);

build_str.append(signs[j]);
build_str.append(num_str+1, 1);

build_str.append(signs[k]);
build_str.append(num_str+2, 1);

tot += evalStringNr(build_str);
}

return tot;
}

int main(void)
{
cout << computeString("123") << endl;		// prints 153
}``````

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

As we have 3 options for every number and "+" and "-" at the beginning will even each other out we are left with the options that start with "nothing", this means the solution will not always be 0, but actually some positive number. My quick brute force approach looks like this:

``````def sum_all sum_strings
sum_strings.inject(0) { |acc, s| acc += eval(s) }
end

def all_sums_rec number_array, sum_strings
return sum_all(sum_strings) if number_array.empty?

next_element = number_array.shift

next_sum_strings = sum_strings.flat_map do |s|
no = "#{s}#{next_element}"
plus = "#{s}+#{next_element}"
minus = "#{s}-#{next_element}"
[no, plus, minus]
end

all_sums_rec number_array, next_sum_strings
end

def all_sums number
all_sums_rec number.to_s.split(""), [""]
end``````

This follows basically exactly the problem statement, expanding the number into its elements and building the equations from this expanded number, in the end using "eval" to evaluate what the equation results to and sum them all up.

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

All the +/- inserts cancel out, leaving a combo of number partitions to sum
first digit x N!
first 2 digits (N-1)!
first 3 digits (N-2)!
Solution works for any number of digits within limits of int range of values for factorial.

``````public class mymain {

public static int factorial(int f) {
return ((f == 0) ? 1 : f * factorial(f - 1));
}

public static void main(String[] args) {

String numbers = "123";
for(int i=0; i<numbers.length(); i++)
{
sum += Integer.parseInt(numbers.substring(0, i+1)) * factorial(N-i);
}
System.out.println("Total sum = " + sum);
}
}``````

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

``````public static int countNumberOfPlusAndMinusInNSlotes((int f) {
if (f ==0) {
return 1;
}
return (int) (2*(Math.pow(3, f-1)));
}

public static void main(String[] args) {
//        String numbers = "123"; // 153
//        String numbers = "1234"; // 1570
String numbers = "1234"; // 15821

int sum = 0;
for (int i = 0; i < numbers.length(); i++) {
int i1 = Integer.parseInt(numbers.substring(0, i + 1));
int N = numbers.length() - i -1;
sum += i1 * countNumberOfPlusAndMinusInNSlotes(N);
}
System.out.println("Total sum = " + sum);
}``````

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

Recursive solution. Some people here have mentioned it should be O(n), but I have not seen a solution O(n) that solves for every n (n being the legth of the string). My solution is O(3^n) which if you need to print all the solutions is your complexity anyway.

``````System.out.println("total is " + printSums("123", 0, 0, ""));

private static int printSums(String str, int curSum, int curNumber, String curCalculation) {
if (str.isEmpty()) {
System.out.println(curCalculation +"=" + curSum);
return curSum;
}
int curDigit = str.charAt(0) - '0';
String left = str.substring(1, str.length());
int nextNumber = curNumber * 10 + (curNumber >= 0 ? curDigit : -curDigit);
return (printSums(left, curSum + curDigit, curDigit, curCalculation + "+" + curDigit) +
printSums(left, curSum - curDigit, -curDigit, curCalculation + "-" + curDigit) +
printSums(left, curSum - curNumber + nextNumber, nextNumber, curCalculation + curDigit));
}``````

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

``````package main

import (
"fmt"
"log"
"strconv"
"strings"
)

func Solver(s string) int {
ds := strings.Split(s, "")
digits := []int{}
for _, d := range ds {
di, err := strconv.Atoi(d)
if err != nil {
log.Fatalln(err)
}
digits = append(digits, di)
}
return len(_count(digits))
}

func _count(digits []int) map[int]bool {
if len(digits) == 0 {
return map[int]bool{0: true}
}
num := 0
result := map[int]bool{}
for i := 0; i < len(digits); i++ {
num = num*10 + digits[i]
res := _count(digits[i+1:])
for r := range res {
result[num+r] = true
result[-num+r] = true
}
}
return result
}

func main() {
fmt.Println(Solver("123")) // Output: 17
}``````

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

I guess it's not optimal that we need number of FOR loops equal to the number of positions in input integer, it is O(3^N) where N is number of positions in incoming integer and 3 is number of operators, in our case "+", "-" and "".
Also when we have +1 in the beginning of expression it's the same as just 1, so we don't need to exclude expressions starting with simple 1.

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

public class printlist {

public void printresult(String numbers) {
ArrayList<Integer> result = new ArrayList<Integer>();
permute(0, numbers, result, 0);
for (Integer i : result) {
System.out.println(i);
}
}

public void permute(int index, String numbers, ArrayList<Integer> result, int sum) {
if (numbers.length() == index) {
result.add(sum);
return;
}
for (int i = index; i < numbers.length(); i++) {
int positive = Integer.valueOf(numbers.substring(index, i + 1)) * 1;
permute(i + 1, numbers, result, sum + positive);
int negative = Integer.valueOf(numbers.substring(index, i + 1)) * -1;
permute(i + 1, numbers, result, sum + negative);
}
}

public static void main(String argv[]) {
printlist p = new printlist();
p.printresult("123");
}
}

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

``````public class printlist {

public void printresult(String numbers) {
ArrayList<Integer> result = new ArrayList<Integer>();
permute(0, numbers, result, 0);
for (Integer i : result) {
System.out.println(i);
}
}

public void permute(int index, String numbers, ArrayList<Integer> result, int sum) {
if (numbers.length() == index) {
result.add(sum);
return;
}
for (int i = index; i < numbers.length(); i++) {
int positive = Integer.valueOf(numbers.substring(index, i + 1)) * 1;
permute(i + 1, numbers, result, sum + positive);
int negative = Integer.valueOf(numbers.substring(index, i + 1)) * -1;
permute(i + 1, numbers, result, sum + negative);
}
}

public static void main(String argv[]) {
printlist p = new printlist();
p.printresult("123");
}
}``````

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

I would solve this using Bit generator.
a) Write Bit Generator code where the width is 3. You get 8 combinations.
b) Replace 1s with +, and leave 0s as it is.
Ex: 0 1 0 => 1+23 = 24
c) Replace 1 with -, and you get another 8 combinations.

In the end we will have 15 unique combinations because 0 0 0 repeats twice.

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

``````void solve(string s, int curSum, int &finalSum) {
if (s.length() == 0) {
finalSum += curSum;
return;
}

int cur = 0;

for (int i = 0; i < s.length(); i++) {
cur = cur * 10 + s[i] - '0';
solve(s.substr(i + 1),curSum + cur,finalSum);
solve(s.substr(i + 1), curSum - cur, finalSum);
}
}

int plusMinusNone(string s) {
int res = 0;
solve(s,0,res);
return res;
}``````

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

It seems the problem is example of generating subset. But instead of subset we need to generate when to insert plus or minus between subset generated. I am trying to solve it using mask, to decide when to insert + or - or just to append number.

``````public class SignPlusMin {
/**
* 0: append "+"
* 1: append "-"
* 2: just append number
*/
private static int[] MASK = { 0, 1, 2 };

private List<String> subsetResult = new ArrayList<>();

public static void main(String[] args) {
SignPlusMin signPlusMin = new SignPlusMin();
signPlusMin.generateSubset("123");
for (String s: signPlusMin.subsetResult) {
System.out.println(s);
solveEquation(s); // TODO
}
}

public void generateSubset(String input) {
int[] mask = new int[input.length()];
subset(input, mask, 0);
}

private void subset(String input, int[] mask, int k) {
if (isSolution(input, k)) {
processSolution(input, mask);
} else {
k++;
for (int i = 0; i < MASK.length; i++) {
mask[k - 1] = MASK[i];
subset(input, mask, k);
}
}
}

private boolean isSolution(String input, int k) {
return k == input.length();
}

private void processSolution(String input, int[] mask) {
StringBuilder tmpBuilder = new StringBuilder();
for (int i = 0; i < input.length(); i++) {
if (mask[i] == 0) {
tmpBuilder.append("+");
} else if (mask[i] == 1) {
tmpBuilder.append("-");
}
tmpBuilder.append(input.charAt(i));
}
String tmp = tmpBuilder.toString();

// remove duplicate when subset started without sign
if (tmp.startsWith("+") || tmp.startsWith("-")) {
subsetResult.add(tmp);
}
}

}``````

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

package AmazonProbs;

import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;
import javax.script.ScriptException;

//You have a string of numbers, i.e. 123. You can insert a + or - sign in front of ever number, or you can leave it empty. Find all of the different possibilities, make the calculation and return the sum.
//For example;
//+1+2+3 = 6
//+12+3 = 15
//+123 = 123
//+1+23 = 24
//...
//-1-2-3 = 6
//...
//Return the sum of all the results.
//

public class PlusMinusNone {
public static void main(String[] args) {
String num= String.valueOf(123);
String val[]=new String[]{"+","-",""};
ScriptEngineManager s = new ScriptEngineManager();
ScriptEngine eng = s.getEngineByName("JavaScript");
for (int i = 0; i < val.length; i++) {
for (int j = 0; j < val.length; j++) {
for (int k = 0; k < val.length; k++) {
String str= (val[i] +num.charAt(0)+ val[j] +num.charAt(1) +val[k] + num.charAt(2));
try {
System.out.println(str + " = " +eng.eval(str));
} catch (ScriptException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}

}

}
}

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

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