Microsoft Interview Question


Team: Office
Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
5
of 7 vote

You can use a stack.

Stack *s = new Stack();
for (int i = 0; i < strlen(str): i++)
{
    if ((str[i] == '{') || (str[i] == '[') || (str[i] == '('))
        s->push(str[i]);
    else
    {
        char tp = s->pop(); // get the element at top
        if (tp == '{') && (sir[i] != '}')
            return false;
        if (tp == '[') && (sir[i] != ']')
            return false;
        if (tp == '[') && (sir[i] != ']')
            return false;
    }
    if (s->empty())
        return true;
    return false;
}

- Mihail Burduja January 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

does priority exist in these characters?
I assume the priority is { > ( > [ then we can use O(1) space to solve it
int a=0,b=0,c=0;
for (int i = 0; i < strlen(str): i++)
{
if(str[i]=='[') a++;
if(str[i]==']'){ a--; if(a<0) return false;}
if(str[i]=='(') {b++; if(a>0) return false;}
if(str[i]==')'){ b--; if(a>0||b<0) return false;}
if(str[i]=='{') {c++; if(a>0||b>0) return false;}
if(str[i]=='}') {c--; if(a>0||b>0||c<0) return false;}
}
if(a==0&&b==0&&c==0) return true;
return false;}

- zyfo2 January 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

initially, the stack is empty, so when you encounter "}", your program will crash because the empty stack couldn't pop anything out

- speedmancs January 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Mihail.. speedmanics is right ..it will crash so u can just check before popping out element if it has any elements... also your second and third case of if statement are same

@zyfo2... your code is definitely better ... and if there is no priority in your code it becomes even simpler and you can just remove those checks and looks something like this

if(str[i]=='[') a++;
if(str[i]==']'){ a--; if(a<0) return false;}
if(str[i]=='(') {b++;}
if(str[i]==')'){ b--; if(b<0) return false;}
if(str[i]=='{') {c++; }
if(str[i]=='}') {c--; if(c<0) return false;}

- vik January 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Use stack to solve it.
When ever an opening bracket encountered push it into stack and
when a closing bracket is encountered pop the top element from stack.
perform a check to match opening and corresponding closing bracket.

in the end there stack should be empty for a correct string

- Abhi January 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Create 3 arrays for keeping the count of 3 different brackets.

Scan from left to right and increment count by 1 for { bracket and decrement by 1 for }.
In the end all three arrays should have 0 value.

- Anonymous January 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

your idea won't work for ({)} because at the end both of them would be 0 so according to you idea it is correct but actually it is incorrect

- francisco.gutierrez.91 January 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Right. using stack seems appropriate here.

- Anonymous January 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class StringCompiler {

/**
* @param args
*/
public static void main(String[] args) {

System.out.println("Valid Pattern :" +check());
}

private static boolean check(){
Stack s = new Stack();
String pattern = "{{}}{}{}{}{}}";
for(int i=0;i<pattern.length();i++){
if( pattern.charAt(i)=='(' || pattern.charAt(i)=='{' || pattern.charAt(i)=='[' ){ // Check All Possible language patterns
s.push(pattern.charAt(i));
System.out.println("Pushing "+i+":"+pattern.charAt(i));
}else{
if(!s.empty()){
char c = (Character) s.pop();
if((c == '(' && pattern.charAt(i)==')') ||
(c == '[' && pattern.charAt(i)==']') ||
(c == '{' && pattern.charAt(i)=='}') ){
System.out.println("Poping "+i+":"+pattern.charAt(i));
}else{
return false;
}
}else {
return false;
}

}

}
if(s.empty())
return true;
return false;
}

}

- cooldudekirth January 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool Match(const string& str)
{
	stack<char> s;
	for (string::const_iterator it = str.begin();
	     it != str.end(); it++)
	{
		if (s.empty())
		{
			s.push(*it);
			continue;
		}
		char c = s.top();
		if ((*it == ']' && c == '[') ||
		    (*it == '}' && c == '{') ||
		    (*it == ')' && c == '('))
		{
			s.pop();
		}
		else{
			s.push(*it);
		}
	}
	return s.empty();
}

- speedmancs January 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if the example is '}'']''[''{', is it balance

- Anonymous January 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

how about '}''{''['']'

- Anonymous January 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

how about '}''{''['']'

- Anonymous January 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Stack;

public class CheckBalance {

	public static boolean check(String str) {
		if (str == null || str.length() == 0) {
			return true;
		}
		char[] strs = str.toCharArray();
		Stack<Character> stack = new Stack<Character>();
		for (char c : strs) {
			if(!check(c)){
				return false;
			}
			if(checkOpeningSymbol(c)){
				stack.push(c);
			}
			if(checkEndingSymbol(c)){
				stack.push(c);
				if(stack.size() < 2)
					return false;
				char right = stack.pop();
				char left = stack.pop();
				if(!match(right,left)){
					return false;
				}
			}
		}
		if(stack.isEmpty()){
			return true;
		}
		return false;
	}

	private static boolean match(char right, char left) {
		if(right == ')' && left == '(' ){
			return true;
		}
		if(right == '}' && left == '{' ){
			return true;
		}
		if(right == ']' && left == '[' ){
			return true;
		}
		return false;
	}

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

	private static boolean checkEndingSymbol(Character peek) {
		if (peek == ')' || peek == '}' || peek == ']') {
			return true;
		}
		return false;
	}

	private static boolean checkOpeningSymbol(Character peek) {
		if (peek == '{' || peek == '[' || peek == '(') {
			return true;
		}
		return false;
	}

	public static void main(String[] args) {
//		String str = "{()[]}";
//		String str = "(({)})";
		String str = "{())";
		System.out.println(check(str));
	}

}

- Kevin February 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<iostream>
using namespace std;
struct list
{
char ch;
struct list *next;
}*head=NULL;
char top()
{
if(!head)return '\0';
return head->ch;
}
struct list *pop(struct list *head)
{
head=head->next;
return head;
}
struct list *push(struct list *head,char ch)
{
struct list *temp;
char cc=top(),cd;
switch(ch)
{
case ']':
cd='[';
break;
case '}':
cd='{';
break;
case ')':
cd='(';
break;
default:
cd='a';
break;
}
if(cc==cd)
head=pop(head);
else{
if(!head)
{
head=new list;
head->ch=ch;
head->next=NULL;
}
else
{
temp=new list;
temp->ch=ch;
temp->next=head;
head=temp;
}
}
return head;
}
int main()
{
char str[100];
int i=0;
printf("enter the string:\n");
scanf("%s",str);
while(str[i]){head=push(head,str[i]);i++;}
if(!top())printf("\ncorrect");
else printf("\nincorrect");
return 0;
}

- ram rs March 23, 2013 | Flag Reply


Add a Comment
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.

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