## Microsoft Interview Question

Software Engineer / DevelopersI get it.

const int TOTALOPS = 4;

string expr[exprLength] = {"6","7"...};

string operators[TOTALOPS] = {"+","-","*","/"};

We know that we need (exprLength - 1) operators. Each operator can be {+,-,*,/}

void generate(int index, int maxOps, string opCum[maxOps])

{

if (index == maxOps) //We have filled up operators[]

{

Check these operators against expr

}

else{

for (int op = 0; op < TOTALOPS; ++op)

{

opCum[index] = operators[op];

generate(index + 1, maxOps, opCum);

} //for

} //else

} //generate

The complexity of the above algorithm is 4^N

Here is a backtracking algorithm. It will terminate as soon it found a solution.

bool generate(int index, int maxOps, string opCum[maxOps])

{

if (index == maxOps) //We have filled up operators[]

{

return true if we found the solution.

return false otherwise.

}

else{

for (int op = 0; op < TOTALOPS; ++op)

{

opCum[index] = operators[op];

bool isSuccess = generate(index + 1, maxOps, opCum);

if (isSuccess)

return true;

} //for

} //else

return false;

} //generate

(3/3) + 1 + 6

- os June 19, 2007