Microsoft Interview Question
Software Engineer / Developersif i call the function with generate( "", 0,0, 2 ), the output contains only {{}}. Am I missing something?
U can look into the catalan number approach. learn to generate catalan numbers through C.
Catalan gives the number of patterns of balanced parentheses. But how can you generate the pattern itself with the catalan number. Please explain.
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <assert.h>
#include <algorithm>
using namespace std;
//Q:
//Write a function to generate all possible n pairs of balanced parentheses. For example, if n=1
//{}
//for n=2
//{}{}
//{{}}
void pairs(int);
void pairs(int, int, int, string); //aux function for recursive
int main(int argc, char* argv[])
{
int n = 0;
while(n<=0)
cin>>n;
pairs(n);
return 0;
}
void pairs(int n)
{
pairs(n, n, 0, "");
}
void pairs(int left, int right, int diff, string s)
{
if(left == 0 && right == 0)
{
cout<<s<<endl;
return;
}
if(diff == 0)
{
pairs(left-1, right, diff+1, s+'{');
return;
}
else
{
if(left>0)
pairs(left-1, right, diff+1, s+'{');
pairs(left, right-1, diff-1, s+'}');
}
}
Same idea with JD but refine in comparision
void createParentheses(int pos, int length, int open, int close){
if (close == length){
cout << str << endl;
return;
}
else{
if (open > close){
str[pos] = '}';
createParentheses(pos+1,length,open,close+1);
}
if (open < length){
str[pos] = '{';
createParentheses(pos+1,length,open+1,close);
}
}
}
Please note that open always >= close
Here's some C# code, based on JD, but simplified. (I believe some cases were unnecessary).
// Call with generate ( "", 0, 0, n );
static void generate ( string p, int o, int c, int n ) {
if ( o==n && c==n ) {
Console.Write ( p ) ;
return;
}
if ( o < n ) {
generate ( p + '{', o+1, c, n ) ;
}
if ( c < o ) {
generate ( p + '}', o, c+1, n ) ;
}
Console.WriteLine ( ) ;
}
Here's some C# code, based on JD, but simplified. (I believe some cases were unnecessary).
// Call with generate ( "", 0, 0, n );
static void generate ( string p, int o, int c, int n ) {
if ( o==n && c==n ) {
Console.Write ( p ) ;
return;
}
if ( o < n ) {
generate ( p + '{', o+1, c, n ) ;
}
if ( c < o ) {
generate ( p + '}', o, c+1, n ) ;
}
Console.WriteLine ( ) ;
}
static void Main(string[] args)
{
int n = 5;
breaknext("", n);
Console.ReadLine();
}
static void breaknext(string pre, int n)
{
for (int head = 1; head <= n; head++) {
int next = n - head;
if (next > 1) {
breaknext(pre + deep(head), next);
} else if (next == 0) {
Console.WriteLine(pre + deep(head));
} else if (next == 1) {
Console.WriteLine(pre + deep(head) + deep(next));
}
}
}
static string deep(int deep)
{
string result = "";
for (int i = 0; i < deep; i++) {
result = "{" + result + "}";
}
return result;
}
Here is my code in C#:
private void GenerateBrackets(int openCount, int closeCount, string str, HashSet<string> bracketList)
{
if ((openCount == 0) && (closeCount == 0))
{
bracketList.Add(str);
}
if ((openCount <= closeCount) && (openCount > 0))
{
GenerateBrackets(openCount - 1, closeCount, str + "(", bracketList);
}
if (closeCount > 0)
{
GenerateBrackets(openCount, closeCount - 1, str + ")", bracketList);
}
}
/// <summary>
/// Given number of brackets, find all permutations of open / close sets
/// e.g. n = 4, ()()()(), (())(()), ((()))(), (((())))),....
/// </summary>
[TestMethod]
public void BracketCombinations()
{
int n = 4;
HashSet<string> bracketList = new HashSet<string>();
GenerateBrackets(n, n, string.Empty, bracketList);
}
pseudoCode :
- JD January 25, 2010void generate(string p,int o,int c ,int n)
{
if( o==n && c==n )
{
PRINT(p);
return ;
}
if(c>o)return;
if( o >=c && o<n )
generate(p+'{' ,o+1,c,n );
if( c<o )
generate( p+ '}' ,o,c+1,n );
}