Microsoft Interview Question Software Engineer in Tests


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

- siva.sai.2020 on April 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

So according to your algo...

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

- Water on July 24, 2012 | Flag
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.

- jgvdangelo on February 18, 2013 | Flag Reply
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;
    }

}

- Test on May 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I solved this using C++ in my blog - addaxsoft.com/?p=58

- Abdulkarim on March 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I'm sorry if this is considered spamming, but I don't check comments here. :-)

- Abdulkarim on March 04, 2014 | Flag
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.

- Sanjay Kumar on April 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous on April 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

correct...

- Sanjay Kumar on April 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 ?

- ps on April 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ps on April 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 ?

- ps on April 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Agreed that many of these things should be clarified first.

- eugene.yarovoi on April 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Sanjay Kumar on July 24, 2012 | Flag


Add a Comment
Name:

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

Books

is a comprehensive book walking you through getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More