Facebook Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
Scala code for it using recursion.
object Encoder {
def main(args: Array[String]): Unit = {
allValidEncodedValues("12")
}
def toAlphabet(i : Int): String = (i+64).toChar.toString
def allValidEncodedValues(ss : String): Any = {
def loop(str : String, acc : String) : Unit = {
if(str.isEmpty) print(acc)
else if (str.length == 1) print(acc + toAlphabet(str.toInt))
else{
val secPart = str.substring(0,2)
loop(str.substring(2,str.length), acc + toAlphabet(secPart.toInt))
println
val firstPart = str.substring(0,1)
loop(str.substring(1,str.length), acc + toAlphabet(firstPart.toInt))
}
}
loop(ss,"")
}
}
O(n) Solution
public static int numDecodings(String s) {
if(s == null || s.length() == 0) {
return 0;
}
int n = s.length();
int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = s.charAt(0) != '0' ? 1 : 0;
for(int i = 2; i <= n; i++) {
int first = Integer.valueOf(s.substring(i-1, i));
int second = Integer.valueOf(s.substring(i-2, i));
if(first >= 1 && first <= 9) {
dp[i] += dp[i-1];
}
if(second >= 10 && second <= 26) {
dp[i] += dp[i-2];
}
}
return dp[n];
}
//Iterative Time Complexity:O(N)
public int countEncodings(String str){
if(str == null || str.length() == 0 || str.charAt(0) == 0){
return 0;
}
int n_1 = 1;
int n_2 = 1;
for(int i = 1; i < str.length(); i++){
int oneDigit = Integer.parseInt(str.substring(i,i+1));
int twoDigit = Integer.parseInt(str.substring(i - 1, i + 1));
if(oneDigit == 0 && twoDigit == 0){
return 0;
}
int nextTotal = 0;
if(oneDigit >= 1 && oneDigit < 10){
nextTotal += n _ 1;
}
if(twoDigit >= 10 && twoDigit <= 26){
nextTotal += n _2;
}
n_2 = n_1;
n_1=nextTotal;
}
return n_1;
}
function nTranslations(s) {
if(s == null || s.length == 0) {
return 0;
}
n = s.length;
dp = Array(n + 1).fill(0);
dp[0] = 1;
dp[1] = s[0] != '0' ? 1 : 0;
for(i = 2; i <= n; i++) {
first = parseInt(s.substring(i-1, i), 10);
second = parseInt(s.substring(i-2, i), 10);
if(first >= 1 && first <= 9) {
dp[i] += dp[i-1];
}
if(second >= 10 && second <= 26) {
dp[i] += dp[i-2];
}
}
return dp[n];
}
public class Solution {
public int getNumValidCombinations(String number) {
Map<String, Integer> cache = new Map<>();
if(number == null || number.isEmpty()) {
return 0;
}
return this.getNumValidCombinations(number, 0, cache);
}
private int getNumValidCombinations(String number, int index, Map<String, Integer> cache) {
if(index >= number.length) {
return 1;
}
else if(Integer.parse(number.charAt(index)) <= 0 || Integer.parse(number.charAt(index)) >= 10) {
throw new IllegalArgumentException("Param is not valid");
}
else if(cache.hasKey(number.substring(index, number.length))) {
return cache.get(number.substring(index, number.length));
}
int numWays = 0;
for(int i = index; i < number.length; i++) {
if(!isValid(number, index, i)) {
break;
}
numWays += this.getNumValidCombinations(number, i + 1, cache);
}
cache.put(number.substring(index, number.length), numWays);
return numWays;
}
/**
Returns true if we should consider the next character in the same iteration otherwise return false
*/
private boolean isValid(String number, int indexFrom, int indexTo) {
if( indexFrom - indexTo >= 2 || indexFrom >= number.length || indexTo >= number.length || indexFrom < indexTo ||
number.charAt(indexFrom) < 1 || number.charAt(indexFrom) > 2 || number.getCharAt(indexTo) >= 7 ||
number.getCharAt(indexTo) <= 0) {
return false;
}
return true;
}
}
<?php
function Combinations($n) {
if (strlen($n) == 1) return 1;
else {
$valid = 0;
for ($i=0; $i<strlen($n)-1; $i++) {
echo "$i\n";
if (IsValid(substr($n, $i, 2)))
$valid++;
}
return $valid + strlen($n);
}
}
function IsValid($number) {
if (strlen($number) == 1) return 1;
else if (strlen($number) && (int)$number>0 && (int) $number <=26 ) return 1;
else return 0;
}
// main
$number = 26377654;
echo $number[0];
$numberS = "$number";
echo "Combinations: ".Combinations($numberS)."\n";
?>
<?php
function Combinations($n) {
if (strlen($n) == 1) return 1;
else {
$valid = 0;
for ($i=0; $i<strlen($n)-1; $i++) {
echo "$i\n";
if (IsValid(substr($n, $i, 2)))
$valid++;
}
return $valid + strlen($n);
}
}
function IsValid($number) {
if (strlen($number) == 1) return 1;
else if (strlen($number) && (int)$number>0 && (int) $number <=26 ) return 1;
else return 0;
}
// main
$number = 26377654;
echo $number[0];
$numberS = "$number";
echo "Combinations: ".Combinations($numberS)."\n";
?>
public class ValidCombinations {
public int solution(String decode){
int count=0;
if(decode.length()==0 || decode.isEmpty()){
return 1;
}
if(Integer.parseInt(decode.substring(0,1)) < 26){
count = solution(decode.substring(1));
}
if(decode.length()>=2) {
if (Integer.parseInt(decode.substring(0, 2)) < 26) {
count+= solution(decode.substring(2));
}
}
return count;
}
public static void main(String[] args){
ValidCombinations v = new ValidCombinations();
System.out.println(v.solution("1221"));
}
}
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
public class GenTokens {
private Map<Integer, Character> getIndexToks() {
Map<Integer, Character> tokens = new HashMap<>();
int index = 1;
for (char alphabet = 'a'; alphabet <= 'z'; alphabet++) {
tokens.put(index++, alphabet);
}
return tokens;
}
public void tokens(String token) {
char[] chars = token.toCharArray();
Map<Integer, Character> tokens = getIndexToks();
Set<String> tokenHolder = new HashSet<String>();
int tokenLength = chars.length;
char[] transTok = new char[tokenLength];
int loc = 0;
for (char c : chars) {
int intValue = Integer.parseInt(c + "");
char tokChar = tokens.get(intValue);
transTok[loc++] = tokChar;
}
tokenHolder.add(String.valueOf(transTok));
for (int index = 0; index < tokenLength; index++) {
transTok = new char[tokenLength];
for (int index1 = 0; index1 < index; index1++) {
int intValue = Integer.parseInt(chars[index1] + "");
char tokChar = tokens.get(intValue);
transTok[index1] = tokChar;
}
loc = index;
for (int index2 = index; index2 < tokenLength; index2++) {
if (index2 + 1 < tokenLength) {
int tok = Integer
.parseInt(chars[index2] + "" + chars[index2 + 1]);
if (tok <= 26) {
transTok[loc++] = tokens.get(tok);
index2++;
} else {
int intValue = Integer.parseInt(chars[index2] + "");
char tokChar = tokens.get(intValue);
transTok[loc++] = tokChar;
}
}
}
tokenHolder.add(String.valueOf(transTok));
}
for(String strTok: tokenHolder){
System.out.println(strTok);
}
}
public static void main(String[] args) {
GenTokens genTokens = new GenTokens();
genTokens.tokens("12393213");
}
}
and
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
public class GenTokens {
private Map<Integer, Character> getIndexToks() {
Map<Integer, Character> tokens = new HashMap<>();
int index = 1;
for (char alphabet = 'a'; alphabet <= 'z'; alphabet++) {
tokens.put(index++, alphabet);
}
return tokens;
}
public void tokens(String token) {
char[] chars = token.toCharArray();
Map<Integer, Character> tokens = getIndexToks();
Set<String> tokenHolder = new HashSet<String>();
int tokenLength = chars.length;
char[] transTok = new char[tokenLength];
int loc = 0;
for (char c : chars) {
int intValue = Integer.parseInt(c + "");
char tokChar = tokens.get(intValue);
transTok[loc++] = tokChar;
}
tokenHolder.add(String.valueOf(transTok));
for (int index = 0; index < tokenLength; index++) {
transTok = new char[tokenLength];
for (int index1 = 0; index1 < index; index1++) {
int intValue = Integer.parseInt(chars[index1] + "");
char tokChar = tokens.get(intValue);
transTok[index1] = tokChar;
}
loc = index;
for (int index2 = index; index2 < tokenLength; index2++) {
if (index2 + 1 < tokenLength) {
int tok = Integer
.parseInt(chars[index2] + "" + chars[index2 + 1]);
if (tok <= 26) {
transTok[loc++] = tokens.get(tok);
index2++;
} else {
int intValue = Integer.parseInt(chars[index2] + "");
char tokChar = tokens.get(intValue);
transTok[loc++] = tokChar;
}
}
}
tokenHolder.add(String.valueOf(transTok));
}
for(String strTok: tokenHolder){
System.out.println(strTok);
}
}
public static void main(String[] args) {
GenTokens genTokens = new GenTokens();
genTokens.tokens("12393213");
}
}
and
package com.me.binarytree;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
public class GenTokens {
private Map<Integer, Character> getIndexToks() {
Map<Integer, Character> tokens = new HashMap<>();
int index = 1;
for (char alphabet = 'a'; alphabet <= 'z'; alphabet++) {
tokens.put(index++, alphabet);
}
return tokens;
}
public void tokens(String token) {
char[] chars = token.toCharArray();
Map<Integer, Character> tokens = getIndexToks();
Set<String> tokenHolder = new HashSet<String>();
int tokenLength = chars.length;
char[] transTok = new char[tokenLength];
int loc = 0;
for (char c : chars) {
int intValue = Integer.parseInt(c + "");
char tokChar = tokens.get(intValue);
transTok[loc++] = tokChar;
}
tokenHolder.add(String.valueOf(transTok));
for (int index = 0; index < tokenLength; index++) {
transTok = new char[tokenLength];
for (int index1 = 0; index1 < index; index1++) {
int intValue = Integer.parseInt(chars[index1] + "");
char tokChar = tokens.get(intValue);
transTok[index1] = tokChar;
}
loc = index;
for (int index2 = index; index2 < tokenLength; index2++) {
if (index2 + 1 < tokenLength) {
int tok = Integer
.parseInt(chars[index2] + "" + chars[index2 + 1]);
if (tok <= 26) {
transTok[loc++] = tokens.get(tok);
index2++;
} else {
int intValue = Integer.parseInt(chars[index2] + "");
char tokChar = tokens.get(intValue);
transTok[loc++] = tokChar;
}
}
}
tokenHolder.add(String.valueOf(transTok));
}
for(String strTok: tokenHolder){
System.out.println(strTok);
}
}
public static void main(String[] args) {
GenTokens genTokens = new GenTokens();
genTokens.tokens("12393213");
}
}
static int translationNumber(String s) {
return translationNumberInternal(s, "", 0);
}
private static int translationNumberInternal(String s, String untilNow, int translationCount) {
for (int i = 1; i <= 2 && i <= s.length(); i++) {
int n = Integer.parseInt(s.substring(0, i));
String remainder = s.substring(i);
if (n > 0 && n < 27) {
String newUntilNow = untilNow + ((char)('a' + n - 1));
if (remainder.isEmpty())
return translationCount+1;
else
translationCount = translationNumberInternal(remainder, newUntilNow, translationCount);
}
}
return translationCount;
}
{{
static int translationNumber(String s) {
return translationNumberInternal(s, "", 0);
}
private static int translationNumberInternal(String s, String untilNow, int translationCount) {
for (int i = 1; i <= 2 && i <= s.length(); i++) {
int n = Integer.parseInt(s.substring(0, i));
String remainder = s.substring(i);
if (n > 0 && n < 27) {
String newUntilNow = untilNow + ((char)('a' + n - 1));
if (remainder.isEmpty())
return translationCount+1;
else
translationCount = translationNumberInternal(remainder, newUntilNow, translationCount);
}
}
return translationCount;
}
}}
Here is a solution in JavaScript. It is not optimized (memoization is an option):
function nTranslations(number) {
if (number.length <= 1) {
return 1;
}
return isValid(number[0]) * nTranslations(number.substring(1, number.length)) +
nTranslations(number[0]) * isValid(number.substring(1, number.length));
}
function isValid(s) {
if (s.length === 1) {
return 1;
}
else if (s.length == 2) {
return parseInt(s, 10) <= 26;
}
return 1;
}
Here is the C# code with explanation:
- sminfo March 12, 2017using System; using System.Collections.Generic; namespace PracticeProgrammingPack { public partial class Program { public static void Main() { string input = "7616419165243716"; foreach (var solution in TranslateNumbersToChars(input)) { Console.WriteLine(solution); } } private static List<string> TranslateNumbersToChars(string numbersSeq) { // TODO: if numbersSeq is null or not all characters are between '1' and '9' // throw argument exception // One option could be converting numbersSeq from string to an integer or long // This should assume that the sequence will not exist int or long capacity // this will make the encoding logic cleaner, // but then taking out the prefix will be messier return BuildSubSequenses(numbersSeq); } // This method recursively builds all possible string-encoded presentations. // The algorithm is, for example for "1234", all possible encoding are the union of: // "a" + BuildSubSequenses("234") and "l" + BuildSubSequenses("34") // then again, for "234", all possible encoding are the union of: // "b" + BuildSubSequenses("34") and "w" + BuildSubSequenses("4") private static List<string> BuildSubSequenses(string subSequense) { if (subSequense.Length == 0) { return null; } if (subSequense.Length == 1) { return new List<string> { EncodeIntToString(subSequense) }; } List<string> solutions = new List<string>(); string prefix = subSequense.Substring(0, 1); List<string> subSolutions = BuildSubSequenses(subSequense.Substring(1)); foreach (var subSolution in subSolutions) { solutions.Add(EncodeIntToString(prefix) + subSolution); } if (subSequense.Length >= 2) { prefix = subSequense.Substring(0, 2); int prefixValue = int.Parse(prefix); if (prefixValue >= 1 && prefixValue <= 26) { subSolutions = BuildSubSequenses(subSequense.Substring(2)); if (subSolutions == null) { solutions.Add(EncodeIntToString(prefix)); } else foreach (var subSolution in subSolutions) { solutions.Add(EncodeIntToString(prefix) + subSolution); } } } return solutions; } private static string EncodeIntToString(string intPresentation) { const int AsciiOffset = 96; // for example 'a' ASCII code is 1 + 96 = 97 return ((char)(int.Parse(intPresentation) + AsciiOffset)).ToString(); } } }