Facebook Interview Question for Senior Software Development Engineers


Country: United States
Interview Type: Phone Interview




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

this is pretty easy if you think in terms of Dp approach.
Lets say we have String as "1" so our output will be 1 because we only form 'A'
but if we add 2 to the existing string "12" then output is "AB" and "L" so if you see
the logic is when you add a character to an existing string the number of combinations increase by combining last 2 digits
in dp it can be formulized As
d[i]=dp[i-1]+dp[i-2](if the last 2 digits combined is smaller than 27)
else dp[i]=dp[i-1];
code is as below

void getMappingDp(String str)
	{
		int arr[]=new int[str.length()];
		long Dp[]=new long[str.length()];
		
		for(int i=0;i<arr.length;i++)
		{
			arr[i]=Integer.parseInt(""+str.charAt(i));
		}
	
		Dp[0]=1;
		if(arr[0]*10+arr[1]<27)
			Dp[1]=2;
		else
			Dp[1]=1;
		
		for(int i=2;i<arr.length;i++)
		{
			long combinedLast2didgits=0;
			if(arr[i-1]*10+arr[i]<27)
				combinedLast2didgits=Dp[i-2];
			Dp[i]=Dp[i-1]+combinedLast2didgits;	
		}
		System.out.println("Total mapping are:"+Dp[Dp.length-1]);
	}

- blackfever August 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

if(arr[i-1]*10+arr[i]<;27) is not enough
like "02", can add Dp[i-2] in this situation?

- chenkainp August 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

public int subStringReprensation(String inputNumber){

char[] inputChars=inputNumber.toCharArray();
int count=0;

if(inputChars.length==1){
return 1;
}

int i=0;
StringBuffer numberSampleString =new StringBuffer();

int numberSample=0;
while(i < inputChars.length){

numberSampleString.append(inputChars[i]);

numberSample=new Integer(numberSampleString.toString());

i++;

if(numberSample>26) break;

if(numberSampleString.length()==inputNumber.length()&& numberSampleString.length()==2 && numberSample<=26){
count++;
}else{
count+=subStringReprensation(inputNumber.substring(i,inputChars.length));
}
}

return count;

}

- Vik September 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

You can improve the space complexity of your solution to O(1)

- German September 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

The dynamic programming code does not handle the case where the string contains 0.

- Praks November 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 vote

DP problem, just check the previous 1 and 2 numbers are valid or not;

int ValidDecoding(string s)
{
    int t, l = s.length();
    int * f = new int[l+1];
    f[0] = 1;
    for (int i = 1; i <= l; ++i)
    {
        f[i] = 0;
        if (s[i-1] != '0')
            f[i] += f[i-1];
        if (i-2 >= 0){
            t = 10 * (s[i-2] - '0') + s[i-1] - '0';
            if (t > 9 && t < 27){
                f[i] += f[i-2];
            }
        }
    }
    return f[l];
}

- ronnie.alonso October 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

Dynamic programming version of my previous answer:

// We want to branch the string at every valid character and count the
// fully form string permutations indicated by when we reach a point where
// we can go no further, i.e. a full permutation has been calculated.
function branchAndCount(string, index, twoDigits, lookup) {
	
	var sub;
	
	// If we've fallen off the end of the string, and there was a string
	// to begin with, we know that we have traversed a full permutation
	// of one of the result strings and should count it in the final result;
	if(index == string.length) {
		return (string.length > 0 && !twoDigits) ? 1 : 0;
	}
	
	if(twoDigits) {
		
		// We check the two-digit case including the digit from the previous iteration
		// of the function. If this two digit number in the range 1 - 26 then we explore
		// it further as it is a valid path.
		sub = string.substring(index -1, index + 1);
		
		// Dynamic programming version. The number of permutations rooted
		// at this index has already been stored by the one-digit case.
		// Look it up and reuse it.
		return (sub >= '1' && sub <= '26') ?
			lookup[index] : 0;
	} else {
		
		// The one-digit case is always valid, so we branch here in order to explore the
		// succeeding one-digit and two-digit cases.
		return (lookup[index] = branchAndCount(string, index + 1, false, lookup))
						+ branchAndCount(string, index + 1, true, lookup);
	}
}

// Wrapper function to invoke the main processing function correctly.
function countPermutations(string) {
	var lookup;
	lookup = [];
	return branchAndCount(string, 0, false, lookup);
}

// Invoke
console.log(countPermutations('111'));

