CareerCup Interview Question for Software Engineer / Developers


Country: United States




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

The thought is backtrace, following is code in C with easy-to-understand comments:

#include <stdio.h>
#define MAX_PAIR  20

void printAllPairs(char s[], int left, int right, int pair)
{
//check if all '(' and ')' have been used up
    if(left == pair && right == pair){
        s[left + right] = '\0';
        puts(s);
        return;
    }
//try to let current position be '('    
    if(left < pair){
        s[left + right] = '(';
        printAllPairs(s, left + 1, right, pair);
    }
//try to let current position be ')' 
    if(left > right){
        s[left + right] = ')';
        printAllPairs(s, left, right + 1, pair);
    }
}

int main()
{
    char s[MAX_PAIR * 2 + 1];
    int  pair = 10;
    
    printAllPairs(s, 0, 0, pair);
    return 0;
}

- uuuouou July 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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);
}

- NL July 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;


    }

- mosh111 July 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- Satveer Singh July 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use the forum to discuss CTCI questions.

- Anonymous July 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

- jls July 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
	}

- Phoenix July 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);	
	}
}

- Phoenix July 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algo
1)find first element ')(' from the right side of the string
2)substitute it by '()'
3) count the balance from left to current position
4)add so many close parenthesis as you need to keep the balance
5)Fill the rest with ()

- glebstepanov1992 July 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Dan July 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

print the Catalan number series

- Anonymous July 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Unless I'm missing something, this will just tell you how many combinations there are but it won't generate them.

- cassio.neri July 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- cassio.neri July 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Brett Pershing Stahlman July 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- cassio.neri July 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice solution

- Anonymous September 04, 2020 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Mhret November 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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);
		}
	}

- Anonymous July 18, 2014 | Flag Reply


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