## Microsoft Interview Question Software Engineer in Tests

• 0

Identify whether an math expression is legal.

for example: {[3*(3+2)]+1}*5 is legal
{(]3++}+4 is illegal

Team: Server and tools in microsoft erp
Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 4 vote

by using stack, we can check whether parenthesis are matched or not. Same algo we can use to check the above valid math expression.

Does any one has idea to solve short cut expression problems.

e.g :: (a+ (b+=c)) // valid
(a+(b=+c)) // invalid

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

5 + () is a valid experession....
Is it ??

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

I wrote the following pseudo-code:

``````for each character in the string
push onto a stack, keeping track of the braces that are being used.
if you encounter any non-numeric characters, braces, or operands, return false
if you encounter a closing brace that has NOT has an opening brace, return false
if you encounter an opening brace following by an operand, return false
if you encounter a closing brace, pop off all values off the stack (until you reach opening)
if there is an operand by the closing brace, return false
if there is nothing between the opening & closing brace, return false
if you encounter two operands in a row, return false
once you pop off the opening brace, pop in any number.``````

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

``````package mytest;

import java.util.Stack;

/**
*
* @author Sun
*/
public class MyTest {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
String test="12*9-[(66+11)]*(77-22)";
System.out.println("Test equation: "+test);
System.out.println("Valid ? "+checkValid(test.toCharArray()));
}
static boolean checkValid(char[] equ){
int i,j=equ.length;
Stack<Character> astack=new Stack<>();
if(j==0)return false;

for(i=0;i<j;i++){
// System.out.println("?"+equ[i]);
if(isOpen(equ[i])){
if(!astack.isEmpty() && isNumber(astack.peek())){
return false;
}
astack.push(equ[i]);
}else if(isNumber(equ[i])){
astack.push(equ[i]);
}else if(isOp(equ[i])){
if(astack.isEmpty() || !isNumber(astack.peek())){
return false;
}
astack.push(equ[i]);
}else if(isClose(equ[i])){
if(astack.isEmpty() || !isNumber(astack.peek())){
return false;
}
while(!astack.isEmpty()){
char temp=astack.pop();
if(isOpen(temp)){
if(doMatch(temp,equ[i])){
break;
}else{
return false;//unexpected open
}
}else{
if(astack.isEmpty()){
return false;
}
}
}
astack.push('1');
}else{ //unexpected char
return false;
}
}
if(!astack.isEmpty() && !isNumber(astack.peek())) {
return false;
}
while(!astack.isEmpty()){
if(isOpen(astack.pop()))return false;
}

return true;
}

private static boolean isOpen(char c) {
if(c=='(' || c=='[')return true;
return false;
}

private static boolean isNumber(char c) {
if(c>='0' && c<='9')return true;
return false;
}

private static boolean isOp(char c) {
if(c=='+' || c=='-' || c=='*' || c=='/')return true;
return false;
}

private static boolean isClose(char c) {
if(c==')' || c==']')return true;
return false;
}

private static boolean doMatch(char temp, char c) {
if((temp=='(' && c==')')||(temp=='[' && c==']'))return true;
return false;
}

}``````

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

take 3 variables for each type of brackets initialize to 0, for open one do ++ for close one do -- and whenever the value become negative. Not a possible expression, and also after every operator there should not be an operator. after the end of expression check each variable is zero.

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

That's definitely not right. According to you, {2 + [4 + 3} + 1] is valid. You need to keep something like a stack and check if each parenthesis matches the previously-seen parenthesis. And checking the lack of two operators in a row is not strong enough. According to you, 2 + 6 3 2 1 (space between the numbers) is valid too.

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

correct...

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

Agree with Anonymous. given, {[3*(3+2)]+1} *5 .
first add, { [ 3 * ( 3 + 2 into the stack until you find a closing bracket . When you find ' )' pop elements out of the stack until you find a matching brace. check if '(' is a matching braces for ')' . If yes, continue iterating. Again ']' pop element until you find ']' . In any case, if the stack doesnt contain a matching brace or there are no elements to pop, return false. Correct me if I am wrong.
But how do we check if the operators are in the right place ?

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

//faculty.cs.niu.edu/~hutchins/csci241/eval.htm

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

You have to discuss with the interviewer as how the expression is going to be.
What kind of braces ( { [ ] } )
Whether it contains numbers/ characters
- 3a + 2b // legal , a3+b4 // illegal ?
What operators it can have ?
*,+,/,-,++,--,+-,+=,-=,*=,/=, ~ . Should you consider the operator precedence ?

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

Agreed that many of these things should be clarified first.

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

use a stack or braces. for open push, for close and corresponding one pop.. at the end of expression if stack is empty.. expression is valid else not..

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

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