## Google Interview Question for Software Engineer / Developers

• -7

Country: United States
Interview Type: In-Person

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

Ok. Now you are just posting random shit.

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

Obiwana, hi friend.

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

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

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

Recursively iterate all possible () and +-*/ group.

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

You could probably do something with recursive backtracking (iterate through all valid expressions given the (I assume) fixed set of symbols), but this sounds a bit too tough for a 45min interview question.

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

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

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.

### 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.