Google Interview Question


Country: United States
Interview Type: In-Person




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

f1(n) is the number of strings with the last two char same;
f2(n) is the number of strings with the last two char different;
f1(n)=f1(n-1)+f2(n-1);
f2(n)=2*f1(n-1)+f2(n-1);
f1(2)=3;
f2(2)=6;

- xuzhiwen1024 November 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is correct I think - I came to exactly the same solution. The remaining question is, if we can with a bit of magic make a nonrekurent formula a compute it in constatn time :-)

- tpcz November 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

O(log n) (arithmetic operations) can be done (view as matrix multiplication).

O(1)? unlikely, as the result would be exponential (have to compute x^n).

- Subbu. November 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Its simple 3^n - 6×(n-2)!

- yo yo honey singh November 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@yo yo honey singh: Can you please explain how you got that formula?

- Anonymous December 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sure. If f1 and f2 are defined as above. f1(n) can be derived from string of length n-1, with last two char the same and not the same. For the last two char the same for n-1 length string, if the resulted last two char are the same, that constrains the last char of n length to be only one option. For string of length n-1, with last two char different, the resulting n length string with the last two char the same also constrains the last char of n length to be only one option. Therefore, f1(n)=f1(n-1)+f2(n-1).

Similarly, f2(n)=2*f1(n-1)+f2(n-1), since if we start from n-1 length string with last two char the same, we can have two options for the last char of n length string. If we start from n-1 length string with last two char different, we only have one option for the last char of n length string.

- xuzhiwen1024 January 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@yo yo honey singh: your formula does not work for n=4. I think the right one is: 3^n - [3^(n - 3)] * (n - 2) * 3!

- dan January 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

f1(n) is the number of strings with the last two char same;
f2(n) is the number of strings with the last two char different;
f1(n)=f1(n-1)+f2(n-1);------------------1
f2(n)=2*f1(n-1)+f2(n-1);----------------2
f1(2)=3;
f2(2)=6;


Now,
f(n)=f1(n)+f2(n)
=>f(n-1)=f1(n-1)+f2(n-1)=f1(n)=========from 1------------3

=>f(n)=f(n-1)+f2(n)
=>f(n)=f(n-1)+2*f1(n-1)+f2(n-1)=======from 2
=>f(n)=f(n-1)+(f1(n-1)+f2(n-1))+f1(n-1)
=>f(n)=f(n-1)+f(n-1)+f1(n-1)
=>f(n)=f(n-1)+f(n-1)+f(n-2)
=>f(n=)2*f(n-1)+f(n-2)

Also,
f(2)=f1(2)+f2(2)=3+6=9
f(1)=f1(2)=3

This final solution is f(n)=2*f(n-1)+f(n-2), f(1)=3, f(2)=9

- Deepak November 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the problem can be solved using RabinKarp Algorithm,
Here is the code.
Please tell me if I have done any error.

package com.algorithm.string.pattern.search;

import java.util.Arrays;

public class RabinKarpApplication {

	public int hashValue(String input, int start, int end) {
		int temp = 0;
		char[] inputarr = input.toCharArray();
		for (int i = 0; i < end; i++) {
			temp += inputarr[i];
		}
		return temp;
	}

	boolean checkEquality(char[] source, char[] desti){
		Arrays.sort(source);
		Arrays.sort(desti);
		for(int i=0 ;i< source.length;i++){
			if(source[i] != desti[i]){
				return false;
			}
		}
		return true;
	}

	public boolean matchPattern(String source, String pattern) {
		int patternHashValue = hashValue(pattern, 0, pattern.length());
		int sourceHashValue = hashValue(source, 0, pattern.length());
		if (sourceHashValue == patternHashValue) {
			if(checkEquality(source.substring(0, pattern.length()).toCharArray(), pattern.toCharArray())){
				return true;
			}
		}

		char[] sourcearray = source.toCharArray();
		for (int i = pattern.length() ; i < sourcearray.length; i++) {
			sourceHashValue = sourceHashValue -  sourcearray[i - pattern.length()] + sourcearray[i];
			if(sourceHashValue == patternHashValue){
				if(checkEquality(source.substring(i-pattern.length()+1, i+1).toCharArray(), pattern.toCharArray())){
					return true;
				}
			}
		}

		return false;
	}

