## Microsoft Interview Question

• 0

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;
}``````

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

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;}

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

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

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

@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;}

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

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.

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

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

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

Right. using stack seems appropriate here.

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;
}

}

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();
}``````

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

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

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

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

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));
}

}``````

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;
char top()
{
}
{
}
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)
else{
{
}
else
{
temp=new list;
temp->ch=ch;
}
}
}
int main()
{
char str[100];
int i=0;
printf("enter the string:\n");
scanf("%s",str);
if(!top())printf("\ncorrect");
else printf("\nincorrect");
return 0;
}

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.