## Facebook Interview Question for SDE1s

• 0

Country: United States

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

Assumptions:

* I am using integer arithmetic here (6/10=0)
* No multiplication precedence
* The order of the numbers is fixed. only the operators are changing

``````#include "CommonHeader.h"

typedef std::tuple<int, std::vector<int>, std::string> QueueElement;

bool isEqual42(std::vector<int> numbers)
{
if(numbers.size() != 5) return false;
std::queue<QueueElement> q;
int num = numbers[0];
numbers.erase(numbers.begin());
q.push(std::make_tuple(num, numbers, std::to_string(num)));
while(!q.empty()) {
QueueElement e = q.front();
q.pop();
int currentValue = std::get<0>(e);
std::vector<int> currentNumbers = std::get<1>(e);
std::string strOperation = std::get<2>(e);
if(currentNumbers.empty() && (currentValue == 42)) {
std::cout << "42=" << strOperation << std::endl;
return true;
} else if(currentNumbers.empty()) {
continue;
}

num = currentNumbers[0];
currentNumbers.erase(currentNumbers.begin());
q.push(std::make_tuple(currentValue + num, currentNumbers, strOperation + "+" + std::to_string(num)));
q.push(std::make_tuple(currentValue * num, currentNumbers, strOperation + "*" + std::to_string(num)));
if(num > 0) {
// division by zero
q.push(std::make_tuple(currentValue / num, currentNumbers, strOperation + "/" + std::to_string(num)));
}
q.push(std::make_tuple(currentValue - num, currentNumbers, strOperation + "-" + std::to_string(num)));
}
return false;
}

void checkIfEqual42(std::vector<int> numbers)
{
if(numbers.size() != 52) {
return;
}

// Pick 5 unique numbers
std::vector<int> fiveNumbers;
for(size_t i = 0; i < 5; ++i) {
int index = (rand() % numbers.size());
fiveNumbers.push_back(numbers[index]);
numbers.erase(numbers.begin() + index);
}
isEqual42(fiveNumbers);
}``````

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

``````/*
Step 1: Pick 5 numbers from 1...52. That is al combinations of C(52,5)
achivable using comb([1:53],5)
Now, pick any of these 4 ops [ +,-,*,/] on these 5 numbers.
Use floating point to be exact
Each permutation has then 4^4 ways of assigning operators.
stringify it, do an eval.
Check it out if result is 42
*/
__OPS__ = { _'0' : '+' , _'1' : '-' , _'2' : '*' , _'3' : '/' }

total_ops = 4 ** 4
// create the operator varities
ops = list()
for ( k : [0:total_ops] ){
s = str(k,4)
s = '0' ** (4 - size(s)) + s // left pad by '0'
ops += s
}
// select tuple from C(52,5) :: for demo.. we have to 8
for ( nums : comb( [1:8] , 5 ) ){
// select operators....
for ( op : ops ){
s = ''
for ( i = 0; i < 4; i+= 1 ){
s += ( str(nums[i]) + '.0' +  __OPS__[ op[i] ] )
}
s += ( str(nums[4]) + '.0' )
// do eval ?
x = #'#{s}' // yes
if ( x == 42.0 ) {
// the answer to life, universe and everything...
println(s)
}
}
}
}

Yields...
=====
1.0*3.0*4.0+5.0*6.0
1.0/2.0*3.0*4.0*7.0
1.0+2.0*3.0+5.0*7.0
1.0+2.0+4.0+5.0*7.0
1.0*3.0+4.0+5.0*7.0
1.0+2.0-3.0+6.0*7.0
1.0+2.0*4.0*6.0-7.0
1.0+3.0-4.0+6.0*7.0
2.0+3.0+5.0*6.0+7.0
2.0+3.0-5.0+6.0*7.0
1.0+4.0+5.0*6.0+7.0
1.0+4.0-5.0+6.0*7.0
=====

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

``````import java.util.*;
import java.util.stream.*;
import java.util.function.*;

