Google Interview Question: Write a function Brackets(int... | Glassdoor

Interview Question

Software Engineer Interview New York, NY

Write a function Brackets(int n) that prints all

  combinations of well-formed brackets. For Brackets(3) the output would be ((())) (()()) (())() ()(()) ()()()
Tags:
brain teaser, algorithm, recursive algorithm
Answer

Interview Answer

11 Answers

0

public class Parenth2 {

    static int total = 3;

    static private void Brackets(String output, int open, int close, int pairs) {
        if ((open == pairs) && (close == pairs) && output.length() == total * 2) {
            System.out.println(output);
        } else {
            if (open < pairs)
                Brackets(output + "(", open + 1, close, pairs);
            if (close < open)
                Brackets(output + ")", open, close + 1, pairs);
        }

    }

    public static void main(String[] args) {
        Brackets("", 0, 0, total);
}
}

Interview Candidate on May 8, 2010
0

You almost got thte answer, just a couple of errors...
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author Owner
 */
public class Parenth4 {

    static private void Brackets(String output, int open, int close, int pairs, boolean opened, boolean closed, int total) {
        if ((open == pairs) && (close == pairs) && output.length() == total * 2) {
            System.out.println(output);
        } else {
            if ((open < pairs))
                Brackets(output + "(", open + 1, close, pairs,true, closed, total);
            if ((close < open)&& opened)
                Brackets(output + ")", open, close + 1, pairs,opened,closed, total);
        }

    }

    public static void Brackets(int total) {
        Brackets("", 0, 0, total,false,false, total);
    }
    public static void main(int number){
        Brackets(number);
    }
}

Interview Candidate #2 on May 11, 2010
3

This is a DP/memoization question, I believe. The base case is 0 and 1 bracket (the answer is empty or (). The recurrence is:

bracket(n) =
all combination of results from bracket(n-1) and from bracket (1)
from bracket(n-2) and bracket(2)
.
.
from bracket(1) and bracket(n-1)
lastly, '(' . bracket(n-1) ')'

The DP version of the above recurrence is straightforward. (Btw, this recurrence obviously will produce duplicate, but it's not hard to produce a modification that does not produce duplicate.) ;)

shards on May 11, 2010
1

Here is a F# implementation:

let rec Br total output openp closep =
    if openp = total && closep = total
    then
            printfn "%s" output
    else
            if openp < total then Br total (output + "( ") (openp + 1) closep
            if closep < openp then Br total (output + " )") openp (closep + 1)

let Brackets total =
    Br total "" 0 0

Brackets 5

let read = System.Console.ReadLine()

Horia on May 13, 2010
0

void parens(int nPairs) {
        parens("", nPairs, nPairs);
    }

    void parens(string ans, int leftCount, int rightCount) {
        if (leftCount==0 && rightCount==0) {
          cout 0) {
          parens(ans+"(", leftCount-1, rightCount);
        }
        if (rightCount>leftCount) {
          parens(ans+")", leftCount, rightCount-1);
        }
    }

marcos on May 17, 2010
1

To Remove duplicates simply use java Set :)

public static String bracket(int a) {

        Set s = new TreeSet();
        bracketIntern(s, a, "", "");
        System.out.println(s);
        return s.toString();
    }

    public static void bracketIntern(Set set,int a, String preFix,String suffix) {
        if(a == 1) {
            set.add(preFix+"()"+suffix);
            return;
        }
        bracketIntern(set, a-1, preFix+"()", suffix);
        bracketIntern(set, a-1, preFix+"(", ")"+suffix);
        bracketIntern(set, a-1, preFix, "()"+suffix);
    }

Rohan Dhapodkar on May 21, 2010
0

I think you can also build a trie, and the traverse the trie to print out all the combinations.

somebody on Jul 20, 2010
1

Complete python program to print the all combinations of well-formed brackets.

How to calculate its Big-o?
The recursive recurrence seems a little bit complicated.

----
def brackets(n):
    sol = []
    li = [' ' for x in range(n*2)]
    def recu_brackets(opened, closed):
        if n - opened:
            li[opened + closed] = '('
            recu_brackets(opened + 1, closed)
        if n - closed and opened > closed:
            li[opened + closed] = ')'
            recu_brackets(opened, closed + 1)
        if opened == n and closed == n:
            sol.append(''.join(li))
    recu_brackets(0, 0)
    print ' '.join(sol)

brackets(3)

userisyo on Aug 19, 2010
1

wasn't all that neat. o well

public class MakeBrackets{
    static List make(int number){
        List list = new LinkedList();

        if (number == 0) {list.add(""); return list;}
        if (number == 1) {list.add("()"); return list;}

        for (int i = 0; i < number; i++){
            for (String item : make(i)){
                for (String item2 : make(number - 1 - i)){
                    list.add("(" + item + ")" + item2);
                }
            }
        }
        return list;
    }

    public static void main(String[] args){
        System.out.println(make(Integer.parseInt(args[0])));
    }
}

xster on Aug 25, 2010
0

def brackets(n):
    return bracketsPrefix("", n, n)

def bracketsPrefix(prefix, opens, closes):
    total = 0
    assert opensopens:
        total += bracketsPrefix(prefix+")", opens, closes-1)
    if opens>0:
        total += bracketsPrefix(prefix+"(", opens-1, closes)
    return total

if __name__=="__main__":
    for i in range(6):
        n = brackets(i)
        print i,n
        x = raw_input("** ")

anon on Jun 1, 2011
0

This question gets so popular and I found this article has a really good explanation: https://goo.gl/E0m0EC

Jack on Dec 22, 2016

Add Answers or Comments

To comment on this, Sign In or Sign Up.