Google Interview Question for Software Engineer in Tests


Country: United States
Interview Type: Phone Interview




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

Let's first solve simplified problem: Let assume that we are only interested if there exist a solution such that 'target' integer can be expressed by combination of given integers in array 'a', operators '+ - * /' and braces '( )'. For instance, given integers 30 2 2 and a target value 16 then 16 = (2+30)/2, however there is no solution if the target value was 8.

Notice that if you remove two numbers from the array 'a' of the length N, apply an operator to these values and append the new value to the array 'a', you obtain a new array of the length N-1. Now you have to solve exactly the same problem as in the beginning, however with reduced size to N-1.

Hence the problem can be solved recursively, in each recursive call try all pairs from 'a' with all operators, while reducing the problem. Eventually the array contains a single integer, the base case. If the integer is equal to the target value we are done : the target value can be expressed as valid mathematical expression composed of given operators, braces and by given N integers. Otherwise we have to explore different branch of the tree.

There are two important remarks:
1) Let assume that non-integer division is not allowed
2) Division operator is not symmetric, hence in general x/y != y/x
This must be carefully handled in the code.

Finally, to solve the original problem we have to modify the recursive algorithm such that it will be able to keep track of the expression. This can be implemented via linked list of strings.

A sample code is shown below:

public static String decompose(int[] a, int target) {
	LinkedList<Integer> x = new LinkedList<Integer>();
	LinkedList<String> expr = new LinkedList<String>();
	for (Integer y : a) {
		x.addLast(y);
		expr.addLast(y+"");
	}

	return decompose(x, expr, target);
}

private static String decompose(LinkedList<Integer> x, LinkedList<String> expr, int target) {
	if (x.size() == 1) { 			// Base case
		if (x.get(0) == target) 	return (expr.get(0)+" = "+target);
		else 						return null;
	}

	for (int i = 0; i<x.size(); i++) {
		for (int j = i+1; j<x.size(); j++) {
			int a = x.get(j);
			int b = x.get(i);
			
			String ae = exp.get(j);
			String be = exp.get(i); 
			
			for (int k=0; k<5; k++) {
 				// Copy of the integer list
				LinkedList<Integer> xnew = new LinkedList<Integer>() ;
				for (Integer y : x) { xnew.addLast(y); }
				xnew.remove(j); xnew.remove(i);
 				// Copy of the expression string list
				LinkedList<String> exprnew = new LinkedList<String>();
				for (String s : expr) { exprnew.addLast(s); }
				exprnew.remove(j); exprnew.remove(i);
 				// Handling division and zero
				if ( k==3 && (b==0 || a%b != 0)) 	continue;
				if ( k==4 && (a==0 || b%a != 0)) 	continue;
				// Applying operator
				int res = applyOperator(a, b, k);
				xnew.addFirst(res);	
				// Merging expression strings 
				String e = stringOperator(ae, be, k);
				exprnew.addFirst(e);
				
				String ans = decompose(xnew, exprnew, target);
				if (ans != null)					return ans;
			}
		}
	}
	return null;
}

private static int applyOperator(int a, int b, int k) {
	switch (k) {
		case 0: 	return a+b;
		case 1: 	return a-b;
		case 2: 	return a*b;
		case 3:     return a/b;
	}
	return b/a;
}

private static String stringOperator(String ae, String be, int k) {
	if (ae.matches(".+[-+*/].+"))	ae = "(" + ae + ")";
	if (be.matches(".+[-+*/].+"))	be = "(" + be + ")";

	switch (k) {
		case 0: 	return ae + "+" + be;
		case 1: 	return ae + "-" + be;
		case 2: 	return ae + "*" + be;
		case 3: 	return ae + "/" + be;
	}
	return be + "/" + ae;
}

Notice that division is handled by two cases: 'k=3' for 'a/b' and 'k=4' for b/k. Indeed it works, example:
input: 4, [5 7 13 169]
output: (7+(169/13))/5 = 4

