## 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]);
}``````

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?

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

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;

}

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)

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.

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];
}``````

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'));``````

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

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)

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

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

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

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.

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

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

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

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) {
} else if (remaining.length() == 1) {
String charMap = convert(remaining);
if (charMap != null) {
}
} 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));
}``````

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

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

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

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

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

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

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

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

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

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

String last2 = this.am.get(number);
if(null != 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){
}

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

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

}``````

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

}

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

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

Memoization can easily be added, to improve runtime

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 tail = n>=100? Integer.parseInt(nstr.substring(2)) : 0;

}``````

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

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];

}
}

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

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

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

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

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

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

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];
};``````

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

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

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

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

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

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

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

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

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

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

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:])``````

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;

}

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];

}
}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.