Booking.com Interview Question Software Developers
Country: Netherlands
Interview Type: Phone Interview
I will be using stack.
{-->push to stack
{--->push to stack
}--->check in top of stack whether character '{' is present or not.if present pop it out.if it is not present return false
follow similar steps for '[',']','(',')'
after processing enter string if you find stack is empty then brackets are balanced.
Algorithm:
1) Declare a character stack S.
2) Now traverse the expression string exp.
a) If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[‘) then push it to stack.
b) If the current character is a closing bracket (‘)’ or ‘}’ or ‘]‘) then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced.
3) After complete traversal, if there is some starting bracket left in stack then “not balanced”
Time Complexity: O(n)
Space: O(n) for stack.
import java.util.*;
class BalancedParenthesis {
public static void main(String [] args){
Scanner scan=new Scanner(System.in);
String exp=scan.next();
if(isParenthesisBalance(exp))
System.out.println("Parenthesis is balanced");
else
System.out.println("Parenthesis is not balanced");
}
public static boolean isParenthesisBalance(String exp){
Stack<Character> stack=new Stack<Character>();
int size=exp.length();
int i=0;
char popChar;
while(i<size){
if(exp.charAt(i)=='{'||exp.charAt(i)=='('||exp.charAt(i)=='['){
stack.push(exp.charAt(i));
i++;
}
else if(exp.charAt(i)=='}'||exp.charAt(i)==']'||exp.charAt(i)==')'){
if(stack.isEmpty())
return false;
else
popChar=stack.pop();
if(isSamePairsOfParenthesis(popChar,exp.charAt(i))){
i++;
}
else
return false;
}
}
if(stack.isEmpty())
return true;
else
return false;
}
public static boolean isSamePairsOfParenthesis(char left, char right){
if(left=='(' && right==')' || left=='{' && right=='}'|| left=='[' && right==']')
return true;
else
return false;
}
c# implementation.
Complexity: O(c*n), c is a constant - a number of all possible brackets pairs, so roughly O(n).
Space: O(c), for dictionary with all possible brackets pairs, roughly - 0 ( in the example below - 32 bytes).
Return values: true - balanced, false - not balanced.
public bool ValidateBrackets( string str ) {
const uint n = 0;
var dic = new Dictionary<string, uint> { {"{}", n}, {"()", n}, {"[]", n}, {"<>", n} }; // here must be all the possible brackets
foreach ( char c in str ) {
foreach ( var item in dic ) {
if ( item.Key[0] == c ) {
dic[item.Key]++;
break;
}
if ( item.Key[1] == c ) {
try {
checked { dic[item.Key]--; }
} catch ( OverflowException ) {
return false;
}
break;
}
}
}
return dic.All(item => item.Value == 0);
}
Effective Java solution using ArrayDeque
import java.util.*;
import java.io.*;
public class Solution {
public static void main(String[] args) {
new Solution().solve();
}
public boolean isCorrectBracketExpression(String s) {
ArrayDeque<Character> q = new ArrayDeque<>();
String brackets = "({<[)}>]";
for (Character cur : s.toCharArray()) {
if (brackets.indexOf(cur) < 4)
q.addFirst(cur);
else {
if (q.size() > 0) {
if (brackets.charAt(brackets.indexOf(q.peek()) + 4) == cur)
q.poll();
else
return false;
} else // nothing in the queue, but we want to add something, incorrect expression
return false;
}
}
return q.size() == 0;
}
public void solve() {
Scanner in = new Scanner(System.in);
PrintWriter out = new PrintWriter(System.out);
String s = in.nextLine();
out.print(isCorrectBracketExpression(s) ? "Correct" : "Incorrect");
out.close();
}
}
function isBalanced($input)
{
$brackets = [']' => '[', ')' => '(', '}' => '{'];
$stack = new SplStack();
$pointer = 0;
while ($pointer < strlen($input))
{
$currentChar = substr($input, $pointer, 1);
if (in_array($currentChar, $brackets))
{
$stack->push($currentChar);
}
else
{
if ($stack->isEmpty() || $stack->pop() != $brackets[$currentChar]) return false;
}
$pointer++;
}
return $stack->isEmpty();
}
function isBalanced($input)
{
$brackets = [']' => '[', ')' => '(', '}' => '{'];
$stack = new SplStack();
$pointer = 0;
while ($pointer < strlen($input))
{
$currentChar = substr($input, $pointer, 1);
if (in_array($currentChar, $brackets))
{
$stack->push($currentChar);
}
else
{
if ($stack->isEmpty() || $stack->pop() != $brackets[$currentChar]) return false;
}
$pointer++;
}
return $stack->isEmpty();
}
Stack solution in C#.
private const char L_PAREN = '(';
private const char R_PAREN = ')';
private const char L_BRACE = '{';
private const char R_BRACE = '}';
private const char L_BRACKET = '[';
private const char R_BRACKET = ']';
public static bool isBalanced(string s)
{
Stack<char> stack = new Stack<char>();
for (int i = 0; i < s.Length; i++)
{
if (s[i] == L_PAREN)
stack.Push(L_PAREN);
else if (s[i] == L_BRACE)
stack.Push(L_BRACE);
else if (s[i] == L_BRACKET)
stack.Push(L_BRACKET);
else if (s[i] == R_PAREN)
{
if (stack.Count == 0)
return false;
if (stack.Pop() != L_PAREN)
return false;
}
else if (s[i] == R_BRACE)
{
if (stack.Count == 0)
return false;
if (stack.Pop() != L_BRACE)
return false;
}
else if (s[i] == R_BRACKET)
{
if (stack.Count == 0)
return false;
if (stack.Pop() != L_BRACKET)
return false;
}
}
return stack.Count == 0;
}
def paranthesis(inp):
stream = (i for i in inp)
m = {
'{' : '}',
'(' : ')',
'[' : ']'
}
stack = []
for s in stream:
if s in ['{','(', '[']:
stack.append(s)
elif m[stack.pop()] == s:
continue
else:
return False
if not len(stack):
return True
return False
if paranthesis('{[{}]}'):
print "Valid"
else:
print "Invalid"
def paranthesis(inp):
stream = (i for i in inp)
m = {
'{' : '}',
'(' : ')',
'[' : ']'
}
stack = []
for s in stream:
if s in ['{','(', '[']:
stack.append(s)
elif m[stack.pop()] == s:
continue
else:
return False
if not len(stack):
return True
return False
if paranthesis('{[{}]}'):
print "Valid"
else:
print "Invalid"
def paranthesis(inp):
stream = (i for i in inp)
m = {
'{' : '}',
'(' : ')',
'[' : ']'
}
stack = []
for s in stream:
if s in ['{','(', '[']:
stack.append(s)
elif m[stack.pop()] == s:
continue
else:
return False
if not len(stack):
return True
return False
if paranthesis('{[{}]}'):
print "Valid"
else:
print "Invalid"
//############### CPP ###############
bool ArePair(char opening,char closing) {
if(opening == '(' && closing == ')') return true;
else if(opening == '{' && closing == '}') return true;
else if(opening == '[' && closing == ']') return true;
return false;
}
void AreParanthesesBalanced() {
std::string exp = "(a+b{c+d})";
std::stack<char> S;
for(int i =0;i<exp.length();i++) {
if(exp[i] == '(' || exp[i] == '{' || exp[i] == '[')
S.push(exp[i]);
else if(exp[i] == ')' || exp[i] == '}' || exp[i] == ']') {
if(S.empty() || !ArePair(S.top(),exp[i])) {
std::cout<<"Not Balanced\n";
return;
}
else
S.pop();
}
}
if(S.empty())
std::cout<<"Balanced\n";
else
std::cout<<"Not Balanced\n";
return;
}
import java.util.Stack;
public class BalancedBrackets {
public static void main(String[] args) {
System.out.println(isBalanced("{{}}{()[]([])}"));
}
private static boolean isBalanced(String text) {
Stack<Character> helper = new Stack<Character>();
for(Character c : text.toCharArray()) {
if(isOpenBracket(c)) {
helper.push(c);
} else if(isClosingBracket(c)) {
if(helper.isEmpty() || !matches(helper.pop(), c)){
return false;
}
}
}
return helper.isEmpty();
}
private static boolean isOpenBracket(Character c) {
return c == '(' || c == '{' || c == '[';
}
private static boolean isClosingBracket(Character c) {
return c == ')' || c == '}' || c == ']';
}
private static boolean matches(Character open, Character close) {
switch (open) {
case '(':
return close == ')';
case '{':
return close == '}';
case '[':
return close == ']';
default:
break;
}
return false;
}
}
def solve(brackets):
stack = []
lookup = {
'}': '{',
']': '[',
')': '('
}
start_brackets = set(lookup.values())
end_brackets = set(lookup.keys())
for character in brackets:
if character in start_brackets:
stack.append(character)
elif character in end_brackets and stack[-1] == lookup[character]:
stack.pop()
else:
continue
return len(stack) == 0
import java.util.*;
public class Jib {
public static void main (String args[]) {
System.out.println(new Jib().add("{{(4[][])}}"));
}
private Stack<Character> stack;
public Jib() {
this.stack = new Stack<Character>();
}
public boolean add(String string) {
for (int i = 0 ;i < string.length() ;i++) {
if (okayToAdd(string.charAt(i))) {
stack.add(string.charAt(i));
}else {
return false;
}
}
Set<Character> set = new HashSet<>();
set.add(new Character('['));
set.add(new Character('{'));
set.add(new Character('('));
while(!stack.isEmpty()) {
if (set.contains(stack.pop()))
return false;
}
return true;
}
private boolean okayToAdd(char character) {
switch (character) {
case '}':
return poll('}');
case ')':
return poll(')');
case ']':
return poll(']');
default:
return true;
}
}
private boolean poll(char c) {
Set<Character> notAllowed = buildNotAllowed(c);
boolean found = false;
while(!stack.isEmpty() && !found) {
Character character = stack.pop();
if (notAllowed.contains(character))
return false;
if (character.charValue() == getOpeningParenthesis(c))
return true;
}
return true;
}
private Set<Character> buildNotAllowed(char c) {
Set<Character> set = new HashSet<>();
set.add(new Character('['));
set.add(new Character('{'));
set.add(new Character('('));
char op = getOpeningParenthesis(c);
Set<Character> results = new HashSet<>();
Iterator<Character> iterator = set.iterator();
while(iterator.hasNext()) {
Character character = iterator.next();
if (character.charValue() != op)
results.add(character);
}
return results;
}
private char getOpeningParenthesis(int c) {
switch (c) {
case '}':
return '{';
case ')':
return '(';
case ']':
return '[';
default:
return ' ';
}
}
}
public void matchBraces()
{
Map <Character,Integer> counterMap= new HashMap<Character, Integer>();
Map <Character, Character> braceMap = new HashMap<Character, Character>();
braceMap.put('{', '}');
braceMap.put('[', ']');
braceMap.put('(', ')');
String str = "..{{]scvs]sdd} ff[ds[}huda f";
String input = str.replaceAll("[^\\[\\]\\{\\}\\(\\)]", "");
String output = "";
for(int i = 0;i<input.length();i++)
{
if(counterMap.containsKey(input.charAt(i)))
{
counterMap.put(input.charAt(i), Integer.valueOf(counterMap.get(input.charAt(i))+1));
}
else
{
counterMap.put(input.charAt(i), 1);
}
}
for(char j : braceMap.keySet())
{
if(counterMap.get(j) == counterMap.get(braceMap.get(j)))
output = "Balanced";
else
{
output = "Not Balanced";
break;
}
}
System.out.println(output);
}
i've tried by this way, checking premature closure with wrong syntax
Python 2.7
[update] Just a fix, close parenthesis at close chars.
def check_closures(input):
open_chars = '[{(<'
close_chars = ']})>'
balance = [0] * len(open_chars)
input = re.sub(r'[^][{}<>()]', '', input)
print('input', input)
if(bool(len(input)%2)):
return False
closures = {}
last_opened = False
char_closure_index = None
for char in input:
char_closure_index = open_chars.find(char)
if(char_closure_index > -1):
last_opened = True
balance[char_closure_index] += 1
elif(char in close_chars):
char_closure_index = close_chars.find(char)
if(last_opened):
possible_close = close_chars[char_closure_index]
if(char is not possible_close):
return False
balance[char_closure_index] -= 1
last_opened = False
if(balance[char_closure_index] < 0):
return False
return sum(balance) == 0
print(check_closures('[{}]'))
print(check_closures('{{}}{)([][]'))
My implementation using a stack
- Mario November 19, 2015public static void main(String[] args) { Map<Character, Character> map = new HashMap<Character, Character>(); map.put('{', '}'); map.put('[', ']'); map.put('(', ')'); String s = "{{\ndoiajsodpijasoidja\t\nadoij saois()}}{}[][]".replaceAll("[^\\[\\]\\{\\}\\(\\)]", ""); process(s, map); } private static void process(String s, Map<Character, Character> map) { LinkedList<Character> stack = new LinkedList<Character>(); char[] c = s.toCharArray(); for (int i = 0; i < c.length; i++) { if(map.containsKey(c[i])){ stack.push(c[i]); }else{ if(!map.get(stack.peek()).equals(c[i])){ System.out.println("Not Balanced"); return; }else{ stack.pop(); } } } System.out.println(stack.isEmpty() ? "Balanced" : "Not Balanced"); }