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

- S O U N D W A V E October 07, 2013 | Flag Reply
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+")");
}

- Akhilesh Pandey October 07, 2013 | Flag Reply
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)
		find(n, left+1, right, s.add(true));
	if(right < left)
		find(n, left, right+1, s.add(false));
}

- Darida October 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Darida
Nice....Thumbs Up

- Akhilesh Pandey October 26, 2013 | Flag
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[1] = ["()"]
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

- mingjun October 07, 2013 | Flag Reply
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 );
}

- md October 08, 2013 | Flag Reply
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+")")

- anon October 12, 2013 | Flag Reply
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 + ")");
	    }
	}

- Anand October 19, 2013 | Flag Reply
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);
    }
}

- shin November 24, 2013 | Flag Reply
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

- VP December 28, 2013 | Flag Reply
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);
	}

- Anonymous December 20, 2014 | Flag Reply
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.
Start with comb = 1
()
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
()(())(()(()))

- houseUrMusic October 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- houseUrMusic October 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes
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: () ()()(()) ()()()(())(()()(())) ()()()()(())(()()(()))(()()()(())(()()(()))) - houseUrMusic October 17, 2013 | Flag
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:
()
()()(())
()()()(())(()()(()))
()()()()(())(()()(()))(()()()(())(()()(())))

- houseUrMusic October 17, 2013 | Flag Reply
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.

- mingjun October 08, 2013 | Flag
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
of 0 votes

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.

- Darida October 21, 2013 | Flag
Comment hidden because of low score. Click to expand.


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