	public static void main(String[] args) {
		RabinKarpApplication rkapps = new RabinKarpApplication();
		String source = "bcabbcde";
		String pattern = "abc";
		if(rkapps.matchPattern(source, pattern)){
			System.out.println("Invalid");
		}else{
			System.out.println("Valid");
		}
	}
}

- Rudra November 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

is your hash function valid for Rabin-Karp algorithm?

By the way problem is different, you are given Alphabet A={a,b,c}, generate a sequence of strings in which characters a, b and c are not adjacent to each other

- confused_banda November 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think you need to output number of possible solutions.

- Orkhan November 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

wht abt checking whether abc#bac#cab#cba#acb#bca and generated string have a common substring ..if not then valid otherwise invalid..

- @@@@@@@ November 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

i mean substring of length 3.

- @@@@@@@ November 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use Dynamic Programming , Let define T[n,'ab'] be the number of valid strings of length n which starts with 'ab', in the same way we can define T[n,'bc'], T[n,'aa'], T[n,'ba'] .... Then T[n,'ab'] = T[n-2,'bc]+T[n-2,'ba']+T[n-2,'bb]+T[n-2,'aa']+T[n-2,'ac']+T[n,'ab']
in the same way we can calculate for the rest for n = 2 and n=3 which are the base cases we can calculate them easily, The running time would be O(n) and the storage space is O(n) too

- HoneyBall November 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This looks right, if the question it to count the total number (and it seems to be that, other folks seem to have misread).

- Anonymous November 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The question asks to "output the amount of all possible strings", so I haven't quite answered that below; rather, I've outputted all possible strings. I believe this solution is essentially what HoneyBall was describing.

def emitStrings(stringSoFar, N, strings) :
	length = len(stringSoFar)
	if length is N : return

	validChars = ['a','b','c']

	if length >= 2 :
		# To figure out whether we have consecutive characters, we try
		# removing the last two characters from a copy of validChars. If we
		# were able to remove 'char2', then we have a combination like "ab",
		# and we must remove "c" from validChars.
		validChars2 = validChars[:]
		char1 = stringSoFar[length - 1]
		char2 = stringSoFar[length - 2]

		validChars2.remove(char1)
		if char2 in validChars2 :
			validChars2.remove(char2)

			# There's only one left now.
			validChars.remove(validChars2[0])

	for char in validChars :
		if length is N - 1 :
			strings.append(stringSoFar + char)
		emitStrings(stringSoFar + char, N, strings)

def main():
	strings = []
	emitStrings('', 8, strings)
	print strings

if __name__ == '__main__':
	main()

Output:

['aaaaa', 'aaaab', 'aaaac', 'aaaba', 'aaabb', 'aaaca', 'aaacc', 'aabaa', 'aabab', 'aabba', 'aabbb', 'aabbc', 'aacaa', 'aacac', 'aacca', 'aaccb', 'aaccc', 'abaaa', 'abaab', 'abaac', 'ababa', 'ababb', 'abbaa', 'abbab', 'abbba', 'abbbb', 'abbbc', 'abbcb', 'abbcc', 'acaaa', 'acaab', 'acaac', 'acaca', 'acacc', 'accaa', 'accac', 'accbb', 'accbc', 'accca', 'acccb', 'acccc', 'baaaa', 'baaab', 'baaac', 'baaba', 'baabb', 'baaca', 'baacc', 'babaa', 'babab', 'babba', 'babbb', 'babbc', 'bbaaa', 'bbaab', 'bbaac', 'bbaba', 'bbabb', 'bbbaa', 'bbbab', 'bbbba', 'bbbbb', 'bbbbc', 'bbbcb', 'bbbcc', 'bbcbb', 'bbcbc', 'bbcca', 'bbccb', 'bbccc', 'bcbba', 'bcbbb', 'bcbbc', 'bcbcb', 'bcbcc', 'bccaa', 'bccac', 'bccbb', 'bccbc', 'bccca', 'bcccb', 'bcccc', 'caaaa', 'caaab', 'caaac', 'caaba', 'caabb', 'caaca', 'caacc', 'cacaa', 'cacac', 'cacca', 'caccb', 'caccc', 'cbbaa', 'cbbab', 'cbbba', 'cbbbb', 'cbbbc', 'cbbcb', 'cbbcc', 'cbcbb', 'cbcbc', 'cbcca', 'cbccb', 'cbccc', 'ccaaa', 'ccaab', 'ccaac', 'ccaca', 'ccacc', 'ccbba', 'ccbbb', 'ccbbc', 'ccbcb', 'ccbcc', 'cccaa', 'cccac', 'cccbb', 'cccbc', 'cccca', 'ccccb', 'ccccc']