class Sum42 {

enum Op {
MINUS("-", Math::subtractExact),
MUL("*", Math::multiplyExact),
DIV("/", Math::floorDiv);

String opName;
BiFunction<Integer, Integer, Integer> opFunc;

Op(String opName, BiFunction<Integer, Integer, Integer> opFunc) {
this.opName = opName;
this.opFunc = opFunc;
}

int apply(int i, int y) {
return opFunc.apply(i, y);
}
}

static Stream<List<Op>> ops() {
return perms_(0, 4, true, Arrays.asList(Op.values()), new ArrayList<>());
}

static Stream<List<Integer>> perms(int n) {
List<Integer> li = IntStream.range(0, n + 1)
.mapToObj(x -> x)
.collect(Collectors.toList());
return perms_(0, 5, false, li, new ArrayList<>());
}

static <Z> Stream<List<Z>> perms_(int count, int limit, boolean dup, List<Z> input, List<Z> acc) {
if (count == limit) {
return Stream.of(acc);
} else {
return input.stream()
.filter(x -> dup || !acc.contains(x))
.flatMap(x -> {
List<Z> newAcc = new ArrayList<>(acc);
return perms_(count + 1, limit, dup, input, newAcc);
});
}
}

public static void main(String[] args) {
perms(52).limit(100).forEach(p -> {
ops().filter(ops -> {
int res = p.get(0);
int index = 1;
for (Op op : ops) {
res = op.apply(res, p.get(index++));
}
return res == 42;
})
.findFirst()
.ifPresent(ops -> System.err.println(p + " " + ops));
});
}
}``````

gives:

``````[0, 1, 2, 3, 7] [PLUS, PLUS, PLUS, MUL]
[0, 1, 2, 3, 14] [PLUS, DIV, PLUS, MUL]
[0, 1, 2, 3, 21] [PLUS, MINUS, PLUS, MUL]
[0, 1, 2, 3, 33] [PLUS, PLUS, MUL, PLUS]
[0, 1, 2, 3, 36] [PLUS, PLUS, PLUS, PLUS]
[0, 1, 2, 3, 37] [PLUS, MUL, PLUS, PLUS]
[0, 1, 2, 3, 38] [MINUS, PLUS, PLUS, PLUS]
[0, 1, 2, 3, 39] [PLUS, DIV, PLUS, PLUS]
[0, 1, 2, 3, 40] [PLUS, MINUS, PLUS, PLUS]
[0, 1, 2, 3, 41] [PLUS, PLUS, DIV, PLUS]
[0, 1, 2, 3, 42] [PLUS, PLUS, MINUS, PLUS]
[0, 1, 2, 3, 43] [PLUS, MINUS, DIV, PLUS]
[0, 1, 2, 3, 44] [MINUS, PLUS, MINUS, PLUS]
[0, 1, 2, 3, 45] [PLUS, MINUS, MUL, PLUS]
[0, 1, 2, 3, 46] [PLUS, MINUS, MINUS, PLUS]
[0, 1, 2, 3, 47] [MINUS, MUL, MINUS, PLUS]
[0, 1, 2, 3, 48] [MINUS, MINUS, MINUS, PLUS]
[0, 1, 2, 3, 51] [MINUS, MINUS, MUL, PLUS]
[0, 1, 2, 4, 6] [PLUS, PLUS, PLUS, MUL]
[0, 1, 2, 4, 7] [PLUS, MUL, PLUS, MUL]
[0, 1, 2, 4, 14] [PLUS, MINUS, PLUS, MUL]
[0, 1, 2, 4, 21] [MINUS, MUL, PLUS, MUL]
[0, 1, 2, 4, 30] [PLUS, PLUS, MUL, PLUS]
[0, 1, 2, 4, 34] [PLUS, MUL, MUL, PLUS]
[0, 1, 2, 4, 35] [PLUS, PLUS, PLUS, PLUS]
[0, 1, 2, 4, 36] [PLUS, MUL, PLUS, PLUS]
[0, 1, 2, 4, 37] [MINUS, PLUS, PLUS, PLUS]
[0, 1, 2, 4, 38] [PLUS, DIV, PLUS, PLUS]
[0, 1, 2, 4, 39] [PLUS, MINUS, PLUS, PLUS]
[0, 1, 2, 4, 40] [MINUS, MUL, PLUS, PLUS]
[0, 1, 2, 4, 41] [MINUS, MINUS, PLUS, PLUS]
[0, 1, 2, 4, 42] [PLUS, PLUS, DIV, PLUS]
[0, 1, 2, 4, 43] [PLUS, PLUS, MINUS, PLUS]
[0, 1, 2, 4, 44] [PLUS, MUL, MINUS, PLUS]
[0, 1, 2, 4, 45] [MINUS, PLUS, MINUS, PLUS]
[0, 1, 2, 4, 46] [PLUS, MINUS, MUL, PLUS]
[0, 1, 2, 4, 47] [PLUS, MINUS, MINUS, PLUS]
[0, 1, 2, 4, 48] [MINUS, MUL, MINUS, PLUS]
[0, 1, 2, 4, 49] [MINUS, MINUS, MINUS, PLUS]
[0, 1, 2, 4, 50] [MINUS, MUL, MUL, PLUS]``````

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