- enzeart August 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Here's my solution
Given a string x where x=[x0,x1....x[x.length]], the solution for x is the sum of all solutions of all substrings from i=1.. to x.length plus 1 if the length of string x is less than 27( a check).

Eg
solve(111) ---> check(111)+solve(11) + solve(1)
solve(11) ---> check(11) + solve(1)
solve(1) = 1 (base case)
Code:

static int solve(String x){
		int sum = 0;
		int i =1;
		if (x.length()>0 && Integer.parseInt(x) < 27){
			sum = 1;
		}
		while (i < x.length()){
			sum = sum + solve(x.substring(i,x.length()));
			i++;
		}
		return sum;
	}

- Anonymous August 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

You can use a recursive function which remembers two things: the current index in the input string and the number we have got so far. From here, we can do two things: we can either add the current digit to the number we have so far or we can start a new number.

string s;
int solve(int idx, int sofar) {
	if(sofar > 26) return 0;
	// There can't be leading zeros
	if(sofar == 0) return 0;
	
	// This is a valid splitting of the string
	if(idx == (int)s.size()) return 1;
	
	int ret = solve(idx + 1, sofar * 10 + s[idx] - '0');
	
	ret += solve(idx + 1, s[idx] - '0');
	
	return ret;
}

The answer is solve(1, s[0] - '0')
Note that the states may repeat so you can use memoisation to reduce the time complexity to O(n)

- Balajiganapathi S August 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I gave a solution which generates duplicates too and which were pruned later. But interviewer interested in solution without duplicates.

- skrish August 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Like he said, you can just use memoization to avoid processing each case more than once:

int calc(int n, string& s, vector<int>& dp) {
    if (n == s.size()) return 1;
    if (dp[n] != -1) return dp[n];
    int res = calc(n + 1, s, dp);
    if (n+1 < s.size() && ) {
       int next = s[n] + s[n+1] - '0' - '0';
       if (next <= 26) res += calc(n + 2, s, dp);
    }
    return dp[n] = res;
}

The function calculates the number of mappings of the suffix of s starting at position n, so the original call must be calc(n, s, dp). dp has the same size as the string and is initialized with -1.

- xlREDlx August 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry, I forgot to erase an "&&" in the code above :)

- xlREDlx August 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int func(char a[],int n)
{
if (n==0 || n==1)
return 1;
int count=0;
if (a[n-1] > '0' )
{
count=func( a , n-1 );
}
if (a[n-2] < '2' || (a[n-2] == '2' && a[n-1] < '7' ))
{
count+=func( a , n-2 );
}
return count;
}

- Pawan August 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution in Java

import java.util.HashSet;
import java.util.Set;

public class GetNumValidMappings {
	
	public static int getNumValidMappings(String input) {
		try {
			Integer.parseInt(input);
		} catch (NumberFormatException e) {
			return 0;
		}
		Set<String> validMappings = new HashSet<String>();
		getAllValidMappings(validMappings, "", input);
		return validMappings.size();
		
	}
	
	private static String convert(String input)  {
		char c;
		try {
			c = (char) (64 + Integer.parseInt(input));
			if (c > 'Z') {
				return null;
			}
		} catch (Exception e) {
			return null;
		}
		return new String(new char[] {c});
	}
	
	public static void getAllValidMappings(Set<String> validMappings, String currentMapping, String remaining) {
		if (remaining.length() == 0) {
			validMappings.add(currentMapping);
		} else if (remaining.length() == 1) {
			String charMap = convert(remaining);
			if (charMap != null) {
				validMappings.add(currentMapping + charMap);
			}
		} else {
			String singleCharMap = convert(remaining.substring(0, 1));
			String doubleCharMap = convert(remaining.substring(0, 2));
			if (singleCharMap != null) {
				getAllValidMappings(validMappings, currentMapping + singleCharMap, remaining.substring(1));
			}
			if (doubleCharMap != null) {
				getAllValidMappings(validMappings, currentMapping + doubleCharMap, remaining.substring(2));
			}
		}
	}
	
