## Microsoft Interview Question for SDE-3s

• -1
of 1 vote

Country: United States
Interview Type: In-Person

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

1. Convert the infix expression to prefix
2. Evaluate prefix expression using stack.

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

Copy pasting a comment of fun4LeetCode from leetcode.
General structure

``````public int calculate(String s) {
int l1 = 0, o1 = 1; // Initialization of level one
int l2 = 1, o2 = 1; // Initialization of level two

for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);

if (c is a digit) {

--> we have an operand of type number, so find its value "num"
--> then evaluate at level two: l2 = (o2 == 1 ? l2 * num : l2 / num);

} else if (c is a lowercase letter) {

--> we have an operand of type variable, so find its name "var"
--> then look up the variable mapping table to find its value "num";
--> lastly evaluate at level two: l2 = (o2 == 1 ? l2 * num : l2 / num);

} else if (c is an opening parenthesis) {

--> we have an operand of type subexpression, so find its string representation
--> then recursively call the "calculate" function to find its value "num";
--> lastly evaluate at level two: l2 = (o2 == 1 ? l2 * num : l2 / num);

} else if (c is a level two operator) {

--> o2 needs to be updated: o2 = (c == '*' ? 1 : -1);

} else if (c is a level one operator) {

--> demotion happens here: l1 = l1 + o1 * l2;
--> o1 needs to be updated: o1 = (c == '+' ? 1 : -1);
--> l2, o2 need to be reset: l2 = 1, o2 = 1;

}

return (l1 + o1 * l2); // end of expression reached, so demotion happens again
}``````

Recursive solution: O(n^2) time, O(n) space

``````public int basicCalculatorIII(String s) {
int l1 = 0, o1 = 1;
int l2 = 1, o2 = 1;

for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);

if (Character.isDigit(c)) {
int num = c - '0';

while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
num = num * 10 + (s.charAt(++i) - '0');
}

l2 = (o2 == 1 ? l2 * num : l2 / num);

} else if (c == '(') {
int j = i;

for (int cnt = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') cnt++;
if (s.charAt(i) == ')') cnt--;
if (cnt == 0) break;
}

int num = basicCalculatorIII(s.substring(j + 1, i));

l2 = (o2 == 1 ? l2 * num : l2 / num);

} else if (c == '*' || c == '/') {
o2 = (c == '*' ? 1 : -1);

} else if (c == '+' || c == '-') {
l1 = l1 + o1 * l2;
o1 = (c == '+' ? 1 : -1);

l2 = 1; o2 = 1;
}
}

return (l1 + o1 * l2);
}``````

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.