Facebook Interview Question for Interns


Country: United States
Interview Type: In-Person




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

The code prints all forms without duplicates. This question (solution) is in "Cracking the coding interview" Book.

def paren(left,right,string):
    if(left == 0 and right == 0):
        print string
    if(left>right):
        return
    if (left > 0):
        paren(left-1,right,string+"(")
    if (right > 0):
        paren(left,right-1,string+")")

def parentheses(n):
    paren(n/2,n/2,"")

parentheses(6)

output:
((()))
(()())
(())()
()(())
()()()

- maitreyak December 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This solution is beautiful.

- Cobra July 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 vote

C version:

#include <stdio.h>
#include <stdlib.h>
#define MAX 20

int n, kind;
char s[MAX*2+1];
/*
    we can recursively determine next character of the string
    if left < n
        we can choose to use one more left parenthesis or not
    if right < left
        we use one more right parenthesis
*/
void print(char* dest, int left, int right)
{
    if(left == n && right == n){
        puts(dest);
        ++kind;
        return;
    }
    if(left < n){
        dest[left+right] = '(';
        print(dest, left+1, right);
    }
    if(right < left){
        dest[left+right] = ')';
        print(dest, left, right+1);
    }
}

int main()
{   
    while(scanf("%d", &n), n){
        s[n<<1] = '\0';
        kind = 0;
        print(s, 0, 0);
        printf("%d kinds in total\n", kind);
    }
    
    return 0;
}

- uuuouou December 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

first call need be print(s, 1, 0); or else can't recursive...

- Will December 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Recursive version.

Keep track of how many open and close brackets are remaining.

Also keep track of number of open - number of closed used so far (called the balance_factor).

Python code:

def paren(num_open, num_close, balance_factor, paren_list):
    if num_open + num_close == 0:
        print "".join(paren_list)
        return
   
    if balance_factor > 0 and num_close > 0:
        paren_list.append(")")
        paren(num_open, num_close-1, balance_factor-1, paren_list)
        paren_list.pop()
   
    if num_open > 0:
        paren_list.append("(")
        paren(num_open -1, num_close, balance_factor+1, paren_list)
        paren_list.pop()
    
def paren_gen(n):
    print "n =", n
    paren(n, n, 0, [])
    print "-----"
  
def main():
    paren_gen(2)
    paren_gen(3)
    paren_gen(4)
  
if __name__ == "__main__":
	main()

output

n = 2
()()
(())
-----
n = 3
()()()
()(())
(())()
(()())
((()))
-----
n = 4
()()()()
()()(())
()(())()
()(()())
()((()))
(())()()
(())(())
(()())()
(()()())
(()(()))
((()))()
((())())
((()()))
(((())))
-----

- Subbu. December 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

balance_factor = num_close - num_open

so we don't exactly need to pass that around. Makes it easier to read though.

- Subbu. December 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

And here is the same code using generators (note that will multiply time complexity by n or n^2, depending on implementation).

def paren(num_open, num_close, balance_factor, paren_list):
    if num_open + num_close == 0:
        yield  "".join(paren_list)
   
    if balance_factor > 0 and num_close > 0:
        paren_list.append(")")
        for s in paren(num_open, num_close-1, balance_factor-1, paren_list):
            yield s
        paren_list.pop()
   
    if num_open > 0:
        paren_list.append("(")
        for s in paren(num_open -1, num_close, balance_factor+1, paren_list):
            yield s
        paren_list.pop()
   
def paren_gen(n):
    print "n =", n
    for s in paren(n, n, 0, []):
        print s
    print "-----"
   
def main():
    paren_gen(2)
    paren_gen(3)
    paren_gen(4)
  
if __name__ == "__main__":
    main()

- Subbu. December 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The code above looks correct. I am still posting the java version I wrote using a similar approach. The recursive implementation is in fact dynamic programming.

public class ParanthesisSequence {    
    public static void GetSequence(int N, int nClose) {
        if (N == 0) {
            sequences.add(a_sequence);
            return;
        }
        if (nClose == 0) {
            // We don't have to close any paranthesis since there are no open ones
            a_sequence = a_sequence + "(";
            GetSequence(N - 1, 1);
        }
        if (nClose > 0) {
            if (N >= nClose + 2) {
                // We could still open paranthesis
                String temp = a_sequence;
                a_sequence = a_sequence + "(";
                GetSequence(N - 1, nClose + 1);
                a_sequence = temp;
            }
            a_sequence = a_sequence + ")";
            GetSequence(N - 1, nClose - 1);
        }
    }
    