	public static void main(String[] args) {
		String input = "12321";
		System.out.println(getNumValidMappings(input));
	}

- Anonymous August 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/** Use dynamic programming technique.
	 * time: O(N)
	 * space: O(1)
	 */
	int mappingsCount(String str){
		
		char[] arr = str.toCharArray();
		
		int lastWays = 1;
		int preLastWays = 1;		
		
		if( arr[arr.length-1] == '0' ){
			preLastWays = 0;
		}	
		
		for( int i = arr.length-2; i >= 0; i-- ){
			int value = arr[i] - '0';
			int curCount = 0;
			
			if( value != 0 ){
				curCount += preLastWays;
				
				value = value*10 + arr[i+1]-'0';
				
				if( value < 27 ){
					curCount += lastWays;
				}				
			}
			
			lastWays = preLastWays;
			preLastWays = curCount;			
		}
		
		return preLastWays;		
	}

- m@}{ August 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using recursion to find count and strings

int arr[]={1,2,2,4};
int len;
//find combo of 2 strings at a time and then call recursively
//handle case of only one character 
int findCombo(string str, int i)
{
	int pos;
	static int countCombo;
	//cout<<"pos="<<pos<<endl;
	//terminating condition
	if(i>=len-2)
	{
		//look for combo of last 2 digits	
		if(arr[i]<=2 && arr[i+1]<7)
		{
			pos=arr[i]*10+arr[i+1];
			cout<<str<<char(96+pos)<<endl;
			++countCombo;
		}
		//print combo of individual characters
		cout<<str<<char(96+arr[i])<<char(96+arr[i+1])<<endl;
		return ++countCombo;
	}
	string newstr;
	//if at leas 2 more digits found,create character from 2 digits and call further
	if(i<len-2 && arr[i]<=2 && arr[i+1]<27)
	{
		pos=arr[i]*10+arr[i+1];
		newstr=str+string(1,96+pos);
		//cout<<"newstr"<<newstr<<endl;
		findCombo(newstr,i+2);
	}
	//create character from 1 digit and call further
	pos=arr[i];
	newstr=str+string(1,96+pos);
	//cout<<"newstr1"<<newstr<<endl;
	findCombo(newstr,i+1);
	return countCombo;
}
 
int main()
{
	cout<<"Program to find combination of mapping numbers as string, returning the number of ways input string can be split into sub-strings"<<endl;
	len=sizeof(arr)/sizeof(arr[0]);
	cout<<"len="<<len<<endl;
	string str;
	int pos=0;
	int count=findCombo(str,pos);
	cout<<"count of combo="<<count<<endl;
	/*string str1="kan";
	string str2=str1+string(1,'h')+string(1,char(96+1));
	cout<<"str2="<<str2<<char(96+1)<<endl;
	*/return 0;
}

- Anonymous August 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Example{
public static boolean validateInt(String ch) throws Exception
{
return Integer.parseInt(ch) <= 26;
}

public static int getSub(String remaining, int len) throws Exception
{
if (remaining.length() < len)
return 0;
if (remaining.length() == len && validateInt(remaining))
return 1;
if (remaining.length() == len && !validateInt(remaining))
return 0;
else
return getSub(remaining.substring(len), 1) + getSub(remaining.substring(len), 2);
}

public static int getlen(String num) throws Exception
{
return getSub(num, 1) + getSub(num, 2);
}

public static void main(String []args) throws Exception{
System.out.println(getlen("132"));
}
}

- tester August 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<?php

function combination($string, &$cache)
{
if (strlen($string) <= 1) {
return 1;
}

if (!isset($cache[$string])) {
$string1 = substr($string, 1);
$prefix = substr($string, 0, 2);
if ($prefix > 26) {
$cache[$string] = combination($string1, $cache);
} else {
$string2 = substr($string, 2);
$cache[$string] = combination($string1, $cache) + combination($string2, $cache);
}
}
return $cache[$string];
}

$cache = [];
var_dump(combination('1111235346345', $cache));

- paul4156 August 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Forgot to handle '0'.

<?php

function combination($string, &$cache) 
{
	if (strlen($string) <= 1) {
		if ($string == '0') {
			return 0;
		}
		return 1;
	}

	if (!isset($cache[$string])) {
		$prefix1 = $string[0];
		$string1 = substr($string, 1);
		if (combination($prefix1, $cache) == 0) {
			$num1 = 0;			
		} else {
			$num1 = combination($string1, $cache);
		}
		$prefix = substr($string, 0, 2);
		if ($prefix > 26 || $prefix == '00') {
			$cache[$string] = $num1;
		} else {
			$string2 = substr($string, 2);
			$cache[$string] = $num1 + combination($string2, $cache);
		}
	}
	return $cache[$string];
}

$cache = [];
var_dump(combination('12351200004034', $cache));

- paul4156 August 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int countDifferentWays(String str){
		int n = str.length();
		if(n < 2) return n;
		int[] dp = new int[n];
		
		dp[0] = 1;
		dp[1] = (isOk(str,0,1)? 2: 1);
		
		for(int i = 2; i <n; i++){
			dp[i] = dp[i-1];
			if(isOk(str,i-1,i)) dp[i]+=dp[i-2];
		}
		return dp[n-1];
	}
	private boolean isOk(String s, int from, int to){
		
		return Integer.parseInt(s.substring(from, to+1)) < 27;
	}

- eng.akramgab August 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<conio.h>
#include<alloc.h>
int ar[20];
char ch[]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};