- autoboli April 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

There's a bug when applying the division operator no? You're returning a/b, both integers. What if the solution requires a/b to be not an integer?

- Anonymous November 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Brute force here is fine .. we don't need to count any parenthesis and just try to invoke +,-,*,/,j.
So the complexity will be:
4! - Generating permutations of the given number
4^4 - Assigning the operators between the number and evaluating them.

which is very reasonable to run in a more than fair amount of time.

A simple recursive solution:

#include <vector>
#include <iostream>
#include <algorithm>

#define RES 24

using namespace std;

bool is24(vector<int>& v,int start,long long res)
{
     if (start >= v.size()) {
        return res == RES;
     }

     for (int k=start;k<v.size();++k) {
        swap(v[start],v[k]);
        if (is24(v,start+1,res + v[start])) return true; // check addition
        if (is24(v,start+1,res * v[start])) return true; // check mul
        if (is24(v,start+1,res - v[start])) return true; // check minus
        if (is24(v,start+1,res / v[start])) return true; // check divide
        swap(v[start],v[k]);
     }
     return false;
}


int main()
{
    vector<int> v = {1,2,3,88};
    if (is24(v,0,0))
        cout << "True" << endl;
    else
        cout << "False" << endl;
}

- Someone. April 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It looks like your code is not working, did you test it? :)

- autoboli April 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes i did, the example in the main should not work.
On which input it doesn't work for you ?

- Someone. April 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes i did, the example in the main should not work.
On which input it doesn't work for you ?

- Someone. April 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I agree with no parens.
We don't need to worry about parens in general because the problem did not specify the order so one of permutations will eventually cover paren case.

- istudy January 31, 2016 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

var decompose = function (A, B, s) {
	if (!A.length) {
		B.push(s);
		return;
	}
	if (!s.length) {
		s += '(' + A[0] + ')';
		return decompose(A.slice(1), B, s);
	}
	for (var i = 0; i < A.length; i++) {
		decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + s + ' + ' + A[i] + ')');
		decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + s + ' * ' + A[i] + ')');
		decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + s + ' - ' + A[i] + ')');
		decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + A[i] + ' - ' + s + ')');
		decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + s + ' / ' + A[i] + ')');
		decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + A[i] + ' / ' + s + ')');
	}
}

var solveFourIntegers = function (A, target) {
	var B = [];
	decompose(A.slice(), B, "");
	return B.filter(function (exp) {
		return eval(exp) === target;
	});
};

console.log(solveFourIntegers([2,3,4,6], 24));

//output

[ '(((3 - (2)) * 4) * 6)',
  '(6 / ((3 - (2)) / 4))',
  '((4 / (3 - (2))) * 6)',
  '(((3 - (2)) * 6) * 4)',
  '(4 / ((3 - (2)) / 6))',
  '((6 / (3 - (2))) * 4)',
  '((((2) + 4) * 3) + 6)',
  '((6 - ((2) - 4)) * 3)',
  '(((4 - (2)) + 6) * 3)',
  '(((4 / (2)) + 6) * 3)',
  '((((2) * 6) - 4) * 3)',
  '((4 - ((2) - 6)) * 3)',
  '(((6 - (2)) + 4) * 3)',
  '(((6 / (2)) + 3) * 4)' ]

- srterpe May 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

var decompose = function (A, B, s) {
	if (!A.length) {
		B.push(s);
		return;
	}
	if (!s.length) {
		s += '(' + A[0] + ')';
		return decompose(A.slice(1), B, s);
	}
	for (var i = 0; i < A.length; i++) {
		decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + s + ' + ' + A[i] + ')');
		decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + s + ' * ' + A[i] + ')');
		decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + s + ' - ' + A[i] + ')');
		decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + A[i] + ' - ' + s + ')');
		decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + s + ' / ' + A[i] + ')');
		decompose(A.slice(0, i).concat(A.slice(i+1, A.length)), B, '(' + A[i] + ' / ' + s + ')');
	}
}

