Microsoft

  www.microsoft.com
Work in HR? Unlock Free Profile

Microsoft Software Development Engineer I Interview Question (student candidate)

I interviewed in Redmond, WA and was asked:
"Given a string of format '2+3*2-1', calculate and return the result. No parenthesis in the input, just integers and + - * / operators. Operator precedence has to be considered. Linear time complexity and minimal data structure use is preferred."
Tags: algorithm
Add Tags [?]
Answer

Part of a Software Development Engineer I Interview Review - one of 3,371 Microsoft Interview Reviews

Answers & Comments

0
of 1
vote
I did 2 pass on input string.
- Interview Candidate on Jan 03, 2013
0
of 0
votes
I also did two passes on the input string. I created the following helper classes:

Calculate, which takes in the input string, the location of the operation and the operation itself, and returns the result of the calculation. It's not too hard to figure out how to extract the operands from the string (just iterate backwards/forwards until you bump into the end, beginning or another operator).

InsertResultInStr, which takes in the input string, the location of insertion and places a given integer into the input string. I couldn't prove this, but I think its true that the result of a multiplication between m and n digit numbers can always fit in the concatenation of those numbers with '*' in the middle. Sorry if the explanation is a little confusing, but InsertResultInStr(input, 3, 6) for input string = "2 + 3*2* - 1" should result in string = "2 + 6 - 1".

Now, in the main fn, iterate through the string until we find a '*' or a '/', and when we do, calculate the answer via Calculate(), then InsertResultInStr(). Then iterate through the string again looking for '+' and '-', and finally convert the final string to an int and return it.

One thing that is not clear in the description is what we should do to handle if a/b is not an int. My guess is that a/b will always return an integer. I guess you can handle this in any way you want: ignore the stuff after the decimal point, or maybe keep the maximum amount of precision that your string-space can handle.
- Anonymous on Jan 07, 2013
0
of 0
votes
I used a different approach by making use of a queue:
- parse the string, and push in the operands and operators onto a queue
- evaluate the queue

My general approach was this:
- read in lhs, operator and rhs
- if operator is "+" or "-", enqueue lhs and operator
   > if string is empty, we are done parsing --> enqueue rhs
   > else, prepend rhs to the string (e.g. str = rhs + str), to be parsed further
- else, the operator is "*" or "/" --> perform the operation on lhs and rhs, and prepend the result to the string

Final step is evaluating the queue -- simply dequeue lhs, operator and rhs and evaluate.
 (*note: this was tricky to get right on paper, and I've made a few mistakes which I had to debug)

// Given: a well-formatted string e.g. "2 + 2*3 - 1". Evaluate the expression.
string getCurr(string& str);

int eval(string str)
{
    if (str.empty())
        return -1;

    // operand / operator queue
    std::queue<string> q;

    // construct it
    char buf[5];
    while (!str.empty())
    {
        string lhs = getCurr(str),
               oper = getCurr(str),
               rhs = getCurr(str);

        // evaluate directly
        if (oper == "*")
        {
            int res = atoi(lhs.c_str()) * atoi(rhs.c_str());

            // restore the string
            str = itoa(res, buf, 10) + str;
        }
        // evaluate directly
        else if (oper == "/")
        {
            int res = atoi(lhs.c_str()) / atoi(rhs.c_str());

            // restore the string
            str = itoa(res, buf, 10) + str;
        }
        else // "+" or "-"
        {
            q.push(lhs);
            q.push(oper);

            // finished parsing the expression
            if (str.empty())
                q.push(rhs);
            else // restore the string
                str = rhs + str;
        }
    }

    // evaluate the queue
    int res, rhs;
    string oper;

    res = atoi(q.front().c_str()); q.pop();

    while (!q.empty())
    {
        oper = q.front(); q.pop();
        rhs = atoi(q.front().c_str()); q.pop();

        if (oper == "+")
            res += rhs;
        else // "-"
            res -= rhs;
    }

    return res;
}

string getCurr(string& str)
{
    if (str.empty())
        return "";

    string curr("");
    // operator
    if (str[0] == '-' || str[0] == '+' || str[0] == '*' || str[0] == '/')
    {
        curr += str[0];
        str = str.substr(1);
    }
    else // a number
    {
        do {
            curr += str[0];
            str = str.substr(1);
        } while (!str.empty() && str[0] >= '0' && str[0] <= '9');
    }

    return curr;
}
- Anonymous on Feb 18, 2013
0
of 0
votes
Use 2 stacks. one for operands and one for operators. Keep pushing in operator as long as the newly pushed opertor has higher precedence than the "top of stack " operator. if not, pop out 2 operands and calculate result and again push it on stack
- NCGUY on Jun 18, 2013

To comment on this question, Sign In with Facebook or Sign Up

Tags are like keywords, helping to categorise interview questions that have something in common.