## Directi Interview Question for SDE1s

• 2

Country: India
Interview Type: Phone Interview

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

Logic used is similar but put into a more compact recursive relation:

``C(n) = C(n-1) + C(n-2) + F(n+2)``

where F(n) is the nth term in the Fibonacci sequence.
C(n) has base cases C(1) = 3, C(2) = 7.

Reasoning:
-can append "c" to any n-1 length sequence to make an n length sequence.
-can append "b" to any n-1 length sequence that has no b in it already.
-can append "ca" to any n-2 length sequence
-can append "ba" to any n-2 length sequence that has no b in it already.

This "has no b in it already" is a sequence consisting of only "a" and "c" which is very easily found with relation f(n) = f(n-1) + f(n-2) which has an offset of 2 from the Fibonacci sequence.

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

Should have mentioned, this solution is O(n) time using bottom up/DP. If it is really desired F(n) can be calculated in constant time with its explicit formula, though even without it it will still technically be O(n). For even more efficiency, if the program needs to do multiple queries, never erase old data since they can be used as subcases for future queries.

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

very good reasoning!

We can compute C and F separately:

``````F(n) = F(n-1) + F(n-2);
C(n) = C(n-1) + C(n-2) + F(n);``````

Init values:

``````C(1) = 3; C(2) = 7;
F(1) = 2; F(2) = 3;``````

Result: C(n)

Can be implemented with O(n) time, O(1) space.

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

This problem can be solved by recursive/DP with O(n) time and O(1) space.

My way of thinking is following. Given that we already know everything for length (n-1), to compute for length n string, we need to know: if n-th position is "A" (or "B" or "C"), what must be the previous position?

For this problem, we define 6 variables:

``````A0 = number of strings with (n-1)-th position is "A" and have zero "B" so far.
A1 = number of strings with (n-1)-th position is "A" and have 1 "B" so far.
B0 = number of strings with (n-1)-th position is "B" and have zero "B" so far. // always none! Ignore it!
B1 = number of strings with (n-1)-th position is "B" and have 1 "B" so far.
C0 = number of strings with (n-1)-th position is "C" and have zero "B" so far.
C1 = number of strings with (n-1)-th position is "C" and have 1 "B" so far.``````

According to the rules, the n-th position is constructed by following table:

``````--	"A"	"B"	"C"
A0	x	B1	C0
A1	x	x	C1
B1	A1	x	C1
C0	A0	B1	C0
C1	A1	x	C1``````

Thus, the values of these variables at n-th position is (read from the table):

``````Recursive formulas for next position:
A0 = C0;
A1 = B1 + C1;
B1 = A0 + C0;
C0 = A0 + C0;
C1 = A1 + B1 + C1;``````

Initial values at first position

``````n = 1:
A0 = 1; "A"
A1 = 0; (no such)
B1 = 1; "B"
C0 = 1; "C"
C1 = 0; (no such)

n = 2:
A0 = C0 = 1; // "CA"
A1 = B1 + C1 = 1; // "BA"

B1 = A0 + C0 = 2; // "AB" "CB"

C0 = A0 + C0 = 2; // "AC" "CC"
C1 = A1 + B1 + C1 = 1; // "BC"``````

The result will be

``res = A0 + A1 + B1 + C0 + C1;``

This formulation can be implemented in O(n) time and O(1) space.
(Note, the values increase exponentially)

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

As explained by Booley, it boils down to compute C(n) given by the recurrence

``````F(n) = F(n - 1) + F(n - 2);
C(n) = C(n - 1) + C(n - 2) + F(n).``````

with C(-1) = 0, C(0) = 1, F(-1) = 1, F(0) = 1. One can show by induction that

``````/          \   /         \^n /   \
| C(n)     |   | 1 1 1 0 |   | 1 |
| C(n - 1) | = | 1 0 0 0 |   | 0 |
| F(n + 1) |   | 0 0 1 1 |   | 2 |
| F(n)     |   | 0 0 1 0 |   | 1 |
\          /   \         /   \   /``````

Therefore, to get C(n), it suffices to compute the right hand side above and retrieve the first coordinate.

Notice that dimensions of matrices and vectors involved do not depend on n. Matrix exponentiation can be done in O(lg n), in time and space, through exponentiation by squaring. So the total complexity is O(lg n).

This method is good to get a single C(n). If one needs to compute C(n) for n = 1, ..., N, then the bottom up dynamic programming algorithm suggested by others would be preferable.