- Adam November 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

As there are N spaces available and we have 3 unique things to choose from so to print all different combinations we have only one choice 3*3*3*3*3 (no of iterations)
But we got no other choice.
However if we don't want sequence then we can simply ignore the cases in which we get a sequence.

Here is the code:

void allPossibleStrings(char *a, char *b, int len, int n, int k)
{
	int i=0, j=0;

	for(i=0; i<len; i++)
	{
		if(k < n)
		{
			b[k] = a[i];
			if(k >= len-1)
			{
				if(hasAllElements(b+k-len+1, len))
				{					
					continue;		
				}
			}
			allPossibleStrings(a,b,len,n,k+1);
		}
		else
		{
			printf("\n");
			for(j=0; j<n; j++)
			{
				printf("%c,",b[j]);
			}
			break;
		}
	}
}

The function hasAllElements() will check if b has all the elements that are in array a (which basically checks all kinds of sequence).
This code i have written is a general form.

- Alok November 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The function can be called like this:

char a[] = {'a','b','c'};
	char b[N];

	allPossibleStrings(a, b, 3, N, 0);
	return 0;

- Alok November 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

You got it almost right, the problem needs no programming. A simple counting can do.

3^5 - 3*3! = 225 is the answer.
3^5 for all the possible combinations of a,b & c in a 5-letter string.
3 is for the possible number of consecutive locations for 3 elements. (1,2,3) (2,3,4) and (3,4,5) are the 3 possibilities for consecutive locations of 3 elements in 5 places.
3! is the for the permutation of (a,b,c) in the 3 consecutive locations identified above.

- Murali Mohan November 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@Erasmus. It is not 225. for n = 3 it is 123. The formula doesn't seem to be right

- Anonymous December 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Erasmus is right.
For n=3, following above 'correct' formula - f(n)=2*f(n-1)+f(n-2), f(1)=3, f(2)=9
f(3) = 2 * 9 + 3
f(3) = 21

According to permutation logic-
1 2 3 - 3 places, 3 characters - total 3^3 = 27 permutations.
unwanted permutations - 1 2 3 having a b c -> 1 location possible. a b c can be permuted amongst each other at positions [1 2 3] in (nPr ways) - 3P3 ways = 3!

final ans = Total permutations - unwanted permutations
final ans = 27 - 6
final ans = 21

- Roxanne January 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Considering that all the generated permutations of length N can have repeated characters then here is a simple solution written in Ruby:

def non_repeat_permutation(str)

  #min number of characters that should not get repeated e.g: min len {"ab", "abc", "abbca"...}
  min_repeat = 2

  # number of unique characters in the string e.g: {str = "aerfdcse"}, uniq_char_length = 7
  uniq_char_len = str.split("").uniq.length

  # number of unique characters that should not be present next to each other e.g: len {a ,b ,c}
  uniq_repeat_char_len = 3

  repeat_str_permutations = (uniq_repeat_char_len ** min_repeat) * (uniq_char_len ** (str.length - min_repeat))

  total_permutations = (uniq_char_len ** str.length)

  non_repeat_permutations = total_permutations - repeat_str_permutations
  puts non_repeat_permutations

end

non_repeat_permutation ARGV[0]

- codinator November 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

f(0)=0
f(1)=3
f(2)=9
f(n) = f(n-1) + 2*f(n-2) + 2*f(n-3) + ... + 2*f(4) + 24

- coder November 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void findSolutions(String word, int n) {
char[] letters = word.toCharArray();
int sum = getSum(letters);
findSolutions(letters, n, "", sum);
}