    private static String  a_sequence = "";
    public static ArrayList<String> sequences;
}

Sample usage:

public static void main(String[] args) {
        // TODO code application logic here
        int N = 6; // N = 2 * n
        ParanthesisSequence.sequences = new ArrayList<String>();
        ParanthesisSequence.GetSequence(N, 0);
        for (String s : ParanthesisSequence.sequences) {
            System.out.println(s);
        }
    }

Output:

((()))
(()())
(())()
()(())
()()()

- Ehsan December 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Problem with this is the huge space usage (which is not the case with the python solution above).

- Subbu. December 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

(And that is something the interviewer will be worried about).

- Subbu. December 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Of course, since there is probably a super-polynomial number of terms. I could as well print the sequence out instead of adding it to the list. Either way, writing it to console does not resolve the space problem.

- Ehsan December 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The total number is Catalan number (call it C_n).

And no, space usage being O(n) and that is relevant.

For example, instead of printing it, all I would have to do is yield it (a python feature for creating generators).

Now I have a generator which can do something similar to hasNext(), next() of Java. It would use only O(n) space, and can be used to print out only the first 1000 arragements or 10000 or whatever. The space usage will remain O(n) irrespective of how many times you do a next.

The fact that I am printing it is not any indication that the space usage will be Omega(C_n).

Of course, now that I look at your solution more carefully, you don't really need to use that much space and our solutions are quite similar. So actually that is not a problem with your solution and can potentially be converted into a hasNext, next generator using O(n) space.

- Subbu. December 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

See update to my answer using generators.

- Subbu. December 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks for the reference to Cn and generators in python. I guess I see your point.
I believe one way to modify my implementation to work as a generator is to store the state after each call (e.g., sequence and the last value of "N" and "nClose" before finding a new sequence).

- Ehsan December 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

class NBrackets{

	public static void main( String[] args ){
		sumCombination( "", Integer.parseInt( args[0] ) );
	}

	static void sumCombination( String output, int sum ){
		if( sum == 0 ) {
			generateOutput( output );
			return;
		}
	
		for( int i = 1; i <= sum; i++ ){
			sumCombination( output + i, sum - i );
		}
	}
	
	static void generateOutput( String output ){
		StringBuilder builder = new StringBuilder();
			
		for( int i = 0; i < output.length(); i++){
			char c = output.charAt( i );
			builder.append( toBrackets( c - 48 ) );
		}
		
		System.out.println( builder.toString() );
	}
	
	static String toBrackets( int n ){
		StringBuilder builder = new StringBuilder();
		for( int i = 0; i < n; i ++ ){
			builder.append( "(" );
		}
		for( int i = 0; i < n; i ++ ){
			builder.append( ")" );
		}
		
		return builder.toString();
	}
}

- PH December 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python code below:

def R(n, buf=''):
    if len(buf) == 2*N:
        print buf

    if n > 0:
        buf += ')'
        R(n-1, buf)
        buf=buf[:-1]

    if 2*N - (n+len(buf)) >= 2:
        buf += '('
        R(n+1, buf)
        buf=buf[:-1]


N = 4
R(0)

- shivkalra1 December 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<stdlib.h>
void printParanthesis(char *str,int index,int num,int open,int close)
{
  if( open==close&&open==num)
  {
   printf("\n %s",str);
     return;
  }
   
   if(open<num)
{
 
str[index]='(';
   printParanthesis(str,index+1,num,open+1,close);

}
 
   if(open>close)
  {
    
     str[index]=')';
     printParanthesis(str,index+1,num,open,close+1);

   }
}
int main()
{

char str[50]={'\0'};
 printParanthesis(str,0,3,0,0);


}

- A simple recursive solution December 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice one

- @@@@@@@ December 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Another C Program using "BackTracking"

#include<stdio.h>


#define MAXN 100
#define MAXC 3