var solveFourIntegers = function (A, target) {
	var B = [];
	decompose(A.slice(), B, "");
	return B.filter(function (exp) {
		return eval(exp) === target;
	});
};

console.log(solveFourIntegers([2,3,4,6], 24));

//output
[ '(((3 - (2)) * 4) * 6)',
  '(6 / ((3 - (2)) / 4))',
  '((4 / (3 - (2))) * 6)',
  '(((3 - (2)) * 6) * 4)',
  '(4 / ((3 - (2)) / 6))',
  '((6 / (3 - (2))) * 4)',
  '((((2) + 4) * 3) + 6)',
  '((6 - ((2) - 4)) * 3)',
  '(((4 - (2)) + 6) * 3)',
  '(((4 / (2)) + 6) * 3)',
  '((((2) * 6) - 4) * 3)',
  '((4 - ((2) - 6)) * 3)',
  '(((6 - (2)) + 4) * 3)',
  '(((6 / (2)) + 3) * 4)' ]

- srterpe May 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
   output:
[2,3,5,11] = 24
(5-(3-(2*11))) = 24

[7,8,9,3] = 24
(8*3) = 24

[7,7,7,7] = 24
NO SOLUTION = 24

[1,2,3,4] = 24
(3*(2*4)) = 24

[100,50,20,5] = 24
((100+20)/5) = 24

*/
function express(tree) {
    if(tree.left) {
        return "("+express(tree.left)+tree.operation+express(tree.right)+")";
    }
    else {
        return tree.value;
    }
}

function solve(array, target) {
    
    var nodes = [];
    for(var i=0;i<array.length;i++) {
        nodes.push(
            {
                value:array[i],
                bits: 1<<i
            }
        );
    }
    
    for(var i=0;i<nodes.length;i++) {
        for(var j=0;j<nodes.length;j++) {
            if(i!=j) {
                if(nodes[j].value==target) {
                    return express(nodes[j]);
                }
                
                var nodeLeft = nodes[i];
                var nodeRight = nodes[j];
                if((nodeLeft.bits & nodeRight.bits) == 0) {
                    nodes.push(
                        {
                            operation:'+',
                            value:nodeLeft.value+nodeRight.value,
                            left:nodeLeft,
                            right:nodeRight,
                            bits: nodeLeft.bits|nodeRight.bits
                        }
                    );
                    nodes.push(
                        {
                            operation:'-',
                            value:nodeLeft.value-nodeRight.value,
                            left:nodeLeft,
                            right:nodeRight,
                            bits: nodeLeft.bits|nodeRight.bits
                        }
                    );
                    nodes.push(
                        {
                            operation:'*',
                            value:nodeLeft.value*nodeRight.value,
                            left:nodeLeft,
                            right:nodeRight,
                            bits: nodeLeft.bits|nodeRight.bits
                        }
                    );
                    nodes.push(
                        {
                            operation:'/',
                            value:nodeLeft.value/nodeRight.value,
                            left:nodeLeft,
                            right:nodeRight,
                            bits: nodeLeft.bits|nodeRight.bits
                        }
                    );
                }
            }
        }
    }
    return "NO SOLUTION";
}




function outputSolution(array, target) {
    var html = "<b>[" + array + "]</b> = <i>" + target + "</i>";
    var div = document.createElement("div");

    var result = solve(array, target);
    div.innerHTML = html + "<br>" + result + " = " + target + "<hr>";
    document.body.appendChild(div);
}

outputSolution([2, 3, 5, 11], 24);
outputSolution([7, 8, 9, 3], 24);
outputSolution([7, 7, 7, 7], 24);
outputSolution([1, 2, 3, 4], 24);
outputSolution([100, 50, 20, 5], 24);

- Jack Le Hamster May 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Javascript code on jsfiddle/jacklehamster/z3gyv29a/

