Google Interview Question


Country: United States
Interview Type: Phone Interview




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

DP solution

public static int getCombinationsNumber(String s){
        if (s.length() == 0)
            return 0;
        int[] dp = new int[s.length()];
        dp[0] = 1;
        for (int i = 1 ; i < s.length() ; i++){
            int num = (s.charAt(i-1) - '0') * 10 + (s.charAt(i) - '0');
            if (dp[i-1] != 0) {
                dp[i] += dp[i - 1];
            }
            if (num <= 25) {
                dp[i] += i == 1 ? 1 : dp[i - 2];
            }
        }
        return dp[s.length()-1];
    }

If you wish, you can optimize it to use O(1) memory.

- GK January 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can any body explain this code? What is the overlapping problem of the subproblem. More precisely, why {dp[i-2] + d[i-1]} gives out the combination number for d[i]?

- Wi January 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can check my explanation and the O(1) space solution below.

- pavelkushtia January 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

def numStrings(s, n):
         if n == 0:
             return 0
         if n == 1:
              return 1

         if n == 2:
            num = int(s[n-1] * 10) + int(s[n])
            s = ( num >=10 and num <=25)? 3 : 2
             return s

         else:
              num = int(s[n-1] * 10) + int(s[n])
              s = (num >=10 and num <=25)?1 : 2
              return s  + numStrings(s, n-2)

At any pt i where i > 1, you have a chance to consider char at i-1 and i together if they form a number between 10 and 25 both inclusive, if so then you have one extra string along with 2 others formed by single chars at i-1 and i, to which you will add strings formed at i-2. If you draw out the recursion tree you can see that there are overlapping calls which ultimately leads to the DP soln above

- saurav January 24, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

def numStrings(number):
    n = len(number)
    print "n is: ", n
    if n == 0:
        return 0
    
    elif n == 1:
        return 1

    elif n == 2:
        num = int(number[-2])* 10 + int(number[-1])
        s = 3 if (num >=10 and num <= 25) else 2
        print "num  now: ", num
        print "s is: ", s
        return s

    else:
        num = int(number[-2])* 10 + int(number[-1])
       
        s = 3 if (num >=10 and num <=25) else 2
        print "num  now: ", num
        print "s is: ", s
        return (s  + numStrings(number[:-1]))

Improved the code above a bit

- Anonymous January 24, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Need explanation!!!

- Anonymous January 24, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Anonymous and @saurav: I don't agree with your solution

if string = "25", you can either generate "CF" or "Z", => you suggested 3
if string = "55", you can only generate "FF",=> you suggested 2

I don't think the questions is asking for sub-strings, if you want to consider sub-strings, then you have to count the number of distinct strings,

Am I missing something here?

- koosha.nejad February 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I'm afraid the answers given are wrong,
consider the string "11111" (5 characters), here are the strings you can generate:

1- "BBBBB"

2- "BBBL"
3- "BBLB"
4- "BLBB"
5- "LBBB"

6- "BLL"
7- "LBL"
8- "LLB"

NONE OF THE ANSWERS ABOVE GENERATES THIS

- koosha.nejad February 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This solution clearly does not have an optimal substructure because it ignores the presence of duplicate characters when using the smaller substring to obtain the count for a larger substring. It would only work if all characters were unique.

- Michael February 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This solution clearly does not work because it does not have an optimal substructure. It fails every time the string has duplicate characters.

- Michael February 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Tested with a very basic sample: "123" your solution returns 3, but shouldn't it be: 5? - 1 = B, 2 = C, 3 = D, 12 = M and 23 = X ?

- guilhebl April 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your solution is correct for all cases except handling 0s. 0 cannot be joined with another digit (01 is just AB and not A). So you have to handle the case

s.charAt(i-1) == '0'

separately.

- damluar July 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

We will use dynamic programming by creating an int[] count array, where each element, count[i], stores the number of strings we can make with a substring starting from i. For example, input = "01234", count[3] = # of diff strings of "34", count[2] = # of diff string of "234".