char a[MAXN];
char c[MAXC];

int is_solution(char a[], int k, int n)
{
  return (k == n-1);
}

void process_solution(char a[], int k, int n)
{
  a[k+1] = '\0';
  printf("\n%s",a);
}

int construct_candidates(char a[], int k, int n, char c[])
{
  int nopen = 0;
  int nclosed = 0;
  int ncandidates = 0;

  int i=0;
  for(i=0;i<k;i++)
  {
    if( a[i] == '(' )
    {
      nopen++;
    }
    else 
      if(a[i] == ')' )
      {
        nclosed++;
      }
  }

  if( nopen < (n>>1) )
    c[ ncandidates++] = '(';

  if( nclosed < nopen )
    c[ ncandidates++] = ')';

  return ncandidates;
}


void backtrack(char a[], int k, int n)
{
  if( is_solution( a,k, n ) )
  {
    process_solution(a,k,n);
    return;
  }
  else
  {
    char c[MAXC];
    k = k+1;
    int ncandidates = construct_candidates(a,k,n,c);
    int i = 0;
    for(i=0; i<ncandidates; i++)
    {
      a[k] = c[i];
      backtrack(a,k,n);  
      a[k] = '\0';
    }
  }
}

int main()
{
  int n; 
  scanf("%d",&n);
  backtrack(a,-1,n<<1);
  printf("\n");
}

- confused_banda December 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void generateValidParanthesis(int n, String s) {
		if(n == 0) { System.out.println(s); return; }
		
		
		String s1 = "(" + s + ")";
		String s2 = "()" + s;
		String s3 = s + "()" ;
		
		if(!s1.equals(s2) && !s1.equals(s3)) {
			generateValidParanthesis(n-1, s1 );
		}
		if(!s2.equals(s3)) {
			generateValidParanthesis(n-1, s2);
		}
		
		generateValidParanthesis(n-1,  s3 );
		
	}

- Arth December 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Call it like generateValidParanthesis(4, "");

- Arth December 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I've came with similar solution in Objective-C, but then have realised that it doesn't generate `(())(())` when n equals 4. Probably your code also doesn't handle this case...

- ilyukevich.victor December 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Haha,how about this bit-flipping solution
1.define an int , i1, with n length bit initialized to 0
2.flip i1 to acquire i2
3. Starting from i2 , you read the two ints
bit by bit, print a left paran for a set bit and a right paran for an unset.
4. Increment i1, if the highest bit is still 0, print a line separator and loop back to step 2

- eThomas December 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you explain more? What do you do in step 4 "if the highest bit is not 0"?

- Anonymous December 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Haha,how about this bit-flipping solution
1.define an int , i1, with n length bit initialized to 0
2.flip i1 to acquire i2
3. Starting from i2 , you read the two ints
bit by bit, print a left paran for a set bit and a right paran for an unset.
4. Increment i1, if the highest bit is still 0, print a line separator and loop back to step 2

- eThomas December 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Another C++ version

#include <algorithm>
#include <cmath>
#include <iostream>
#include <stack>
#include <vector>

using namespace std;

/* Main Code Starts from here */

void bracketPermut(vector<vector<char> >& vii, vector<char>& vi, int l, int r, int n) {
    if(l>n)
        return;
    if(r == n) {
        vii.push_back(vi);
        return ;
    }
    else {
        if(l>r) {
            vi.push_back(')');
            bracketPermut(vii, vi, l, r+1, n);
            vi.pop_back();
        }
        vi.push_back('(');
        bracketPermut(vii, vi, l+1, r, n);
        vi.pop_back();
    }
}

vector< vector <char> > bracketPermut(int n) {
    vector <vector<char> > vii;
    vector<char> vi;
    bracketPermut(vii, vi, 0, 0, n);
    return vii;
}

int main() {

    vector< vector<char> > out = bracketPermut(5);
    for(auto i: out) {
        for(auto j:  i)
            cout << j << " ";
        cout<< endl;
    }
    return 0;
}

- jitendra.theta December 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def gen(n, left=0, right=0,index=0,str=""):

    if index == 2*n:
        print(str)
        return

    if left < n:
        gen(n, left+1, right, index+1, str+"(")

    if right < left:
        gen(n, left, right+1, index+1, str+")")

