Directi Interview Question for Software Engineer / Developers


Country: India
Interview Type: Phone Interview




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

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

G(N) = G(N-2) + G(N-1) 
where N >2 and 
simple permutations results
G(0) = 0
G(1) = |{a,c }| = 2
G(2) = |{ac, ca,cc}| = 3

In summary,

F(0) = 0,
F(1) = 3,
for N >= 2, 
F(N) = G(N) + 2* G(N-1) + G(x) * G(N-1-x)
 where 
1) x ranges from [1, N-2]  
2) G(N) = G(N-1) + G(N-2) where G(0) = 0, G(1) = 2 and G(2) = 3 ...

Hence 3, 7, 15 ....

- Leo.li.dba March 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- rahul1202.08 June 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

how f(2)=7 .. in question given that "no more than 2 consecutive 'a' appear in string. " .. means "aa" is also count ..

- vivek July 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

with no condition on 'c' would not the max len for the generated string be infinity? (baacaacaac.....aacaacccccccccccccccccccccccccc...)

- just_passing_through March 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

read question carefully. length of string is N .u have to how many strings is possible with length n.

- spider March 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- sk March 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

explain?? how?

- spider March 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- BusyMan March 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- shine April 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Nitish May 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Let total possibility be p:
Case 1: 1c,1a p1= N;
Case 2: 1c,2a p2= N*(N-1)/2
Case 3: 1c,1b p3= N
Case 4: 1a,1b,1c p4= N*(N-1)
Case 5: 2a,1b,1c p5= N*(N-1)*(N-2)/2

Total possibility p=p1+p2+p3+p4+p5

- codeAddict June 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Rushiraj October 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Rushiraj October 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More