void fun(int i,char a[20],int n)
{
	if(i==n)
	{
		printf("%s\n",a);
	}
	else
	{
		char * temp=(char*)malloc(n);
		sprintf(temp,"%s%c",a,ch[ar[i]-1]);
		fun(i+1,temp,n);
		free(temp);
		if(i<n && (ar[i]*10+ar[i+1])<=26)
		{
			temp=(char *)malloc(n);
			sprintf(temp,"%s%c",a,ch[ar[i]*10+ar[i+1]-1]);
			fun(i+2,temp,n);
			free(temp);
		}
	}
}

void main()
{
	clrscr();
	int info,tmp[20],t,i=0,j=0,n;
	printf("Enter digit:");
	scanf("%d",&info);
	while(info!=0)
	{
		tmp[i]=info%10;
		i++;
		info=info/10;

	}
	n=i;
	for(t=i-1;t>=0;t--)
	{
		ar[j]=tmp[t];
		j++;
	}
	ar[j]=1000;
	fun(0,"",n);
	getch();
}

- RajanParmar August 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class AlphabetMapping {

	protected HashMap<String, String> am;
	public AlphabetMapping() {
		am = new HashMap<String, String>();
		am.put("1", "A");
		am.put("2", "B");
		am.put("3", "C");
		am.put("4", "D");
		am.put("5", "E");
		am.put("6", "F");
		am.put("7", "G");
		am.put("8", "H");
		am.put("9", "I");
		am.put("10", "J");
		am.put("11", "K");
		am.put("12", "L");
		am.put("13", "M");
		am.put("14", "N");
		am.put("15", "O");
		am.put("16", "P");
		am.put("17", "Q");
		am.put("18", "R");
		am.put("19", "S");
		am.put("20", "T");
		am.put("21", "U");
		am.put("22", "V");
		am.put("23", "W");
		am.put("24", "X");
		am.put("25", "Y");
		am.put("26", "Z");	
	}
	
	public String number;
	
	public ArrayList<String> calculateStrings(String number) {
		
		if(number.length() == 1){
			
			ArrayList<String> ret = new ArrayList<String>();
			ret.add(this.am.get(number));
			
			return ret;
		}
		
		else if (number.length() == 2) {
			
			ArrayList<String> temp1 = calculateStrings(number.substring(0, 1));
			ArrayList<String> ret = new ArrayList<String>();
			String lastchar = number.substring(1);
			for (String str : temp1){
				ret.add(str.concat(this.am.get(lastchar)));
			}
			
			String last2 = this.am.get(number);
			if(null != last2) {
				ret.add(last2);
		
			}
			
			return ret;
			
			
		}
		
		else {
			ArrayList<String> temp1 = calculateStrings(number.substring(0, number.length()-1));
			ArrayList<String> ret = new ArrayList<String>();
			String lastchar = this.am.get(number.substring(number.length()-1));
			
			for (String str : temp1){
				ret.add(str.concat(lastchar));
			}
			
			
			String last2char = this.am.get(number.substring(number.length()-2));
			
			if(null != last2char) {
				ArrayList<String> temp2 = calculateStrings(number.substring(0, number.length()-2));
				for (String str : temp2){
					ret.add(str.concat(last2char));
				}
			}
		
			return ret;
		}
	}
		
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		
		String str = "123";
		
		AlphabetMapping am = new AlphabetMapping();
		
		ArrayList<String> words = am.calculateStrings(str);
		
		for(String word: words) {
			System.out.println(word);
		}
	}

}