``````public static void main(String[] args) {
Set<List<Integer>> set = new HashSet<>();
choose(1, new int[5], 0, set);
System.out.println(set.size());
}

/**
* Given numbers 1 through 52, take 5 unique numbers and determine if the
* number 42 can be made using any combination of addition (+), subtraction
* (-), multiplication (*), and division (/) on those 5 numbers
*/

public static void choose(int n, int[] nums, int ind, Set<List<Integer>> set) {
if (n > 52)
return;
if (ind == 5) {
check(nums, new ArrayList<Integer>(), 0, set);
return;
}

nums[ind] = n;
choose(n + 1, nums, ind + 1, set);
choose(n + 1, nums, ind, set);
}

public static void check(int[] nums, List<Integer> list, int ind, Set<List<Integer>> set) {

if (ind > 4) {
int sum = 0;
for (int i : list)
sum += i;
if (sum == 42){
List<Integer> s = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
}
//System.out.println(set);
}
return;
}

check(nums, list, ind + 1, set);
list.remove(new Integer(nums[ind]));

// for subtract
check(nums, list, ind + 1, set);
list.remove(new Integer(-nums[ind]));

// for multiply
int get = 1;
if (list.size() > 0) {
get = list.get(list.size() - 1);
list.remove(list.size() - 1);
}
check(nums, list, ind + 1, set);
list.remove(new Integer(get * nums[ind]));

// for divide
get = 1;
if (list.size() > 0) {
get = list.get(list.size() - 1);
list.remove(list.size() - 1);
}
check(nums, list, ind + 1, set);
list.remove(new Integer(get / nums[ind]));

}``````

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

Using integer division. 2597419 valid subsets found.

``````#include <iostream>
#include <vector>
#include <unordered_set>
#include <string>

using namespace std;

void GetSubsets(int max, int size, unordered_set<int> &subset, vector<unordered_set<int>> &subsets, int n = 1)
{
if (n < 0 ||
n > max + 1 ||
size <= 0 ||
subset.size() > size)
{
return;
}
if (subset.size() == size) {
subsets.push_back(subset);
return;
}
GetSubsets(max, size, subset, subsets, n + 1);
subset.insert(n);
GetSubsets(max, size, subset, subsets, n + 1);
subset.erase(n);
}

bool EquationIsTrue(unordered_set<int> &a, int val, vector<string> &equation, bool first_operand = true, int val_so_far = 0)
{
if (a.empty()) {
return val_so_far == val;
}
std::vector<int> keys(a.begin(), a.end());
for (int n : keys) {
a.erase(n);
if (first_operand) {
equation.push_back(to_string(n));
if (EquationIsTrue(a, val, equation, false, n)) {
return true;
}
equation.pop_back();
} else {
equation.push_back('+' + to_string(n));
if (EquationIsTrue(a, val, equation, false, val_so_far + n)) {
return true;
}
equation.pop_back();
equation.push_back('-' + to_string(n));
if (EquationIsTrue(a, val, equation, false, val_so_far - n)) {
return true;
}
equation.pop_back();
equation.push_back('*' + to_string(n));
if (EquationIsTrue(a, val, equation, false, val_so_far * n)) {
return true;
}
equation.pop_back();
equation.push_back('/' + to_string(n));
if (EquationIsTrue(a, val, equation, false, val_so_far / n)) {
return true;
}
equation.pop_back();
}
a.insert(n);
}
return false;
}

int main(int argvc, char const **argv)
{
unordered_set<int> subset;
vector<unordered_set<int>> subsets;
GetSubsets(52, 5, subset, subsets);
reverse(subsets.begin(), subsets.end());

vector<string> equation;
int val = 42;
for (auto s : subsets) {
equation.clear();
if (EquationIsTrue(s, val, equation)) {
for (int i = 0; i < equation.size(); ++i) {
cout << '(';
}
for (auto s : equation) {
cout << s << ')';
}
cout << "=" << val << "\n";
}
}
return 0;
}``````

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.

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