## Flipkart Interview Question

Country: India

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

geeksforgeeks.org/archives/5094 good solution

Comment hidden because of low score. Click to expand.
0

What is the time complexity of the above solution?

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

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 ---- () () () & () (()) & (()()) & ((())) & (())()

Comment hidden because of low score. Click to expand.
0

It's wrong. How do you generate "(())(())" from "())(()" ???

Comment hidden because of low score. Click to expand.
0
of 2 vote

en.wikipedia.org/wiki/Catalan_number
catalan number search on wiki

Comment hidden because of low score. Click to expand.
0

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

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

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)

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

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)

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

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,"");

}

}

Comment hidden because of low score. Click to expand.
0
of 2 vote

We can use recursion to do this:

basicalgos.blogspot.com/2012/03/8-generate-parentheses.html

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

I made a video demo to illustrate how to use recursion to print all valid combinations: youtube.com/watch?v=_Uq1dmgZj0I&feature=youtu.be

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

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

}``````

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

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

I am sorry but we can ignore the last if statement and the code would still work. Mea Culpa. Some changes not removed while debugging :)

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

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

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

``````#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,"");
}``````

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

geeksforgeeks.org/print-all-combinations-of-balanced-parentheses

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

``````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+")");
}``````

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

``````def printParam(toOpen, toClose, currString):
if not toOpen and not toClose:
print currString
return
if toOpen > 0:
printParam (toOpen -1, toClose, currString + "(")
if toClose > toOpen:
printParam(toOpen, toClose-1, currString + ")")

printParam(3,3,'')``````

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

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``````

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

``````<?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.")");
}
?>``````

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

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

}

}

Comment hidden because of low score. Click to expand.
0

Initially what value i will pass?

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

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

Comment hidden because of low score. Click to expand.
0

Doesn't work. If called as

``print(0, n, '');``

it will print

``(((((``

.

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

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

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote
{{{ 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); }; 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); } }
Comment hidden because of low score. Click to expand.
0

#define OBrace '('
#define CBrace ')'

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

``````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

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

why arent people usng stack! cant that help?

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

``````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``````

Comment hidden because of low score. Click to expand.
-2
of 4 vote

This comment has been deleted.

Comment hidden because of low score. Click to expand.
0

For which position you have given the interview.

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.

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