## Google Interview Question for Software Engineer / Developers

• 3

Team: None
Country: United States
Interview Type: Phone Interview

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

``````public static void Permutations(string prefix, int n, bool bUsedEarlier, bool cExhaustedEarlier, ref int count)
{
char[] chars = { 'a', 'b', 'c' };

if (n == 0)
{
Console.WriteLine(prefix);
count++;
return;
}

foreach (var @char in chars)
{
if (@char == 'b' && bUsedEarlier)
continue;

if (@char == 'c' && cExhaustedEarlier)
continue;

var bUsed = bUsedEarlier || @char == 'b';
var cExhausted = cExhaustedEarlier || prefix.Length > 0 && prefix[prefix.Length - 1] == 'c' && @char == 'c';

Permutations(prefix + @char, n - 1, bUsed, cExhausted, ref count);
}
}

public static void StringTest()
{
int count = 0;
Permutations("", 4, false, false, ref count);
Console.WriteLine("Count of Permutations: " + count);
}``````

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

O(n) solution is provided.

We can divide strings in two types;
A type which does not contain ‘b’
and B type which contain ‘b’.
We can define matrix A and B as follows.

A[i]: the number of strings of length i in A type.
B[i]: the number of strings of length i in B type.

And the answer is A[n] + B[n]

Because B type strings with lengh i can be generated
by picking any sting in A type strings with length i-1,
and put ‘b’ in any position in the string.
There are total i positions to insert ‘b’,
thus, following equation holds between A[i] and B[i].

B[i] = i * A[i-1]

So, it is enough to compute A[i].
For considering strings in A, there are three possible
prefixes which end with ‘a’.
(because there is no constraint in the substring after ‘a’)

1. ‘a’ + A type strings with length i - 1
2. ‘ca’ + A type strings with length i - 2
3. ‘cca’ + A type strings with length i - 3

i.e., A[i] = A[i-1] + A[i-2] + A[i-3]
where A = 2, A = 4, A = 7

We can compute matrix A iteratively.

As an example, the number of strings of length 3 is
A + B = A + 3 * A = 7 + 3*4 = 19.

``````int countStr(int n)
{
vector<int> A;
A.reserve(n + 1);

A = 1, A = 2, A = 4, A = 7;

for(int i = 4; i <= n; i++){
A[i] = A[i-1] + A[i-2] + A[i-3];
}

return A[n] + n*A[n-1];
}``````

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

countStr(4) gives 41. The correct answer is 43.

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

A DP solution with inputs as the number of characters left, whether b has already been used in the built prefix and trailing number of c in the built prefix:

``````val memo = mutable.HashMap[(Int, Boolean, Byte), Long]()
memo.put((1, true, 0), 2l)
memo.put((1, true, 1), 2l)
memo.put((1, true, 2), 1l)
memo.put((1, false, 0), 3l)
memo.put((1, false, 1), 3l)
memo.put((1, false, 2), 2l)

def getCount(n: Int, containsB: Boolean, endC: Byte): Long = {
memo.get((n, containsB, endC)) match {
case Some(x) => return x
case None => {
var ans = 0l
if (!containsB)
ans += getCount(n - 1, true, 0)
if (endC < 2)
ans += getCount(n - 1, containsB, (endC + 1).toByte)
ans += getCount(n - 1, containsB, 0)
ans
}
}
}

println(getCount(3, false, 0))``````

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

Whats the time complexity? Isn't it exponential.

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

``````public static void main(String arr[])
{
System.out.println(count(new String(), 3));
}

public static int count(String str, int count)
{
int sum = 0;
if (count <= 0)
{
System.out.println(str);
return 1;
}
if (str.indexOf('b') == -1)
{
sum = sum + count(str + "a", count - 1);
sum = sum + count(str + "b", count - 1);
if (str.length() > 0 && str.charAt(str.length() - 1) != 'c')
{
sum = sum + count(str + "c", count - 1);
} else if (str.length() == 0)
{
sum = sum + count(str + "c", count - 1);
}
} else
{
sum = sum + count(str + "a", count - 1);
if (str.length() > 0 && str.charAt(str.length() - 1) != 'c')
{
sum = sum + count(str + "c", count - 1);
} else if (str.length() == 0)
{
sum = sum + count(str + "c", count - 1);
}
}
return sum;
}``````

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

``````public static void main(String arr[])
{
System.out.println(count(new String(), 3));
}

public static int count(String str, int count)
{
int sum = 0;
if (count <= 0)
{
System.out.println(str);
return 1;
}
if (str.indexOf('b') == -1)
{
sum = sum + count(str + "a", count - 1);
sum = sum + count(str + "b", count - 1);
if (str.length() > 0 && str.charAt(str.length() - 1) != 'c')
{
sum = sum + count(str + "c", count - 1);
} else if (str.length() == 0)
{
sum = sum + count(str + "c", count - 1);
}
} else
{
sum = sum + count(str + "a", count - 1);
if (str.length() > 0 && str.charAt(str.length() - 1) != 'c')
{
sum = sum + count(str + "c", count - 1);
} else if (str.length() == 0)
{
sum = sum + count(str + "c", count - 1);
}
}
return sum;``````

}

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

``````public static void main(String arr[])
{
System.out.println(count(new String(), 3));
}

