Directi Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
Good Way of doing the whole Thing and precise explanation.
But I suppose ur answer for G(n) = G(n-1) + G(n-2) is wrong. Should be G(n) = G(n-1) + G(n-2) +G(n-3) as new strings that could be made using constraints on 'a' and 'c' could be appending caa,ca or c.
with no condition on 'c' would not the max len for the generated string be infinity? (baacaacaac.....aacaacccccccccccccccccccccccccc...)
constraints :
(1) either no consecutive a's + only 1 b = 2N
(2) only 1 consecutive pair of a + only 1 b = (N-1) * (N-2)
Total = (1) + ( 2)
Case 1: All 'N' Characters are c
i.e ccccccc.. ......cccccccc (N times)
(total is '1' for this case).
Case 2: Permutation of 'b' and 'c'
i.e bcccccccccccccc......cc(c N-1 times)
cbccccccccccccccc..cc(c N-1 times)
.............
ccccccccccccccccc....cb.(c N-1 times)
(total is 'N' for this case).
Case 3: 1-a's,N-1 c's i.e acccccccccccccccc total n
2-a's,N-2 c's i.e acacccccccccccccc
................
N/2+1 a's, N/2 c's i.e acacac...........acac
or cacacacacacacac.
Case 4: contains single a,b,c
Case 5: Contains only two Consecutive aa,c
i.e aaccccccccccccccccccccccc(N-2 times c)
caacccccccccccccccccccccc(N-2 times c)
total N-2.
Case 6: Contains only two Consecutive aa,c,b
...........................
In These way You can try to solve...
Try it...
rama.paital@gmail.com
the question is how many no. of N length strings and all strings are formed by 3 characters
except single b ,rest of the string is composed of (aa)+(c).There will be only three cases as per position of b.
Case1:aacaaccccaa.....b......aacaacccccccccc
case2 : baacaa....cccccccccccc
case 3: aacaacccccccccccccccaa...b
c++ code
int a=0,b=0,cnt=0,N;
void fn(int n,char ch) {
if(n==N) { cnt++; return; }
if(a!=2) { a++; fn(n+1,'a'); }
if(b!=1) {a=0; b++; fn(n+1,'b'); }
a=0; fn(n+1,'c');
}
int main() {
a=0;b=0;cnt=0;
cin>>N;
a++; fn(1,'a');
a=0; b++; fn(1,'b');
a=0; fn(1,'c');
cout<<cnt;
system("pause");
return 0;
}
import java.util.*;
public class RegexExample {
static int count=0;
public static void main(String args[]) throws Exception {
genPattern("", 2);
System.out.println(count);
}
public static void genPattern(String temp, int n){
String t1="a",t2="b",t3="c";
if(temp.length()==n){
if(temp.matches("[c-z]*b[c-z]*|[c-z]*a[c-z]*b[c-z]*|" +
"[c-z]*b[c-z]*a[c-z]*|[c-z]*a[c-z]*b[c-z]*a[c-z]*|" +
"[c-z]*aa[c-z]*b[c-z]*|[c-z]*b[c-z]*aa[c-z]*|" +
"[c-z]*aa[c-z]*b[c-z]*aa[c-z]*")){
System.out.println(temp);
count++;
}
return;
}
genPattern(temp+t1,n);
genPattern(temp+t2,n);
genPattern(temp+t3,n);
}
}
import java.util.*;
public class RegexExample {
static int count=0;
public static void main(String args[]) throws Exception {
genPattern("", 2);
System.out.println(count);
}
public static void genPattern(String temp, int n){
String t1="a",t2="b",t3="c";
if(temp.length()==n){
if(temp.matches("[c-z]*b[c-z]*|[c-z]*a[c-z]*b[c-z]*|" +
"[c-z]*b[c-z]*a[c-z]*|[c-z]*a[c-z]*b[c-z]*a[c-z]*|" +
"[c-z]*aa[c-z]*b[c-z]*|[c-z]*b[c-z]*aa[c-z]*|" +
"[c-z]*aa[c-z]*b[c-z]*aa[c-z]*")){
System.out.println(temp);
count++;
}
return;
}
genPattern(temp+t1,n);
genPattern(temp+t2,n);
genPattern(temp+t3,n);
}
}
Let the target function be F
Started with thinking about b's 4 scenarios where (N) means qualified ac string of length N.
a) no appearance : (N)
b) one to the head : b(N-1)
c) one to the end : (N-1)b
d) one in the middle: (x)b(N-1-x)
Then F(N) = G(N) + 2*G(N-1) + sigma (G(x) *G(N-1-x)) where x is in [1, N-2]
Hence the question is transformed to G(N) which asks about qualifying strings of ac of length N only.
For G, two scenarios:
a) Start with a, b) start with c
hence
In summary,
- Leo.li.dba March 29, 2012