- m@}{ December 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def generateParenComb(left, right, left_stack, output):
    if right == 0:
				    print output
    if left > 0:
				    generateParenComb(left-1, right, left_stack+1, output+'(' )					
    if right>0 and left_stack>0:
				    generateParenComb(left, right-1, left_stack-1, output+')')
								
def topGenerateParenComb(num):
    generateParenComb(num, num, 0, "")				


topGenerateParenComb(4)

output:
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()

- Haoju Ho December 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

anyone knows the complexity?

- Anonymous December 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

2^n exponential..since at every 2n places there are 2 choices to be made.

- shivkalra1 December 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The total number is the nth Catalan number: (2n Choose n)/(n+1).

The compexity of this is Theta(4^n/n^(1.5))

@shivkalra: There aren't 2 choices at every step. It could be any of 0, 1 or 2 choices.

- Subbu. December 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

shivkalra1 was close

he used a different n
in this problem there are 2n parentheses

so 2^(2n) is number of possible parentheses without regard to balancing them

which is 4^n

so it is O(4^n)

But Subbu have tighter bound for it by dividing by n^1.5, which is basically adjusting for only including balanced results.

- correcting shivkalra1 December 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

ArrayList<String> pairs(int n){
	return pairs(n, n, "");
}
ArrayList<String> pairs(int open, int close, String s){
	ArrayList<String> ret = new ArrayList<String>();
	if(open == 0){
		for(int i = 0; i<close; i++){
			s += ")";
		}
		ret.add(s);
	} else{
		ret.addAll(pairs(open-1, close, s+"(");
		if(close > open){
			ret.addAll(pairs(open, close-1, s+")");
		}
	}
	return ret;
}

- ShiguangWang December 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import unittest

def paren(n):
    if n == 0: yield ""
    for i in xrange(n):
        for j in paren(i):
            for k in paren(n - i - 1):
                yield j + "(" + k + ")"

def generate(n):
    print("Generating: 2 * {}".format(n))
    for s in paren(n):
        if len(s) == 2 * n:
            print(s)

class Test(unittest.TestCase):
    def test_generate(self):
        generate(0)
        generate(1)
        generate(2)
        generate(3)

if __name__ == "__main__":
    unittest.main()

- yaojingguo December 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

unittest which really does not do any testing?

- Anonymous December 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class ParanTest {
	public static void main(String[] args) {
		buildParan(new StringBuilder(), 0, 0, 3);
	}
	
	public static void buildParan(StringBuilder sb, int open, int close, int tot){
		if(close < open){
			StringBuilder newSb = new StringBuilder(sb.toString());
			newSb.append(')');
			int newClose = close;
			if(++newClose == tot){
				System.out.println(newSb.toString());
			}
			else{
				buildParan(newSb, open, newClose, tot);
			}
		}
		
		if(open < tot){
			int newOpen = open+1;
			sb.append('(');
			buildParan(sb, newOpen, close, tot);
		}
	}
}

- ChongHyuk Won December 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class AllBrackets {

    public static void main(String... a) throws Exception {
        printAll(Integer.parseInt(a[0]));
    }

    public static void printAll(int n) {
        printAll(new char[2 * n], 0, 0);
    }

    private static void printAll(char[] c, int index, int level) {
        if (index >= c.length) {
            System.out.println(new String(c));
            return;
        }
        if (level > 0) {
            c[index] = ')';
            printAll(c, index+1, level-1);
        }
        if (c.length - index > level) {
            c[index] = '(';
            printAll(c, index+1, level+1);
        }
    }
}

- gensay December 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<?php

function printParanthesis(array $str,$index,$num,$open,$close)
{
if($open == $close && $open == $num)
{
echo implode("",$str)."\n";
return;
}

if($open < $num)
{
$str[$index]='(';
printParanthesis($str,$index+1,$num,$open+1,$close);
}

if($open > $close)
{
$str[$index]=')';
printParanthesis($str,$index+1,$num,$open,$close+1);
}
}

//main
$str = array();
$n = trim(fgets(STDIN));
printParanthesis($str,0,$n,0,0);

- yorgen December 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<?php

function printParanthesis(array $str,$index,$num,$open,$close)
{
    if($open == $close && $open == $num)
    {
        echo implode("",$str)."\n";
        return;
    }
   
    if($open < $num)
    {
        $str[$index]='(';
        printParanthesis($str,$index+1,$num,$open+1,$close);
    }
 
    if($open > $close)
    {
        $str[$index]=')';
        printParanthesis($str,$index+1,$num,$open,$close+1);
    } 
}

//main
$str = array();
$n = trim(fgets(STDIN));
printParanthesis($str,0,$n,0,0);

- yorgen December 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>

using namespace std;

void allPatterns(string str, int n, int open, int close){
        string str1, str2;
        str1 = str;
        str2 = str;
        if(n == 0){
                if((open - close) == 0)
                        cout<<str<<"\n";
                return;
        }
        else if((open - close) < 0)
                return;
        else{
                str1.append(1,'(');
                allPatterns(str1,--n,open+1,close);
                str2.append(1,')');
                allPatterns(str2,n,open,close+1);
        }
        return;
}

int main(){
        int open = 0, close = 0;
        string str;
        int n = 6;
        allPatterns(str,n,open,close);
}

- sunnynaval December 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The following algorithm uses the recursive formula to generate Catalan Numbers.

public class Catalan{
	public ArrayList< ArrayList< String> > allCatalanParentheses;

	public Catalan( int n ){
		for( int i = 0; i <= n; i ++ )
			allCatalanParentheses.add( new ArrayList<String>() );
		allCatalanParentheses.get( 0 ).add( "" );
	}

	public void generate( int n ){
		for( int k = 1; k < n; k ++ ){
			if( allCatalanParentheses.get( k ).size() == 0 ){
				generate( k-1 );
			}
			if( allCatalanParentheses.get( n - k ).size() == 0 ){
				generate( n - k );
			for( int i = 0; i < allCatalanParentheses.get( k-1 ).size(); i ++ ){
				for( int j = 0; j < allCatalanParentheses.get( n-k ).size(); j ++ ){
					allCatalanParentheses.get( n ).add( "(" + allCatalanParentheses.get( k-1 ).get( i ) + ")" + allCatalanParentheses.get( n-k ).get( j ) );
				}
			}
		}
	}

	public void print( int k ){
		for( int i = 0; i < allCatalanParentheses.get( k ).size(); i ++ )
			System.out.println( allCatalanParentheses.get( k ).get( i ) );
	}
}

- chandler.c.zuo December 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This one uses grammar to generate

#include <iostream>
#include <list>
#include <string>
using namespace std;

list<string> allParens2n(int n)
{
    list<string> allParens(int n);

    return allParens(2*n);
}

//Direct implementation of B -> "" | B(B)
//Which is the unambiguous grammar of balanced parenthese
list<string> allParens(int n)
{
    list<string> returnValue;
    if(n == 0)
    {
        string s(""); 
        returnValue.push_back(s);
        return (returnValue);
    }
    
    for(int i = 0; i <= (n-2);i+= 2)
    {
        list<string> l = allParens(i);
        list<string> r = allParens(n-2-i);
        for(list<string>::iterator li = l.begin();li != l.end();li++)
            for(list<string>::iterator ri = r.begin();ri != r.end();ri++)
                {
                    string s("");
                    s+=*li;
                    s+="(";
                    s+=*ri;
                    s+=")";
                    returnValue.push_back(s);
                }
    }

    return returnValue;  
}
 
int main ()
{
    list<string> l = allParens2n(4);
    for(list<string>::iterator i = l.begin(); i != l.end();i++)
    {
        cout<<*i<<"\n";
    }
}

- Anonymous December 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Ruby 2.0.0 implementation using a binary tree

OUTPUT = []
N=2

# creates a binary tree where left adds ( and right adds )
def search node
  # stop condition on the height of the tree
  if node.size >= 2*N
    # Add to valid output if it's valid
    OUTPUT << node if valid_answer node
    # return to father
    return node
  else
    # go left and go right adding the char
    left = search node+'('
    right = search node+')'
  end
end

# Verify if it's a valid leef
def valid_answer answer
  # temporary because we need to destroy the answer
  temp = answer.dup

  # keep closing parentesis
  while temp.include? "()"
    # remove closed parentesis
    temp.slice! "()"
  end

  # if there's no more char the all parentesis are valid
  if temp.size == 0
    return true
  else
    return false
  end
end

# Start tree
search ""

# output
puts OUTPUT

- JĂșlio Bueno December 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void printAllParenthessis(int n, int openPar, int closePar, string currStr)
        {
            if (2 * n == currStr.Length)
            {
                Console.WriteLine(currStr);
            }
            if (openPar - closePar <= (2 * n - currStr.Length) / 2)
            {
                
                string newStr = currStr+"(";
                printAllParenthessis(n, openPar+1, closePar, newStr);
            }
            if (closePar < openPar)
            {
                string newStr = currStr + ")";
                printAllParenthessis(n, openPar, closePar + 1, newStr);
            }

        }

- Saar December 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void Trace(std::vector<std::string> & rs, std::string cur, int left, int right, int n) {
  if (left == n) {
    cur.append(n - right, ')');
    rs.push_back(cur);
  } else {
    Trace(rs, cur + "(", left + 1, right, n);
    if (left > right) {
      Trace(rs, cur + ")", left, right + 1, n);
    }
  }
}

- guoliqiang2006 December 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ Solution:

#include<iostream>
using namespace std;
int n;
void f(int o,int c,string t){
if(o==n && c==n){cout<<t<<"\n";}
else{
if(o+1<=n && o+1-c>=0){f(o+1,c,t+'(');}
if(c+1<=n && o-c-1>=0){f(o,c+1,t+')');}
}
}
int main(){
cin>>n;cout<<"\n\n";
string t;f(0,0,t);
}

However this is a recursive solution.. I'm wondering if we can use memorization to solve it for a better time complexity...

- Uma Priyadarsi January 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python recursive implementation

def gen_valid_par(p, length, para_hist):
    if length < 0 or para_hist < 0:
        return -1
        
    if para_hist > length:
        return -1
        
    if length == 0 and para_hist == 0:
        print p
        return 1
        
    return gen_valid_par(p + '(', length - 1, para_hist + 1) + gen_valid_par(p + ')', length - 1, para_hist - 1)    


def main():
    n = int(raw_input())
    gen_valid_par("", 2*n, 0)


if __name__ == "__main__":
    main()

- brinkofglory April 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In the following
{...} means "a set of the elements ..."
where S = {...}, s is a string
S + s means the set of each of elements of S concatenated with s
s + S means the set of s concatenated with each of the elements of S
s1 + S + s2 means the s1 concatenated with each of the elements of S concatenated with s2

For n = 0 we have S0 == {}
For n = 1 we have S1 == {()}
For n > 1 we have Sk == {Sk-1 + (), () + Sk-1, ( + Sk-1 + )}

This is very easy to write in Scala as follows:

def parens(l:Int):Set[String] = {
  l match {
    case 0 => Set.empty
    case 1 => Set("()")
    case _ => (for (a <- parens(l-1)) yield Set("()" + a, a + "()", "(" + a + ")")).flatten
  }
}

To pretty print the results is similarly simply:

def pparens(l:int):Unit = parens (l) foreach println

For example:

scala> pparens(0)

scala> pparens(1)
()

scala> pparens(2)
()()
(())

scala> pparens(3)
(()())
((()))
()()()
(())()
()(())

scala> pparens(4)
(()()())
(()())()
((()()))
(()(()))
((()))()
(((())))
()(()())
()(())()
()((()))
()()(())
()()()()
(())()()
((())())

scala>

- Steve Schleimer May 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void print(int n) {
	vector<char> par(2 * n);
	int noOpen = 0, noClosed = 0;
	
	function<void(int)> back = [&](int k) {
		if(k == 2 * n) {
			for(int i = 0; i < par.size(); i++)
				cout << par[i];
			cout << endl;
		}
		else {

			if(noOpen - noClosed < 2 * n - k) {
				par[k] = '(';
				noOpen++;
				back(k + 1);
				noOpen--;
			}

			if(noClosed < noOpen) {
				par[k] = ')';
				noClosed++;
				back(k + 1);
				noClosed--;
			}
		}
	};

	back(0);
}

- Outermeasure November 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A simple c# implmentation

using System;

public class Test
{
	public static void Main()
	{
		// your code goes here
		int val = 3;
		char[] ch = new char[val * 2];
		PrintValidParanthesis(ch, val, val, 0);
	}
	
	public static void PrintValidParanthesis(char[] str, int left, int right, int count)
	{
		if (count == str.Length) { PrintParanthesis(str); return; }
		
		if (left != 0) 
		{
			str[count] = '(';
			PrintValidParanthesis(str, left - 1, right, count + 1);
		}
		
		if (left < right) 
		{
			str[count] = ')';
			PrintValidParanthesis(str, left, right - 1, count + 1);
		}
		
	}
	
	public static void PrintParanthesis(char[] str)
	{
		Console.WriteLine(str);
	}
}

- Shanmuk February 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python

# number of left and right parenthesis not used yet
def foo(left,right):
    if left==0:
        temp = [')' for i in range(right)]
        return [''.join(temp)]
    
    if left==right:
        lst = foo(left-1,right)
        #what if lst == []
        return ['('+x for x in lst]
    else:
        lst1 = foo(left-1,right)
        
        lst2 = foo(left,right-1)
        l1= ['('+x for x in lst1]
        l2=[')'+x for x in lst2]
        return l1+l2
        
   


if __name__ == '__main__':
    for string in foo(3,3):
        print string

- smillence1992 February 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
public static void printValidParens(int k) {
printValidParens("", k, k);
}

private static void printValidParens(String prefix, int open, int close) {
if (open == 0 && close == 0) {
System.out.println(prefix);
return;
}

if (open >= 1) printValidParens(prefix + "(", open - 1, close);
if (close > open) printValidParens(prefix + ")", open, close - 1);
}
}}

- Tarball February 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
public static void printValidParens(int k) {
printValidParens("", k, k);
}

private static void printValidParens(String prefix, int open, int close) {
if (open == 0 && close == 0) {
System.out.println(prefix);
return;
}

if (open >= 1) printValidParens(prefix + "(", open - 1, close);
if (close > open) printValidParens(prefix + ")", open, close - 1);
}
}}

