Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
I decided for convenience to collect all possible expressions with the post-fix notations.
This has solved out the problem of parenthesis and the problem to execute the expressions.
An expression is represented here as a queue of operations.
Funny puzzle ;-)
enum OperationType { OP_VAL, OP_SUM, OP_SUB, OP_ISUB, OP_MULT, OP_DIV, OP_IDIV };
typedef pair< OperationType, int > Operation;
typedef deque< Operation > Expression;
void find_expressions( vector< int >& input, int target )
{
vector< Expression > collection;
for (int i = 0; i < input.size( ); ++i )
{
Expression exp( 1, Operation( OP_VAL, input[i] ) );
collect_expressions( collection, input, i, exp, target );
}
for( const auto& exp: collection )
{
print_expression( exp );
}
}
void collect_expressions( vector< Expression >& collection,
const vector< int >& input,
int begin,
Expression& exp,
int target )
{
int val = 0;
if ( execute_expression( exp, val ) && val == target )
{
collection.push_back( exp );
}
for ( int i = begin + 1; i < input.size( ); ++i )
{
int val = input[i];
exp.push_back( Operation( OP_SUM, val ) );
collect_expressions( collection, input, i, exp );
Operation& op = exp.back( );
op.second = 1;
op.first = OP_SUM;
collect_expressions( collection, input, i, exp );
op.first = OP_SUB;
collect_expressions( collection, input, i, exp );
op.first = OP_ISUB;
collect_expressions( collection, input, i, exp );
op.first = OP_MULT;
collect_expressions( collection, input, i, exp );
op.first = OP_DIV;
collect_expressions( collection, input, i, exp );
op.first = OP_IDIV;
collect_expressions( collection, input, i, exp );
exp.pop_back( );
}
}
bool execute_expression( const Expression& exp, int& result )
{
deque<int> stack;
if ( exp.size( ) == 1)
{
val = exp[0].second;
return exp[0].first == OP_VAL;
}
for (Operation op: exp)
{
if ( op.first == OP_VAL )
{
stack.push_back( op.second );
continue;
}
if ( stack.size( ) < 2 )
{
return false;
}
int op1 = stack.back( ); stack.pop_back( );
int op2 = stack.back( ); stack.pop_back( );
int tmp_val = 0;
switch( op.first )
{
case OP_SUM:
tmp_val = op1 + op2;
break;
case OP_SUB:
tmp_val = op1 - op2;
break;
case OP_ISUB:
tmp_val = op2 - op1;
break;
case OP_MUL:
tmp_val = op1 * op2;
break;
case OP_DIV:
if ( op2 == 0 ) return false;
tmp_val = op1 / op2;
break;
case OP_IDIV:
if ( op1 == 0 ) return false;
tmp_val = op2 / op1;
break;
}
stack.push_back( tmp_val );
}
result = stack.front( );
return stack.size( ) == 1;
}
void print_expression( const Expression& exp )
{
deque< string > stack;
for( Operation op: exp )
{
if ( op.first == OP_VAL )
{
stringstream buf;
buf << op.second;
stack.push_back( buf.str( ) );
continue;
}
string op1 = stack.back( ); stack.pop_back( );
string op2 = stack.back( ); stack.pop_back( );
if ( op.first == OP_ISUB || op.first == OP_IDIV )
{
op1.swap(op2);
}
stringstream buf;
buf << “( “ << op1 << “ )“;
switch( op.first )
{
case OP_SUM:
buf << “ + ”;
break;
case OP_SUB:
case OP_ISUB:
buf << “ - ”;
break;
case OP_MUL:
buf << “ * ”;
break;
case OP_DIV:
case OP_IDIV:
buf << “ / ”;
break;
}
buf << “( “ << op2 << “ )“;
stack.push_back( buf.str( ) );
}
cout << stack.front( ) << endl;
}
I coded a solution to a similar problem a while back. This one only finds one expression, but can be easily modified to return all expressions.
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);
}
Ok. Now you are just posting random shit.
- Anonymous March 21, 2014