Google Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
Output is not correct by above code.
it is giving + + - but ideally it should be + -.
so can you recheck
I think should also consider */ before +-. Also, might not have to traverse all the situations, can be eliminated for some case.
Please take care to Operator Precedence & floating points.
E.g. for arr[]={1,2,6,2,4}; its gives following outputs but none of them are correct answer.
+ + + /
+ * + /
+ / + -
- + * -
- / + -
@shondik, well, I think @SRB has given some examples.
Here are some thoughts:
1. Use a stack to save each operation with priority, as well as saving the current number as the input stream. To do */ first, and push the result back to the stack, then do +-.
2. The solution above does check the situations with *0 or /0, there can be more situation to check -- like "+" may not be a proper choice for the last operation when the current result is already larger than the last number, etc. It might be tricky to implement all possible cases, but to some extent, it does help a little for the exponential solution space.
3. Just as @SRB said, the problem never says the input array is int, which shouldn't be, considering "/" operation. When I did it in the interview, I mentioned this, and the interviewer said "what do you think? Make it right".
what about precedence of each operator?
eg. if we have an equation: 2+3*6=20
then this algorithm will execute as
2+3=5
5*6=30
so this will contradict the solution.
The correct Solution would be solving the whole equation when
depth==size keeping in mind precedence priority.
For properly implementing precedence convert the infix to postfix and then evaluate postfix equation using stack.
Dynamic programing is the right way to think about it, start searching for all operations on current input value, stop when all inputs are over and the result value is as desired, on search we might have to record the sequence of operations. Also special handling is required for */ operations like they need to know the last operand other than the entire expression value.... complex enough... one could write pseudo code....
Using DP to log the temp values got and make adjustment according to current operator and previous operator could achieve good performance. Here is my solution by Python:
import sys
dp = {}
def calc(inp, length, index, pre):
global dp
pre_value = dp[pre]
if index == (length-1):
if pre_value == inp[len(inp)-1]:
result = str(inp[0])
for i in range(1,length):
result += pre[i] + str(inp[i])
print "matching: " + result + "=" + str(inp[length])
return
# "+"
nex = pre + '+'
dp[nex] = pre_value + inp[index+1]
calc(inp, length, index+1, nex)
# "-"
nex = pre + '-'
dp[nex] = pre_value - inp[index+1]
calc(inp, length, index+1, nex)
last = pre[len(pre)-1]
# "*"
nex = pre + '*'
if last == '*' or last == '/' or last == '$':
dp[nex] = pre_value * inp[index+1]
else:
pre_value = dp[pre[:len(pre)-1]]
if last == '+':
dp[nex] = pre_value + inp[index] * inp[index+1]
else:
dp[nex] = pre_value - inp[index] * inp[index+1]
calc(inp, length, index+1, nex)
# "/"
if inp[index+1] == 0:
return
nex = pre + '/'
if last == '*' or last == '/' or last == '$':
dp[nex] = pre_value / inp[index+1]
else:
pre_value = dp[pre[:len(pre)-1]]
if last == '+':
dp[nex] = pre_value + inp[index] / inp[index+1]
else:
dp[nex] = pre_value - inp[index] / inp[index+1]
calc(inp, length, index+1, nex)
if __name__ == "__main__":
inp = [2,1,3,4,5,8]
length = len(inp) - 1
pre = '$'
dp[pre] = inp[0]
calc(inp, length, 0, pre)
for 3 operand, 3 operators are needed..
ie.. for the given example +2+3-1 = 4
for n operand, n operators are needed.. number of combinations are (4^n)... and result is analyzed!
Fundamental question. Can this be solved better than exponential complexity? I don't "think" so but I cant seem to prove it either.
// this shud work :)
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,x,c=0;
vector<int> a;
int solve(int i,int val)
{ if(i==n-1)
{
if(val==a[n-1]) { c++; return 0; }
else return 0;
}
solve(i+1,val+a[i]);
solve(i+1,val-a[i]);
solve(i+1,val*a[i]);
if(a[i]!=0)
solve(i+1,val/a[i]);
}
main()
{ int i;
scanf("%d",&n);
for(i=0;i<n;i++) scanf("%d",&x), a.push_back(x);
solve(1,a[0]);
printf("number of ways are : %d\n",c);
return 0;
}
the code above doesn't take into account precedence of */ over +-
is that also need's to be considered .(which shud be .)
one possibe way is to . push all number's 2 a stack . generate all combination of these 4 operator. evaluated in post fix order.
eg.
2345+-+
2345+-*
...
generate all such expression an evaluate one by one. using stack.
I think your approach is good but have high complexity.
According to you, here is what I think:
1) Push 2 numbers in stack.
2) Now calculate (Based on operator precedence) all possible numbers push these in stacks
3) now pick the next number from an Array and again generate all possible numbers from the numbers already pushed into stack. Now we need to store these numbers in new stack.
4) we will break the loop as soon as any number is reached to the result and count = n-1.
I know this is not efficient solution since we are declaring lots of stacks and calculating all combinations.
Anyone knows any better solution please let us know.
Thanks
#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>
#include <sstream>
#include <vector>
using namespace std;
vector<vector<int> > permute(vector<vector<int> > curr)
{
vector<vector<int> > opers;
vector<int> tmpopers;
if (curr.empty()){
for (int i=0;i<4;i++){
tmpopers.push_back(i);
opers.push_back(tmpopers);
tmpopers.clear();
}
}
else{
for (int i=0;i<4;i++){
for (vector<vector<int> >::iterator it=curr.begin();it!=curr.end();it++){
tmpopers.push_back(i);
copy(it->begin(),it->end(),back_inserter<vector<int> >(tmpopers) );
opers.push_back(tmpopers);
tmpopers.clear();
}
}
}
return opers;
}
vector<vector<int> > permuteOperators(int n)
{
vector<vector<int> > curr;
for (int i=0;i<n;i++){
curr=permute(curr);
}
return curr;
}
int calculate(vector<int> values, vector<int> oper)
{
int index;
vector<int>::iterator it=oper.begin();
while(it!=oper.end()){
if (*it==2){// multiplication
index=it-oper.begin();
values.at(index)*=values.at(index+1);
values.erase(values.begin()+index+1);
it=oper.erase(it);
}
else if (*it==3){// division
index=it-oper.begin();
values.at(index)/=values.at(index+1);
values.erase(values.begin()+index+1);
it=oper.erase(it);
}
else
it++;
}
it=oper.begin();
while(values.size()>1){
if (*it==0){// summation
index=it-oper.begin();
values.at(index)+=values.at(index+1);
values.erase(values.begin()+index+1);
it=oper.erase(it);
}
else if (*it==1){// subtraction
index=it-oper.begin();
values.at(index)-=values.at(index+1);
values.erase(values.begin()+index+1);
it=oper.erase(it);
}
else
it++;
}
return values.at(0);
}
string printString(vector<int> vals, vector<int> opers)
{
stringstream out;
int index;
out<<vals.at(0)<<" ";
for (vector<int>::iterator it=opers.begin();it!=opers.end();it++){
index=it-opers.begin();
switch (opers.at(index)){
case 0: out<<"+ "; break;
case 1: out<<"- "; break;
case 2: out<<"* "; break;
case 3: out<<"/ "; break;
}
out<<vals.at(index+1)<<" ";
}
return out.str();
}
string getEquation(vector<int> vals)
{
int currVal;
string outputString;
int total=vals.at(vals.size()-1);
stringstream tmp;
tmp<<total;
vals.erase(vals.end()-1);
vector<vector<int> > opers=permuteOperators(vals.size()-1);
for (vector<vector<int> > ::iterator it=opers.begin();it!=opers.end();it++){
currVal=calculate(vals,*it);
if (currVal==total){
outputString=printString(vals,*it)+"= "+tmp.str();
return outputString;
}
}
return outputString;
}
void main()
{
int val[]={8,6,-3,9,6,7,0};
vector<int> vec_vals(val,val+7);
string out;
out=getEquation(vec_vals);
for(vector<int>::iterator it=vec_vals.begin();it!=vec_vals.end();cout<<*it<<" ",it++);
cout<<endl;
cout<<out<<endl;
system("pause");
}
This should work. Takes care of precedence. Takes care of 0 as the result element.
import java.util.Stack;
public class CalculateResult {
public static void main(String args[]) {
Integer[] elements = new Integer[args.length];// = {2, 3, 1, 4};
for(int i = 0; i < args.length; i++) {
elements[i] = Integer.valueOf(args[i]);
}
Character[] operators = {'+', '-', '*', '/'};
Stack<Character> opStack = new Stack<Character>();
Integer curResult = elements[0];
int eI = 1;
if(elements[elements.length-1] == 0) {
for(int i = 0; i < elements.length-2; i++) {
opStack.push('*');
}
} else {
calc(elements, eI, operators, curResult, opStack);
}
printEquation(elements, opStack);
}
private static void printEquation(Integer[] elements, Stack<Character> opStack) {
if(opStack.size() != 0) {
StringBuffer resultStr = new StringBuffer("");
for(int i = 0; i < opStack.size()-1; i++) {
resultStr.append("(");
}
for(int i = 0; i < opStack.size(); i++) {
resultStr.append(elements[i]);
if(i != 0) {
resultStr.append(")");
}
resultStr.append(" " + opStack.elementAt(i) + " ");
}
resultStr.append(elements[elements.length - 2] + "");
System.out.println(resultStr.toString());
} else {
System.out.println("stack size is "+ opStack.size());
System.out.println("no equation");
}
}
private static boolean calc(Integer[] elements, int eI, Character[] operators, Integer curResult, Stack<Character> opStack) {
int tempResult = curResult.intValue();
if(eI == elements.length - 1) {
if(curResult == elements[elements.length - 1]) {
return true;
} else {
return false;
}
}
for(int i = 0; i < operators.length; i++) {
switch(operators[i]) {
case '*':
curResult *= elements[eI];
break;
case '/':
if(elements[eI] == 0) {
continue;
}
curResult /= elements[eI];
break;
case '+':
curResult += elements[eI];
break;
case '-':
curResult -= elements[eI];
break;
}
opStack.push(operators[i]);
if(! calc(elements, eI + 1, operators, curResult, opStack)) {
opStack.pop();
curResult = Integer.valueOf(tempResult);
} else {
return true;
}
}
return false;
}
}
I'm a newbie here.This is my very first try on careercup. : )
My thought is pretty straightforward:Given user input 2,1,3,4,I list out all possible combinations of different operands beforehand,like (+,+) or (+,-) or (-,+ )...all the way to (/,/).Then combine the user input with these operands combinations to get the math expression (something like 2+1+3 or 2+1-3 or 2-1+3 .......).Then,I evaluate every expression.
Time complexity:because it's brute-force solution ,no wonder that time complexity is O(4^n)
________________________________________
Python code:
from fractions import Fraction
"""
function
example:product('+-*/',2)---->++ +- +* +/ -+ -- -* ........
"""
def product(*args, **kwds):
# product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
# product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
pools = map(tuple, args) * kwds.get('repeat', 1)
result = [[]]
for pool in pools:
result = [x+[y] for x in result for y in pool]
for prod in result:
yield tuple(prod)
"""
Main entry
"""
# receive user input
input = raw_input("Enter something(ex:2,1,3,4 or 1,2,1/2): ")
# operands list ,example: [2,1,3,4]
items = input.split(',')
# all possible operators' combinations ,example:[(+,+),(+,-),(+,*)...........,(/,/)]
operators = product('+-*/',repeat = len(items)-2)
# try every possible operator combination and find out the right one
for operator in operators:
expression = str(float(items[0]))
for i in range(len(items)-2):
expression = expression + operator[i] + str(float(items [i+1])) # combine the operands and the operators to produce the expression,example:2+1+3
if float(eval(expression)) == Fraction(items[len(items)-1]):# evaluate the math expression we just got above
print expression
break;
else:
print 'no expression'
}
________________________________________
Sample:
(1)input:2,1,3,4----->output:2.0-1.0+3.0
(2)input:1,2,3,4,5/4---->output:1.0*2.0-3.0/4.0
package google;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
public class Get_All_Compute_Results {
public static ArrayList<Integer> compute(int[] test,int begin,int end,
ArrayList<Integer> deal,HashMap<Integer,String> resultsStore){
if(begin==end){
deal.add(test[begin]);
resultsStore.put(test[begin], String.valueOf(test[begin]));
return deal;
}
HashMap<Integer,Boolean> keep=new HashMap<Integer,Boolean>();
if(begin==end-1){
resultsStore.put(test[begin]+test[end],"("+String.valueOf(test[begin])+"+"+String.valueOf(test[end])+")");
deal.add(test[begin]+test[end]);
keep.put(test[begin]+test[end], true);
if(!keep.containsKey(test[begin]-test[end])){
resultsStore.put(test[begin]-test[end],"("+String.valueOf(test[begin])+"-"+String.valueOf(test[end])+")");
deal.add(test[begin]-test[end]);
keep.put(test[begin]-test[end], true);
}
if(!keep.containsKey(test[begin]*test[end])){
resultsStore.put(test[begin]*test[end],"("+String.valueOf(test[begin])+"*"+String.valueOf(test[end])+")");
deal.add(test[begin]*test[end]);
keep.put(test[begin]*test[end], true);
}
if(test[end]!=0){
if(!keep.containsKey(test[begin]/test[end])){
resultsStore.put(test[begin]/test[end],"("+String.valueOf(test[begin])+"/"+String.valueOf(test[end])+")");
deal.add(test[begin]/test[end]);
keep.put(test[begin]/test[end], true);
}
}
return deal;
}
for(int let=begin;let!=end;let++){
HashMap<Integer,String> leftStore=new HashMap<Integer,String>();
HashMap<Integer,String> rightStore=new HashMap<Integer,String>();
ArrayList<Integer> left=compute(test,begin,let,new ArrayList<Integer>(),leftStore);
ArrayList<Integer> right=compute(test,let+1,end,new ArrayList<Integer>(),rightStore);
for(int i=0;i!=left.size();i++){
String leftPart=leftStore.get(left.get(i));
for(int j=0;j!=right.size();j++){
if(!keep.containsKey(left.get(i)+right.get(j))){
String rightPart=rightStore.get(right.get(j));
resultsStore.put(left.get(i)+right.get(j),"("+leftPart+"+"+rightPart+")");
deal.add(left.get(i)+right.get(j));
keep.put(left.get(i)+right.get(j), true);
}
if(!keep.containsKey(left.get(i)-right.get(j))){
String rightPart=rightStore.get(right.get(j));
resultsStore.put(left.get(i)-right.get(j),"("+leftPart+"-"+rightPart+")");
deal.add(left.get(i)-right.get(j));
keep.put(left.get(i)-right.get(j), true);
}
if(!keep.containsKey(left.get(i)*right.get(j))){
String rightPart=rightStore.get(right.get(j));
resultsStore.put(left.get(i)*right.get(j),"("+leftPart+"*"+rightPart+")");
deal.add(left.get(i)*right.get(j));
keep.put(left.get(i)*right.get(j), true);
}
if(right.get(j)!=0){
if(!keep.containsKey(left.get(i)/right.get(j))){
String rightPart=rightStore.get(right.get(j));
resultsStore.put(left.get(i)/right.get(j),"("+leftPart+"/"+rightPart+")");
deal.add(left.get(i)/right.get(j));
keep.put(left.get(i)/right.get(j), true);
}
}
}
}
}
return deal;
}
public static void main(String[] args) {
int [] test=new int[]{4,5,4,6};
HashMap<Integer,String> resultsStore=new HashMap<Integer,String>();
ArrayList<Integer> results=compute(test,0,test.length-1,new ArrayList<Integer>(),resultsStore);
Collections.sort(results);
for(int i=0;i!=results.size();i++){
System.out.println(resultsStore.get(results.get(i))+"="+results.get(i));
}
}
}
Fizzbuzz ruby solution..
def findEquation(arr)
result = arr.pop
operators = ['+', '-', '*', '/'].repeated_permutation(arr.length - 1)
operators.each do |op|
eq = calc arr, op
return eq if eval(eq) == result
end
puts 'no equation'
end
def calc(arr, operators)
return false if arr.length - 1 != operators.length
index = 1
equation = arr[0].to_s
operators.each do |op|
equation << op << arr[index].to_s
index += 1
end
equation
end
I am using brute force, but maybe using DP to cache some previous computed result can help pruning. I think my solution is essentially the same to shondik's.
Runnable code here: ideone.com/NSuWj
void PrintEquation(const vector<int>& series, stack<char>* ops) {
assert(series.size() - 2 == ops->size());
int ub = series.size() - 1;
for (int i = 0; i < ub; ++i) {
cout << series[i] << " ";
if (!ops->empty()) {
cout << ops->top() << " ";
ops->pop();
}
}
cout << "= " << series[series.size() - 1] << endl;
}
bool FindOperators(const vector<int>& series, int last_idx, float result, stack<char>* ops) {
if (last_idx == 0) {
if (series[0] == result) {
PrintEquation(series, ops);
return true;
} else
return false;
}
ops->push('+');
if (FindOperators(series, last_idx - 1, result - series[last_idx], ops))
return true;
ops->pop();
ops->push('-');
if (FindOperators(series, last_idx - 1, result + series[last_idx], ops))
return true;
ops->pop();
ops->push('*');
if (FindOperators(series, last_idx - 1, result / series[last_idx], ops))
return true;
ops->pop();
ops->push('/');
if (FindOperators(series, last_idx - 1, result * series[last_idx], ops))
return true;
ops->pop();
return false;
}
int main(int argc, char** argv) {
vector<int> series;
int tmp;
while (cin >> tmp)
series.push_back(tmp);
// sanity check for series.size()
if (series.size() < 3) {
cout << "Not enough operands" << endl;
return 0;
}
stack<char> ops;
if (!FindOperators(series, series.size() - 2, series[series.size() - 1], &ops))
cout << "No equation" << endl;
return 0;
}
Here's my solution in Python. It uses an iterator to go through all the possible sign assignments. For each one, it transforms the infix expression to postfix form, then evaluates.
def generate_operators(n,s):
signs = ["+", "-", "*", "/"]
if len(s) == n:
yield s
else:
for sign in signs:
for c in generate_operators(n, s+sign):
yield c
def get_expression(numbers, operators):
s = []
for i in range(len(operators)):
s.extend([numbers[i], operators[i]])
s.append(numbers[-1])
return s
def infix_to_postfix(numbers, operators):
prec = {}
prec["-"] = 1
prec["+"] = 1
prec["*"] = 2
prec["/"] = 2
s = get_expression(numbers, operators)
postfix = []
stack = []
for i in range(len(s)):
if i%2 == 0:
postfix.append(s[i])
else:
while (len(stack) > 0 and prec[stack[-1]] >= prec[s[i]]):
postfix.append(stack.pop())
stack.append(s[i])
while (len(stack)>0):
postfix.append(stack.pop())
return postfix
def compute(op1, op2, sign):
if sign == "+":
return op1+op2
elif sign == "-":
return op1-op2
elif sign == "*":
return op1*op2
elif sign == "/":
return op1/op2
def evaluate_postfix(expr):
stack = []
for i in range(len(expr)):
if str(expr[i]) not in "+-/*":
stack.append(expr[i])
else:
op2 = stack.pop()
op1 = stack.pop()
result = compute(op1, op2, expr[i])
stack.append(result)
return stack.pop()
def solution(alist):
assert(len(alist) > 1)
n = len(alist) - 1
numbers = alist[:-1]
result = alist[-1]
for op in generate_operators(n-1, ""):
pexpr = infix_to_postfix(numbers, op)
if evaluate_postfix(pexpr) == result:
print "".join([str(x) for x in get_expression(numbers, op)]) + "=" + str(result)
return
print "no equation"
solution([2,3,1,4])
bool findeqHelper(int* arr, int size, std::vector<char>& ops)
{
if (size < 3)
return false;
for (int i = 0; i < 4; i++)
{
int val0 = arr[0];
int val1 = arr[1];
int newVal = 0;
if (i==0)
{
newVal = val0*val1;
ops.push_back('*');
}
if (i==1 && val1 != 0)
{
newVal = val0/val1;
ops.push_back('/');
}
if (i==2)
{
newVal = val0+val1;
ops.push_back('+');
}
if (i==3)
{
newVal = val0-val1;
ops.push_back('-');
}
if (size == 3 && newVal == arr[2])
return true;
arr[1] = newVal;
if (findeqHelper(arr+1, size-1, ops))
return true;
ops.pop_back();
arr[1] = val1;
}
return false;
}
bool findeq(std::vector<int> arr, int size, std::vector<char>& ops)
{
return findeqHelper(&arr[0],size,ops);
}
int _tmain(int argc, _TCHAR* argv[])
{
std::vector<int> input;
input.push_back(5);
input.push_back(5);
input.push_back(5);
input.push_back(5);
std::vector<char> ops;
int size = input.size();
bool found = findeq(input, size, ops);
if (found)
{
for(int i = 0; i < size - 2; i++)
{
cout << input[i] << " " << ops[i] << " ";
}
cout << input[size-2] << " = " << input[size-1] << endl;
}
return 0;
}
static double apply(char op, double x, double y){
switch (op) {
case '+':
return x+y;
case '-':
return x-y;
case '/':
return x/y;
case '*':
return x*y;
default:
return 0;
}
}
public static void main(String[] args) {
double[] a = {2,3,1,4};
char[] op = {'+','-','*','/'};
for(int i=0; i<op.length;i++)
for(int j=0; j<op.length;j++)
{
double result;
if(op[i]=='*' || op[i]=='/'){
result = apply(op[j], apply(op[i], a[1],a[2]),a[0]);
}
else{
result = apply( op[i], apply(op[j],a[1],a[2]), a[0] );
}
if ( result == a[3] ) {
System.out.println(a[0]+" "+op[i]+" "+a[1]+" "+op[j]+" "+a[2]+" = "+a[3]);
}
}
}
void solver(vector<float> &vec, string operators = string()){
if(operators.size() == vec.size()-2){
stack<float> num;
stack<char> op;
num.push(vec[0]);
for(int i=0; i<operators.size(); ++i){
if(operators[i] == '*')
num.top() *= vec[i+1];
else if(operators[i] == '/')
num.top() /= vec[i+1];
else{
num.push(vec[i+1]);
op.push(operators[i]);
}
}
while(!op.empty()){
int n = num.top(); num.pop();
if(op.top() == '+')
num.top() += n;
else if(op.top() == '-')
num.top() -= n;
op.pop();
}
if (num.top() == vec.back()){
for(int i=0; i<vec.size()-2; ++i){
cout << vec[i] << operators[i];
}
cout << vec[vec.size()-2] << " = " << vec.back() << endl;
}
return;
}
solver(vec, operators + '+');
solver(vec, operators + '-');
solver(vec, operators + '*');
if(vec[operators.size()+1])
solver(vec, operators + '/');
}
Exponential
private static boolean possible(List<Integer> l, int x) {
int size = l.size();
if (size == 1) {
return l.get(0) == x;
}
for (int i = 1; i < size; i++) {
int a = l.get(i - 1);
int b = l.get(i);
l.remove(0);
l.set(i - 1, a + b);
if (possible(l, x))
return true;
l.set(i - 1, a - b);
if (possible(l, x))
return true;
l.set(i - 1, a * b);
if (possible(l, x))
return true;
if (b != 0 && a % b == 0) {
l.set(i - 1, a / b);
if (possible(l, x))
return true;
}
l.set(i - 1, b);
l.add(i - 1, a);
}
return false;
}
void print(char* op,int depth) { int i; for(i=0;i<depth;++i) printf("%c ",op[i]); } int calculate(int* arr,int size,char* op,int depth,int result,int val) { if(depth==size) { if(val==result) { print(op,depth); printf("\n"); return 1; } } else { op[depth]='+'; calculate(arr+1,size,op,depth+1,result,val+*arr); op[depth]='-'; calculate(arr+1,size,op,depth+1,result,val-*arr); op[depth]='*'; if(val) calculate(arr+1,size,op,depth+1,result,val*(*arr)); op[depth]='/'; if(*arr && val) calculate(arr+1,size,op,depth+1,result,val/(*arr)); } }Complete code here: ideone.com/XDML8
- Aashish July 20, 2012