/* output:
[2,3,5,11] = 24
(5-(3-(2*11))) = 24

[7,8,9,3] = 24
(8*3) = 24

[7,7,7,7] = 24
NO SOLUTION = 24

[1,2,3,4] = 24
(3*(2*4)) = 24

[100,50,20,5] = 24
((100+20)/5) = 24
*/


function express(tree) {
    if(tree.left) {
        return "("+express(tree.left)+tree.operation+express(tree.right)+")";
    }
    else {
        return tree.value;
    }
}

function solve(array, target) {
    
    var nodes = [];
    for(var i=0;i<array.length;i++) {
        nodes.push(
            {
                value:array[i],
                bits: 1<<i
            }
        );
    }
    
    for(var i=0;i<nodes.length;i++) {
        for(var j=0;j<nodes.length;j++) {
            if(i!=j) {
                if(nodes[j].value==target) {
                    return express(nodes[j]);
                }
                
                var nodeLeft = nodes[i];
                var nodeRight = nodes[j];
                if((nodeLeft.bits & nodeRight.bits) == 0) {
                    nodes.push(
                        {
                            operation:'+',
                            value:nodeLeft.value+nodeRight.value,
                            left:nodeLeft,
                            right:nodeRight,
                            bits: nodeLeft.bits|nodeRight.bits
                        }
                    );
                    nodes.push(
                        {
                            operation:'-',
                            value:nodeLeft.value-nodeRight.value,
                            left:nodeLeft,
                            right:nodeRight,
                            bits: nodeLeft.bits|nodeRight.bits
                        }
                    );
                    nodes.push(
                        {
                            operation:'*',
                            value:nodeLeft.value*nodeRight.value,
                            left:nodeLeft,
                            right:nodeRight,
                            bits: nodeLeft.bits|nodeRight.bits
                        }
                    );
                    nodes.push(
                        {
                            operation:'/',
                            value:nodeLeft.value/nodeRight.value,
                            left:nodeLeft,
                            right:nodeRight,
                            bits: nodeLeft.bits|nodeRight.bits
                        }
                    );
                }
            }
        }
    }
    return "NO SOLUTION";
}




function outputSolution(array, target) {
    var html = "<b>[" + array + "]</b> = <i>" + target + "</i>";
    var div = document.createElement("div");

    var result = solve(array, target);
    div.innerHTML = html + "<br>" + result + " = " + target + "<hr>";
    document.body.appendChild(div);
}

outputSolution([2, 3, 5, 11], 24);
outputSolution([7, 8, 9, 3], 24);
outputSolution([7, 7, 7, 7], 24);
outputSolution([1, 2, 3, 4], 24);
outputSolution([100, 50, 20, 5], 24);

- Jack Le Hamster May 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

(((160%4 )-20)*3)+(-36) = 24

PS: Question says use Integers so (-34) is a negative integer not an operand minus that is used twice.