To find count[0], we use a the following relationship:
Number of different string of "1234" = number of different string of "234" + number of different string of "34" if "12" is in the mapping lookup table.

Let LU be the lookup table containing the keys, and let N = input length. Then, initialize count[N] = 1, count[N-1] = 1 and follow the relationship
count[i] = count[i+1] + LU.containsKey(input.substring[i, i+2])? count[i+2]: 0;
Loop through i from N-2 to 0.
Finally, count[0] is what we are looking for.

- t4k9 January 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

here is the c++ code

int CountStrings( char * s, int n )
{
	if ( n < 2 )
	{
		return 1;
	}

	int number = (s[n-1]-'0') + (s[n-2]-'0')*10;

	if ( ( number >= 10 ) && ( number <= 25 ) )
	{
		return CountStrings( s, n-1 ) + CountStrings( s, n-2 );
	}
	else
	{
		return CountStrings( s, n-1 );
	}
}

- koosha.nejad February 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

int CountStrings( char * s, int n )
{
	if ( n < 2 )
	{
		return 1;
	}

	int number = (s[n-1]-'0') + (s[n-2]-'0')*10;

	if ( ( number >= 10 ) && ( number <= 25 ) )
	{
		return CountStrings( s, n-1 ) + CountStrings( s, n-2 );
	}
	else
	{
		return CountStrings( s, n-1 );
	}
}

- koosha.nejad February 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@koosha.nejad I guess your solution is missing a 1 + before the recurrence please see my solution in java.

- guilhebl April 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

This is a linear combinatorics question

given 2 digit numbers that are > 10 and < 25 for example, count the number of adjacent numbers:

22222 = 5 adjacent numbers
1111 = 4 adjacent numbers
1101 = 2 adjacent numbers