private static void findSolutions(char[] letters, int n, String result, int sum) {
if (result.length() > 2 && getSum(result.substring(result.length() - 3, result.length()).toCharArray()) == sum) {
return;
}
if (result.length() == n) {
System.out.println(result);
} else {
for (int i = 0; i < letters.length; i++) {
findSolutions(letters, n, result + letters[i], sum);
}
}
}

private static int getSum(char[] lookUp) {
int sum = 0;
for (int i = 0; i < lookUp.length; i++) {
sum += lookUp[i];
}
return sum;
}

- Using backtracking solution November 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use backtracking:

public static void findSolutions(String word, int n) {
		char[] letters = word.toCharArray();
		int sum = getSum(letters);
		findSolutions(letters, n, "", sum);
	}


	private static void findSolutions(char[] letters, int n, String result, int sum) {
		if (result.length() > 2 && getSum(result.substring(result.length() - 3, result.length()).toCharArray()) == sum) {
			return;
		}
		if (result.length() == n) {
			System.out.println(result);
		} else {
			for (int i = 0; i < letters.length; i++) {
					findSolutions(letters, n, result + letters[i], sum);
			}
		}
	}
	
	private static int getSum(char[] lookUp) {
		int sum = 0;
		for (int i = 0; i < lookUp.length; i++) {
			sum += lookUp[i];
		}
		return sum;
	}

- Orkhan November 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursive solution. If the last two characters are distinct we should use only them as the next character.

public static void print(int n) {
    print(n, "");
}

private static void print(int n, String s) {
    if (n == s.length()) {
        System.out.println();
        return;
    }
    
    Set<Character> validChars = new HashSet<>();
    //if last two characters are distinct, we should use only them as the next character
    if (s.length() > 1 && s.charAt(s.length() - 1) != s.charAt(s.length() - 2)) {
        validChars.add(s.charAt(s.length() - 1));
        validChars.add(s.charAt(s.length() - 2));
    } else {
        validChars.add('a');
        validChars.add('b');
        validChars.add('c');
    }
    
    for (Character c : chars) {
        print(n, s + c);
    }
}

- myk November 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

System.out.println(s);

- myk November 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Let a=0, b=1 and c=2. Let counts[m][i][j] be the number of valid strings with length m+1, and the last 2 characters being what i & j would correspond to. For instance, counts[1][0][2] would be the number of valid strings with length 2, where the last 2 characters are "a" and "c". In this case, there's only 1 such string so counts[1][0][2] would be 1. We can then use dynamic programming to fill up this multi-dimensional array to compute the number of valid strings of length N.

Below is my Java code for doing so. Note that it can be improved in at least 2 ways:
(1) Leverage the symmetry so instead of computing for all "a", "b" and "c", we only compute one of them and multiply result by 3.
(2) After calculating the new values for each iteration "m", we don't need all the old values at iteration "m-1" anymore. So we can reuse that array.

class ABC {
	static int combinations(int n) {
		if(n <= 2)
			return (int)Math.pow(3, n);
		int counts[][][] = new int[n][3][3];
		for(int i=0; i<3; i++) {
			for(int j=0; j<3; j++) {
				counts[1][i][j] = 1;
			}
		}

		for(int m=2; m<n; m++) {
			for(int i=0; i<3; i++) {
				for(int j=0; j<3; j++) {
					for(int k=0; k<3; k++) {
						if(compatible(i,j,k))
							counts[m][j][k] += counts[m-1][i][j];
					}
				}
			}
		}

		int total = 0;
		for(int i=0; i<3; i++) {
			for(int j=0; j<3; j++) {
				total += counts[n-1][i][j];
			}
		}
		return total;
	}

	static boolean compatible(int i, int j, int k) {
		int sum = i + j + k;
		return(sum != 3 || i == j || j == k || k == i);
	}

	public static void main(String[] args) {
		System.out.println(combinations(Integer.parseInt(args[0])));
	}
}

- Sunny November 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean check (String s) {
char ch[]=s.toCharArray();
boolean flag = true;
int clen= ch.length;
if (clen<3) { flag=false; }
// System.out.println("String length is " + clen);
for (int i=0;i<clen-2;i++)
{if (ch[i]!=ch[i+1] && ch[i]!=ch[i+2] && ch[i+1]!=ch[i+2])
{ return false; }
}
return true;
}