- SS May 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool find_exp_aux(std::vector<int> & v, std::vector<std::string>& e, const int t, std::string& r)
{
    if (v.empty()) return false;
    auto n = v.size();
    if (1 == n)
    {
        if (t == v[0])
        {
            r = e[0];
            return true;
        }
        return false;
    }
    for (auto i = 0; i < n; ++i)
    {
        auto v1 = v[i];
        const auto& e1 = e[i];
        for (auto j = i + 1; j < n; ++j)
        {
            auto v2 = v[j];
            const auto& e2 = e[j];
            auto vc(v);
            auto ec(e);
            vc.erase(vc.begin() + j);
            vc.erase(vc.begin() + i);
            ec.erase(ec.begin() + j);
            ec.erase(ec.begin() + i);
            auto vnew = 0;
            std::string enew = "";
            vnew = v1 + v2;
            enew = "(" + e1 + ")" + "+" + "(" + e2 + ")";
            vc.push_back(vnew);
            ec.push_back(enew);
            if (find_exp_aux(vc, ec, t, r)) return true;
            ec.pop_back();
            vc.pop_back();
            vnew = v1 * v2;
            enew = "(" + e1 + ")" + "*" + "(" + e2 + ")";
            vc.push_back(vnew);
            ec.push_back(enew);
            if (find_exp_aux(vc, ec, t, r)) return true;
            ec.pop_back();
            vc.pop_back();
            vnew = v1 - v2;
            enew = "(" + e1 + ")" + "-" + "(" + e2 + ")";
            vc.push_back(vnew);
            ec.push_back(enew);
            if (find_exp_aux(vc, ec, t, r)) return true;
            ec.pop_back();
            vc.pop_back();
            vnew = v2 - v1;
            enew = "(" + e2 + ")" + "-" + "(" + e1 + ")";
            vc.push_back(vnew);
            ec.push_back(enew);
            if (find_exp_aux(vc, ec, t, r)) return true;
            ec.pop_back();
            vc.pop_back();
            if (0 != v2)
            {
                vnew = v1 / v2;
                enew = "(" + e1 + ")" + "/" + "(" + e2 + ")";
                vc.push_back(vnew);
                ec.push_back(enew);
                if (find_exp_aux(vc, ec, t, r)) return true;
                ec.pop_back();
                vc.pop_back();
            }
            if (0 != v1)
            {
                vnew = v2 / v1;
                enew = "(" + e2 + ")" + "/" + "(" + e1 + ")";
                vc.push_back(vnew);
                ec.push_back(enew);
                if (find_exp_aux(vc, ec, t, r)) return true;
                ec.pop_back();
                vc.pop_back();
            }
        }
    }
    return false;
}

bool find_exp(const std::vector<int>& v, const int t, std::string& r)
{
    std::vector<int> vc(v);
    std::vector<std::string> ec;
    for (auto i : vc)
    {
        ec.push_back(std::to_string(i));
    }
    return find_exp_aux(vc, ec, t, r);
}

- Omri.Bashari May 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a somewhat different solution, brute force using polish expression for evaluation
and infix to print out the solution (superfluous parentheses are skipped):

import java.util.*;

class CareerCup_5735906000502784{
    public static void main(String[]arg){
        System.out.println(gen(new int[]{5, 7, 13, 169}, 4));
    }

    private static char[] OPERATORS = "+-*/".toCharArray();

    public static String gen(int[] numbers, int target){
        String[] expr = new String[2*numbers.length-1];
        for(int j = 0; j < numbers.length; ++j){
            expr[j] = ""+numbers[j];
        }

        int[] selectedOperatorIds = new int[numbers.length-1];
        selectedOperatorIds[0] = -1;
        int allOperatorComboCount = exp(OPERATORS.length,selectedOperatorIds.length);
        for(int i = 0; i < allOperatorComboCount; ++i){
            genNextOperatorCombos(expr, numbers.length, selectedOperatorIds);
            String ret = find(expr, target, 0, expr.length);
            if (ret != null) return ret;
        }

        return null;
    }

    private static String find(String[] expr, int target, int lo, int hi){
        if (lo == hi){
            String ret = eval(expr, target);
            return ret;
        }
        for(int i = lo; i < hi; ++i){
            swap(expr, lo, i);
            String ret = find(expr, target, lo+1, hi);
            if (ret != null) return ret;
            swap(expr, lo, i);
        }
        return null;
    }

    private static String eval(String[] expr, int target){
        Deque<String> stack = new ArrayDeque<>();
        for(int i = expr.length-1; i >= 0; --i){
            String op = expr[i];
            if (isOperand(op)){
                stack.push(op);
            } else {
                String operator = op;
                if (stack.isEmpty()) return null;
                String a = stack.pop();
                if (stack.isEmpty()) return null;
                String b = stack.pop();
                Integer val = eval(Integer.parseInt(a), operator.charAt(0), Integer.parseInt(b));
                if (val == null) return null;
                stack.push(val.toString());
            }
        }
        if (stack.isEmpty()) return null;
        if (target == Integer.parseInt(stack.pop())){
            return polishToInfix(expr);
        }
        return null;
    }