- Tarball February 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Set<String> genBrackets(int n) {
        if (n == 1) {
            return Collections.singleton("()");
        } else {
            Set<String> subs = genBrackets(n - 1);
            Set<String> retval = new HashSet<>();
            for (String s : subs) {
                retval.add("()" + s);
                retval.add("(" + s + ")");
            }

            return retval;
        }
    }

- Daniel August 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void GenerateValidParenthesis(std::string& s, int open, int close, int n)
{
    if (close == n)
    {
        std::cout << s << std::endl;
    }

    if (open > close)
    {
        GenerateValidParenthesis(s + ')', open, close + 1, n);
    }

    if (open < n)
    {
        GenerateValidParenthesis(s + '(', open + 1, close, n);
    }
}

- artur.ghandilyan November 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def print_all_parenthesis(stack, history, iterations_left):
    
    if iterations_left == 0:
        if not stack:
            print(history)
    
    else:
        if not stack:        
            print_all_parenthesis(stack + [1], history + '(', iterations_left - 1)
        else:
            print_all_parenthesis(stack + [1], history + '(', iterations_left - 1)
            print_all_parenthesis(stack[:-1], history + ')', iterations_left - 1)
            

def wrapper(n):
    print_all_parenthesis([], '', n * 2)
    
wrapper(4)

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

A JavaScript solution

function _nParens(number){
    if(number < 1){
        return [];
    } 
    if(number === 1){
        return ["()"];
    }

    var holder = [];

    var prevParenthesis = nParens(number - 1);
    for(var i = 0; i < prevParenthesis.length; i++){
        var parenthesisAtIndex = prevParenthesis[i];

        for(var j = 0; j <= parenthesisAtIndex.length; j++){
            var left = parenthesisAtIndex.slice(0, j);
            var right = parenthesisAtIndex.slice(j, parenthesisAtIndex.length);
            holder.push(`${left}()${right}`);
        }
    }

    return holder;
}

function nParens(number){
    var res = _nParens(number);
    return Array.from(new Set(res))
}

- mche1987 March 30, 2018 | 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