Technical Interview: Parenthesis Problem

· algorithm, development, interview
Author

Problem Statement:

I recently went through an interview process, for a software engineer position, during which the interviewer asked me to solve the following problem:

Given N parenthesis, write a program that outputs all the valid parenthesis combinations.

Explanations:

Of course, for N odd, the program should output some error message. For N=2, the program should output something like {(), }. For other values of N:

N=4: {(()), ()(), }
N=6: {((())), ()()(), ()(()), (())(), (()())}
etc.

My solution I (during the interview):

For the solutions I propose, I use Python syntax, which makes it easy to use directly characters like '(' and ')'. I guess with C or Java, you may rather use another data representation, like 0 and 1.

After analyzing quickly the previous series, I thought there could be some rule to build the set at a given N, N>2, using the set done at N-2:

1
2
3
4
5
brackets(N):
    SetAtNMinus2 = brackets(N-2)
    SetAtN = []
    for each element e in SetAtNMinus2,
        SetAtN.add( '('+e+')', '()'+e, e+'()' )

Such an algorithm leads to many repetitions, and many comparisons are therefore needed. According to the previous series, for N=2, 4 and 6, the above rule, i.e. adding 3 elements for each element of the previous set, seems to work.

The actual code in Python that I provided is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def brackets(N):
    """
    brackets(N) returns all the possible
    valid bracket combinations of N elements
 
    ERRATUM: this function might actually not return ALL
    the possible combinations - and sometimes duplicates as well...
    """
    if N%2 != 0 or N <= 0:
        raise ValueError('N should be even and non-negative.')
 
    if N == 2:
        return ['()']
 
    A = brackets(N - 2) # T(N-2)
    B = []
    patternToRuleOut = ''
    for n in range(N/2-1):
        patternToRuleOut += '()'
    for a in A: # O(len(A))
        B.append('('+a+')')
        B.append('()'+a)
        if a != patternToRuleOut:
            B.append(a+'()')
 
    return B

As the careful reader would already have noticed, I wrote in the above comments that this program does not output the correct answer. Indeed, I first noticed that there were duplicates, and additionally, the number of combinations was not equal to the Catalan number, which is the theoretical size of the answer (although I did not check that).

My solution II (after-thought: sol. I is buggy!):

The error of solution I comes from the selected rule. A probably better rule is also a bit more complicated. The elements of the set for a given N>2 are:

  • either the elements of the set for N-2, enclosed into brackets: for all element a in validBrackets(N-2), (a) is in validBrackets(N)
  • or, for all 2<= i <= N-2 the concatenation of the elements of validBrackets(i) and validBrackets(N-i). There may be some “smart” way to create these concatenations while avoiding the repetitions, as I believe I did on the following program.

The code corresponding to this rule is therefore a bit more complicated, but seems to output the correct set (at least, sets of size equal to the Catalan number). For each n<=N, It needs to keep track of coinstar tax Coinstar Money Transfer in Himachal pradesh, India “pure” combinations of size n (i.e. combinations that are not concatenations – that is also to say the combinations of the first category), as well as track of the pure concatenations. By doing so, the correct set validBrackets(N) is derived from the others such that:

  • for all a in pureBrackets(N-2), put (a) in pureBrackets(N)
    

 

  • for all 2<=i<=N-2,
        for all a in pureBrackets(i),
            for all b in pureBrackets(N-i) or in concatenatedBrackets(N-i),
                put ab in concantenatedBrackets(N)
    

The Python code is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def brackets2(N):
 
    """
    brackets2(N) returns all the possible
    valid bracket combinations of N elements
    """
    if N%2 != 0 or N &lt;= 0:
        raise ValueError('N should be even and non-negative.')
 
    if N == 2:
        return {N: ['()']}, {N: []}
 
    bracketsPure, bracketsCombo = brackets2(N-2)
    ##print bracketsPure
    ##print bracketsCombo
 
    bracketsPure[N] = []
    bracketsCombo[N] = []
    for item in bracketsPure[N-2]:
        bracketsPure[N].append('('+item+')')
    for item in bracketsCombo[N-2]:
        bracketsPure[N].append('('+item+')')
 
    for n in range(1, N/2):
        for itemP in bracketsPure[2*n]:
            for itemC in bracketsPure[N-2*n]:
                bracketsCombo[N].append(itemP+itemC)
            for itemC in bracketsCombo[N-2*n]:
                bracketsCombo[N].append(itemP+itemC)
 
    return bracketsPure, bracketsCombo
 
def listBrackets(N):
    bracketsPure, bracketsCombo = brackets2(N)
    return bracketsPure[N]+ bracketsCombo[N]

 

The output of this program, in an iPython shell:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
In [3]: listBrackets(2)
Out[3]: ['()']
 
In [4]: listBrackets(4)
Out[4]: ['(())', '()()']
 
In [5]: listBrackets(8)
Out[5]: 
['(((())))',
 '((()()))',
 '(()(()))',
 '(()()())',
 '((())())',
 '()((()))',
 '()(()())',
 '()()(())',
 '()()()()',
 '()(())()',
 '(())(())',
 '(())()()',
 '((()))()',
 '(()())()']
 
In [6]: len listBrackets(16)
------> len(listBrackets(16))
Out[6]: 1430

The Catalan number are: C(2/2) = 1, C(8/2) = 14, C(16/2) = 1430… There does not seem to be any duplicate either, which seems to confirm that this program actually provides the correct set! QED!

Maybe later I might get interested in proving the result for the Catalan number.

This could actually be quite straightforward with the rule I enunciated above.

Hope that helps!

Cheers!