///is this code right?

- Amol November 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This question asks "the amount of", so the answer should be some value.
In here, I would like to show O(N) answer.

Let's define functions A,B and C

A(N) is the amount of all possible cases a string is consists of a, b, and c with length N
B(N) is the amount of all possbile cases a string is consists of a, b, and c with length N have consecutive a,b,c
C(N) is the amount of all possible strings of length N that don't of have consecutive a,b,c

A(N) = 3^N
B(N) = C(N-2) * Combination(N, 3)
= C(N-2) * (N ) * (N - 1)* (N - 2) / 3 * 2* 1

C(0) = 1
C(1) = 1
C(2) = 1
C(N) = A(N) - B(N)

We can caclurate C using DP.

long calcAmount(int N){
	assert N > 2;
	long[] dp = new long[N+1]; // 1 indexed
	dp[0] = 1;
	dp[1] = 1;
dp[2] = 1;
	for(long i = 3; i <= N; i++){
		dp[i] = (long) Math.pow(i, 3) - dp[i - 2] * i * (i - 1) * (i - 2) / 6L; 
}
return dp[N];
}

- kuroobi November 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Bonus points for reading the question.

- B November 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
char[] chars= {'a', 'b', 'c'};
int N = 5;
char[] ret = new char[N];
print(ret, chars, N, 0);
}

private static void print(char[] ret, char[] chars, int size, int idx) {
if (size == 0) {
for (int i = 0; i < ret.length; ++i)
System.out.print(ret[i]);
System.out.println();
return;
}

for (int i = 0; i < size; ++i) {
for (int j = 0; j < chars.length; ++j) {
ret[idx] = chars[j];
if (idx >= 2) {
Map<Character, Boolean> map = new HashMap<Character, Boolean>();
for (int k = idx - 2; k <= idx ; ++k) {
map.put(ret[k], true);
}
if (map.size() == chars.length) {
continue;
}
}
print(ret, chars, size - 1, idx + 1);
}
}
}

- luke lee November 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

First consider only the strings that begin with 'a'. We can build a tree with the number of valid strings (beginning with 'a') equal to the number of leaves in the tree. Start a tree with root 'a' and to this we can add 3 children 'a', 'b' and 'c'. To the child node 'a', we can attach children 'a','b' and 'c'. However, to the 'b' and 'c' children we can only attach 2 children. Continuing, this looks something like:

n = length of string;
S(n) = number of valid strings beginning with 'a';
a 									n=1, S(1) = 1
a | b | c 								n=2, S(2) = 3
a b c | a b | a c 						n=3, S(3) = 7
a b c | a b | a c | a b | a b c | a c | a b c		n=4, S(4) = 15
...									n=N, S(N) = 2*S(N-1)+1

The separators divide the child nodes amongst the parent notes. Namely, the number of groupings of nodes at depth n+1 should equal the number of nodes at height n. Note that we could create similar trees with roots 'b' and 'c' and the valid strings in each tree will be distinct (since they begin with different letters!). Therefore, the total number of valid strings of length N, call this T(N), is given by T(N)=3*S(N) which can be computed recursively.

Also note that this formula only computes the number of valid strings. To list the strings themselves simply store the trees. In fact, you only need to store the tree corresponding to 'a' and write a small algorithm that relabels the nodes appropriately.

- jayflo November 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry for the lack of formatting in the code.

Also, there should not be any separators in the depth n=2 nodes in the example of the tree.

- jayflo November 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually, the formula is incorrect...it should actually be

