Flipkart Interview Question
Country: India
Can we consider this as a DP problem? Lets call Solution[k] as the list of possible string for n = k;
Solution for n = k + 1 is
{ ()Solution[k] Union Solution[k]() Union (Solution[k]) }
1. Case n = 1
()
2. Case n = 2
a. () Solution[0] ---- () ()
b. ( Solution[0] ) ----- (())
c. Solution[0] () ----- () ()
a U b U c ---- ()() and (())
Case 3.
a. () Solution[2] ---- ()()() & () (())
b. (Solution[2]) ---- (()()) & ((()))
c. Solution[2]() ---- ()()() & (()) ()
a U b U c ---- () () () & () (()) & (()()) & ((())) & (())()
static String parenthesis="";
public static void paren(int n)
{
String rollback="";
if(n<=0)
{
System.out.println(parenthesis);
parenthesis="";
return;
}
for(int i=1;i<=n;i++)
{
rollback=parenthesis;
parenthesis+=makeParen(i);
paren(n-i);
parenthesis=rollback;
}
}
public static String makeParen(int k)
{
String str="";
for(int i=0;i<k;i++)
{
str="{"+str+"}";
}
return str;
}
def matched_pare(n, left_in, all_in, exp, ct):
if all_in==2*n: # done
print "%d: %s" % (ct+1, exp)
return ct+1
elif left_in==n: # almost done
ct = matched_pare(n, left_in, 2*n, exp+')'*(2*n-all_in), ct)
return ct
else: # can proceed with either a '(' or, if the number of '(' is greater than the number of ')', a ')'
ct = matched_pare(n, left_in+1, all_in+1, exp+'(', ct)
if all_in-left_in<left_in:
ct = matched_pare(n, left_in, all_in+1, exp+')', ct)
return ct
def main():
n = input('Enter the number of parenthesis pair:')
matched_pare(n, 0, 0, '', 0)
def matched_pare(n, left_in, all_in, exp, ct):
if all_in==2*n: # done
print "%d: %s" % (ct+1, exp)
return ct+1
elif left_in==n: # almost done
ct = matched_pare(n, left_in, 2*n, exp+')'*(2*n-all_in), ct)
return ct
else: # can proceed with either a '(' or, if the number of '(' is greater than the number of ')', a ')'
ct = matched_pare(n, left_in+1, all_in+1, exp+'(', ct)
if all_in-left_in<left_in:
ct = matched_pare(n, left_in, all_in+1, exp+')', ct)
return ct
def main():
n = input('Enter the number of parenthesis pair:')
matched_pare(n, 0, 0, '', 0)
public class PermuteBrace{
private static void printPermute(int openBrace,int closeBrace, int currOpen, int currClose,String str){
if(openBrace>=1){
printPermute(openBrace-1,closeBrace,currOpen+1,currClose,str+"{");
}
if(closeBrace>=1){
if(currOpen-currClose>=1){
if(openBrace==0 && closeBrace-1==0){
System.out.println(str+"}");
return;
}
printPermute(openBrace,closeBrace-1,currOpen,currClose+1,str+"}");
}
}
}
public static void main(String[] args){
printPermute(3,3,0,0,"");
}
}
public class Parenthesis {
public static void main(String[] args) {
int noOfPairs = Integer.parseInt(args[0]);
char[] output = new char[noOfPairs * 2];
System.out.println("");
print(output, 0, 0);
}
/**
* This method is called recursively to generate valid permutations for parenthesis
*/
private static void print(char[] out /* output array to be filled*/,
int left /* number of left parenthesis in output array */,
int right /* number of right parenthesis in output array */) {
int len = out.length;
// Case 0: Array is filled
if(right == len/2) {
printArr(out);
return;
}
// Case 1: All left are used
if(left == len/2) {
while(right < len/2) {
out[left + right] = ')';
right++;
}
printArr(out);
return;
}
// Case 2: Array is balanced
if(left == right) {
out[left + right] = '(';
print(out, left + 1, right);
return;
}
// Case 3: More left parenthesis than right
if(left > right) {
out[left + right] = '(';
print(out, left + 1, right);
out[left + right] = ')';
print(out, left, right + 1);
}
}
/** Keeps track of number of valid permutaions already printed */
private static int printCnt = 0;
/**
* Utility to print output array
*/
private static void printArr(char[] arr) {
System.out.print(++printCnt + ":\t");
for(char ch: arr) {
System.out.print(ch);
}
System.out.println("");
}
}
class ParanthesisC
{
int mTotPair;
public:
ParanthesisC(void);
~ParanthesisC(void);
void TestThis();
public:
void EnumerateParanthesis(int totPair);
private:
void PrintHelper(int fbrace, int bbrace, char* str);
};
#define OBrace '('
#define CBrace ')'
ParanthesisC::ParanthesisC(void): mTotPair(0)
{
}
ParanthesisC::~ParanthesisC(void)
{
}
void ParanthesisC::TestThis()
{
EnumerateParanthesis(6);
}
void ParanthesisC::EnumerateParanthesis(int totPair)
{
if(totPair <= 0)
return;
if(totPair == 1)
{
cout<<OBrace<<CBrace<<endl;
return;
}
mTotPair = totPair;
char* str = new char[2*totPair + 1];
str[2*totPair] = 0;
PrintHelper(0, 0, str);
delete []str;
}
void ParanthesisC::PrintHelper(int fbrace, int bbrace, char* str)
{
if(fbrace < bbrace)
return;
if(fbrace == mTotPair)
{
int index = fbrace + bbrace;
while(index < 2*mTotPair)
{
str[index] = CBrace;
index++;
}
cout<<str<<endl;
return;
}
str[fbrace + bbrace] = OBrace;
PrintHelper(fbrace + 1, bbrace, str);
if((bbrace + 1 < mTotPair))
{
str[fbrace + bbrace] = CBrace;
PrintHelper(fbrace, bbrace + 1, str);
}
}
To understand the code, what you need to see is that such an enumeration problem is like traversing a tree. In this case we have a binary tree with root containing open brace and left child of each node an open brace if it is less than N else null and right side a closed brace if it less than N, else null.
In the code, I have a place to enumerate and print the permutation namely str. It is set to length 2*N + 1 and str[2*N] = 0. Here N is total number of braces pair to be printed legally (as far as compiler is considered)
When I call PrintHelper, I check first if total forward brace or opening brace is less than total backward brace or closing brace. If it is, we have got an error because at any point of time, while moving from 0 to N in str, the number of forward brace must be more than number of backward brace.
Secondly I check the condition if forward brace is equal to total number of Braces (N). If it is, we are now left with only backward braces to be filled in str and print.
Else, I fill the str with forward brace and repeat the function with forward brace increased by 1
if backward brace is less than total number of brace ( to remove redundancy in permutation) we repeat the function with backward brace increased by 1
To understand the code, what you need to see is that such an enumeration problem is like traversing a tree. In this case we have a binary tree with root containing open brace and left child of each node an open brace if it is less than N else null and right side a closed brace if it less than N, else null.
In the code, I have a place to enumerate and print the permutation namely str. It is set to length 2*N + 1 and str[2*N] = 0. Here N is total number of braces pair to be printed legally (as far as compiler is considered)
When I call PrintHelper, I check first if total forward brace or opening brace is less than total backward brace or closing brace. If it is, we have got an error because at any point of time, while moving from 0 to N in str, the number of forward brace must be more than number of backward brace.
Secondly I check the condition if forward brace is equal to total number of Braces (N). If it is, we are now left with only backward braces to be filled in str and print.
Else, I fill the str with forward brace and repeat the function with forward brace increased by 1
if backward brace is less than total number of brace ( to remove redundancy in permutation) we repeat the function with backward brace increased by 1
#include <stdio.h>
void par(int open,int close,int n,int idx)
{
static char a[100];
int i;
if(close==n)
{
for(i=0;i<2*n;i++)
printf("%c",a[i]);
printf("\n");
}
if(open<n)
{
a[idx]='(';
par(open+1,close,n,idx+1);
}
if(close<open)
{
a[idx]=')';
par(open,close+1,n,idx+1);
}
}
int main()
{
par(0,0,3,0);
return 0;
}
#include <iostream>
#include <string>
using namespace std;
void printParenth(int n,int curr_open,int remain_open,string s){
if(remain_open == 0){
for(int i=0;i<curr_open;i++){
s += ")";
}
cout<<s<<endl;
return;
}
if(curr_open > 0){
printParenth(n,curr_open-1,remain_open,s+")");
}
if(remain_open > 0){
printParenth(n,curr_open+1,remain_open-1,s+"(");
}
}
int main(){
int n;
cin>>n;
printParenth(n,0,n,"");
}
void print_parentheses(int n)
{
string s="";
print(0, 0, n, s);
}
void print(int left, int right, int n, string s)
{
if(left>n || right>n || right>left)
return;
if(left==right && left+right==2*n)
{
cout<<s<<endl;
return;
}
print(left+1, right, n, s+"(");
print(left, right+1, n, s+")");
}
Sorry. Didn't mean to post anonymously... Not sure how to delete the anonymous submission.
import java.util.*;
public class PermuteParensSimple {
// 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 numOpen = N, numClose = N;
walkTree(numOpen, numClose, "");
}
// Walk "virtual tree" of nodes recursively, outputting all valid
// permutations of N parens. Each node in the tree represents either a `('
// or `)'. Each complete traversal represents a possible permutation of N
// pairs of parens, defined by the nodes in the path from root to leaf.
// Note: Traversals that end before all open/close parens have been used
// (i.e., traversals with fewer than 2N nodes) represent impossible
// permutations and produce no output: e.g.,
// N=2: ())
// N=2: (((
// Inputs:
// numOpen: # of open parens remaining in current traversal
// numClose: # of close parens remaining in current traversal
static void walkTree(int numOpen, int numClose, String path) {
if (numOpen == 0 && numClose == 0) {
// Output accumulated path at end of complete traversal.
System.out.println(path);
return;
}
// Has this traversal used all open parens?
if (numOpen > 0)
// Recurse left.
walkTree(numOpen - 1, numClose, path + "(");
// Are there any unmatched open parens in this traversal?
if (numOpen < numClose)
// Recurse right.
walkTree(numOpen, numClose - 1, path + ")");
}
}
// vim:ts=4:sw=4:et:tw=78
<?php
$n = 3;
$pairsArray=array();
generatePair($n,$pairsArray);
echo "<pre>";
print_r($pairsArray);
function generatePair($n,&$pairsArray=array(),$currentPair=""){
$countOpen = substr_count($currentPair,"(");
$countClose = substr_count($currentPair,")");
$isOpenAllowed=( $countOpen < $n) ? true : false;
$isCloseAllowed=($countClose < $n && $countOpen > $countClose) ? true : false;
if(!$isOpenAllowed && !$isCloseAllowed){
$pairsArray[]=$currentPair;
return;
}
if($isOpenAllowed)
generatePair($n,$pairsArray,$currentPair."(");
if($isCloseAllowed && $currentPair<>"")
generatePair($n,$pairsArray,$currentPair.")");
}
?>
void par(int open,int close,int n,int idx)
{
static char a[1000];
if(close==n)
{
printf(a);
return;
}
if(close<open)
{
a[idx]=")";
par(open,close+1,n,idx+1,a);
}
if(open<n)
{
a[idx]="(";
par(open+1,close,n,idx+1,a
}
}
void print(int l, int r, string str){
if(l+1<=n){
print(l+1, r, str+"(");
}
if(r+1 <= l){
print(l, r+1, str+")");
}
if(l>=n && r>=n) cout<<str<<endl;
}
Please ignore time complexity, feel free to optimize this code
#include<stdio.h>
#include<conio.h>
void permuteAll(char *str,int i,int n);
void swap(char *p, char *q);
int validate(char *str);
void printStr(char *str);
int calculate(char *str);
int verfiyDuplicate(int total);
int unique[100] = {0};
int n = 0;
int main()
{
int i;
char str[] = "11110000";
permuteAll(str,0,7);
getch();
return 0;
}
int verfiyDuplicate(int total)
{
int check = 1;
int i =0;
for(i = 0; i < n ; i++)
{
if(unique[i] == total)
{
check = 0;
break;
}
}
if(check == 1)
{
unique[n] = total;
n++;
}
return check;
}
int validate(char *str)
{
int i=0;
int total = 0;
for(i = 0; *(str+i);i++)
{
if(*(str+i) == '1')
total = total + 1;
else
total = total - 1;
if(total < 0)
return 0;
}
return 1;
}
void printStr(char *str)
{
int i =0;
printf("\n");
for(i = 0; *(str+i);i++)
{
if(*(str+i) == '1')
printf("[");
else
printf("]");
}
}
int calculate(char *str)
{
int i = 0;
int total = 0;
for(i = 0; *(str+i);i++)
{
if(*(str+i) == '1')
total = total + (pow(2,i) * 1);
else
total = total + (pow(2,i) * 0);
}
return total;
}
void permuteAll(char *str,int i,int n)
{
if(i == n)
{
if( validate(str) )
{
int total = calculate(str);
if (verfiyDuplicate(total))
printStr(str);
}
}
else
{ int j ;
for(j = i; j<= n; j++)
{
swap((str+i),(str+j));
permuteAll(str,i+1,n);
swap((str+i),(str+j));
}
}
}
void swap(char *p, char *q)
{
char ch ;
ch = *p;
*p = *q ;
*q = ch;
}
Arrange(n)
{
char arr[2n];
arr[0]="(";
arr[2n-1]=")";
int l=1,r=1;
for(i=1;i<2n-1;i++)
{
if(r>=l && r-l<2n-i)
Random m=new random();
//will select a no. between 1 and 2
int c=r.nextInt(2);
if(c==1)
arr[i]="(";
else
arr[i]=")";
}
else
arr[i]=")";
}
}
hope u wld like it...includes oll cases
import java.util.*;
public class PermuteParensSimple {
// 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 numOpen = N, numClose = N;
walkTree(numOpen, numClose, "");
}
// Walk "virtual tree" of nodes recursively, outputting all valid
// permutations of N parens. Each node in the tree represents either a `('
// or `)'. Each complete traversal represents a possible permutation of N
// pairs of parens, defined by the nodes in the path from root to leaf.
// Note: Traversals that end before all open/close parens have been used
// (i.e., traversals with fewer than 2N nodes) represent impossible
// permutations and produce no output: e.g.,
// N=2: ())
// N=2: (((
// Inputs:
// numOpen: # of open parens remaining in current traversal
// numClose: # of close parens remaining in current traversal
static void walkTree(int numOpen, int numClose, String path) {
if (numOpen == 0 && numClose == 0) {
// Output accumulated path at end of complete traversal.
System.out.println(path);
return;
}
// Has this traversal used all open parens?
if (numOpen > 0)
// Recurse left.
walkTree(numOpen - 1, numClose, path + "(");
// Are there any unmatched open parens in this traversal?
if (numOpen < numClose)
// Recurse right.
walkTree(numOpen, numClose - 1, path + ")");
}
}
// vim:ts=4:sw=4:et:tw=78
geeksforgeeks.org/archives/5094 good solution
- abkk July 08, 2012