Facebook Interview Question
SDE1sCountry: United States
/*
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' : '/' }
def do_facebook(){
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)
}
}
}
}
do_facebook()
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
=====
import java.util.*;
import java.util.stream.*;
import java.util.function.*;
class Sum42 {
enum Op {
PLUS("+", Math::addExact),
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);
newAcc.add(x);
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]
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++) {
s.add(nums[i]);
}
set.add(s);
//System.out.println(set);
}
return;
}
// for add
list.add(nums[ind]);
check(nums, list, ind + 1, set);
list.remove(new Integer(nums[ind]));
// for subtract
list.add(-nums[ind]);
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);
}
list.add(get * nums[ind]);
check(nums, list, ind + 1, set);
list.remove(new Integer(get * nums[ind]));
list.add(get);
// for divide
get = 1;
if (list.size() > 0) {
get = list.get(list.size() - 1);
list.remove(list.size() - 1);
}
list.add(get / nums[ind]);
check(nums, list, ind + 1, set);
list.remove(new Integer(get / nums[ind]));
list.add(get);
}
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;
}
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
- PenChief October 18, 2017