Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
I should note that this implementation produces combinations not listed in Yayagamer's original problem statement (his example for when N == 3 doesn't include "(()())"). My suspicion is that we are in fact supposed to print all possible strings of balanced parentheses that have N matched pairs, but in an actual interview, I'd definitely want to clarify that with the interviewer.
<pre lang="" line="1" title="CodeMonkey97910" class="run-this">#include <stdio.h>
#include <stdlib.h>
/*
synopsis: ./a.out 3
recursively call print_p
a is an array to store results
n is the total number of chars, must be even
rem is the number of parenthesis left
left is how many ('s more than )'s so far
*/
void print_p(char * a, int n, int rem, int left)
{
int i;
if(rem == 0){//one result is available
for(i = 0; i < n; i++)
printf("%c",a[i]);
printf("\n");
return;
}
if(rem > left){
if(left > 0){
a[n - rem] = ')';
print_p(a, n, rem-1, left-1);
}
a[n- rem] = '(';
print_p(a, n, rem-1, left+1);
}
else if(rem == left){
a[n - rem] = ')';
print_p(a, n, rem-1, left-1);
}
else
return;
}
int main(int argc, char *argv[])
{
int n = atoi(argv[1]);
char * a = malloc(2*n);
print_p(a, 2*n, 2*n, 0);
return 0;
}
</pre><pre title="CodeMonkey97910" input="yes">
</pre>
Here is the C# version for the same
public static void printParen(int pos, int open, int close, char[] str, int n)
{
if(close == n)
{
Console.WriteLine(new string(str));
return;
}
else
{
if(open > close)
{
str[pos] = '}';
printParen(pos + 1, open, close + 1, str, n);
}
if(open < n)
{
str[pos] = '{';
printParen(pos + 1, open + 1, close, str, n);
}
}
}
{
1
11 2
111 12 21 3
1111 112 121 13 211 22 31 4
0*: _
1*: ()+0
2*: ()+1* + (())+0*
3*: ()+2* + (())+1* + ((()))->0*
string getBalls(number):
if number == 0 :
return ' '
else :
ret = ''
for (int i=0; i<number; i++) :
return += '('
for (int i=0; i<number; i++) :
return += ')'
print(string prefix, int number) :
if number == 0 :
print ' '
else if number == 1 :
print '()'
else :
for (int i = 1; first < number; first++) :
print(getBalls(i),number-i)
This can be viewed as following numeric sequences:
1 : 1
2 : 11 2
3 : 111 12 21 3
4 : 1111 112 121 13 211 22 31 4
where 1 is (), 2 is (()), 3 is ((())) etc.
now, you can see that there is a recursion. Assume that 0 is '' and 1 is 1. Then (e.g.) 2 is 1 appended in front of all results for (2-1=) 1 and 2 appended in front of all results for (2-2=)0. So for any general number x you take every y value in range [1,x] and append it in front of the answer for (x-y).
The running time with recursion is O(n^2), no extra space. It is possible to use dynamic programming and do this in O(n) by building the answer bottom-up and saving the previous results.
using System;
using System.Collections.Generic;
using System.Text;
namespace CSharp
{
public class Class1
{
public static void Main(string[] args)
{
StringBuilder b = new StringBuilder();
print(0,0,3,b);
}
static void print (int o, int c, int l, StringBuilder b)
{
if(o==l)
{
if(c>0)
{
b.Append(")");
print(o,c-1,l,b);
b.Remove(b.Length-1,1);
}
else
System.Console.WriteLine(b.ToString());
}
else
{
b.Append("(");
print(o+1,c+1,l,b);
b.Remove(b.Length-1,1);
if(c>0)
{
b.Append(")");
print(o,c-1,l,b);
b.Remove(b.Length-1,1);
}
}
}
}
}
A basic recursive function: Gool is to reach desired lenght for open paranthesis number and zero our closed paranthesis. As you add open paranthesis both increment open and close paranthesis number and call again, next step if you have any close paranthesis call recursive again this time decrementing close paranthesis number.
private static void FindCombinations(int num,ref Queue<string> queue)
{
int size,iterator;
string str;
if (num == 1)
{
queue.Enqueue("()");
}
else
{
FindCombinations(num - 1,ref queue);
Queue<string> tempQueue = new Queue<string>();
size = iterator = queue.Count;
while (iterator > 0)
{
str = queue.Dequeue();
tempQueue.Enqueue("()" + str);
queue.Enqueue(str);
iterator--;
}
iterator = size;
while (iterator > 0)
{
str = queue.Dequeue();
tempQueue.Enqueue("(" + str + ")");
queue.Enqueue(str);
iterator--;
}
queue = tempQueue;
}
return;
}
This queue will contain all the combinations of the desired result
Correct me if i'm Wrong..
parens(n):
if(n==1):
return ['()']
else:
prev=parens(n-1)
ans=[]
for i in prev:
ans.append( "(" + i + ")" )
ans.append( "(" + ")" + i )
ans.append( i + "(" + ")" )
return ans.
This method will include (()()) as an answer for N==3 which i suppose i correct. Question just mentions valid combinations of ( and ) and this is a valid combination.
A simple code :
public void printBracket(int n)
{
int x = 0;
int[] arr = new int[n];
x = ((n - 1) * n) / 2 + 1;
for (int i = 0; i < n; i++)
{
arr[i] = 1;
}
for (int j = 0; j < x; j++)
{
for (int k = 0; k < n; k++)
{
for (int i = 0; i < arr[k]; i++)
{
Console.Write("(");
}
for (int i = 0; i < arr[k]; i++)
{
Console.Write(")");
}
}
Console.Write("\n");
bool check = false;
if (arr.Length > 1)
{
for (int i = 0; i < n; i++)
{
if (arr[i] > 1)
{
if (i == n - 1)
{
n = n - 1;
int a = arr[i];
arr = new int[n];
arr[0] = a + 1;
for (int p = 1; p < arr.Length; p++)
{
arr[p] = 1;
}
}
else
{
arr[i + 1] = arr[i];
arr[i] = 1;
}
check = true;
break;
}
}
if (check == false)
{
n = n - 1;
arr = new int[n];
arr[0] = 2;
for (int p = 1; p < arr.Length; p++)
{
arr[p] = 1;
}
}
}
}
}
a simple solution:
void printBracket(int n){
if (n <= 0) return;
unsigned int max = 1<<(n-1);
int numOpenBrackets = 0;
for (unsigned int i = 0; i < max; i++) {
printf("(");
numOpenBrackets++;
for (int j = 0; j < n-1; j++) {
if (i & 1<<j) {
printf("(");
numOpenBrackets++;
}
else{
while (numOpenBrackets--) printf(")");
numOpenBrackets = 0;
printf("(");
numOpenBrackets++;
}
}
while (numOpenBrackets--) printf(")");
numOpenBrackets = 0;
if(i != max-1) printf(", ");
}
printf("\n");
}
a simple solution:
void printBracket(int n){
if (n <= 0) return;
unsigned int max = 1<<(n-1);
int numOpenBrackets = 0;
for (unsigned int i = 0; i < max; i++) {
printf("(");
numOpenBrackets++;
for (int j = 0; j < n-1; j++) {
if (i & 1<<j) {
printf("(");
numOpenBrackets++;
}
else{
while (numOpenBrackets--) printf(")");
numOpenBrackets = 0;
printf("(");
numOpenBrackets++;
}
}
while (numOpenBrackets--) printf(")");
numOpenBrackets = 0;
if(i != max-1) printf(", ");
}
printf("\n");
}
STATE = {#left_lp, #left_rp, str}
INITIAL_STATE = {N,N, ‘’}
SUCCESSOR_STATES =
{#left_lp - 1, #left_rp, str + ‘(’}
{#left_lp, #left_rp - 1, str + ‘)’}
constraints :
#left_rp >= #left_lp
#left_lp >= 0 && #left_rp >= 0
GOAL_STATE = {#lp == 0 && #rp == 0}
public class test {
public static void pp(int size) {
pp(size, size, "");
}
private static void pp(int left_lp, int left_rp, String s) {
if (left_lp == 0 && left_rp == 0) {
System.out.println(s);
}
if ((left_rp >= left_lp - 1) && (left_lp - 1 >= 0)) {
pp(left_lp - 1, left_rp, s + "(");
}
if ((left_rp - 1 >= left_lp ) && (left_rp - 1 >= 0)) {
pp(left_lp, left_rp - 1, s + ")");
}
}
public static void main(String[] args){
pp(3);
}
}
N is the number of pairs
N=1 build tab= +1,-1
N=2 build tab= +1, -1, +1, -1
N=3 build tab= +1, -1, +1, -1, +1, -1
etc
Step 1: get all the permutations of tab into a tabindexes.
Step 2: for each entry in tabindexes, check if the entry is valid.
The entry is valid if a linear addition never goes negative, then print.
There are 2 functions to write: get_all_permute_indexes()
and check_with_linear_addition.
Do you agree with my strategy?
I started out by thinking that we could generate strings a single character at a time. If we have an unmatched opening parenthesis, we could choose to append an ')' to our string, but if the number of opening parentheses is fewer than the number of matched pairs we need to make, we could also output a '('. Not sure that it's the best solution, but I think it works. Here's my Python implementation:
def balanced_parens(n): return helper(0, n) def helper(unmatched, to_match): if to_match == 0: return [""] res = [] if unmatched < to_match: tails = helper(unmatched + 1, to_match) res.extend("(" + tail for tail in tails) if unmatched > 0: tails = helper(unmatched - 1, to_match - 1) res.extend(")" + tail for tail in tails) return res if __name__ == "__main__": for i in range(5): print(balanced_parens(i))And the output for n = 0..3 is:
- beangonz November 17, 2011['']
['()']
['(())', '()()']
['((()))', '(()())', '(())()', '()(())', '()()()']