Ebay Interview Question
Java DevelopersCountry: United States
Interview Type: In-Person
public static List<String> getCombinations(int n) {
List<String> result = new ArrayList<String>();
getCombinations(n, 0, "", result);
return result;
}
public static void getCombinations(int available, int currentlyOpen, String prefix, List<String> acc) {
// First possibility: add opening parenthesis (only if parentheses are still available)
if (available > 0) {
getCombinations(available-1, currentlyOpen+1, prefix + "(", acc);
}
// Second possibility: add closing parenthesis (only if at least one is open)
if (currentlyOpen > 0) {
getCombinations(available, currentlyOpen-1, prefix + ")", acc);
}
// If no parentheses are left and all of them are closed, we're done
if (available == 0 && currentlyOpen == 0) {
acc.add(prefix);
}
}
public String parenthe(int n){
List<String>pr= new ArrayList<String>();
if(n==1){
return pr.add("()");
}
for(String s:parenthe(n-1)){
pr.add(s+"()");
pr.add("("+s+")");
if(s+"()"!="()"+s)
pr.add("()"+s);
}
public class Quiz {
String left = "(";
String right = ")";
static String output="";
public static void main(String[] args) {
Quiz quiz = new Quiz();
int number = 4;
quiz.parensSeperate(number);
if (number > 1){
output += ",";
quiz.parensConsis(number);
if(number > 2){
quiz.parensDiff(number, 1);
}
}
System.out.println(output);
}
private void parensDiff(int number, int i) {
if(number == (i+1)){
return;
}
output += ",";
parensConsis(number-i) ;
parensSeperate(i);
output += ",";
parensSeperate(i);
parensConsis(number-i) ;
parensDiff(number,i+1);
}
private void parensConsis(int i) {
for(int x=0;x<i;x++){
output += left;
}
for(int x=0;x<i;x++){
output += right;
}
}
private void parensSeperate(Integer i) {
if(i == null || i==0){
return;
}
output += left+right;
parensSeperate(i-1);
}
}
public class Quiz {
String left = "(";
String right = ")";
static String output="";
public static void main(String[] args) {
Quiz quiz = new Quiz();
int number = 4;
quiz.parensSeperate(number);
if (number > 1){
output += ",";
quiz.parensConsis(number);
if(number > 2){
quiz.parensDiff(number, 1);
}
}
System.out.println(output);
}
private void parensDiff(int number, int i) {
if(number == (i+1)){
return;
}
output += ",";
parensConsis(number-i) ;
parensSeperate(i);
output += ",";
parensSeperate(i);
parensConsis(number-i) ;
parensDiff(number,i+1);
}
private void parensConsis(int i) {
for(int x=0;x<i;x++){
output += left;
}
for(int x=0;x<i;x++){
output += right;
}
}
private void parensSeperate(Integer i) {
if(i == null || i==0){
return;
}
output += left+right;
parensSeperate(i-1);
}
}
String left = "(";
String right = ")";
static String output="";
public static void main(String[] args) {
Quiz quiz = new Quiz();
int number = 4;
quiz.parensSeperate(number);
if (number > 1){
output += ",";
quiz.parensConsis(number);
if(number > 2){
quiz.parensDiff(number, 1);
}
}
System.out.println(output);
}
private void parensDiff(int number, int i) {
if(number == (i+1)){
return;
}
output += ",";
parensConsis(number-i) ;
parensSeperate(i);
output += ",";
parensSeperate(i);
parensConsis(number-i) ;
parensDiff(number,i+1);
}
private void parensConsis(int i) {
for(int x=0;x<i;x++){
output += left;
}
for(int x=0;x<i;x++){
output += right;
}
}
private void parensSeperate(Integer i) {
if(i == null || i==0){
return;
}
output += left+right;
parensSeperate(i-1);
}
//Scala code
import scala.collection.mutable._
object BracketCombinations{
def bracketCombinations(n: Int) = {
def bracketCombinationsInternal(currN: Int,
balanceStack: Stack[Char] = new Stack[Char],
curr: String = "",
acc: List[String] = Nil): List[String] =
currN match {
case 0 if balanceStack.isEmpty => acc:+curr
case 0 if balanceStack.nonEmpty=>
balanceStack.pop
bracketCombinationsInternal(currN, balanceStack, curr+")", acc)
case _ if balanceStack.isEmpty=>
balanceStack.push('(')
bracketCombinationsInternal(currN-1, balanceStack, curr+"(", acc)
case _ if balanceStack.nonEmpty=>
val newStack = new Stack[Char]
balanceStack.foreach(newStack.push(_))
newStack.push('(')
balanceStack.pop
bracketCombinationsInternal(currN-1, newStack, curr+"(", acc) ++
bracketCombinationsInternal(currN, balanceStack, curr+")", acc)
}
bracketCombinationsInternal(n)
}
}
void printBrackets(int n, int n_l, int n_r, string list){
if(n_l == n_r) {
if(n_l != n){
// only left bracket can be printed
list[n_l+n_r] = '(';
return printBrackets(n,n_l+1, n_r, list);
} else {
// print it
cout << list << endl;
return;
}
}
// if possible add '('
if(n_l < n){
list[n_l+n_r] = '(';
printBrackets(n,n_l+1, n_r, list);
}
list[n_l+n_r] = ')';
return printBrackets(n,n_l, n_r +1, list);
}
int main()
{
int numbers;
cin >> numbers;
string list(2*numbers,' ');
printBrackets(number,0,0,list);
return 0;
}
void printBrackets(int n, int n_l, int n_r, string list){
if(n_l == n_r) {
if(n_l != n){
// only left bracket can be printed
list[n_l+n_r] = '(';
return printBrackets(n,n_l+1, n_r, list);
} else {
// print it
cout << list << endl;
return;
}
}
// if possible add '('
if(n_l < n){
list[n_l+n_r] = '(';
printBrackets(n,n_l+1, n_r, list);
}
list[n_l+n_r] = ')';
return printBrackets(n,n_l, n_r +1, list);
}
int main(int argc, char **argv)
{
int number;
cin >> number;
string list(2*number, ' ');
printBrackets(number,0,0,list);
return 0;
}
Why is ((())) not valid?
- Amit October 13, 2015