I believe that, similarly to F(N), an algorithm to get C(n) in O(1) is mathematically possible but it requires working with floating point numbers. This might introduce small rounding errors that can propagate and yield a wrong result.

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

Awesome!

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

awesome!!

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

Maybe this could be made shorter, but it seems straightforward. O(n).

\$ ./ternary.py 1
3
\$ ./ternary.py 2
7
\$ ./ternary.py 3
15
\$ ./ternary.py 4
30

``````#!/usr/bin/env python

import sys

def num_ternary(previous_letter, b_used, length):
if length == 1:
# can place either a, b, or c
if previous_letter == 'a':
return 1 if b_used else 2
else:
return 2 if b_used else 3
if b_used:
if previous_letter == 'a':
# can only place 'c'
return num_ternary('c', True, length - 1)
else:
# can place 'a' or 'c'
return  num_ternary('a', True, length - 1) + num_ternary('c', True, length - 1)
else:
if previous_letter == 'a':
# can place 'b' or 'c'
return  num_ternary('b', True, length - 1) + num_ternary('c', False, length - 1)
else:
# 'a', 'b', or 'c'
return  num_ternary('a', False, length - 1) + num_ternary('b', True, length - 1) + num_ternary('c', False, length - 1)

if __name__ == '__main__':
# assume one interger arg, length N
print num_ternary(None, False, int(sys.argv))``````

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

O-of-what?
Why for n=30 it takes 10 seconds, for n=31 – 18 sec., for n=32 – 31 sec.? It doesn't look like linear. And it isn't because your algorithm is exponential in n.

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

True, probably not O(n) strictly. There can be multiple recursive calls for each place in the sequence (up to 2 for each). So worst case...I guess O(2 ^ n)?

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

Yeah, I think it is O(2 ^ n). The later solution from llambda is way faster, though a bit harder to read and understand.

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

``````def effecient_num_ternary(n):
a = [[0, 0] for _ in xrange(n+1)]
a = 1
a = 1
a = 2
a = 3
for i in xrange(2, n + 1):
for k in xrange(2):
a[i][k] = a[i-2][k] + a[i-1][k] + (a[i-2][k-1] + a[i-1][k-1] if k > 0 else 0)

return a[n]``````

This obviously works in O(n) (where n is length of string). Thanks to Dan, one can check that it's correct.

Why it works: let's take any valid string of length n and see what it's made of:
- If the last symbol is b, then previous (n-1) symbols are any valid combinations of a's and c's
- If the last symbol is c, then previous (n-1) symbols are any valid combinations of a's and b
- If the last symbol is a, then (n-1)th symbol is either c or b (if we can put any) and the previous (n-2) symbols are any valid string

This gives us formula for string of length n containing k b's (may work wrong with b != {0,1})

``````l(n, k) = l(n-1, k) // if it was c
+ (k > 0 ? l(n-1, k-1) : 0) // if it was b
+ l(n-2, k) // if it was ac
+ (k > 0 ? l(n-2, k-1) : 0) // if it was ab``````

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

N.B.: though my implementation uses O(n) memory, it's easy to reduce it to O(1) since I use only neighbor cells.

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

Clever. Non-obvious code it seems, but clever. Seems to work.

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

Very nice! I think it would be even easier to understand if it had the post of "ninhnnsoc" as an explanatory comment, but your post does a good job, too. Your code makes me miss my Python days a bit. :)

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

Algo Steps:

1) Calculate the number of possible entries of length (N-1) with 'a' and 'c' given the constraint.Here, we are reserving 1 slot for 'b', which is being allowed only once.Let the total number of entries be p.

2) For each of the p entries calculated in Step 1, we have effectively N slots in each entry where
we can place 'b'.

3) Hence, the solution turns out to be (p*N).

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

Solution fails for N=2:

p = 2 (one slot is "a" or "c")
N = 2

p*N = 4 != 7

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

@Booley

The string should be such that a,b,c are always mandatory.
can a,b,c be optional also ?
I think the above algo works for n>=4.

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

``````n=int(raw_input())
f=[2,3]
c=[3,7]
for i in range(2,n):
f.append(f[i-1]+f[i-2])
c.append(c[i-1]+c[i-2]+f[i])
print c[n-1]``````

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

``````A0 = 1;
A1 = 0;
B1 = 1;
C0 = 1;
C1 = 0;

n=int(raw_input())
for i in range(1,n):
(A0,A1,B1,C0,C1) = (C0,B1+C1,A0+C0,A0+C0,A1+B1+C1);
res = A0 + A1 + B1 + C0 + C1;
print res``````

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.