    private static String polishToInfix(String[] expr){
        Deque<String> stack = new ArrayDeque<>();
        for(int i = expr.length-1; i >= 0; --i){
            String op = expr[i];
            if (isOperand(op)){
                stack.push(op);
            } else {
                stack.push(
                        String.format("%s%s%s%s%s",
                                parenthesesIfNeeded(op, "("),
                                stack.pop(), op, stack.pop(),
                                parenthesesIfNeeded(op, ")")));
            }
        }
        return stack.pop();
    }

    private static String parenthesesIfNeeded(String operator, String p){
        if (operator.equals("+") || operator.equals("-")) return p;
        return "";
    }

    private static Integer eval(int a, char op, int b){
        switch (op){
            case '+': return a+b;
            case '*': return a*b;
            case '-': return a-b;
            case '/':
                if (b == 0) return null;
                else return a/b;
            default: throw new IllegalArgumentException(""+op);
        }
    }

    private static boolean isOperand(String s){
        return s.charAt(s.length()-1) >= '0' && s.charAt(s.length()-1) <= '9';
    }

    private static void swap(String[] ss, int from, int to){
        String tmp = ss[from];
        ss[from] = ss[to];
        ss[to] = tmp;
    }

    private static void genNextOperatorCombos(String[] expr, int shift, int[] selectedOperatorIds){
        stepCursor(selectedOperatorIds, OPERATORS.length);
        for(int j = 0; j < selectedOperatorIds.length; ++j){
            expr[shift+j] = ""+ OPERATORS[selectedOperatorIds[j]];
        }
    }

    private static void stepCursor(int[] cursor, int limit){
        for(int i = 0; i < cursor.length; ++i){
            int prev = cursor[i];
            cursor[i] = (cursor[i]+1)%limit;
            if (prev < cursor[i]) break;
        }
    }

    public static int exp(int base, int exp){
        int ret = 1;
        while(exp > 0){
            if ((exp & 1) > 0) ret *= base;
            base *= base;
            exp >>= 1;
        }
        return ret;
    }
}

- madno May 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The solution below also handles non integer division. Brackets aren't normalized, but returned expression is nevertheless valid. I think the code is self explanatory:

static string GetExp(int[] nums)
{
    bool[] used = new bool[nums.Length];
    return GetExp(nums, used, nums.Length, 24);
}

static string GetExp(int [] nums, bool [] used, int numsLeft, double sum)
{
    for (int i = 0; i < nums.Length; i++)
    {
        if (used[i])
            continue;

        int x = nums[i];

        if (numsLeft == 1)
        {
            return x == sum ? x.ToString() : null;
        }

        used[i] = true;

        string res = GetExp(nums, used, numsLeft, sum, x);
        if (res != null)
        {
            return res;
        }

        used[i] = false;
    }

    return null;
}

static string GetExp(int[] nums, bool[] used, int numsLeft, double sum, int x)
{
    string res;

    // x + <next>
    res = GetExp(nums, used, numsLeft - 1, sum - x);
    if (res != null)
    {
        return "(" + x.ToString() + "+" + res + ")";
    }

    // x - <next>
    if (x >= sum)
    {
        res = GetExp(nums, used, numsLeft - 1, x - sum);
        if (res != null)
        {
            return "(" + x.ToString() + "-" + res + ")";
        }
    }

    // <next> - x
    res = GetExp(nums, used, numsLeft - 1, sum + x);
    if (res != null)
    {
        return "(" + res + "-" + x.ToString() + ")";
    }

    // x * <next>
    res = GetExp(nums, used, numsLeft - 1, sum / x);
    if (res != null)
    {
        return x.ToString() + "*" + res;
    }

    // x / <next>
    res = GetExp(nums, used, numsLeft - 1, x / sum);
    if (res != null)
    {
        return x.ToString() + "/" + res;
    }

    // <next> / x
    if (x != 0)
    {
        res = GetExp(nums, used, numsLeft - 1, x * sum);
        if (res != null)
        {
            return res + "/" + x.ToString();
        }
    }

    return null;
}