public static int count(String str, int count)
{
int sum = 0;
if (count <= 0)
{
System.out.println(str);
return 1;
}
if (str.indexOf('b') == -1)
{
sum = sum + count(str + "a", count - 1);
sum = sum + count(str + "b", count - 1);
if (str.length() > 0 && str.charAt(str.length() - 1) != 'c')
{
sum = sum + count(str + "c", count - 1);
} else if (str.length() == 0)
{
sum = sum + count(str + "c", count - 1);
}
} else
{
sum = sum + count(str + "a", count - 1);
if (str.length() > 0 && str.charAt(str.length() - 1) != 'c')
{
sum = sum + count(str + "c", count - 1);
} else if (str.length() == 0)
{
sum = sum + count(str + "c", count - 1);
}
}
return sum;
}``````

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

``````package main

import (
"fmt"
"strings"
)

func main() {
fmt.Println(count(3))
}

func count(chars_length int, args...string) int {
prefix := ""
if len(args) == 1 {
prefix = args
}
if chars_length == 0 {
return 1
}
sum := 0
if !strings.Contains(prefix, "b") {
sum += count(chars_length-1, prefix+"b")
}

sum += count(chars_length-1, prefix+"a")
c_count := 0
for _, r := range prefix {
if r == 'c' {
c_count += 1
}
}
if (c_count < 2) {
sum += count(chars_length-1, prefix+"c")
}
return sum
}``````

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

``````package main

import (
"fmt"
"strings"
)

func main() {
fmt.Println(count(3))
}

func count(chars_length int, args...string) int {
prefix := ""
if len(args) == 1 {
prefix = args
}
if chars_length == 0 {
return 1
}
sum := 0
if !strings.Contains(prefix, "b") {
sum += count(chars_length-1, prefix+"b")
}

sum += count(chars_length-1, prefix+"a")
c_count := 0
for _, r := range prefix {
if r == 'c' {
c_count += 1
}
}
if (c_count < 2) {
sum += count(chars_length-1, prefix+"c")
}
return sum
}``````

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

``````public int countWays(int n, int[] last,int bFreq, int cFreq){
if(n==0){
return 1;
}
int total=0;
if(bFreq<1){

total+=countWays(n-1,last,1,0);

}
if(cFreq<2){

total+=countWays(n-1,last,bFreq,cFreq+1);

}
total+=countWays(n-1,last,bFreq,0);
}``````

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

``````@interface StringCounter: NSObject
+(NSInteger)countStrings:(NSInteger) n;
@end

@implementation StringCounter
+(NSInteger)countStrings:(NSInteger) n {
if (n==1) {
return 3;
}
if (n==2) {
return 4;
}
if (n==3) {
return 19;
}

// Use N=3 case to build upon.
// Strings ending in A, not containing B: "AAA", "ACA", "CAA", "CCA"
NSInteger ANotContainB = 4;
// Strings ending in A, containing B: "ABA", "BAA", "BCA", "CBA"
NSInteger AContainB = 4;
// Strings ending in Ac, containing B: "BAC"
NSInteger AcContainB = 1;
// Strings ending in Ac, not containing B:"AAC", "CAC"
NSInteger AcNotContainB = 2;
// Strings ending in Cc, containing B:"BCC"
NSInteger CcContainB = 1;
// Strings ending in Cc, not containing B:"ACC"
NSInteger CcNotContainB = 1;
// Strings ending in Bc: "ABC", "CBC"
NSInteger Bc = 2;
// Strings ending in B: "AAB", "ACB", "CAB", "CCB"
NSInteger B = 4;

// Use calculations of prev counts for current counts, n - 3 times.
for (NSInteger i = 4; i <= n; i++) {

// Make temporary copies.
NSInteger prevANotContainB = ANotContainB;
NSInteger prevAContainB = AContainB;
NSInteger prevAcContainB = AcContainB;
NSInteger prevAcNotContainB = AcNotContainB;
NSInteger prevCcContainB = CcContainB;
NSInteger prevCcNotContainB = CcNotContainB;
NSInteger prevBc = Bc;
NSInteger prevB = B;

ANotContainB = prevAcNotContainB + prevCcNotContainB + prevANotContainB;
AContainB = prevAcContainB + prevCcContainB + prevBc + prevAContainB + prevB;
AcContainB = prevAContainB;
AcNotContainB = prevANotContainB;
CcContainB = prevAcContainB + prevBc;
CcNotContainB = prevAcNotContainB;
Bc = prevB;
B = prevAcNotContainB + prevCcNotContainB + prevANotContainB;
}
return ANotContainB + AContainB + AcContainB + AcNotContainB + CcContainB + CcNotContainB + Bc + B;
}
@end``````

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

Iterative DP solution in Python:

def count(l):
D = [[[None]*3 for i in xrange(2)] for j in xrange(l)]
D = 1
D = 1
D = 0
D = 1
D = 0
D = 0

for i in xrange(1, l):
for char in ["a", "b", "c"]:
if char == "a":
D[i] = D[i-1]
D[i] = D[i-1]
D[i] = D[i-1]
D[i] = D[i-1]
D[i] = D[i-1]
D[i] = D[i-1]
elif char == "b":
D[i] += D[i-1]
D[i] += D[i-1]
D[i] += D[i-1]
elif char == "c":
D[i] += D[i-1]
D[i] += D[i-1]
D[i] += D[i-1]
D[i] += D[i-1]

print D
return sum(D[l-1])+sum(D[l-1])

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

Iterative DP-solution in Python:

``````def count(l):
D = [[[None]*3 for i in xrange(2)] for j in xrange(l)]
D = 1
D = 1
D = 0
D = 1
D = 0
D = 0

