Google Interview Question for Software Engineer / Developers


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

- Munish September 13, 2016 | Flag Reply
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[1] = 2, A[2] = 4, A[3] = 7

We can compute matrix A iteratively.

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

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

        A[0] = 1, A[1] = 2, A[2] = 4, A[3] = 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];
}

- linuxchain September 30, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Evg March 05, 2020 | Flag
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))

- balaudt August 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Whats the time complexity? Isn't it exponential.

- anup August 14, 2016 | Flag
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;
	}

- Koustav August 10, 2016 | Flag Reply
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;

}

- Koustav August 10, 2016 | Flag Reply
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;
	}

- koustav.adorable August 10, 2016 | Flag Reply
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[0]
	}
	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
}

- a random foo August 10, 2016 | Flag Reply
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[0]
	}
	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
}

- cobookman August 10, 2016 | Flag Reply
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);
		return total;
	}

- divm01986 August 11, 2016 | Flag Reply
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

- MacCoder01 August 11, 2016 | Flag Reply
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[0][0][0] = 1
D[0][0][1] = 1
D[0][0][2] = 0
D[0][1][0] = 1
D[0][1][1] = 0
D[0][1][2] = 0

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

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

- Ben August 11, 2016 | Flag Reply
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[0][0][0] = 1
	D[0][0][1] = 1
	D[0][0][2] = 0
	D[0][1][0] = 1
	D[0][1][1] = 0
	D[0][1][2] = 0

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

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

- Ben August 11, 2016 | Flag Reply
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[0] for s in strings]

- bigohsmalloh August 12, 2016 | Flag Reply
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.)

- Mark August 14, 2016 | Flag Reply
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')) {
                    output.add(s);
                }
            }

        }
        return output;
    }

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

- seventhmoon August 14, 2016 | Flag Reply
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

- lukaszjagielski August 14, 2016 | Flag Reply
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)

- mikeyy174 August 16, 2016 | Flag Reply
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);
		return total;
	}

	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

			return total;
		}
		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);
			return total;
		}
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a = new ABCs().howManyStrings (20);
		System.out.println(a);

	}

}

- mrincodi August 17, 2016 | Flag Reply
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;
		}
		return totalPrev;
	}

- birinder.tiwana August 17, 2016 | Flag Reply
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;
  }
}

- wangchenClark0512 August 18, 2016 | Flag Reply
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)) {
				invalidList.add(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) {    		
    		list.add(sb.toString());
    	} 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);
    		}
    	}
    }

}

- guilhebl August 25, 2016 | Flag Reply
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

- jjongpark August 27, 2016 | Flag Reply
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);
	}
}

- Anonymous August 28, 2016 | Flag Reply
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);
	}
}

- Tony August 28, 2016 | Flag Reply
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);
	}

}

- Tony August 28, 2016 | Flag Reply
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[0]);
  }

  static void find(String s, int countb, int countc, int n, int[] result) {
    if (n == 0) {
      result[0]++;
      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);
    }
  }
}

- Anonymous August 31, 2016 | Flag Reply
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[0]);
}

static void find(String s, int countb, int countc, int n, int[] result) {
if (n == 0) {
result[0]++;
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);
}
}
}

- Anonymous August 31, 2016 | Flag Reply
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.

- Vimal August 31, 2016 | Flag Reply
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

- Vimal August 31, 2016 | Flag Reply
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);

}
}

- be.dhaval September 01, 2016 | Flag Reply
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);

    }
}

- be.dhaval September 01, 2016 | Flag Reply
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).

- Minsuk Kang September 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I did submit

- Minsuk Kang September 01, 2016 | Flag Reply
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;
	}

- Mukul September 04, 2016 | Flag Reply
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;
    }

- learner21 September 06, 2016 | Flag Reply
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;
    }

- learner21 September 06, 2016 | Flag Reply
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);
        }

- tryingtosolvemystery September 13, 2016 | Flag Reply
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[0] = arr[i];
            int x = (c==0)?2:c;
            code(arr, st, ret+1, b, x);
        }
        if(i == 1 && b != 0){
            ret[0] = arr[i];
            int x = (c==0)?2:c;
            code(arr, st, ret+1, 0, x);
            
        }
        if(i == 2 && c != 0){
            ret[0] = 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;
}

- vvskrn September 15, 2016 | Flag Reply
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[0] = arr[i];
            int x = (c==0)?2:c;
            code(arr, st, ret+1, b, x);
        }
        if(i == 1 && b != 0){
            ret[0] = arr[i];
            int x = (c==0)?2:c;
            code(arr, st, ret+1, 0, x);
            
        }
        if(i == 2 && c != 0){
            ret[0] = 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;
}

- vvskrn September 15, 2016 | Flag Reply
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=[0]*n
	arr2=[0]*n
	arr1[0]=1
	arr1[1]=2
	arr1[2]=4
	arr2[0]=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

- Sasha September 21, 2016 | Flag Reply
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

- Anonymous September 22, 2016 | Flag Reply
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

- Anonymous September 22, 2016 | Flag Reply
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

- ankitver September 22, 2016 | Flag Reply
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)

- totohero September 23, 2016 | Flag Reply
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;
	}

- robert September 26, 2016 | Flag Reply
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 )

- NoOne October 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry about late response,

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)

- Arminius November 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Trie + DFS

- sanjogj43 November 17, 2016 | Flag Reply
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('')

- kojino November 27, 2016 | Flag Reply
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)

- kojino November 27, 2016 | Flag Reply
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[0] = (s0, 1)
    dp[1] = (s1, sum(s1))
    
    for i in xrange(2, n+1):
        temp = (dp[i-1][1], dp[i-1][0][0], dp[i-1][0][1])
        dp[i] =  (temp, sum(temp))
    
    perms = dp[-1][1]
    for i in xrange(n):
        perms += dp[i][1]*dp[n-1-i][1]
    return perms

print total_perms(4)

- Nitish Garg January 03, 2017 | Flag Reply
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)

- Raghu July 24, 2017 | Flag Reply
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);
}
}

- just the number August 12, 2016 | Flag Reply
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.)

- Mark August 14, 2016 | Flag Reply
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.)

- Mark August 14, 2016 | Flag Reply
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;
}

- duralej August 16, 2016 | Flag Reply


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