CareerCup Interview Question
Software Engineer / DevelopersCountry: United States
C++ approach:
#include <iostream>
using namespace std;
void Brackets(string output, int open, int close, int pairs)
{
if((open==pairs)&&(close==pairs))
{
cout<<output<<endl;
}
else
{
if(open<pairs)
{
Brackets(output + "(", open+1, close, pairs);
}
if(close<open)
{
Brackets(output + ")", open, close+1, pairs);
}
}
}
int main(int argc, const char * argv[])
{
Brackets("",0,0,3);
}
let's take n=3 in the book example you get 4 sequences, but I think there is 5 sequences. ((())), ()(()), ()()(), (()()), (())()
also my solution is much more simple from that in the book
public static ArrayList<String> GetAllNPairsOfParentheses(int n)
{
ArrayList<String> retArray;
if (n==1)
{
retArray=new ArrayList<String>();
retArray.add("()");
return retArray;
}
retArray= GetAllNPairsOfParentheses(n-1);
HashSet<String> hash=new HashSet<String>();
for (String currentPrantheses : retArray)
{
for (int i=0;i<currentPrantheses.length();i++)
{
String currentPranthesesBegin = currentPrantheses.substring(0,i);
String currentPranthesesEnd = currentPrantheses.substring(i);
String newPrantheses= currentPranthesesBegin+"()"+currentPranthesesEnd;
if (!hash.contains(newPrantheses))
{
hash.add(newPrantheses);
}
}
}
retArray=new ArrayList<String>();
for (String currentPrantheses : hash)
{
retArray.add(currentPrantheses);
}
return retArray;
}
#include<iostream>
using namespace std;
void print(char arr[], int n)
{
for(int i = 0; i < n; i++)
cout<<arr[i];
cout<<endl;
}
void PrintBalancedParan(char arr[],int i, int n,int &ref, int n1, int n2, int &count)
{
if(n1 > n/2) return;//To reduce unwanted calls
if(n1 < n2) return; //To reduce unwanted calls
count++;
if(i == n)
{
print(arr,n);
ref++;//To count how many valid arrangements
return;
}
else
{
arr[i] = '(';
PrintBalancedParan(arr,i+1,n,ref,n1+1,n2,count);
arr[i] = ')';
PrintBalancedParan(arr,i+1,n,ref,n1,n2+1,count);
}
}
int main()
{
int ref = 0;
int count = 0;
char arr[6] = {' ', ' ',' ', ' ',' ',' '};
PrintBalancedParan(arr,0,6,ref,0,0,count);
cout<<endl;
cout<<"Function Calls Count"<<count;
cout<<endl;
cout<<"Valid Arrangements = "<<ref;
}
private Set<String> obtainParentheses(int i) {
if (i == 1) {
Set<String> results = new HashSet<String>() { { add("()"); } };
return results;
}
Set<String> previousResults = obtainParentheses(--i);
Set<String> results = new HashSet<String>();
for (Iterator<String> iterator = previousResults.iterator(); iterator.hasNext();) {
String res = iterator.next();
results.add("()" + res);
results.add("(" + res + ")");
results.add(res + "()");
}
return results;
}
public void gen(int sum, String str, int ctr){
if(ctr == sum){
System.out.println(str);
return;
}
for(int i=1;i <= sum-ctr;i++)
//add brackets and recurse to next
gen(sum, str+ getBrackets(i), ctr+i);
}
public String getBrackets(int n){
StringBuffer sb = new StringBuffer();
for(int i=0;i<n;i++)
sb.append('(');
for(int i=0;i<n;i++)
sb.append(')');
return sb.toString();
}
An improved version using cache/memoize technique below
public class SumBrackets {
int sum;
String br[];
public static void main(String[] args) {
new SumBrackets().generate(4);
}
public void generate(int sum){
if(sum <= 0)
return;
this.sum = sum;
br = new String[sum];
br[0]="()";
for(int i=1;i<sum;i++)
br[i] = "("+br[i-1]+")";
gen("",0);
}
public void gen(String str, int ctr){
if(ctr == sum){
System.out.println(str);
return;
}
for(int i=1;i <= sum-ctr;i++)
gen(str+ br[i-1], ctr+i);
}
}
import sys
def all_parens(num):
if num == 0:
return []
if num == 1:
return ['()']
else:
sub_parens = all_parens(num - 1)
return set(['(' + parens + ')' for parens in sub_parens] + \
['()' + parens for parens in sub_parens] + \
[parens + '()' for parens in sub_parens])
if __name__ == '__main__':
pairs = all_parens(int(sys.argv[1]))
print '\n'.join(pairs)
A simple recursive solution:
#include <iostream>
#include <string>
void
parenthesis(int n, int open = 0, int close = 0, const std::string& str = "") {
if (open == n && close == n)
std::cout << str << '\n';
else {
if (open < n)
parenthesis(n, open + 1, close, str + "(");
if (close < open)
parenthesis(n, open, close + 1, str + ")");
}
}
int main() {
parenthesis(3);
}
Note: After I've posted my solution, I've notice that it's the same algorithm as in uuuouou's and NL's. Never mind. (Shame I can't delete this post.)
import java.util.*;
// Each Node instance is a node in a binary tree representing all permutations of N pairs of parens. The permutations
// are generated as follows:
// accumulate the chars (`(' or `)') from root to leaf to build a String for each full tree traversal. (A full tree
// traversal is one whose leaf depth equals maxDepth (i.e., 2N - 1)).
class Node {
Node l, r; // left/right child
char c; // '(' or ')'
Node(char c) {
this.c = c;
}
// Build tree of Nodes recursively.
// depth: 0-based depth of invoking tree node
// numOpen: # of `(' encountered in traversal up to and including this node.
// Note: Traversals that end before maxDepth represent impossible permutations: e.g.,
// N=2: ())
// N=2: (((
void buildTree(int maxDepth, int depth, int numOpen) {
int numClosed = depth + 1 - numOpen;
if (depth >= maxDepth)
return;
// Has this traversal used all open parens?
if (numOpen < (maxDepth + 1) / 2) {
// Recurse left.
l = new Node('(');
l.buildTree(maxDepth, depth + 1, numOpen + 1);
}
// Are there any unclosed open parens in this traversal?
if (numClosed < numOpen) {
// Recurse right.
r = new Node(')');
r.buildTree(maxDepth, depth + 1, numOpen);
}
}
// Performs an in-order DFT on the Node tree, accumulating a path string, which will be output if and only if
// traversal reaches maxDepth.
void outputTree(int maxDepth, int depth, String path) {
path += c; // Accumulate current node's paren.
if (depth == maxDepth) {
// Current traversal complete.
System.out.println(path);
return;
}
if (l != null) l.outputTree(maxDepth, depth + 1, path);
if (r != null) r.outputTree(maxDepth, depth + 1, path);
}
}
public class PermuteParens {
// Usage: java PermuteParens 3
// Output:
/*
((()))
(()())
(())()
()(())
()()()
*/
public static void main(String[] args) {
// Determine # of paren pairs to be permuted.
int N = Integer.parseInt(args[0]);
int maxDepth = 2 * N - 1;
// Construct root node and recurse to build binary tree.
Node root = new Node('(');
// Note: Could simplify client interface by implementing top-level wrappers for both buildTree and outputTree.
// Note: It's not really necessary to build the tree; could just as well generate the output in a single
// traversal of a virtual tree.
root.buildTree(maxDepth, 0, 1);
root.outputTree(maxDepth, 0, "");
}
}
// vim:ts=4:sw=4:et:tw=120
This is a loopless, branchless O(1), 6-lines long algorithm that given a string of properly balanced pair of parentheses (a.k.a. a Dyck word) produces the "next" one.
For more details look my github repo cassioneri / dyck. I can't put the link here! :-(
#include <iostream>
typedef unsigned long long integer;
integer next_dyck_word(integer w) {
integer a = w & -w;
integer b = w + a;
integer c = w ^ b;
c = (c / a >> 2) + 1;
c = c * c - 1;
c = (c & 12297829382473034410u) | b;
return c;
}
void print(integer w, unsigned m) {
integer mask = (integer) 1u << (m - 1);
do
std::cout << (w & mask ? '(' : ')');
while (mask >>= 1);
std::cout << '\n';
}
int main() {
unsigned n = 4;
unsigned two_n = 2 * n;
integer greatest = (1ull << n) * ((1ull << n) - 1);
integer word = 12297829382473034410ull >> (64 - 2 * n);
do {
print(word, two_n);
word = next_dyck_word(word);
} while (word <= greatest);
}
C++ 11
Recursive solution.
vector<string> generateParentCombinations(int n) {
if (n == 1) {
return vector<string>(1,"()");
}
auto prevList = generateParentCombinations(n-1);
vector<string> result;
for(auto comb: prevList) {
result.push_back(comb + "()");
result.push_back("(" + comb + ")");
if(comb + "()" != "()" + comb) {
result.push_back("()" + comb);
}
}
return result;
}
public static void generateParantheses(int numberOfPairs) {
String pre, suf, middle;
for (int i = 0; i < numberOfPairs; i++) {
pre = "";
suf = "";
middle = "";
for (int j = 0; j < i; j++) {
pre += "(";
suf += ")";
}
for (int k = i; k < numberOfPairs; k++) {
middle = "()" + middle;
}
System.out.println(pre + middle + suf);
}
}
The thought is backtrace, following is code in C with easy-to-understand comments:
- uuuouou July 17, 2014