Booking.com Interview Question for Software Developers


Country: Netherlands
Interview Type: Phone Interview




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

My implementation using a stack

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

- Mario November 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- anudeepreddy November 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- R@M3$H.N November 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- zr.roman November 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- megido December 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Armin December 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Armin December 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- ersegun April 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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"

- Deepankar May 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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"

- Deepankar May 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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"

- Deepankar May 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- sosoup85 June 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- f.h March 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Shiplu M April 30, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- w.kinaan July 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Nitesh August 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python code:

def check_balanced_brackets(string):
    a = {'{': '}', '(': ')', '[': ']'}
    b = []
    for s in string:
        print(s)
        if s in a:
            b.append(s)
        elif s != a[b.pop()]:
            return False
    return True

- Anonymous October 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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('{{}}{)([][]'))

- vitoralbano November 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

- Deepankar May 14, 2016 | 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