- Anonymous July 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I'm kinda confused by this question personally, for example can we only use the numbers given or can we use any number as well as the given numbers?

If we can use any numbers we want then I think something along the lines of:

public int return24(int one, int two, int three, int four) {
    		return ((one + two + three + four) * 0) + 24;
    }

Would solve this problem. I could be missing something though?

- Kyle McNutt April 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think according to problem description usage of numbers like 0 or 24 from your example is not allowed.

- Mike L April 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

2*6+3*4

- marcelo segura April 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

2*6+3*4

- marcelo segura April 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Brute force here is fine .. we don't need to count any parenthesis and just try to invoke +,-,*,/,j.
So the complexity will be:
4! - Generating permutations of the given number
4^4 - Assigning the operators between the number and evaluating them.

which is very reasonable to run in a more than fair amount of time.

A simple recursive solution:

#include <vector>
#include <iostream>
#include <algorithm>

#define RES 24

using namespace std;

bool is24(vector<int>& v,int start,long long res)
{
     if (start >= v.size()) {
        return res == RES;
     }

     for (int k=start;k<v.size();++k) {
        swap(v[start],v[k]);
        if (is24(v,start+1,res + v[start])) return true; // check addition
        if (is24(v,start+1,res * v[start])) return true; // check mul
        if (is24(v,start+1,res - v[start])) return true; // check minus
        if (is24(v,start+1,res / v[start])) return true; // check divide
        swap(v[start],v[k]);
     }
     return false;
}


int main()
{
    vector<int> v = {1,2,3,88};
    if (is24(v,0,0))
        cout << "True" << endl;
    else
        cout << "False" << endl;
}

- Someone. April 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Just use brute force. (4! * 4^4)

#include <vector>
#include <iostream>
#include <algorithm>

#define RES 24

using namespace std;

bool is24(vector<int>& v,int start,long long res)
{
     if (start >= v.size()) {
        return res == RES;
     }

     for (int k=start;k<v.size();++k) {
        swap(v[start],v[k]);
        if (is24(v,start+1,res + v[start])) return true; // check addition
        if (is24(v,start+1,res * v[start])) return true; // check mul
        if (is24(v,start+1,res - v[start])) return true; // check minus
        if (is24(v,start+1,res / v[start])) return true; // check divide
        swap(v[start],v[k]);
     }
     return false;
}

/*
bool is24i(const vector<v>& v)
{
     // generate all permutations - can be done by preprocessing.

     // check assignments
}
*/

int main()
{
    vector<int> v = {1,2,3,88};
    if (is24(v,0,0))
        cout << "True" << endl;
    else
        cout << "False" << endl;
}

- Anonymous April 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Just use brute force. (4! * 4^4)

#include <vector>
#include <iostream>
#include <algorithm>

#define RES 24

using namespace std;

bool is24(vector<int>& v,int start,long long res)
{
     if (start >= v.size()) {
        return res == RES;
     }

     for (int k=start;k<v.size();++k) {
        swap(v[start],v[k]);
        if (is24(v,start+1,res + v[start])) return true; // check addition
        if (is24(v,start+1,res * v[start])) return true; // check mul
        if (is24(v,start+1,res - v[start])) return true; // check minus
        if (is24(v,start+1,res / v[start])) return true; // check divide
        swap(v[start],v[k]);
     }
     return false;
}

/*
bool is24i(const vector<v>& v)
{
     // generate all permutations - can be done by preprocessing.

     // check assignments
}
*/

int main()
{
    vector<int> v = {1,2,3,88};
    if (is24(v,0,0))
        cout << "True" << endl;
    else
        cout << "False" << endl;
}

- Anonymous April 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

(2*6) + (4*3)

- shivani narang April 23, 2015 | 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