for i in xrange(1, l):
for char in ["a", "b", "c"]:
if char == "a":
D[i] = D[i-1]
D[i] = D[i-1]
D[i] = D[i-1]
D[i] = D[i-1]
D[i] = D[i-1]
D[i] = D[i-1]
elif char == "b":
D[i] += D[i-1]
D[i] += D[i-1]
D[i] += D[i-1]
elif char == "c":
D[i] += D[i-1]
D[i] += D[i-1]
D[i] += D[i-1]
D[i] += D[i-1]

print D
return sum(D[l-1])+sum(D[l-1])``````

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

Iterative Python solution:

``````def is_c_usable(string):
if len(string)<2:
return True
return string[-2:]!="cc"

def valid_strings_iterative(n):
# O(2^n)
# Format of tuple is (string, isBAvailable)
strings = [("a", True), ("b", False), ("c", True)]
for i in xrange(1, n):
new_strings = []
for string, b_available in strings:
new_strings.append((string+"a", b_available))
if b_available==True:
new_strings.append((string+"b", False))
if is_c_usable(string)==True:
new_strings.append((string+"c", b_available))
strings = new_strings
return [s for s in strings]``````

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

I'm pretty sure this one can be O(lg N) and O(1) via divide and conquer and dynamic programming, but the code seems like it would be very complicated.
(Basically, try all possible middle 2 or 3 characters so sides are each exactly floor((N-2)/2) long; this makes all recursive calls go to the same value of N so call tree is lg N height; only # of 3's on right * # of 3's on left * b allowed = 3*3*2 = 18 calls need to be memo-ized for each used value of N.)

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

``````private static final String[] availableChars =  {"A", "B", "C"};

public static void main(String[] args){

TreeSet<String> combinations = getCombinations(5);
TreeSet<String> filteredCombinations = filter(combinations);

System.out.println(filteredCombinations);
}

private static TreeSet<String> filter(TreeSet<String> input){
TreeSet<String> output = new TreeSet<>();

for (String s : input){
if (!s.contains("CCC")){
if (s.indexOf('B') == s.lastIndexOf('B')) {
}
}

}
return output;
}

private static TreeSet<String> getCombinations(int length){
TreeSet<String> output = new TreeSet<>();
if (length <= 1){
for (String character : availableChars) {
}
}else {
TreeSet<String> set = getCombinations(length - 1);
for (String s : set) {
for (String character : availableChars) {
}
}
}
return output;
}``````

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

Let's say F(N) is the number of such words with length N and G(N) is the number of words not containing any 'b'.
F(0) = 1
F(1) = 3 // 'a' 'b' 'c'
F(2) = 8 // 'aa' 'ab' 'ac' 'cc' 'ca' 'cb' 'ba' 'bc'
G(0) = 1
G(1) = 2 // 'a' 'b'
G(2) = 4 // 'aa' 'ac' 'cc' 'ca'
Now let's see how our words from the problem can begin:
1. a... F(N-1) such words
2. cca... F(N-3) such words
3. ca... F(N-2) such words
4. b... G(N-1) such words
5. cb... G(N-2) such words
6. ccb... G(N-3) such words
Taking similar path with G words, we can see that G(N) = G(N-1) + G(N-2) + G(N-3)
So, finally
F(N) = F(N-1) + F(N-2) + F(N-3) + G(N-1) + G(N-2) + G(N-3)
Proof by example (not really a proof):
F(3) = 8 + 3 + 1 + 4 + 2 + 1 = 19

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

python solution:

``````import itertools

def findStrings(n):
valid = []
for combo in itertools.product('abc', repeat=n):
combo = ''.join(combo)
if combo.count('b') > 1:
continue
if combo.count('ccc') > 0:
continue
valid.append(combo)

return len(valid)``````

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

``````import java.util.HashMap;

public class ABCs {

HashMap <String, Integer> h = new HashMap <String, Integer> ();

int howManyStrings (int n ){
int total = howManyStrings (n,false,0);
}

int howManyStrings (int n, Boolean hasBbeenUsed, int trailingCs){
if ( n == 0) return 0;
int total=0;
if (n == 1){
total = 1; //a

if (!hasBbeenUsed) total++; // b

if ( trailingCs < 2 ) total++; // c

}
else{
//Check if we considered this case already.
String s = n + hasBbeenUsed.toString() + trailingCs;
if ( h.containsKey(s) ) return h.get(s);

total=
howManyStrings (n-1, hasBbeenUsed, 0); //a.
if (!hasBbeenUsed) total+= howManyStrings (n-1, true, 0); //b
if ( trailingCs < 2) total+= howManyStrings (n-1, hasBbeenUsed, trailingCs++); //Final c.

h.put (s, total);
}
}

public static void main(String[] args) {
// TODO Auto-generated method stub
int a = new ABCs().howManyStrings (20);
System.out.println(a);

}

}``````

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

This can be done in O(n) time using DP... we just need to keep track of 4 variables and update them in each iteration.
totalPrev= total result previous value of n
total1cs=total numbers with 1 c in the last two positions
total2cs=total numbers with 2 c in the last two positions
totalBPrev=total numbers which already have b in them..

here is the code which included logic for updates (quite self explanatory so I am not writing it down) ...

``````public static int findStrings(int n){
if(n==0)
return 0;
if(n==1)
return 3;
if(n==2)
return 8;
int k=2;
int totalPrev=8;
int total1cs=2;
int total2cs=1;
int totalBPrev=4;
while(k<n){
k++;
int newTotal=3*totalPrev-totalBPrev-total2cs;
int t2csnew=total1cs;
total1cs=totalPrev-total1cs-total2cs;
total2cs=t2csnew;
totalBPrev=totalPrev;
totalPrev=newTotal;
}
}``````

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

``````public class Solution
{
public static void main(String[] args)
{
Solution s = new Solution();
System.out.println(s.numberOfStr(9));
}

public int numberOfStr(int n) {
return dfs('a', false, 0, n, 0);
}

private int dfs(char current, boolean hasB, int level, int n, int continueC) {
if (level == n) return 1;
int sum = 0;
sum += dfs('a', hasB, level+1, n, 0);
if (!hasB) sum += dfs('b', true, level+1, n, 0);
if (continueC < 2) {
if (current == 'c') sum += dfs('c', hasB, level+1, n, continueC+1);
else sum += dfs('c', hasB, level+1, n, 1);
}

return sum;
}
}``````

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

``````public class PrintAllPerms {

public static void main(String[] args) {
printAllStringCombinations("abc".toCharArray(), 3);
}

public static void printAllStringCombinations(char[] s, int size) {
List<String> l = getCombinations(s, size);

// filter out invalid strings
List<String> invalidList = new ArrayList<>();
for (String st : l) {
if (!isValid(st)) {
}
}
l.removeAll(invalidList);

for (String string : l) {
System.out.println(string );
}
}

private static boolean isValid(String st) {
char[] c = st.toCharArray();
int countBs = 0;
int countConsecutiveCs = 0;
for (int i = 0; i < c.length; i++) {
if (c[i] == 'b') {
countBs++;
} else if (c[i] == 'c' && i + 1 < c.length && c[i+1] == 'c') {
countConsecutiveCs++;
}
}

if (countBs > 1 || countConsecutiveCs > 1) {
return false;
}

return true;
}

public static List<String> getCombinations(char[] c, int size) {
List<String> r = new ArrayList<>();
generateCombinations(r, new StringBuilder(), c, size);
return r;
}

public static void generateCombinations(List<String> list, StringBuilder sb, char[] c, int size) {
if (sb.length() == size) {
} else {
for (int i = 0; i < c.length; i++) {
sb.append(c[i]);
generateCombinations(list, new StringBuilder(sb.toString()), c, size);
sb.deleteCharAt(sb.length() - 1);
}
}
}

}``````

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

Using recursion:

define s(n): total number of valid cases with length n
define a(n): number of valid cases with length n starting with 'a'
define b(n): '' with 'b'
define c(n): '' with 'c'

base cases:
a(1) = 1 // "a" is the only valid string of length 1
b(1) = 1 // "b"
c(1) = 1 // "c"
s(1) = a(1) + b(1) + c(1)

s(n) = a(n) + b(n) + c(n) // the string can start with either a, b or c

a(n) = s(n-1) // "a" + any valid string of length n-1
b(n) = 1 + (n-1) + (n-2) // if "b" is the first character, the remaining string only consists of 'a' and 'c'.
// 1 is for "b" + "aaaa....a" is the only valid string with no 'c'
// (n-1) is for "b" + any valid string of length n-1 with only one 'c'
// (n-2) is for "b" + any valid string of length n-1 with only one 'cc'
c(n) = s(n-1) - 1 (if n >2)// "c" + any valid sting of length n-1 except for 'cc????'
= s(n-1) (if (n <= 2)

``````int a(int n) {
if (n == 1) return 1;
else return s(n-1);
}
int b(int n) {
if (n == 1) return 1;
else return 1 + (n-1) + (n-2);
}
int c(int n) {
if (n == 1) return 1;
else if (n == 2) return s(n-1);
else return s(n-1) - 1;
}

int s(int n) {
return a(n) + b(n) + c(n);
}

s(3) = a(3) + b(3) + c(3)
= s(2) + 4 + s(2) -1 = 2 * s(2) + 3

s(2) = a(2) + b(2) + c(2)
= s(1) + 2 + s(1)  = 2 * s(1) + 2

s(1) = a(1) + b(1) + c(1) = 1 + 1+ 1 = 3

Therefore, s(2) = 2 * 3 + 2 =8
s(3) = 2 * 8 + 3 = 19 // correct``````

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

``````public class GenerateStringsOneBTwoConsecutiveC
{
public static void main(String[] args)
{
generate(new StringBuilder(""), 50, 0);
}

public static void generate(StringBuilder sb, int len, int numB)
{
if (numB >= 2)
{
return;
}

int strLen = sb.length();
if (strLen >= 3 && sb.charAt(strLen - 1) == 'c' &&
sb.charAt(strLen - 2) == 'c' && sb.charAt(strLen - 3) == 'c')
{
return;
}

if (strLen >= len)
{
System.out.println(sb);
return;
}

//A
generate(sb.append('a'), len, numB);
sb.deleteCharAt(sb.length() - 1);

//B
generate(sb.append('b'), len, numB + 1);
sb.deleteCharAt(sb.length() - 1);

//C
generate(sb.append('c'), len, numB);
sb.deleteCharAt(sb.length() - 1);
}
}``````

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

``````public class GenerateStringsOneBTwoConsecutiveC
{
public static void main(String[] args)
{
generate(new StringBuilder(""), 50, 0);
}

public static void generate(StringBuilder sb, int len, int numB)
{
if (numB >= 2)
{
return;
}

int strLen = sb.length();
if (strLen >= 3 && sb.charAt(strLen - 1) == 'c' &&
sb.charAt(strLen - 2) == 'c' && sb.charAt(strLen - 3) == 'c')
{
return;
}

if (strLen >= len)
{
System.out.println(sb);
return;
}

//A
generate(sb.append('a'), len, numB);
sb.deleteCharAt(sb.length() - 1);

//B
generate(sb.append('b'), len, numB + 1);
sb.deleteCharAt(sb.length() - 1);

//C
generate(sb.append('c'), len, numB);
sb.deleteCharAt(sb.length() - 1);
}
}``````

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

``````public class GenerateStringsOneBTwoConsecutiveC
{
public static void main(String[] args)
{
generate(new StringBuilder(""), 50, 0);
}

public static void generate(StringBuilder sb, int len, int numB)
{
if (numB >= 2)
{
return;
}

int strLen = sb.length();
if (strLen >= 3 && sb.charAt(strLen - 1) == 'c' &&
sb.charAt(strLen - 2) == 'c' && sb.charAt(strLen - 3) == 'c')
{
return;
}

if (strLen >= len)
{
System.out.println(sb);
return;
}

//A
generate(sb.append('a'), len, numB);
sb.deleteCharAt(sb.length() - 1);

//B
generate(sb.append('b'), len, numB + 1);
sb.deleteCharAt(sb.length() - 1);

//C
generate(sb.append('c'), len, numB);
sb.deleteCharAt(sb.length() - 1);
}``````

}

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

``````public class StringPermute {
public static void main(String... args) {
int[] result= new int[]{0};
find("",0,0,3, result);
System.out.println(result);
}

static void find(String s, int countb, int countc, int n, int[] result) {
if (n == 0) {
result++;
return;
}

for (char c: "abc".toCharArray()) {
int newCountb = countb;
int newCountc = countc;
if (c =='b') newCountb ++;
if (c == 'c') newCountc++;
else newCountc = 0;

if (newCountb > 1) continue;
if (newCountc == 3) continue;

find(s + c, newCountb, newCountc, n-1, result);
}
}
}``````

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

public class StringPermute {
public static void main(String... args) {
int[] result= new int[]{0};
find("",0,0,3, result);
System.out.println(result);
}

static void find(String s, int countb, int countc, int n, int[] result) {
if (n == 0) {
result++;
return;
}

for (char c: "abc".toCharArray()) {
int newCountb = countb;
int newCountc = countc;
if (c =='b') newCountb ++;
if (c == 'c') newCountc++;
else newCountc = 0;

if (newCountb > 1) continue;
if (newCountc == 3) continue;

find(s + c, newCountb, newCountc, n-1, result);
}
}
}

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

It is permutation problem with conditions.

The number of permutations which contain 2 c's is n*(n-1).
The number of permutations which contain 1 b's and 1 c's is n*(n-1) + n
The number of permutations which does not contain c is n-1
The number of permutations which does not contain b is n-1

Adding all these we get the formula 2(n^2) + n - 2.

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

This is a permutation problem with conditions.

The number of permutations with 2 c's is n*(n-1)
The number of permutations with 1 b and 1 c is n*(n-1) + n
The number of permutations with 1 c is n
The number of permutations with no b and no c is 1.

Adding all these we get the formual 2(n^2) + 1

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

- Basic logic is to create permutation set but just add the additional condition given to avoid those possibilities of consecutive more than 2 'c' and allow only one instance of 'b'.

public class PermutationSpecial {
public int count = 0;
void permutationSet(StringBuilder strBuilder, String str, int index, HashMap<Character, Integer> soFarMap) {
if (index == strBuilder.length()) {
System.out.println(strBuilder.toString());
count++;
return;
}

for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == 'b' && soFarMap.containsKey('b')) {
continue;
}

if (str.charAt(i) == 'c' && (index > 1 && strBuilder.charAt(index - 1) == 'c'
&& strBuilder.charAt(index - 2) == 'c')) {
continue;
}

strBuilder.setCharAt(index, str.charAt(i));

// add the hashset to allow to look back.
if (soFarMap.containsKey(str.charAt(i)) != true) {
soFarMap.put(str.charAt(i), 1);
} else {
soFarMap.put(str.charAt(i), soFarMap.get(str.charAt(i)) + 1);
}

permutationSet(strBuilder, str, index + 1, soFarMap);

if (soFarMap.get(str.charAt(i)) == 1) {
soFarMap.remove(str.charAt(i));
} else {
soFarMap.put(str.charAt(i), soFarMap.get(str.charAt(i)) - 1);
}
}
}

public static void main(String [] args) {
PermutationSpecial permutationSpecial = new PermutationSpecial();
String str = new String("abc");
StringBuilder strBuilder = new StringBuilder(3);
strBuilder.append('a');
strBuilder.append('b');
strBuilder.append('c');
HashMap<Character, Integer> soFarMap = new HashMap<>();
permutationSpecial.permutationSet(strBuilder, str, 0, soFarMap);
System.out.println(permutationSpecial.count);

}
}

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