S(N)=2*(# nodes at height N-1 whose value does not equal their parent's) + 3*(# nodes at height N-1 whose value equals their parents)

- jarflores November 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think S(4) is 17:
aaaa
aaab
aaac
aaba
aabb
aaca
aacc
abaa
abab
abba
abbb
abbc
acaa
acac
acca
accb
accc

By now I have seen at least 4 ppl suggest this same formula. For n=4, this formula would return 3^4 - 6*2 = 69. That means there should be 23 strings as opposed to the 17 strings that I counted. Can someone confirm what's the answer for n=4?

- Sunny November 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is more of a mathematical problem than a programming one.

The general formula for the solution to this problem:
N= String length
x=number of unique letters

#valid Strings = x^N - (N-x)*(N-x+1)*x!

- arindam November 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#define HAS_A 1
#define HAS_B 2
#define HAS_C 4

#define HAS_NONE 0
#define HAS_ALL  (HAS_A | HAS_B | HAS_C )

#define CHAR2BIT(c) ((c) == 'a' ? HAS_A : ((c) == 'b' ? HAS_B : HAS_C))

static void
print_non_consec (int len, char *buf, char *ptr)
{
    char prev = HAS_NONE;
    char ch = 0;

    // check for illegal values (len 0, buf > ptr)
    assert(len);
    assert(buf <= ptr);
    // get the previous char and the previous-previous one
    // the order does not matter, so keep it in a bitmap
    if (ptr - buf >= 1) {
        prev |= CHAR2BIT(*(ptr-1));
    }
    if (ptr - buf >= 2) {
        prev |= CHAR2BIT(*(ptr-2));
    }
    // try add each char and check for non-consecutive requirement
    for (ch = 'a'; ch <= 'c'; ch++) {
        if ( (prev | CHAR2BIT(ch)) != HAS_ALL) {
        // if allowed, build the rest of the word recursively
            *ptr = ch;
            if (len > 1) {
                print_non_consec(len-1, buf, ptr+1);
        }    else { 
        // if reached the word end, print it
                *(ptr+1) = '\0';
                printf("%s\n",buf);
            }
        }
    }
}

- shin November 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is an O(N) solution for finding the *count* of acceptable strings. It calculates the count for strings of length up to N. It uses O(N) space, but it is trivial to bring the space to O(1). The way it is below, you can make lookups to countsameA and countdiffA vectors for different values of N.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    int N=50;
    vector<long> countsameA(N), countdiffA(N);

    // initialize the count vector for two same chars and two different chars
    countsameA[0] = 1;
    countdiffA[0] = 1;
    for (int i = 1; i<N; ++i){
        countsameA[i] = countsameA[i-1] + 2*countdiffA[i-1];
        countdiffA[i] = countsameA[i-1] + countdiffA[i-1];
    }
    
        long total = 3*countsameA[N-2] + 6*countdiffA[N-2];
        cout << N << " " << total << endl;
    
    return 0;
}

Generating all strings obeying the rule would require exponential complexity -- either via recursion or dynamic programming.

- murat November 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A recursion works but when you are adding the next character, you have to check for the "constraints". In this case, making sure that the last two character of the sequence are either equal or at least one of them equal to the new character you are adding.

public class AllStrings {    
        
    public static void PrintAll(int length) {        
        char_arr = new char[length];
        pos = 0;
        PrintSeq();
    }
    
    private static void PrintSeq() {
        if (pos == char_arr.length) {
            for (int i = 0; i < char_arr.length; i++)
                System.out.print(char_arr[i]);
            System.out.println();                        
        }
        else {
            if (IsValid('a')) {
                char_arr[pos++] = 'a';
                PrintSeq();
                pos--;
            }
            if (IsValid('b')) {
            char_arr[pos++] = 'b';
            PrintSeq();
            pos--;
            }
            if (IsValid('c')) {
                char_arr[pos++] = 'c';
                PrintSeq();
                pos--;
            }            
        }        
    }
    private static boolean IsValid(char a) {
        if (pos < 2)
            return true;
        else
            return !((a != char_arr[pos - 1]) && (a != char_arr[pos - 2]) && (char_arr[pos - 1] != char_arr[pos - 2]));
    }


    private static char[] char_arr;
    private static int pos = 0;
}

- Ehsan November 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a simple resursion will solve this

char str[1000];
int n;

void solve(int s , int n) {
	if(n==s) {
		str[s] = 0;
		printf("%s\n", str);
		return;
	}
	
	FOR(i,0,2) {
		if(s<=1) {
			str[s] = 'a' + i;
			solve(s+1,n);
		}
		else if('a'+i == str[s-1] || 'a'+i == str[s-2]){
			str[s] = 'a' + i;
			solve(s+1,n);		
		}
	}
}