it becomes a n choose k. What that means is for a string of 22222 the number of combinations is 5 choose 2 (since there's 2 possibilities for each pair).

given that information the problem becomes easier to understand.

Step 1: iterate through the string by pairs for instance:
[22]222 -> 2[22]222
count the number of continuos pairs >10 < 25 and store them in a hashmap. So you would have the key be the n in (n choose 2) and the value is the number of times the continuous pair has been seen.

At the end, iterate over the hash map and add all the numbers ignoring singles.

Example:

2205022

220 = 3 choose 2
22 = 2 (because there's 2 values here)

So the answer is 7 for that example string

- Anonymous January 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Shouldn't it be 6, how it is 7?

- pavelkushtia January 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I disagree

consider the string "11111" (5 characters), the solution is 8, 5 choose 2 is 10

1- "BBBBB"

2- "BBBL"
3- "BBLB"
4- "BLBB"
5- "LBBB"

6- "BLL"
7- "LBL"
8- "LLB"

- koosha.nejad February 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int noOfStringsFromIntegerString(String s,int index,int length)
    {   int count =0;
    	if(index+1>=length)
    		count = 1;
    	else {
    		count = noOfStringsFromIntegerString(s, index+1, length);
    		int temp = Integer.parseInt( s.substring(index,index+2));
    		if(temp < 26){
    			count += noOfStringsFromIntegerString(s, index+2, length);
    		}
    	}
    	return count;
    }

- Akky January 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think you have a mistake because you also consider the case that numbers can also be written in the form 03, 04, 05... I don't suppose that this is the case. To avoid this stuff you should add the statement

Integer.parseInt(s.substring(index, index + 1)) > 0

into your "if" which checks if temp is less than 26.

- nonameno January 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I believe you should replace "if(temp < 26)" with "if(temp < 26) && (temp>=10)"

- koosha.nejad February 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int noOfStringsFromIntegerString(String s,int index,int length)
    {   int count =0;
    	if(index+1>=length)
    		count = 1;
    	else {
    		count = noOfStringsFromIntegerString(s, index+1, length);
    		int temp = Integer.parseInt( s.substring(index,index+2));
    		if(temp < 26){
    			count += noOfStringsFromIntegerString(s, index+2, length);
    		}
    	}
    	return count;
    }

- akshay January 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ DP solutions with O(n) space and O(1) space

// O(n) time, O(n) space
int CountPossibleStrings(const string &s) {
    vector<int> cnt(s.size()+1, 1);
    for (int i = s.size()-2; i >= 0; --i) {
        cnt[i] = cnt[i+1];
        if (s[i] == '1' || (s[i] == '2' && s[i+1] <= '5'))
            cnt[i] += cnt[i+2];
    }
    return cnt[0];
}

// O(n) time, O(1) space
int CountPossibleStringsO1Space(const string &s) {
    int cnt[] = {1, 1}, slot = 0;
    for (int i = s.size()-2; i >= 0; --i, ++slot) {
        int v = cnt[slot%2];
        if (s[i] == '1' || (s[i] == '2' && s[i+1] <= '5'))
            v += cnt[(slot+1)%2];
        cnt[(slot+1)%2] = v;
    }
    return cnt[slot%2];
}

- tobi January 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

s[i]==1 and s[i+1]==9 is acceptable, but your code doesn't allow it

- koosha.nejad February 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Perform DFS via reursion or stack. At each step on can either (i) use one digit or (ii) use two digits to map to char. Well not actually, be careful because two digits can be used if and only if the first digit is 1 or if the first digit is 2 and the following is 0-5.
A sample code is shown below:

public int howMany(String s) {
	return howMany(s, 0);
}
private int howMany(String s, int k) {
	int N = s.length();
	if (k >= N)			return 0;
	int cnt = 1;

	cnt += howMany(s, k+1);
	if (k == N-1) 			return cnt;
	
	char c = s.charAt(k);
	char d = s.charAt(k+1);
	if (c == '1' || (c == '2' && d <= '5'))		
		cnt += howMany(s, k+2);
	
	return cnt;
}

- autoboli January 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

c=='1' and d=='9' is acceptable, but your code doesn't allow it

- koosha.nejad February 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a non-recursive version:
Based on this function

f(n)(k) means
	for a string of length n in which any adjacent character are combinable, 
        the solution number of splitting it so that there k substring with a pair of character while others of one character.
        Then.
        f(n)(0) = 1
        f(n)(1) = n-1
        f(n)(k) = f(n-2)(k-1) + f(n-3)(k-1) + ... + f(2k-2)(k-1)
        f(n)(n/2) = 1 if n is oven else f[l-2][l/2-1]


This is a simple implementation:

#The string can be divided into 'super substring'
# 11111121, is a kind of super substring
# any adjacent unit in super substring is combinable.

#calculate all possible combination of super_substring

data_dict = {1:[1]}

# l is length of super substring
def solv_super_substring(l):
    if l <= 1:
        return
    data_dict[l] = [0] * (l/2+1)
    data_dict[l][0] = 1
    data_dict[l][1] = l-1
    for i in xrange(2, l/2):
        for j in xrange((i-1)*2, l-1):
            data_dict[l][i] += data_dict[j][i-1]

    if l % 2 == 1:
        data_dict[l][l/2] = 1+data_dict[l-2][l/2-1]
    else:
        data_dict[l][l/2] = 1

def extract_super_substring(s):
    ssstr = []

    tmp = ''
    lofs = len(s)
    for c in xrange(lofs):
        if s[c] in '12':
            tmp += s[c]
            continue
        elif s[c] in '3456' and len(tmp) > 0:
            tmp += s[c]
        ssstr.append(tmp)
        tmp = ''
    return ssstr

#test
if __name__ == '__main__':
    s = '123121241291'
    sstr = extract_super_substring(s)
    print s
    print sstr
    
    lofss = map(lambda x: len(x), sstr)
    ml = max(lofss)
    for i in xrange(ml+1):
        solv_super_substring(i)
    print data_dict

    res = []
    for l in lofss:
        res.append(sum(data_dict[l]))
    print res
    r = 1
    for i in res:
        r *= i
    print r

- jilinxie1988@gmail.com January 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int getCount( String num , int k ){

	if(num.length() <= k )
		return 0;

	int count = getCount( num ,k+1 ) ;
	if( num.charAt(k) ==1 || (num.charAt(k) == 2 && num.charAt(k+1) <= 5))
		count += 1 + getCount( num ,k+2 );
	
	return count;
}

- Source January 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def countPossibleStrings(str):
	strNumSoFar = [0 for i in xrange(0, len(str))]
	for i in xrange(0, len(str)):
		if (i > 0):
			if (strNumSoFar[i-1] > 0):
				strNumSoFar[i] += strNumSoFar[i-1]
		else:
			strNumSoFar[i] = 1
		if (i > 1):
			if (strNumSoFar[i-2] > 0 and int(str[i-1]) > 0 and int(str[i-1])*10 + int(str[i])< 26):
				strNumSoFar[i] += strNumSoFar[i-2]
		else:
			if (i > 0):
				if (int(str[i-1]) > 0 and int(str[i-1])*10 + int(str[i]) < 26):
					strNumSoFar[i] += 1
	print strNumSoFar[len(str) - 1]

countPossibleStrings("132493820173849029382910382")

- chehirsCat January 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int countStrings(String string) {
		if("".equals(string) || (string == null)) {
			return 0;
		} else if(string.length() == 1) {
			return 1;
		} else {
			int twoDigits = Integer.valueOf(string.substring(0, 2));
			if((twoDigits >= 10) && (twoDigits <= 25)) {
				return 1 + countStrings(string.substring(1)) + countStrings(string.substring(2));
			} else {
				return 1 + countStrings(string.substring(1));
			}
		}
	}

- sun January 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int decode(string &s){
  if(s.empty()) return 0;
  int pre=1, cur=1;
  for(int i=1; i<s.length(); ++i){
    int t=cur;
    if(s[i-1]=='1' || s[i-1]=='2' && s[i]<='5')
      cur+=pre;
    pre=t;
  }
  return cur;
}

- Isaac January 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// 1 -> B
  // 13 -> BD, N
  // 132 -> BDC, NC
  // 112  -> BBC, LC, BM
  def stringFinder(s:String):List[String] = {

    // convert integer String to a letter
    val is2letter: String => String =  (si:String) =>('a' + si.toInt).asInstanceOf[Char].toString
    
    implicit def cToS(c:Char):String = c.toString

    if(s.length == 1) {
      List(is2letter(s))
    }else if(s.length == 2){
      val s1 =  is2letter(s(0)) + is2letter(s(1))
      val s2:String = s match{
        case a if a.toInt >= 'a'-'a' && a.toInt <= 'z'-'a'=> is2letter(a)
        case _ =>""
      } 
      if(!s2.isEmpty) List(s1,s2) else List(s1)
  
      } else {
  
        var results = List[String]()
        val s0 = is2letter(s(0))
        for(_s:String <- stringFinder(s.tail)) {
          results = (s0+_s) :: results
        }
  
        if(s0 != "a") {
          s.substring(0,2) match{
            case a if a.toInt >= 'a'-'a' && a.toInt <= 'z'-'a'=> {
              val s1 = is2letter(a)
              for(_s:String <-stringFinder(s.tail.tail)) {
                results = (s1+_s) :: results
              }
            } 
            case _ =>""
          }
        } 
  
        results
      }
  }

- flipCoder January 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

c# implementations

int CountOfPossible(string input)
{
if (String.IsNullOrWhiteSpace(input))
{
return 0;
}

int count = input.Length; // each number corresponds to letters

for (int i = 0; i < input.Length - 2; i++)
{
string sub = input.Substring(i, 2);

int num = ConvertToNum(sub);
if (10 <= num && num <= 25) // the two digits neighbors
{
count++;
}
}
return count;
}

int ConvertToNum(string input)
{

int parsedInt = -1;

int.TryParse(input, out parsedInt);

return parsedInt;
}

- Anonymous January 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Map;
import java.util.TreeMap;


public class StringCounter {
    
    private Map<String, Character> myMap;
    
    public StringCounter() {
        myMap = new TreeMap<String, Character>();
        //Builds the map: 0 -> A, ..., 25->Z
        for(int i = 0; i < 26; i++) {
            myMap.put(i+"", (char) (i+65));
        }
    }
    
    //slow recursive strategy.
    public int countStrings(String input) {
        if(input.isEmpty()) return 1;
        
        int num = countStrings(input.substring(1));
        if(input.length() >=2 && myMap.containsKey(input.substring(0, 2))) 
            num += countStrings(input.substring(2));
        
        return num;
    }
    
    //DP Soln - O(n) space, O(n) time
    public int countStringsDP(String input) {
        int[] numStrings = new int[input.length()];
        numStrings[0] = 1;
        numStrings[1] = myMap.containsKey(input.substring(0,2)) ? 2 : 1;
        for(int i = 2; i < input.length(); i++) {
            numStrings[i] = numStrings[i-1];
            if(myMap.containsKey(input.substring(i-1, i+1)))
                numStrings[i] += numStrings[i-2];
        }
        return numStrings[input.length()-1];
    }
    
    //DP Soln - O(n) time, constant space
    public int countStringsDP2(String input) {
        int val1 = 1;
        int val2 = myMap.containsKey(input.substring(0,2)) ? 2 : 1;
        for(int i = 2; i < input.length(); i++) {
            int temp = val2;
            if(myMap.containsKey(input.substring(i-1, i+1)))
                temp += val1;
            val1 = val2;
            val2 = temp;
        }
        return val2;
    }
}

- akyker20 January 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution with Fibonacci Terms:

Sequences for continuous two digit matching numbers can be broken down as Fibonacci term, and the final result is the multiplication of each such terms.

Example:
11 -> 2 F(3)
111 -> 3 F(4)
1111 -> 5 F(5)
11111 -> 8 F(6)
.....
......
n consecutive -> F(n-1)


so, 110511 -> F(4)*F(3) = 3*2 = 6

Here are the 6 variations:
BBAFBB
LAFBB
BKFBB
BBAFL
LAFL
BKFL


Here is the O(n) time and O(1) space solution

int getVariation(char* array)
{
	int retVal = 1;
	int len = strlen(array);
	int prevSum=1, currSum=1;
	
	for (int i=0; i< len; i++)
	{	
		int twoDigitNum = -1;
		if( i>0 && array[i-1] > '0')
		{
			twoDigitNum = (array[i-1]-'0')*10 + array[i] - '0'; 
		}
		
		if (twoDigitNum >=10 && twoDigitNum <=25)
		{
			int tmp = currSum;
			currSum += prevSum;
			prevSum = tmp;
		}
		else
		{
			retVal *= currSum;
			currSum = 1;
			prevSum = 1;
		}
	}
	
	retVal *= currSum;
	return retVal;
}

- pavelkushtia January 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

110511 -> List(lafl, lafbb, bbafbb, bbafl, bkfl, bkfbb)

- flipCoder January 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hello could you please elaborate because i am having difficulty understanding your logic. I would like to know what those 1s mean

- Anonymous February 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static char[] getChars(String s) {
char[] charsExists = new char[26];

if (s == null)
return charsExists;
else if (s.length() < 2) {
charsExists[Character.getNumericValue(s.charAt(0))] = (char) ((65 + Character
.getNumericValue(s.charAt(0))));
} else {
for (int i = 0; i < s.length(); i++) {
if (charsExists[Character.getNumericValue(s.charAt(i))] == '\u0000') {
charsExists[Character.getNumericValue(s.charAt(i))] = (char) ((65 + Character
.getNumericValue(s.charAt(i))));
/* System.out.println(" 1 :"
+ Character.getNumericValue(s.charAt(i)));*/
} else {
System.out.println("character Exists + "
+ String.valueOf(s.charAt(i)));
}
// int num = Character.getNumericValue(s.charAt(i) + s.charAt(i
// + 1));
if (i != s.length() - 1) {
int num = Integer.parseInt(s.substring(i, i + 2));

//System.out.println("2 :" + num);
if (num < 26 && charsExists[num] == '\u0000') {

charsExists[num] = (char) (65 + num);
} else {
System.out
.println("character Exists or not valid number: "
+ num);
}
}
}

}

return charsExists;

}

- Trups January 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def count(s):
	n_ways = [0 for _ in xrange(len(s) + 1)]
	n_ways[len(s)] = n_ways[len(s) - 1] = 1
	idx = len(s) - 2
	while idx >= 0:
		n_ways[idx] = n_ways[idx+1]
		a, b = int(s[idx]), int(s[idx]+1)
		number = a * 10 + b
		if number <= 25:
			n_ways[idx] += n_ways[idx+2]
		idx -= 1
	return n_ways[0]

- Xuan Luong January 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can be solved in O(n) time, both recursively and iteratively. Here is an iterative version:

import java.util.Scanner;

class NumToString {
	public static void main (String[] args) {
		Scanner s = new Scanner(System.in);
		System.out.println("Enter the Number-string");
		String str = s.nextLine();
		char [] cArray = str.toCharArray();
		int [] array = new int[str.length()];
		for (int i = 0; i < array.length; i++) {
			if (cArray[i] >= '0' && cArray[i] <= '9') {
				array[i] = cArray[i] - '0';
			}
			else {
				System.err.println("Wrong input. Exiting...");
			}
		}
		int [] memArray = new int[array.length + 1];
		memArray[array.length] = 1;
		memArray[array.length - 1] = 1;
		for (int i = array.length - 2; i >= 0; i--) {
			if (array[i] > 2 || array[i] == 0 || (array[i] == 2 && array[i + 1] > 5)) {
				memArray[i] = memArray[i + 1];
			}
			else {
				memArray[i] = memArray[i + 1] + memArray[i + 2];
			}
		}
		System.out.println("Number of strings possible = " + memArray[0]);
	}
}

- Sumeet Singhal January 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int get_combination_num(char* s) {
    if (s == NULL) return -1;
    int str_len = strlen(s);
    if (str_len == 0) return 0;

    int* dp = (int*)malloc(sizeof(int)*str_len);
    if (dp == NULL) return -1;

    int i;
    dp[0] = 1;
    for (i = 1; i < str_len; i++) { 
        dp[i] = dp[i-1];
        int value = (s[i-1] - '0') * 10 + (s[i] - '0');
        if (value >= 10 && value <= 25) {
           dp[i] += (i-2 >= 0 ? dp[i-2] : 1);
        }
    }
    int ret = dp[str_len-1];
    free(dp);
    return ret;
}

- Sung January 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int NumberOfPossibleStrings(String str){
		if(str == null || str.length()==0) return 0;
		if(str.length()==1)return 1;
		if(str.length()==2)
			if(str.charAt(0)<'3'&&str.charAt(0)>'0')return 2;
			else return 1;
				
		if(str.charAt(0)=='0'||str.charAt(0)>'2')
			return NumberOfPossibleStrings(str.substring(1));
		return NumberOfPossibleStrings(str.substring(1))+
				NumberOfPossibleStrings(str.substring(2));
	}

- srcnaks January 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Similar to srcnacks, but in c++

#include <string>
using namespace std;

int count_strings(string s)
{
    if(s.length() <= 1)
        return 1;
    
    int count = count_strings(s.substr(1));

    if(s[0] == '1' || (s[0] == '2' && s[1] <= '6'))
        count += count_strings(s.substr(2));

    return count;
}

- ig January 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
using namespace std;

int num2letter( char num0, char num1)
{
assert( num0 >= '0'|| num0 <= '9' );
assert( num1 >= '0'|| num1 <= '9' );

if (0
|| num0 > '2'
|| (num0 == '2') && (num1 > '5')
) {
return 0;
}
return 1;
}


int search_str( const char * str, int start, int end, int num_found ) {
int num = num_found;
if (start < end) {
num++; // the very first one
num += num2letter(str[start], str[end]);
num += search_str(str, start+1, end, num);
} else if (start == end) {
num ++; // last one char
}

return num;
}

int main() {
const char num_str[] = "132493820173849029382910382";
int str_num = search_str( num_str, 0, sizeof(num_str) - 1 - 1, 0);
cout << "number of string is " << str_num << endl;
}

- jason January 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry. The above code is wrong. The fixed one using simple DP is below:
{
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int num2letter( char num0, char num1)
{
assert( num0 >= '0'|| num0 <= '9' );
assert( num1 >= '0'|| num1 <= '9' );

if (0
|| num0 > '2'
|| (num0 == '2') && (num1 > '5')
) {
return 0;
}
return 1;
}


int search_str( const string &input) {
int num = 0;
vector<int> A(input.size(), 0);
A[0] = 1;
for(int i=0; i< input.size() - 1; i++) {
A[i+1] = A[i] + 1 + num2letter(input[i], input[i+1]);
}
return A.back();
}

int main() {
const string input = "132493820173849029382910382";
cout << "input:" << input << endl;
int str_num = search_str(input);
cout << "number of sub string is " << str_num << endl;

const string input1 = "1234";
cout << "input1:" << input1 << endl;
str_num = search_str(input1);
cout << "number of sub string is " << str_num << endl;
}

}

- jason January 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

# s non empty

def findComb(s):
    # base cases:
    if len(s) == 0:
        return 1
    elif len(s) == 1:
        return 1
    elif len(s) == 2:
        if int(s) < 26:
            return 2
        else:
            return 1
            
    # recursive case, split the original string number to left and right
    # total = findComb(left) * findComb(right) + \
    #         findComb(left[:-1]) * findComb(right[1:])  //if <26 
    
    else:
        mid = len(s) / 2
        # print mid 
        left = s[:mid] 
        right = s[mid:] 
        easyComb = findComb(left) * findComb(right)
        addon = 0  
        if int(s[mid-1:mid+1]) < 26:
            addon = findComb(left[:-1]) * findComb(right[1:])
        return easyComb + addon

- Anonymous January 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

it should be simple to implement.
If english alphabets were from 1-99 then solution would have been (2n-1)
Since alphabets are till 25, we need to iterate through the list and figure out how many adjacent digits form a number more than 25 and exclude them from the ans.

number_of_string(int [] arr)
{
  int exclude = 0;
  for(int i=1;i<arr.length;i++)
  {
    if(arr[i-1]*10 + arr[i] > 25) exclude++;
  }
  return 2*arr.length -1 - exclude;
}

- aditya.eagle059 January 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Only need to count numbers less than 26.
input: "132493820173849029382910382";

13, ...24, ... 20, ... 17, ... 10, ...
2^5 =32

output: 32

- Anonymous February 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi, I also came up with this solution. And it works fine until the numbers overlap. Try for example 110511. Your approach will give 8, but the answer is 6. So we have to use DP in the end.

- damluar July 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Only need to count numbers less or equal than 26

input: "132493820173849029382910382"

13, ... 24, ... 20, ...17,...13
2^5 = 32

output: 32

- biolxj12 February 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi, I also came up with this solution. And it works fine until the numbers overlap. Try for example 110511. Your approach will give 8, but the answer is 6. So we have to use DP in the end.

- damluar July 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Main {
	
	public static void printString(String prefix,String suffix, int len){
		if(prefix.length()==len)
			System.out.println(prefix);
		else{
			for(int i=0;i<suffix.length();i++){
				char temp = (char)(Integer.parseInt(suffix.substring(0, 1)) + 65);
				printString(prefix + String.valueOf(temp),suffix.substring(i+1, suffix.length()),len);
				if(i<suffix.length()-1){
					temp = (char)(Integer.parseInt(suffix.substring(0, 2)) + 65);
					if(Integer.parseInt(suffix.substring(0, 2))<=25)
						printString(prefix + String.valueOf(temp),suffix.substring(i+2, suffix.length()),len-1);
				}
				
			}
		}
				
		}
	
	
	public static void main(String args[]){
		
		String input = "1223" ;
		String prefix="";
		String suffix = "";
		printString("",input,input.length());
	}

}

- nitesh.kedia5 February 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. assume the existence of a Hashtable<String, String> table that contains the mapping of a String number to String letter, e.g <"0", "A"> .... <"25", "Z">

2. assume the existence of a function:

private boolean isValid(String str) {
	return table.containsKey(str);
}

3. The requested function:

public int CountCombo(String str) {

	if(str.length <=0) return 0;

	int ones = 0;
	int twos = 0;

	ones = (isValid(str.substring(0,1)))?1:0 + CountCombo(str.substring(1));
	
	if(str.length>=2)
		twos = (isValid(0,2))?1:0 + CountCombo(str.substring(2));

	return ones + twos;
}

}

- YD March 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution in Java based on recursion:

public static int countStrings( char[] s, int n )
{
	if ( n < 2 ) 	{
		return 1;
	}
	
	int number = (s[n-1]-'0') + (s[n-2]-'0')*10;
	if ( ( number >= 10 ) && ( number <= 25 ) )	{
		return 1 + countStrings( s, n-1 ) + countStrings( s, n-2 );
	}
	else 	{
		return 1 + countStrings( s, n-1 );
	}
}

- guilhebl April 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int num_strings_o1space(const std::string& s)
{
    int count_0 = 1;
    int count_1 = 1;
    int len = s.length();
    for (auto i = 1; i < len; ++i)
    {
        int num = s[i-1] - '0';
        num *= 10;
        num += s[i] - '0';
        if (s[i-1] != '0' && num < 26)
        {
            int count_new = count_0 + count_1;
            count_0 = count_1;
            count_1 = count_new;
        }
        else
        {
            count_0 = count_1;
        }
    }
    return count_1;
}

- Omri.Bashari May 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Below is a recursive solution in Java. I've also added cache to avoid calculating the same things more than once.

In each step, we try to take both 1 character and 2 characters (in case it's in the legal range).

The complexity without the cache is: 2^n (since the recurrence relation is T(n) = T(n-1) + T(n-2) in case the 2 chars forms a valid key).

public static int countValidWords(String input) {
		if (input == null || input.isEmpty()) {
			return 0;
		}
		Map<String, String> dict = new HashMap<>();
		for (int i = 0; i < 26; i++) {
			char c = (char) ('A' + i);
			dict.put(i + "", c + "");
		}

		// memorizing already calculated strings 
		Map<String, Integer> cache = new HashMap<>();
		return countValidWordsHelper(input, dict, "", cache);
	}

	private static int countValidWordsHelper(String input, Map<String, String> dict, String currentWord, Map<String, Integer> cache) {
		// you can comment out the if below to get a print of all options (using cache 	
		// doesn't print the parts that are already in the cache
		if (cache.containsKey(input)) {
			return cache.get(input);
		}
		if (input.length() == 0) {
			System.out.println(currentWord);
			return 1;
		}
		if (input.length() == 1) {
			System.out.println(currentWord + ", " + dict.get(input));
			return 1;
		}
		String currentPartCode = input.substring(0, 2);
		String currentPartStr = dict.get(currentPartCode);

		int validaWordsMinusChar = countValidWordsHelper(input.substring(1), dict, currentWord + ", " + dict.get(input.substring(0, 1)), cache);
		cache.put(input.substring(1), validaWordsMinusChar);
		int validWordsMinusTwoChars = 0;
		if (currentPartStr != null) {
			validWordsMinusTwoChars = countValidWordsHelper(input.substring(2), dict, currentWord + ", " + currentPartStr, cache);
			cache.put(input.substring(2), validWordsMinusTwoChars);			
		}
		return validaWordsMinusChar + validWordsMinusTwoChars;
	}

- dl April 29, 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