- Vijay August 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class ValidMapping implements Runnable {
	
	public ValidMapping() {};
	static boolean DEBUG = false;
	
	public void run()
	{
		DEBUG = true;
		//test
		for(String str : new String[] {"111", "11", "123"})
		{
			System.out.println("String :" + str + " Mappings: " + ValidMapping.Mapping(0, str.toCharArray()));
		}
	}
	private static int Mapping(int i, char[] str)
	{
		if(i == str.length)
		{
			if(DEBUG)
			{
				System.out.println("\t" + new String(str));
			}
			return 1;
		}
		else
		{
			int sum = 0;
			
			// one
			if(str[i] >= '1' && str[i] <= '9')
			{
				sum += Mapping(i + 1, str);
			}
			
			
			//two
			if(i+1 < str.length && ((str[i] == '1' && Character.isDigit(str[i+1])) 
					             || (str[i] == '2' && str[i+1] >= '1' && str[i+1] <= '6')))
			{
				sum += Mapping(i + 2, str);
			}
			
			return sum;
		}
	}

}

- Gagan August 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's my solution
Given a string x where x=[x0,x1....x[x.length]], the solution for x is the sum of all solutions of all substrings from i=1.. to x.length plus 1 if the length of string x is less than 27( a check).

Eg
solve(111) ---> check(111)+solve(11) + solve(1)
solve(11) ---> check(11) + solve(1)
solve(1) = 1 (base case)
Code:


static int solve(String x){
int sum = 0;
int i =1;
if (x.length()>;0 && Integer.parseInt(x) < 27){
sum = 1;
}
while (i < x.length()){
sum = sum + solve(x.substring(i,x.length()));
i++;
}
return sum;
}

- Ore Asonibare August 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Memoization can easily be added, to improve runtime

- Ore Asonibare August 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution with dynamic programming:

public static int count(int n) {
		if (n<=10) return 1;
		if (n<=26) return 2;
		
		String nstr = Integer.toString(n);
		int first = Integer.parseInt(nstr.substring(0,1));
		int second = Integer.parseInt(nstr.substring(1,2));
		int head = Integer.parseInt(nstr.substring(1));
		int tail = n>=100? Integer.parseInt(nstr.substring(2)) : 0;

		if (first*10+second<=26) return count(head)+count(tail);
		else return count(head);
	}

- sabz August 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

this will work

public class AlphabetMap {
    static int [][] dp;
    static String pattern;
    int count(int start, int end) {
        if(start >= end || start < 0) return 0;
        if(dp[start][end] != -1) return dp[start][end];
        dp[start][end] =1;
        for(int i=start;i<end;i++) {
            // mixing i and i +1 in one num
            int num = Integer.parseInt(pattern.substring(i,i+2));
            if(num < 27) {
                dp[start][end] += 1+ count(start,i-1)  + count(i+2,end);
            }
         }
        return dp[start][end];
    }
    public static void main(String [] args) {
        AlphabetMap o = new AlphabetMap();
        pattern = "1111";
        dp = new int[pattern.length()][pattern.length()];
        for(int i=0;i<dp.length;i++)
            Arrays.fill(dp[i],-1);
        int ans = o.count(0,pattern.length()-1);
        System.out.println(ans);
    }
}

- sharingan August 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package MANIPULAITON;
public class Count_Possible_Decodings_of_a_given_Digit_Sequence
{
public static void main(String []args)
{
String input = new String("111");
int length = input.length();
Count_Possible_Decodings_of_a_given_Digit_Sequence obj = new Count_Possible_Decodings_of_a_given_Digit_Sequence();
System.out.println(obj.countPossibleDecoding(input.toCharArray(),length));
}

private int countPossibleDecoding(char[] input, int length)
{
int count [] = new int[length+1];

count[0] = 1;
count[1] = 1;

for(int i =2;i<=length;i++)
{
count[i] = 0;

if(input[i-1] > '0')
{
count[i] = count[i-1];
}

if(input[i-2] <'2' || (input[i-2]=='2' && input[i-1] <'7'))
{
count [i] = count[i] + count[i-2];
}
}
return count[length];

}
}

- Prince Seth August 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private int getNumSubStrs(String str) {
        int result = 0;
        if (str == null || str.isEmpty()) {
            return result;
        } else {
            for (int q = Integer.valueOf(str); q>0; q/=10) {
                result++;
                int d1 = q % 10;
                int d2 = (q / 10) % 10;
                if (d2 != 0 && stringMap.values().contains((d2*10 + d1))) {
                    result++;
                }
            }
        }

        return result;
    }
}

