Facebook Interview Question for SDE1s


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);
}

- PenChief October 18, 2017 | Flag Reply
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' : '/' }

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

- NoOne October 19, 2017 | Flag Reply
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 {
		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]

- qmaur October 20, 2017 | Flag Reply
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++) {
					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);
		
	}

- sudip.innovates October 21, 2017 | Flag Reply
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;
}

- Alex October 27, 2017 | Flag Reply


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