Resubmitting with code brackets.

``````/**
* Created by dhavalp on 9/1/16.
*/
public class PermutationSpecial {
public int count = 0;
void permutationSet(StringBuilder strBuilder, String str, int index, HashMap<Character, Integer> soFarMap) {
if (index == strBuilder.length()) {
System.out.println(strBuilder.toString());
count++;
return;
}

for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == 'b' && soFarMap.containsKey('b')) {
continue;
}

if (str.charAt(i) == 'c' && (index > 1 && strBuilder.charAt(index - 1) == 'c'
&& strBuilder.charAt(index - 2) == 'c')) {
continue;
}

strBuilder.setCharAt(index, str.charAt(i));

// add the hashset to allow to look back.
if (soFarMap.containsKey(str.charAt(i)) != true) {
soFarMap.put(str.charAt(i), 1);
} else {
soFarMap.put(str.charAt(i), soFarMap.get(str.charAt(i)) + 1);
}

permutationSet(strBuilder, str, index + 1, soFarMap);

if (soFarMap.get(str.charAt(i)) == 1) {
soFarMap.remove(str.charAt(i));
} else {
soFarMap.put(str.charAt(i), soFarMap.get(str.charAt(i)) - 1);
}
}
}

public static void main(String [] args) {
PermutationSpecial permutationSpecial = new PermutationSpecial();
String str = new String("abc");
StringBuilder strBuilder = new StringBuilder(3);
strBuilder.append('a');
strBuilder.append('b');
strBuilder.append('c');
HashMap<Character, Integer> soFarMap = new HashMap<>();
permutationSpecial.permutationSet(strBuilder, str, 0, soFarMap);
System.out.println(permutationSpecial.count);

}
}``````

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