int main() {
	scanf("%d", &n);
	solve(0,n);
	return 0;
}

- jitendra.theta November 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This seems like it is just a simple math question... I may be wrong but I think the way to solve this is to think of it like this:

If you had a string of abc without any constraints you would have 3^N possible strings
now with the constraints:
You have 3 options for the first spot in the string(abc), and then for each of the remaining slots(N-1) you have 2 options(the two letters you didn't use for the previous spot), so the formula should be 3*2^(N-1)

- Heyden December 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Consider string prefix "abb". You can append all 3 characters to it, so you have 3 options in this case.

- Sunny December 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

i think the correct formula will be
f(n)=2*f(n-1)+f(n-2)
f(1)=3
f(2)=6
here is the source code for displaying all strings

#include<stdio.h>
#include<stdlib.h>
void printString(char *str,int index,int n)
{
 if(index==n)
 {

  printf("\n %s",str);
   return;
  }
 if(index<2)
 {
  str[index]='a';
  printString(str,index+1,n);
 str[index]='b';
  printString(str,index+1,n);
 str[index]='c';
  printString(str,index+1,n);
}
else
{
 if(str[index-2]!=str[index-1])
 {
   str[index]=str[index-1];
   printString(str,index+1,n);
  str[index]=str[index-2];
   printString(str,index+1,n);
 }

else  
 {
   str[index]='c';
   printString(str,index+1,n);
  str[index]='b';
   printString(str,index+1,n);
 str[index]='a';
   printString(str,index+1,n);
 }

}

 


}
int main()
{
char str[50]={'\0'};
printString(str,0,2);

}

- Arunkumar Somalinga December 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void GenerateNonConsecutiveABC(int N, std::string &S,int State)
{
    static char ABC[3] = {'a','b','c'};
    static int SM[11][3] = 
    {
        {1,2,3}, //empty
        {1,4,5}, //a
        {6,2,7}, //b
        {8,9,3}, //c
        {6,2,10}, //ab
        {8,10,3}, //ac
        {1,4,10}, //ba
        {10,9,3}, //bc
        {1,10,5}, //ca
        {10,2,7}, //cb
        {10,10,10} //garbage
    };

    if(S.size() == N)
    {
        cout << S.c_str() << endl;
    }
    else
    {
        for(int i = 0; i < 3; i++)
        {
            if(SM[State][i] != 10)
            {
                S.push_back(ABC[i]);
                GenerateNonConsecutiveABC(N,S,SM[State][i]);
                S.pop_back();
            }
        }
    }
}

- shame_on_me December 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// This is javascript

function out1(w,x) {
	var z= {
		'aa' : 'a',
		'ab' : 'a',
		'ac' : 'a',
		'ba' : 'a',
		'bb' : 'a',
		'bc' : 'b',
		'ca' : 'a',
		'cb' : 'b',
		'cc' : 'a'
	}[w+x];

	return z;
}

function out2(w,x) {
	var z = {
		'aa' : 'c',
		'ab' : 'b',
		'ac' : 'c',
		'ba' : 'b',
		'bb' : 'c',
		'bc' : 'c',
		'ca' : 'c',
		'cb' : 'c',
		'cc' : 'c'
	}[w+x];

	return z;
}

function out3(w,x) {
	var z = {
		'aa' : 'b',
		'ab' : '',
		'ac' : '',
		'ba' : '',
		'bb' : 'b',
		'bc' : '',
		'ca' : '',
		'cb' : '',
		'cc' : 'b'
	}[w+x];

	return z;
}

function gen4( n, p1, p2, str ) {
	if ( n == 0 ) {
		gs.print(str);
	}
	else {
		var x = out1(p1, p2);
		var y = out2(p1, p2);
		var z = out3(p1, p2);

		gen4( n-1, p2, x, str + x);
		gen4( n-1, p2, y, str + y);

		if ( z ) {
			gen4( n-1, p2, z, str + z);
		}
	}
}

function gen3( n, p1, str ) {
	gen4( n-1, p1, 'a', str + 'a');
	gen4( n-1, p1, 'b', str + 'b');
	gen4( n-1, p1, 'c', str + 'c');
}

function gen1( n ) {
	gen3( n-1, 'a', 'a' );
	gen3( n-1, 'b', 'b' );
	gen3( n-1, 'c', 'c' );
}

gen1( 5 );

- Anonymous December 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Total Number of Strings possible: n1= 3^N
Strings With consecutive a,b& c : n2== 3^(N-3)* (3)! * (N-2)!
Strings without consecutive a,b& c : n3= n1-n2

- My_Solution December 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void FindStrings(String result, String str, int size) {
if (result.length() >= size) {
System.out.println(result);
}
else {
for (int i = 0; i < str.length(); i++) {
int nlen = result.length();

if (nlen >= 2)
{
if ((result.charAt(nlen - 1)+"").equals(str.charAt(i)+"") ||
(result.charAt(nlen - 2)+"").equals(str.charAt(i)+"") ||
(result.charAt(nlen - 1)+"").equals(result.charAt(nlen - 2)+""))
FindStrings(result + str.charAt(i), str, size);
}
else
FindStrings(result + str.charAt(i), str, size);
}
}
}

- John January 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

call: FindStrings("", "abc", 4);
results:
aaaa
aaab
aaac
aaba
aabb
aaca
aacc
abaa
abab
abba
abbb
abbc
acaa
acac
acca
accb
accc
baaa
baab
baac
baba
babb
bbaa
bbab
bbba
bbbb
bbbc
bbcb
bbcc
bcbb
bcbc
bcca
bccb
bccc
caaa
caab
caac
caca
cacc
cbba
cbbb
cbbc
cbcb
cbcc
ccaa
ccac
ccbb
ccbc
ccca
cccb
cccc

- John January 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

My code below does not have extensibility. When there are four kinds of distinct letters in str, it doesn't work.
public static int count( String s, int n ) {
int res = 0;
int start = 0;
Set<Character> past = new HashSet<Character>();
char prev = ' ';
char[] chars = s.toCharArray();
int i = 0;
for( ; i < chars.length; i++ ) {
char c = chars[i];
if( past.contains(c) && c == prev ) {
past.clear();
past.add( c );
} else if( !past.contains( c ) ){
past.add( c );
if( past.size() == 3 ) {
past.clear();
past.add( prev );
past.add( c );
if( i - n >= start )
res += ( i-n-start+1 );
start = i - 1;
}
}
prev = c;
}
res += ( i - n >= start ) ? ( i - n - start + 1 ) : 0;
return res;
}

- xuwithsurprise January 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If N is odd, ans = 3 * 7 ^ ((n-1)/2);

If N is even, ans = 51 * 7 ((n-4)/2);

- Venkat January 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If N is odd, ans = 3 * 7 ^ ((n-1)/2);

If N is even, ans = 51 * 7 ^ ((n-4)/2);

- Venkat January 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

i am thinking of generating all the strings of length N means generating all the string of length N by putting a ,b,c at various place of string and then when string size becomes N then check if it contains a,b,c consecutive or not.........
if not then print it

- pink November 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

f1(n) is the number of strings with the last two char same;
f2(n) is the number of strings with the last two char different;
f1(n)=f1(n-1)+f2(n-1);------------------1
f2(n)=2*f1(n-1)+f2(n-1);----------------2
f1(2)=3;
f2(2)=6;


Now,
f(n)=f1(n)+f2(n)
=>f(n-1)=f1(n-1)+f2(n-1)=f1(n)=========from 1------------3

=>f(n)=f(n-1)+f2(n)
=>f(n)=f(n-1)+2*f1(n-1)+f2(n-1)=======from 2
=>f(n)=f(n-1)+(f1(n-1)+f2(n-1))+f1(n-1)
=>f(n)=f(n-1)+f(n-1)+f1(n-1)
=>f(n)=f(n-1)+f(n-1)+f(n-2)
=>f(n=)2*f(n-1)+f(n-2)

Also,
f(2)=f1(2)+f2(2)=3+6=9
f(1)=f1(2)=3

This final solution is f(n)=2*f(n-1)+f(n-2), f(1)=3, f(2)=9

- Deepak November 27, 2013 | Flag


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