- Anonymous August 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Time Complexity : O(n) [n= numbers.length()]
//Space Complexity : O(1)
public static int mappings(String numbers){
int last = 0;
int twolast = 0;
if(numbers.isEmpty()){
return 0;
}else{
twolast=1;//twolast = 1;
}
if(numbers.length()>2){
if(numbers.substring(0,2).compareTo("26")<=0){
last = 2;
}
}
for(int i=2;i<numbers.length();i++){
int one = last;
int two = 0;//0 ways to map the pair
if(numbers.substring(i-1,2).compareTo("26")<=0){//last two are an integer<=26.
two= twolast;//get ways to form the substring until two positions before
}else{
two= 0;
}
int current = one + two;
twolast = last;
last = current;
}
return last;
}

- Solution with Time O(n) and Space O(1) September 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args){
       
		String x="12786";
		
		
		int r=solve(x);
		System.out.println(r);
		
	}	
	
	public static int solve(String x){
		
		int sum = 0;
		int i =1;
		if (x.length()>0 && Integer.parseInt(x) < 27){
			sum = 1;
		}
		while (i < x.length()){
			sum = sum + solve(x.substring(i,x.length()));
			i++;
		}
		return sum;
	}

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

Isn't the answer just [ 1 + (# of valid two digit combinations < 26)! ]?
1, because you could count each number as one character. (E.x. 1111 would be AAAA)
Then you just have to loop over the string twice (once starting with the first letter, once starting with the second letter); count the number of two digit combinations < 26, take their factorial, and add them together.

For example:
11111111
would be 1 + 4! + 3! = 31. [ (11111111), or (11)(11)(11)(11), or 1(11)(11)(11)1 ]

This would run in O(n).

- Shahab Shekari September 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.core.javaTest;

import java.util.HashMap;

public class StringManipulationProblem {
	
	private String inputString;
	private String alphabetString;
	private static HashMap<Integer, Character> map = new HashMap<Integer, Character>();
	public StringManipulationProblem(String inputString){
		this.inputString = inputString;
		this.alphabetString = "";
	}
	
	static{
		map.put(1, 'A');map.put(6, 'F');map.put(11, 'K');map.put(16, 'P');map.put(21, 'U');
		map.put(2, 'B');map.put(7, 'G');map.put(12, 'L');map.put(17, 'Q');map.put(22, 'V');
		map.put(3, 'C');map.put(8, 'H');map.put(13, 'M');map.put(18, 'R');map.put(23, 'W');
		map.put(4, 'D');map.put(9, 'I');map.put(14, 'N');map.put(19, 'S');map.put(24, 'X');
		map.put(5, 'E');map.put(10, 'J');map.put(15, 'O');map.put(20, 'T');map.put(25, 'Y');
		map.put(26,  'Z');
	}
	
	public String getStringValue(int num){
		String stringVal = "";
		if(num <= 26){
			stringVal = String.valueOf(map.get(num));
		}
		return stringVal;
	}
	
	public void solveProblem(){
		char[] inputChar = this.inputString.toCharArray();
		for(int i = 0  ; i < inputChar.length ; i++){
			this.alphabetString = this.alphabetString + String.valueOf(map.get(Integer.parseInt(String.valueOf(inputChar[i]))));
		}
		System.out.println(this.alphabetString);
		String outputString = "";
		
		for(int j=0; j< this.inputString.length()-1; j++){
			if(!getStringValue(Integer.parseInt(String.valueOf(inputChar[j])+String.valueOf(inputChar[j+1]))).isEmpty()){
				outputString = this.alphabetString.substring(0, j) +  getStringValue(Integer.parseInt(String.valueOf(inputChar[j])+String.valueOf(inputChar[j+1]))) + this.alphabetString.substring(j+2);
				System.out.println(outputString);
			}
		}
		
	}
	
