## Google Interview Question for Software Engineer / Developers

Country: United States

Comment hidden because of low score. Click to expand.
3
of 5 vote

Let N be an even number (just double the n from the question), the size of the thing you are building.

Backtracking: left to right build your thing. Keep track of the number of ( and ) braces already in the filled part of the thing you are building.

``````Let numLeft be the tally of ( already built.
Let numRight be the tally of the ) already built.

Take care in what you allow to be added in any position.

- If you are the i-th position "filler" of the recursive backtracking function:
-> You can fill that position with a ) if the numLeft > numRight

[ Because, if numLeft <= numRight, adding a ) won't match a previous ( ]

-> You can fill that position with a ( if numLeft < (1/2)*N

[Because we will have (1/2)*N ( in final result, so can't add more than that ]``````

C:

``````#include <stdio.h>

#define N 6  //question would have given n=3
void filler()
{
static int i, numleft, numright;
static char result[N+1]; // all 0-initialized by compiler

if(i==N) { puts(result); return; }

if(numleft > numright) //can close earlier ( with a ) so do so
result[i++]=')' , numright++, filler(i), numright--, i--;

if(2*numleft < N)     //have room to open a (  so do so
result[i++]='(' , numleft++, filler(i), numleft--, i--;
}

int main(void){
filler();
return 0;
}``````

^^^ Made N fixed compiled time constant and other things simple to make the algo. stand out as the star player.

Made the winding and unwinding of variables explicit on purpose also (otherwise they might be "hidden" for illustrative purposes).

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

The idea is simple - Recursive Backtracking
C++ program to print all valid combinations of 'n' pair of braces

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

void print_parentheses(int n);
void print(int left, int right, int n, string s);

int main()
{
int n;
cout<<"Enter n: ";
cin>>n;
print_parentheses(n);
}

void print_parentheses(int n)
{
string s="";
print(0, 0, n, s);
}

void print(int left, int right, int n, string s)
{
if(left>n || right>n || right>left)
return;
if(left==right && left+right==2*n)
{
cout<<s<<endl;
return;
}
print(left+1, right, n, s+"(");
print(left, right+1, n, s+")");
}``````

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

This is a simple and intuitive solution.

But we can replace string with bit-storage.
There are (2n)!/(n!(n+1)!) total combination for parentheses and copying string is very time-consuming operation.

Here is the comparing of work time (in ms) for string and bit implimintation:

``````n		bit				string
5		0				2
10		8				869
11		28				3164
12		97				11450
13		358 (< 1 sec)	40892 (40 sec)
14		1300 (1 sec)	146235 (2 min)
15		4788 (5 sec)	537079 (8 min)``````

I hope, I assure you that it is bad to copy strings

``````class Parentheses /*save as binary */
{
public:
Parentheses() : parentheses(0), n(0) {}
Parentheses add(bool bracket) //return new object
{
if(bracket) return Parentheses(parentheses | (1 << n), n + 1);
else return Parentheses(parentheses, n + 1);
}
void print()
{
for(size_t i = 0; i<n; ++i)
if(parentheses & (1 << i)) cout<<"("; else cout<<")";
cout<<endl;
}
private:
Parentheses(unsigned long long parentheses, size_t n)
: parentheses(parentheses), n(n) {}
unsigned long long parentheses;
size_t n;
};

void find(int n, int left=0, int right=0, Parentheses s= Parentheses())
{
if(left+right==2*n)
{
s.print(); return;
}
if(left != n)
if(right < left)
}``````

Comment hidden because of low score. Click to expand.
0

@Darida
Nice....Thumbs Up

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

the combinations of braces should be build in following lexical rules

``````E ::= ()
E ::= (E)
E ::= E E``````

we can use dp here, say dp[i] is a list of all possible combinations of i pairs of braces
for rule 1, we have dp = ["()"]
for rule 2, we have dp[i+1] = each item in dp[i] cover with a braces
for rule 3, we have dp[i] = each item in dp[j] combine each item in dp[k], where j+k == i

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

``````void printParen( int n, string pref = "", string suff = "" )
{
if ( n == 1 )
cout << pref << "()" << suff << "\n";

if ( n <= 1 )
return;

printParen( n-1, pref+"(", ")"+suff );
printParen( n-1, pref+"()", suff );
}``````

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

``````#!/usr/bin/env python

# Implement an algorithm to print all possible valid combinations of braces
# when n pairs of parenthesis are given.

def parenthesis(n, left=0, right=0, s=""):
"""

>>> parenthesis(2)
(())
()()

"""
if left > n or right > n or right > left:
return

if left == right and left + right == 2*n:
print s

parenthesis(n, left + 1, right,     s+"(")
parenthesis(n, left,     right + 1, s+")")``````

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

``````public static void brackets(int leftCnt, int  rightCnt, int totalCnt, String out) {
if(leftCnt == totalCnt && rightCnt == totalCnt) {
System.out.println(out);
return;
}

if(leftCnt < totalCnt) {

brackets(leftCnt+1, rightCnt, totalCnt, out + "(");
}

if(rightCnt < leftCnt) {

brackets(leftCnt, rightCnt+1, totalCnt, out + ")");
}
}``````

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

``````static void
all_forms (int level, int left, char *buf, char *ptr)
{
/* start a new nesting */
*ptr = '(';
ptr++;
left--;

if (left) {
// build whatever left as nested
all_forms(level+1, left, buf, ptr);
}
/* close this nesting - over-writing the nested buffer */
*ptr = ')';
ptr++;

/* if any iterations left, do it without nesting */
if (left) {
// build whatever left as un-nested (same level)
all_forms(level, left, buf, ptr);
} else {
// reached the end - close all nesting levels and print it
while (level) {
*ptr = ')';
ptr++;
level--;
}
*ptr = 0;
printf("%s\n",buf);
}
}``````

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

Guys , this looks like finding catalan number problem.
we can use the formula for catalan numbers as
for n=1; Cn =1
for N>1;
Cn = ( n(n+1)/(n+2) ) *Cn-1

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

``````public static void validBraces(String buffer , int open , int close , int len){
if(close>open){
return;
}
if(open >=len){
int k = open-close;
while(--k>=0){
buffer+=")";
}
System.out.println(buffer);
return;
}
validBraces(buffer+")", open, close+1, len);
validBraces(buffer+"(", open+1, close, len);
}``````

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

``````public static String paranComb(int comb)
{
if (comb == 1)
{
return "()";
}
else
{
return paranComb(comb - 1) + "(" + paranComb(comb-1) + ")";
}
}

public static void main(String [] args)
{
System.out.println(paranComb(1));
System.out.println(paranComb(2));
System.out.println(paranComb(3));
System.out.println(paranComb(4));
}``````

The trick to this problem is to realize that increasing there is only 2 ways to add parans.
()
Notice when we go to comb = 2 We prepend a new () and insert a ()
()(())
In otherwords we are prepending and inserting the previous combination.
so for comb = 3 we just add () infront comb2 and surround comb 2 with parans
()(())(()(()))

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0
Sorry please ignore my previous post This one is correct. (I forgot a paran in my return statement :( ) {{{ public static String paranComb(int comb) { if (comb == 1) { return "()"; } else { return "()" + paranComb(comb - 1) + "(" + paranComb(comb-1) + ")"; } } public static void main(String [] args) { System.out.println(paranComb(1)); System.out.println(paranComb(2)); System.out.println(paranComb(3)); System.out.println(paranComb(4)); } } output: () ()()(()) ()()()(())(()()(())) ()()()()(())(()()(()))(()()()(())(()()(())))
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Updated

``````public static String paranComb(int comb)
{
if (comb == 1)
{
return "()";
}
else
{
return "()" + paranComb(comb - 1) + "(" + paranComb(comb-1) + ")";
}
}

public static void main(String [] args)
{
System.out.println(paranComb(1));
System.out.println(paranComb(2));
System.out.println(paranComb(3));
System.out.println(paranComb(4));
}``````

run:
()
()()(())
()()()(())(()()(()))
()()()()(())(()()(()))(()()()(())(()()(())))

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

elegant and fast solution!
but there is an extra { for the base case.

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

Maybe it will work (i did not check), but it is not enough 45-minute interview to prove that it is correct and working solution.

Comment hidden because of low score. Click to expand.

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.

### 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.