It can be solved by 2 process.
1) split to 2 strings by possible position of 'b'
2) strings with 'a' and 'c' with no more than 2 consecutive 'c's

1)
When length = 3
Possible b positions are
1. no b ___
2. b at 0 b__
3. b at 1 _b_
4. b at 2 __b
So the answer is 1 + 2 + 3 + 4 where __ is a string consist by 'a' and 'c' with no more than 2 consecutive 'c's.

2) For given string s
let x = # of permutations
let y = # of permutations ended with 'ac' (or 'c')
let z = # of permutations ended with 'cc'
and let
x0 = 0
y0 = 0
z0 = 0
and
x1 = 2 ("a", "c")
y1 = 1 ("c")
z1 = 0

Then
xn+1, yn+1, zn+1 can be defined as
xn+1 = (xn * 2) - zn
yn+1 = xn - zn
zn+1 = yn - zn

So the final answer is when length is 3
x3 + (x0 + x2) + (x1 + x1) + (x2 + x0)
7 + 4 + 4 + 4 = 19.

Complexity is O(n).

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

I did submit

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

``````int count (String s, int l, int consecutiveC, boolean bUsed, int n) {
if(l == n ) {
System.out.println(s);
return 1;
}
int c1 =0;
int c2 = 0;
int c3 =0;
//use 'a'
c1 = count(s+'a', l+1, 0, bUsed, n);
if(consecutiveC < 2) {
// use 'c'
c2 = count(s+'c', l+1, consecutiveC+1, bUsed, n );
}
if(!bUsed) {
// use 'b'
c3 = count(s+'b', l+1, 0, true, n);
}

return c1+c2+c3;
}``````

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