	public static void main(String str[]){
		StringManipulationProblem smp = new StringManipulationProblem("19191");
		smp.solveProblem();
	}

- Abhishek October 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int cno(string const &t) {

	vector<int> d[2];
	int n = t.size();
	d[0].resize(n, 0);
	d[1].resize(n, 0);
	d[0][0] = 1;
	d[0][1] = 1;

	if(t.size() >= 2)
		d[1][1] = ((t[0] - '0') * 10 + t[1] - '0') <= 26 ? 1 : 0;

	for(int i = 2; i < n; i++) {
		d[0][i] = d[1][i-1] + d[0][i-1];
		if(((t[i - 1] - '0') * 10 + t[i] - '0') <= 26) {
			d[1][i] = d[1][i-2] + d[0][i-2];
		}
	}
	return d[0][n-1] + d[1][n-1];
}

//dynamic programming solution

- Outermeasure October 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(N) time complexity and O(1) space complexity algorithm using dynamic programming

auto W = [](const string& S) {
	const auto n = S.length();
	int N[] = { 1, 0, 0 };
	for (int i = 0; i < n; ++i) {
		N[(i+1)%3] = '1' <= S[i] && S[i] <= '9' ? N[i%3] : 0;
		if (i >= 1) {
			N[(i+1)%3] += (S[i-1]-'0') * 10 + (S[i]-'0') <= 26 ? N[(i-1)%3] : 0;
		}
	};
	return N[n%3];
};

- anonymous November 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class HelloWorld{

     public static void main(String []args){
        System.out.println(method("1523"));
     }
     
     static int method(String input)
{
    if(input.length()==0)
        return 1;
    int oneDigit=method(input.substring(1));
    int twoDigit=0;
    if(input.length()>1 && Integer.parseInt(input.substring(0,2))<=26)    
        twoDigit=method(input.substring(2));
    return oneDigit+twoDigit;
}
}

- shajib khan November 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int numberOfCombination(String number)
	{
		if(number.length() == 1) {
			return 1;
		}
		if(number.length() == 0) {
			return 1;
		}

		int firstNumber = Integer.parseInt(number.substring(0, 2));

		if(firstNumber < 26) {
			//result = resul;
			return numberOfCombination(number.substring(1)) + numberOfCombination(number.substring(2));
		} else {
			return numberOfCombination(number.substring(1));
		}
	}

- Anonymous November 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int numberOfCombination(String number)
	{
		if(number.length() == 1) {
			return 1;
		}
		if(number.length() == 0) {
			return 1;
		}

		int firstNumber = Integer.parseInt(number.substring(0, 2));

		if(firstNumber < 26) {
			//result = resul;
			return numberOfCombination(number.substring(1)) + numberOfCombination(number.substring(2));
		} else {
			return numberOfCombination(number.substring(1));
		}
	}

- Anonymous November 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static public int numberOfCombination(String number)
	{
		if(number.length() == 1) {
			return 1;
		}
		if(number.length() == 0) {
			return 1;
		}

		int firstNumber = Integer.parseInt(number.substring(0, 2));

		if(firstNumber < 26) {
			//result = resul;
			return numberOfCombination(number.substring(1)) + numberOfCombination(number.substring(2));
		} else {
			return numberOfCombination(number.substring(1));
		}
	}

- Anonymous November 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int many = 0;
    static void findPossibleCombination(String num, int start) {
        if (start == num.length()) {
            many++;
            return;
        }
        for (int size = 0; size < 2; size++) {
            if (start + size == num.length()) {
                return;
            }
            final String first = num.substring(start, start + size + 1);
            final int value = Integer.valueOf(first);
            if (0 <= value && value < 25) {
                findPossibleCombination(num, start + size + 1);
            }
        }
    }

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

Regular recursive approach

static void allPossibleMappings(String str) {
		Map<Integer, Character> map = new HashMap<>();
		for(int i=0; i<26; i++) {
			map.put(i+1, (char)('A'+i));
		}
		mappings(map, str, 0, "");
	}
	
