Amazon Interview Question
Software Engineer / DevelopersTeam: Development
Country: India
Interview Type: In-Person
great idea,but does not seem to take care that closed braces printed shud be always less than or equal to opening ones while scanning from left to right
This one uses a lot of memory but it's easy to see the core logic.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
public class ParenthesisCombination {
static final String LP = "{";
static final String RP = "}";
public static void main(String[] args) {
int n = 10;
printCombinations(n);
}
static void printCombinations(int n){
List<String>list=getCombinations(n);
int i=1;
for(String s:list)
System.out.println(i+++"\t"+s);
}
static List<String> getCombinations(int n){
HashMap<Integer,List<String>>map=new HashMap<Integer, List<String>>();
for(int i=1;i<=n;i++){
List<String>newlist=new ArrayList<String>();
if(i==1){
newlist.add(LP+RP);
}
else{
List<String>list=map.get(i-1);
for(String s:list){
newlist.add(LP+RP+s);
newlist.add(LP+s+RP);
}
}
map.put(i,newlist);
map.remove(i-1);
}
return map.get(n);
}
}
This doesn't have the memory overhead.
public class ParenthesisCombination {
static final char LP = '{';
static final char RP = '}';
static final char NULL='\u0000';
public static void main(String[] args) {
int n = 3;
char[]c=new char[n*2];
printCombinations(n,c,0,c.length-1,0);
}
static void printCombinations(int n,char[]c,int start, int end, int count){
if(start>=end)
return;
count+=2;
c[start]=LP;
c[start+1]=RP;
printCombinations(n-1,c,start+2,end,count);
if(count==c.length)
print(c);
if(n==1) //when n=1 there is only one side
return;
c[start]=LP;
c[end]=RP;
printCombinations(n-1,c,start+1,end-1,count);
if(count==c.length)
print(c);
}
static void blankOut(char[]c,int start,int end){
for(int i=start;i<=end;i++)
c[i]=NULL;
}
static void print(char[]c){
for(int i=0;i<c.length;i++)
System.out.print(c[i]);
System.out.println();
}
}
char* result = new char[2*n];
result[0] = '{';
result[2*n-1] = '}';
for( i = 1; i <= 2*n; i++ )
if( i <= n )
a[i-1] = '{';
else
a[i-1] = '}';
print(result);
while( 1 )
{
if( a[2*n-2] == '{' && a[1] == '{' }
break;
validator = 0;
countopen = 0;
countclose = 0;
i = 2*n-2;
do
{
if( a[i] == '{'
validator++;
countopen++;
else
validator--;
countclose++;
i--;
}while( a[i] != '{' );
countopen = n - countopen;
countclose = n - countclose;
validator = -validator;
a[i++] = '}';
validator -= 2;
countopen--;
countclose++;
while( i != 2n-2 )
{
if( validator+1 <= n && countopen+1 <= n )
validator++;
countopen++;
a[i++] = '{';
else
validator--;
countopen--;
a[i++] = '}';
}
print(result);
}
#include<iostream>
using namespace std;
void f(char* arr,int left,int right,int top)
{
if(left<=right && left>0)
{
arr[top]='(';arr[top+1]='\0';
f(arr,left-1,right,top+1);
}
if(left<right && right>0)
{
arr[top]=')';arr[top+1]='\0';
f(arr,left,right-1,top+1);
}
if(left==0 && right==0)
cout<<arr<<endl;
}
int main()
{
int n;
char arr[1000];
cin>>n;
f(arr,n,n,0);
}
#include<iostream>
using namespace std;
void f(char* arr,int left,int right,int top)
{
if(left<=right && left>0)
{
arr[top]='(';arr[top+1]='\0';
f(arr,left-1,right,top+1);
}
if(left<right && right>0)
{
arr[top]=')';arr[top+1]='\0';
f(arr,left,right-1,top+1);
}
if(left==0 && right==0)
cout<<arr<<endl;
}
int main()
{
int n;
char arr[1000];
cin>>n;
f(arr,n,n,0);
}
void mainfunc(int n)
{
char* s = new char[n*2 + 1];
s[n*2] = '\0';
f(n, n, s, 0, 0);
}
void f(int cLeft, int cRight, char* s, int idxS, int leftToMatch)
{
if(cRight == 0)
{
printf("%s\n", s);
return;
}
if(cleft != 0)
{
s[idxS+1]='(';
f(cLeft-1, cRight, s, idxS+1, leftToMatch+1);
}
if(leftToMatch!=0)
{
s[idxS+1] = ')';
f(cLeft, cRight-1,s,idxS+1,leftToMatch-1);
}
}
We should draw a tree to analyze the cases. Suppose we want to enumerate 3 pairs.
(
(( ()
((( (() ()(
((() (()( (()) ()(( ()()
((()) (()() (())( ()(() ()()(
((())) (()()) (())() ()(()) ()()()
Let left and right denote the number of left and right parenthesis needed. The base case is shown on the leaf level, when right == 0; otherwise we need call parenthesis_match recursively on the following cases:
1. if (left == right) {
add "("
parenthesis_match(left - 1, right);
} else if (left < right && left != 0) {
add "("
parenthesis_match(left - 1, right);
remove "("
add ")"
parenthesis_match(left, right - 1);
} else if (left == 0) {
add ")"
parenthesis_match(left, right - 1);
}
PrintBrackets(int count)
{
int i = count;
while(i>0)
{
Print('{;, i);
Print('};, i);
PrintBrackets(count - i);
}
}
Print(char bracket, int count)
{
for(i=0; i<count; i++)
{
cout<<bracket;
}
}
Forgot to enter; i--;
So the code is.
PrintBrackets(int count)
{
int i = count;
while(i>0)
{
Print('{;, i);
Print('};, i);
PrintBrackets(count - i);
i--;
}
}
Print(char bracket, int count)
{
for(i=0; i<count; i++)
{
cout<<bracket;
}
}
Approach:
n=1 { }
n = 2 { } { } and {{ }}
for any n ... just need to put bracket in start and end of previous n result and one {} in start of all
like n = 3
{ {} {} },
and {} {} {}, {}{{}}
i will share the code for it ASAP
anurag, you missed one {{}}{} , I don't know whether it is same as your last combination.
- loveCoding February 28, 2012