``````public static int count(int n) {
// total, not excluding more than 2 consecutive c's
int t = (int)Math.pow(2, n-1) * (2 + n);

// remove all consecutive c's of count 3 or more. Each time
// there are (n-t) + 1 possibilities of t consecutive c's, and
// in the rest of the positions, there can be at most 0 or 1 b (rest are a's)
// so its (n-t+1) options again, so multiply.
for(int i = n-2; i >= 1; i--) {
t -= (i * i);
}

return t;
}``````

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

``````public static int count(int n) {
// total, not excluding more than 2 consecutive c's
int t = (int)Math.pow(2, n-1) * (2 + n);

// remove all consecutive c's of count 3 or more. Each time
// there are (n-t) + 1 possibilities of t consecutive c's, and
// in the rest of the positions, there can be at most 0 or 1 b (rest are a's)
// so its (n-t+1) options again, so multiply.
for(int i = n-2; i >= 1; i--) {
t -= (i * i);
}

return t;
}``````

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

``````public static void Permutations(string prefix, int n, bool bUsedEarlier, bool cExhaustedEarlier, ref int count)
{
char[] chars = { 'a', 'b', 'c' };

if (n == 0)
{
Console.WriteLine(prefix);
count++;
return;
}

foreach (var @char in chars)
{
if (@char == 'b' && bUsedEarlier)
continue;

if (@char == 'c' && cExhaustedEarlier)
continue;

var bUsed = bUsedEarlier || @char == 'b';
var cExhausted = cExhaustedEarlier || prefix.Length > 0 && prefix[prefix.Length - 1] == 'c' && @char == 'c';

Permutations(prefix + @char, n - 1, bUsed, cExhausted, ref count);
}
}

public static void StringTest()
{
int count = 0;
Permutations("", 4, false, false, ref count);
Console.WriteLine("Count of Permutations: " + count);
}``````

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

Simple/Naive C recursive code:

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void code(char* arr, char* st, char* ret, int b, int c){
static int cnt = 0;
int len = strlen(ret);

if(!(*ret)){
cnt++;
printf("%d: %s \n", cnt, st);
return;
}

for(int i=0; i<sizeof(arr); i++){
if(i == 0){
ret = arr[i];
int x = (c==0)?2:c;
code(arr, st, ret+1, b, x);
}
if(i == 1 && b != 0){
ret = arr[i];
int x = (c==0)?2:c;
code(arr, st, ret+1, 0, x);

}
if(i == 2 && c != 0){
ret = arr[i];
int x = (c==0)?2:c;
code(arr, st, ret+1, b, c-1);
}
}

}