	static void mappings(Map<Integer, Character> map, String str, int start, String res) {
		if(start  == str.length()) {
			System.out.println(res);
			return;
		}
		for(int i=1; i + start <= str.length(); i++) {
			if(map.containsKey(Integer.parseInt(str.substring(start, start+i)))) {
				mappings(map, str, start+i, new String(res+map.get(Integer.parseInt(str.substring(start, start+i)))));
			}
			else { 
				return;
			}
		}
	}

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

Non-recursive version. C++

Idea is that on every digit you can
1. Treat it as a standalone digit
2. Complete 2-digit combo started on previous digit
3. Start new 2-digit combo

cases 1 and 2 add up to complete_mappings
case 3 carries previous value of complete_mappings over to next iteration as incomplete_mappings

bool CanComplete(string str, int i)
{
  if ( i == 0)
    return false;
  
  if ( str[i-1] == '0') return false;
  if ( str[i-1] == '1') return true;
  if ( str[i-1] == '2' && str[i] < '7') return true;
  return false;
}

int MappingsNum(string str)
{
   int complete_mappings_num = 1;
   int incomplete_mappings_num = 0;
   int length = str.size();
   for ( int i = 0; i < length; ++i)
   {
      if ( str[i] < '0' || str[i] > '9') // non-valid characters, mapping is impossible
        return 0;
      int next_complete_mappings_num = complete_mappings_num;    // simple one digit mapping 
      if (CanComplete(str, i))
        next_complete_mappings_num += incomplete_mappings_num; // add 2 digit mapping completed on this digit
      incomplete_mappings_num = complete_mappings_num;        // in case we can start new 2digit mapping
      complete_mappings_num = next_complete_mappings_num; // end processing this digit
   }
  return complete_mappings_num;
}

- borisshr August 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

no need to use string function at all;

input: a = "111";
then output should be strlen(a);

input: a= 123;
then output is strlen(a);

input: a = "11";
output : strlen(a);

input: a = "126";
output : strlen(a);

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

#include <stdio.h>
int main(int argc, char *argv[])
{
        char num[] = "111";
        int count=1, i, sum;
        int first_value, second_value;



        for(i=0; num[i+1] != '\0'; i++)
        {
                first_value = (num[i] - '0') * 10 ;
                second_value = num[i+1] - '0' ;

                if( (first_value + second_value) <= 26)
                        count++;
        }

        printf("count:%d\n", count);
}

- Sateesh June 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int count;
int get_number(char *str, int start, int end)
{
        int num = 0;

        while( start <= end)
        {
                num = num * 10 + str[start] - '0' ;
                start++;
        }

        return num;
}

int mapping(char *str, int start, int len)
{
        int i, num;

        if( start == len)
        {
                count++;
                return;
        }

        for(i = start; (i < len) && (i < (start + 2) ); i++)
        {
                 num = get_number(str, start , i);
                 if( num <= 26)
                        mapping(str, i + 1, len);
        }

        return count;
}

- sateesh July 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Dynamic programming is the key here. However, they mention it should work with *any* number sequence. Consider cases like "0000001" or "405006".

import string

def int2str( n ):
    return string.ascii_lowercase[n]

def getNumCombinations( stringNumber ):
    
    if len(stringNumber) == 1:
        if int(stringNumber) > 0:
            return 1
        else:
            return 0
    
    elif len(stringNumber) == 2:
        currInt = int(stringNumber)
        if currInt >=1 and currInt < 10:
            return 1
        else:
            return 2
    
    n1 = int(stringNumber[0])
    n2 = int(stringNumber[:2])
        
    if n1 == 0:
        if n2 != 0:
            return getNumCombinations( stringNumber[1:])
        elif n2 == 0:
            return getNumCombinations( stringNumber[2:])
    else:
        if n2>0 and n2<=26:
            return getNumCombinations( stringNumber[1:])+getNumCombinations( stringNumber[2:])
        else:
            return getNumCombinations( stringNumber[1:])

- mcruley August 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Looks like a simple Dynamic Programming problem. Start with a string of length 1. Initialize answer with 1 since 1 character can be a valid string. Add a new character to the string. If that character and the previous character together makes a valid string number (e.g. "23" but NOT "32") then add f(i-2) to the answer since this new 2-digit number permutes with those i-2 digits to create new valid combinations.

No need to memoize in 1-d array since only two valid states are required.

bool isValidStringNumber(char*str, int st, int end)
{
if(end-st>2)
return false;

if((str[st]>'2' || str[st+1]>'6') && end-st==2)
return false;


return true;
}

int StringNumberSplit(char*str, int st, int end) // mapping 1->a, 2->b , ... 26->z
{
int prev = 1;
int prevprev = 1;
int ans = 1;

for(int i=1;i<end;i++)
{
ans = prev ;

if(isValidStringNumber(str,i-1, i+1))
{
ans = ans + prevprev;

}
prevprev = prev ;
prev = ans ;
}

return ans;

}

- Rohan Raja August 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public class Count_Possible_Decodings_of_a_given_Digit_Sequence
{
public static void main(String []args)
{
String input = new String("121");
int length = input.length();
Count_Possible_Decodings_of_a_given_Digit_Sequence obj = new Count_Possible_Decodings_of_a_given_Digit_Sequence();
System.out.println(obj.countPossibleDecoding(input.toCharArray(),length));
}

private int countPossibleDecoding(char[] input, int length)
{
int count [] = new int[length+1];

count[0] = 1;
count[1] = 1;

for(int i =2;i<=length;i++)
{
count[i] = 0;

if(input[i-1] > '0')
{
count[i] = count[i-1];
}

if(input[i-2] <'2' || (input[i-2]=='2' && input[i-1] <'7'))
{
count [i] = count[i] + count[i-2];
}
}
return count[length];

}
}

- Prince Seth August 19, 2014 | 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