Amazon Interview Question SDE1s
Country: India
Interview Type: In-Person
void p2(int open1,int open2,int open3,int close1,int close2,int close3,int n,char *s){
if(open1==0 && close1==0 && open2==0 && close2==0 && open3==0 && close3==0){
printf("%s\n",s);
return;
}
if(open1==close1 && open2==close2 && open3==close3){
if(open1>0){
s[n]='{';
p2(open1-1,open2,open3,close1,close2,close3,n+1,s);}
}
if((open1<close1 ||(open1==0 && close1==0))&& open2==close2 && open3==close3){
if(open1>0){
s[n]='{';
p2(open1-1,open2,open3,close1,close2,close3,n+1,s);}
if(open2>0){
s[n]='[';
p2(open1,open2-1,open3,close1,close2,close3,n+1,s);}
if(close1>1){
s[n]='}';
p2(open1,open2,open3,close1-1,close2,close3,n+1,s);}
}
if((open2<close2 || (open2==0 && close2==0)) && open3==close3){
if(open2>0){
s[n]='[';
p2(open1,open2-1,open3,close1,close2,close3,n+1,s);}
if(open3>0){
s[n]='(';
p2(open1,open2,open3-1,close1,close2,close3,n+1,s);}
if(close2>1){
s[n]=']';
p2(open1,open2,open3,close1,close2-1,close3,n+1,s);}
}
if(open3<close3){
if(open3>0){
s[n]='(';
p2(open1,open2,open3-1,close1,close2,close3,n+1,s);}
if(close3>0){
s[n]=')';
p2(open1,open2,open3,close1,close2,close3-1,n+1,s);}
}
if(close2==1 && open3==0 && close3==0){
s[n]=']';
p2(open1,open2,open3,close1,close2-1,close3,n+1,s);
}
if(close1==1 && open2==0 && close2==0 && open3==0 && close3==0){
s[n]='}';
p2(open1,open2,open3,close1-1,close2,close3,n+1,s);
}
}
int main(){
char *st=malloc(20);
p2(1,4,1,1,4,1,0,st);
}
Below recursive solution in C# should work. Let me know if I am missing something.
public static void Test()
{
HashSet<string> combinations = new HashSet<string>();
Paranthesize(2, 2, 2, "", combinations);
foreach (string s in combinations)
{
Console.WriteLine(s);
}
}
private static void Paranthesize(int n1, int n2, int n3,
string part, HashSet<string> combinations)
{
if (n1 <= 0 && n2 <= 0 && n3 <= 0)
{
if (!combinations.Contains(part))
{
combinations.Add(part);
}
return;
}
if (n1 > 0)
{
Paranthesize(n1 - 1, n2, n3, "{}" + part, combinations);
Paranthesize(n1 - 1, n2, n3, part + "{}", combinations);
Paranthesize(n1 - 1, n2, n3, "{" + part + "}", combinations);
}
if (n2 > 0)
{
Paranthesize(n1, n2 - 1, n3, "[]" + part, combinations);
Paranthesize(n1, n2 - 1, n3, part + "[]", combinations);
Paranthesize(n1, n2 - 1, n3, "[" + part + "]", combinations);
}
if (n3 > 0)
{
Paranthesize(n1, n2, n3 - 1, "()" + part, combinations);
Paranthesize(n1, n2, n3 - 1, part + "()", combinations);
Paranthesize(n1, n2, n3 - 1, "(" + part + ")", combinations);
}
}
public static Map<Integer,String[]> map = new HashMap<Integer,String[]>();
static{
String[] arr1 = {"()"};
map.put(1, arr1);
String[] arr2 = {"(())","()()"};
map.put(2, arr2);
}
public String buildForN(int n){
StringBuilder sb = new StringBuilder(2*n);
for(int i =1; i<=n; i++)
sb.append('(');
for(int i =1; i<=n; i++)
sb.append(')');
return sb.toString();
}
public void buildBrackets(int num){// bottom up DP
for(int i =3; i<=num; i++){
Set<String> set = new HashSet<String>();
String nZero = buildForN(i);
set.add(nZero);
for(int j=1; j<=i/2; j++){
String[] arr1 = map.get(j);
String[] arr2 = map.get(i-j);
for (String left : arr1) {
for (String right : arr2) {
set.add(left+right);
set.add(right+left);
}
}
}
String[] arrn= set.toArray(new String[0]);
map.put(i, arrn);
}
}
public static void main(String[] args) {
Test test = new Test();
test.buildBrackets(10);
String[] arr = map.get(10);
for (String string : arr) {
System.out.println(string);
}
}
import java.util.HashSet;
import java.util.Set;
// Some interviewers are cruel.
public class Brackets {
public static void main(String[] args) {
Brackets bc = new Brackets();
Set<String> seta =bc.buildForN(1);// for n1 numbers () change here
Set<String> setb =new HashSet<String>();
Set<String> setc =new HashSet<String>();
for (String string : seta) {
//System.out.println(string);
for(int j=1; j<2; j++){ // for n2 numbers {} change here
setb.addAll(bc.spanTrees(string, "{}"));
}
}
for (String string : setb) {
//System.out.println(string);
for(int j=1; j<2; j++){// for n3 numbers [] change here
setc.addAll(bc.spanTrees(string, "[]"));
}
}
for (String string : setc) {
System.out.println(string);
}
}
public Set<String> buildForN(int n){
if(n <= 1){ return spanTrees("");}
else{
Set<String> fset = new HashSet<String>();
Set<String> set = buildForN(n-1);
for (String conf : set) {
fset.addAll(spanTrees(conf));
}
return fset;
}
}
public Set<String> spanTrees(String root){
Set<String> set = new HashSet<String>();
//span left
String left = "()"+root;
set.add(left);
String right = root+"()";
set.add(right);
for(int i=1; i<=root.length()-1; i++){
set.add(root.substring(0, i)+"()"+root.substring(i, root.length()));
}
return set;
}
public Set<String> spanTrees(String root, String regex){
Set<String> set = new HashSet<String>();
//span left
String left = regex+root;
set.add(left);
//span left
String right = root+regex;
set.add(right);
//span middle
String mid = regex.substring(0,1)+ root+regex.substring(1,2);
set.add(mid);
for(int i=1; i<=root.length()-1; i++){
set.add(root.substring(0, i)+regex+root.substring(i, root.length()));
}
return set;
}
}
Logic: the right parentheses can appear in an output string only when there are
already more left parentheses present in the output string. Extending the solution from Gayle's solved problems
c++ code for the problem ... explanation is mostly inline and a brief summary at the end
/*
Since
n1 pairs of “{} ” brackets
n2 pairs of “[] ” brackets
n3 pairs of “() ” brackets
let
l1= r1 =(n1)/2
l2= r2 =(n2)/2
l3= r3 =(n3)/2
*/
/*call from driver function */
char str[13];
str[12]=’\0’;
printAllCombinations(2,2,2,2,2,2,str,0);
//count is the index where we have to put the character currently
void printAllCombinations(int l1, int r1, int l2, int r2, int l3, int r3, char *str, int count) {
if (l1 < 0 || r1 < l1 || l2 < 0 || r2 < l2 || l3 < 0 || r3 < l1 ) return; // invalid state
if (l == 0 && r == 0) {
printf(“%s\n”, str); // found one combination, so print it
return;
}
if (l1 > 0) { // try a left curly brace, if there are some available
str[count] = ‘{‘;
printAllCombinations(l1 - 1, r1, l2, r2, l3, r3, str, count + 1);
}
if (l2 > 0) { // try a left bracket, if there are some available
str[count] = ‘[‘;
printAllCombinations(l1, r1, l2-1, r2, l3, r3, str, count + 1);
}
if (l3 > 0) { // try a left paren, if there are some available
str[count] = ‘(‘;
printAllCombinations(l1, r1, l2, r2, l3-1, r3, str, count + 1);
}
//Now put the matching braces at all possible combinations
if (r1 > l1) { // try a right curly brace, if there’s a matching left
str[count] = ‘)’;
printAllCombinations(l1, r1-1, l2, r2, l3-1, r3, str, count + 1);
}
if (r2 > l2) { // try a right bracket, if there’s a matching left
str[count] = ‘)’;
printAllCombinations(l1, r1, l2, r2-1, l3, r3, str, count + 1);
}
if (r3 > l3) { // try a right parenthesis, if there’s a matching left
str[count] = ‘)’;
printAllCombinations(l1, r1, l2, r2, l3, r3-1, str, count + 1);
}
}
}
Basically at any current index of the result we have 3 options
1. Fill current index using any of the 3 types of left brackets (this can be done only when the left count of that type >0 )
2. Fill current index using any of the 3 type of right bracket (this can be done only when the left count of that type >right count of that type)
3. print the result if all type of brackets has been consumed
Use Stack data structure.
push all opening braces. when you get a braces ending pop and compare pair. A match means its a valid combination.
no matching pair means invalid pair.
non empty stack means Invalid pair.
public static void printMultipleBrackets(int openParen, int closeParen, int openBracket, int closeBracket, int openCBracket, int closeCBracket, char[] str, int count) {
- Adnan Ahmad August 03, 2013if (openParen < 0 || closeParen < openParen) {
return; // invalid state
}
if (openParen == 0 && closeParen == 0 && openBracket == 0 && closeBracket == 0 && openCBracket == 0 && closeCBracket == 0) {
System.out.println(str); // found one, so print it
}
else {
if (openParen > 0) { // try a left parenthesis, if there are some available
str[count] = '(';
printMultipleBrackets(openParen - 1, closeParen, openBracket, closeBracket, openCBracket, closeCBracket, str, count + 1);
}
if (openBracket > 0) { // try a left bracket, if there are some available
str[count] = '[';
printMultipleBrackets(openParen, closeParen, openBracket - 1, closeBracket, openCBracket, closeCBracket, str, count + 1);
}
if (openCBracket > 0) { // try a left curly bracket, if there are some available
str[count] = '{';
printMultipleBrackets(openParen, closeParen, openBracket, closeBracket, openCBracket - 1, closeCBracket, str, count + 1);
}
if (closeCBracket > openCBracket) { // try a right curly bracket, if there’s a matching left
str[count] = '}';
printMultipleBrackets(openParen, closeParen, openBracket, closeBracket, openCBracket, closeCBracket - 1, str, count + 1);
}
if (closeBracket > openBracket) { // try a right bracket, if there’s a matching left
str[count] = ']';
printMultipleBrackets(openParen, closeParen, openBracket, closeBracket - 1, openCBracket, closeCBracket, str, count + 1);
}
if (closeParen > openParen) { // try a right parenthesis, if there’s a matching left
str[count] = ')';
printMultipleBrackets(openParen, closeParen - 1, openBracket, closeBracket, openCBracket, closeCBracket, str, count + 1);
}
}
}
public static void printMultipleBrackets(int count) {
char[] str = new char[count*6];
printMultipleBrackets(count, count, count, count, count, count, str, 0);
}
public static void main(String[] args) {
printMultipleBrackets(1);
}