Google Interview Question
Software Engineer in TestsCountry: United States
Interview Type: Phone Interview
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?
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;
}
Yes i did, the example in the main should not work.
On which input it doesn't work for you ?
Yes i did, the example in the main should not work.
On which input it doesn't work for you ?
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)' ]
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)' ]
/*
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);
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);
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);
}
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;
}
}
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;
}
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?
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;
}
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;
}
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;
}
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:
Notice that division is handled by two cases: 'k=3' for 'a/b' and 'k=4' for b/k. Indeed it works, example:
- autoboli April 23, 2015input: 4, [5 7 13 169]
output: (7+(169/13))/5 = 4