google-code-prettify

Thursday 14 March 2013

Bracket combinations (Google Interview Question)

Write a function that prints all combinations of well-formed brackets. The input is a number which says how many pairs of brackets will the different outputs have. For Brackets(3) the output would be:
((()))  (()())  (())()  ()(())  ()()().

The solution below uses recursion. The logic here is very simple - every output is constructed starting with its first symbol. On each step a new symbol is added following these rules:
  • rule 1: if the number of opened brackets is equal to the number of closing brackets, then the only next possible symbol to add is '('
  • rule 2: if the number of opened brackets is more than the number of closing brackets, then there are two options - either we add ')' or '('
  • rule 3: if the number of opened brackets is more than half the number of all brackets, then the construction went wrong and we break the whole case
  • rule 4: if the number of opened brackets is less than the number of closing brackets, then the construction went wrong and we break the whole case
  • rule 5: the last symbol of the output cannot be '('
Add bracket
private void Brackets(String output, int open, int close, int total) {
    if (output.length() == total * 2 && output.charAt(total * 2 - 1) != '(') {
        System.out.println(output);
    } else if (open > total || open < close) {
        return;
    } else {
        if ((open == close)) {
            Brackets(output + "(", open + 1, close, total);
        }
        if ((open > close)) {
            Brackets(output + "(", open + 1, close, total);
            Brackets(output + ")", open, close + 1, total);
        }
    }
}

public void Brackets(int total) {
    Brackets("", 0, 0, total);
}


This is an Interview Question for Software Engineers at Google. Here you can find more information.

1 comment:

  1. Following having a few days and nights with mid-major March Madness championship video games

    claiming the college or universityMarch Madness

    Live
    field hockey spotlight, the Power 5 March Madness Live Stream conference tournaments commence to take center stage today. These kinds of are the games that

    will help define the way the bubble and the back again end of the NCAA

    March Madness Bracket Tournament bracket shakes away.
    March Madness 2017
    On Wednesday, Syracuse, Arkansas, March

    Madness 2017 Live
    California, TCU, Ohio Condition, Wake Forest, 2017 March Madness Virginia Technical, Texas

    Tech, Xavier and El monte all play video games NCAA March Madness that will either help solidify their

    at-large berth/seed or make Selection On the more of an

    troubled day. march madness schedule

    One other quick note: I moved Gonzaga back up to the top seed line after a third thoroughly

    impressive win over a very good Saint Mary's team in the WCC subject game. That's not

    total, though. The Pac-12 event champion march madness schedule 2017 could easily end up there by the end of the week, particularly if the winner of the

    Arizona/UCLA semifinal beats Or in it game.

    ReplyDelete