int main()
{
char arr[] = {'a', 'b', 'c'};
int size = 3;
char* ret = malloc(sizeof(char)*size+1);
*(ret+sizeof(char)*size+1) = '\n';
char* st = ret;
memset(st, 'x', size);

code(arr, st, ret, 1, 2);

return 0;
}``````

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

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void code(char* arr, char* st, char* ret, int b, int c){
static int cnt = 0;
int len = strlen(ret);

if(!(*ret)){
cnt++;
printf("%d: %s \n", cnt, st);
return;
}

for(int i=0; i<sizeof(arr); i++){
if(i == 0){
ret = arr[i];
int x = (c==0)?2:c;
code(arr, st, ret+1, b, x);
}
if(i == 1 && b != 0){
ret = arr[i];
int x = (c==0)?2:c;
code(arr, st, ret+1, 0, x);

}
if(i == 2 && c != 0){
ret = arr[i];
int x = (c==0)?2:c;
code(arr, st, ret+1, b, c-1);
}
}

}

int main()
{
char arr[] = {'a', 'b', 'c'};
int size = 3;
char* ret = malloc(sizeof(char)*size+1);
*(ret+sizeof(char)*size+1) = '\n';
char* st = ret;
memset(st, 'x', size);

code(arr, st, ret, 1, 2);

return 0;
}``````

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

Using dynamic programming and writing the sequence taking one type of word at a time and adding other starting from a and following row sequence: a,c,b I found the pattern:
0 1 2 3 4 5 6
a 1 1 1 1 1 1 1
c 1 2 4 7 13 24 44
b 1 3 8 19 43 94 200

``````def numberofPermutations(n):
n=n+1
arr1=*n
arr2=*n
arr1=1
arr1=2
arr1=4
arr2=1
if n>2:
for i in xrange(3,n):
# The second column specifying a bag of a and c, follows tribonacci sequence so if only a and c: the number can be given by the second row
arr1[i]=arr1[i-1]+arr1[i-2]+arr1[i-3]

for j in xrange(1,4):
# The third column specifying a bag of a,c and b follows this sequence given below till a range upto n=3
arr2[j]=arr1[j]+j*arr1[j-1]
for j in xrange(4,n):
# The third column specifying a bag of a,c and b follows this sequence given below till for n>3
arr2[j]=arr1[j-1]+arr1[j-2]+arr1[j-3]+arr2[j-1]+arr2[j-2]+arr2[j-3]
return arr2[-1] #return last element of array``````

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

def make(n, curstr, bb, cc, result):

if len(curstr) == n:
result.append(curstr)
return

for c in "abc":

if bb and c == "b": continue
if cc and c == 'c': continue

make(n, curstr+c, 1 if c == 'b' else bb, (curstr and curstr[-1] == 'c' and c == 'c'), result)

def make_comb(n):
if not n: return

result = []
make(n, "", 0, 0, result)
return result

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

``````def make(n, curstr, bb, cc, result):

if len(curstr) == n:
result.append(curstr)
return

for c in "abc":

if bb and c == "b": continue
if cc and c == 'c': continue

make(n, curstr+c, 1 if c == 'b' else bb, (curstr and curstr[-1] == 'c' and c == 'c'), result)

def make_comb(n):
if not n: return

result = []
make(n, "", 0, 0, result)
return result``````

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

``````def make(n, curstr, bb, cc, result):

if len(curstr) == n:
result.append(curstr)
return

for c in "abc":

if bb and c == "b": continue
if cc and c == 'c': continue

make(n, curstr+c, 1 if c == 'b' else bb, (curstr and curstr[-1] == 'c' and c == 'c'), result)

def make_comb(n):
if not n: return

result = []
make(n, "", 0, 0, result)
return result``````

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

findstring(n) = findstring_ac(n) + n * findstring_ac(n-1)
where findstring_ac(n) is number of strings consists only of a and c, not b

And
findstring_ac(n) = fa(n) + fc(n) + fcc(n)
where
fa(n) is number of strings consists of a, c and ends with a
fc(n) is number of strings consists of a, c and ends with only one c
fcc(n) is number of strings consists of a, c and ends with double c
and
fa(1) = fc(1) = 1
fcc(1) = 0
fa(n) = fa(n-1) + fc(n-1) + fcc(n-1)
fc(n) = fa(n-1)
fcc(n) = fc(n-1)

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

``````static int count(int n) {
if (n <= 0)
return 0;

int aNoB = 1;
int cNoB = 1;
int ccNoB = 0;
int aHasB = 0;
int cHasB = 0;
int ccHasB = 0;
int endWithB = 1;

for (int i = 2; i <= n; i++) {
int new_aNoB = aNoB + cNoB + ccNoB;
int new_cNoB = aNoB;
int new_ccNoB = cNoB;
int new_aHasB = aHasB + cHasB + ccHasB + endWithB;
int new_cHasB = aHasB + endWithB;
int new_ccHasB = cHasB;
int new_endWithB = aNoB + cNoB + ccNoB;

aNoB = new_aNoB;
cNoB = new_cNoB;
ccNoB = new_ccNoB;
aHasB = new_aHasB;
cHasB = new_cHasB;
ccHasB = new_ccHasB;
endWithB = new_endWithB;
}

return aNoB + cNoB + ccNoB + aHasB + cHasB + ccHasB + endWithB;
}``````

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

``````// ZoomBA
n = 3
\$count = 0
args = list( [0:n] ) -> { [ 'a' ,'b' ,'c' ] }
join ( @ARGS = args ) :: {
s = str( \$.item, '')
continue ( s !~ '[^b]*(b)?[^b]*' || s =~ '.*ccc.*' )
\$count += 1 // add up
false
}
println( \$count )``````

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

Assume n >= 4

Let R(n) = # of allowed strings of length n
T(n) = # of allowed strings of length n with no 'b's
T(n, aa) = # of allowed strings of length n with no 'b's which end in 'aa.'
Similarly define T(n, ac), T(n, ca), and T(n, cc).

