Facebook Interview Question Software Developers
Country: United States
Interview Type: In-Person
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);
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();
}
}
}
}
}
}
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]
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')
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
}
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.
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);
}
}
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);
}
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));
}
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
}
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.
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");
}
}
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");
}
}
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.
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;
}
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);
}
}
}
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();
}
}
}
}
}
}
1. I think -1-2-3 should be equals to -6, not 6.
- jiahuang March 06, 20172. 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.