Firstly, note T(n) = T(n, aa) + T(n, ac) + T(n, ca) + T(n, cc).
Secondly, looking at prefixes, we notice a recursion

T(n, cc) = T(n-2, aa) + T(n-2, ca)
T(n, ca) = T(n-2, aa) + T(n-2, ac) + T(n-2, ca)
T(n, ac) = T(n-2, aa) + T(n-2, ac) + T(n-2, ca) + T(n-2, cc)
T(n, aa) = T(n-2, aa) + T(n-2, ac) + T(n-2, ca) + T(n-2, cc)

Using dynamic programming, we can do this from bottom up. We already know T(2, aa), T(2, ac), T(2, ca), T(2, cc), T(3, aa), T(3, ac), T(3, ca), T(3, cc), so we can get T(n, aa), T(n, ac), T(n, ca), T(n, cc) for all n >= 4. Then we sum up those 4 values to get T(n).

Now, let's worry about the 'b's. Notice that a 'b' would cleave a string, one of them length k and the other one length n-1-k for some 0 =< k =< n-1. So there are T(k)*T(n-1-k) allowed strings of length n with 'b' in position k (beginning at 0). Thus we get

R(n) = T(n) + Sum(T(k)*T(n-1-k), k = 0 to n-1)

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

Trie + DFS

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

A working Python solution.

``````def longest_palindrome(string):
# count how many times each char shows up
count = {}
for char in string:
if char in count:
count[char] += 1
else:
count[char] = 1
# if there are multiple odds, leave only one odd
odd_appeared = False
odd_char = ""
for key in count:
if count[key] % 2 == 1:
if odd_appeared:
count[key] -= 1
else:
odd_appeared = True
odd_char = key
# go through the dictionary and reconstruct the palindrome string
palindrome = ""
for key in count:
chars = count[key]/2 * key
palindrome = palindrome + chars
palindrome = chars + palindrome
if odd_appeared:
n = len(palindrome)
palindrome = palindrome[:n/2] + odd_char + palindrome[n/2:]
return palindrome

print longest_palindrome('ttaatta')
print longest_palindrome('abc')
print longest_palindrome('aha')
print longest_palindrome('a')
print longest_palindrome('')``````

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

Sorry the last post was for a different problem. Here's the working solution in Python.

``````result = []
def findStrings(n):
if n == 0:
return
if n == 1:
result = ['a','b','c']
# initalize result list and two counts
current_string = ""
count_b = 0
count_c_seq = 0
# throw the values into the recusion
findStringsHelper(current_string,count_b,count_c_seq,n)
return

def findStringsHelper(current_string,count_b,count_c_seq,n):
if len(current_string) >= n:
result.append(current_string)
else:
findStringsHelper(current_string+"a",count_b,0,n)
if count_b == 0:
findStringsHelper(current_string+"b",count_b+1,0,n)
if count_c_seq < 2:
findStringsHelper(current_string+"c",count_b,count_c_seq+1,n)
findStrings(2)
print result
print len(result)``````

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

``````"""
a     c      cc     with b
0 ->  0     0      0      0
1 ->  1     1      0      1
2 ->  2     1      1      1(a + c + cc)*2
3 ->  4     2      1      2*(1(a + c + cc)+ 2(a + c + cc)*0(a + c + cc))
4 ->  7     4      2
5 -> 13     7      4
"""
def total_perms(n):
if n == 0:
return 0
if n == 1:
return 3

dp = [None]*(n+1)
s0 = (0, 0, 0)
s1 = (1, 1, 0)
dp = (s0, 1)
dp = (s1, sum(s1))

for i in xrange(2, n+1):
temp = (dp[i-1], dp[i-1], dp[i-1])
dp[i] =  (temp, sum(temp))

perms = dp[-1]
for i in xrange(n):
perms += dp[i]*dp[n-1-i]
return perms

print total_perms(4)``````

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

if n==1 print(3)
else print( 2n + n*(n-1) + n*(n-1C2) + nC2 + 1)

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

{
int abc_counter(int n) {
return n * n + (n - 1) * (n - 1) + (n + 1);
}
}

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

I'm pretty sure this one can be O(lg N) and O(1) via divide and conquer and dynamic programming, but the code seems like it would be very complicated.
(Basically, try all possible middle 2 or 3 characters so sides are each exactly floor((N-2)/2) long; this makes all recursive calls go to the same value of N so call tree is lg N height; only # of 3's on right * # of 3's on left * b allowed = 3*3*2 = 18 calls need to be memo-ized for each used value of N.)

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

I'm pretty sure this one can be O(lg N) and O(1) via divide and conquer and dynamic programming, but the code seems like it would be very complicated.
(Basically, try all possible middle 2 or 3 characters so sides are each exactly floor((N-2)/2) long; this makes all recursive calls go to the same value of N so call tree is lg N height; only # of 3's on right * # of 3's on left * b allowed = 3*3*2 = 18 calls need to be memo-ized for each used value of N.)

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

DP seems to be an overkill for this.
O(1) runtime, O(1) space

``````int findStrings(int n)
{
int res = 0;

// 0 'c's
res += 1; // 0 'b's
res += n; // 1 'b' in each position

// 1 'c's
res += 1 * n; // 0 'b's, 1 'c' in n pos
res += (n - 1) * n; // 1 'b' in n-1 pos, 1 'c' in n pos

// 2 'c's, (nk) pos
res += 1 * ((n - 1) * n / 2); // 0 'b's, 2 'c's in (nk) pos
res += (n - 2) * (n * (n - 1) /2); // 1 'b' in n-2 pos, 2 'c's in (nk) pos

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