Facebook Interview Question
Android EngineersCountry: United States
Interview Type: Phone Interview
void Combs(unordered_map<char, vector<char>> &map, string const &digits,
vector<string> &combs, string const comb = "")
{
if (comb.size() == digits.size()) {
if (!comb.empty()) {
combs.push_back(comb);
}
return;
}
auto it = map.find(digits[comb.size()]);
if (it != map.end()) {
vector<char> const &chars = it->second;
for (char c : chars) {
Combs(map, digits, combs, comb + c);
}
}
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class CombLetters {
static Map<String, String[]> map = new HashMap<String, String[]>();
List<String> mix(String in, Map<String, String[]> map) {
List<String[]> l = new ArrayList<String[]>();
for (int i = 0; i < in.length(); i++) {
l.add(map.get(in.substring(i, i + 1)));
}
List<String> res = new ArrayList<>();
recMix(l, 0, "", res);
return res;
}
void recMix(List<String[]> letsGr, int i, String s, List<String> res) {
if (i == letsGr.size()) {
res.add(s);
return;
}
String[] lets = letsGr.get(i);
for (int j = 0; j < lets.length; j++) {
recMix(letsGr, i + 1, s + lets[j], res);
}
}
public CombLetters() {
map.put("1", new String[]{"a", "b", "c"});
map.put("2", new String[]{"c", "d", "e"});
map.put("3", new String[]{"f", "g", "h"});
}
public static void main(String[] args) {
// TODO Auto-generated method stub
List<String> l = new CombLetters().mix("12", map);
System.out.println(l);//[ac, ad, ae, bc, bd, be, cc, cd, ce]
}
}
Python Solution:
def crossword(dt,nums):
# populate temp dict for the given numbers
d = dict()
for i in range(len(nums)):
d[i] = dt.get(int(nums[i]))
print(d)
#call helper method with initial values
helper(d,'',0)
#helper method implementation
def helper(d,s,n):
temp =[]
if n == len(d):
print(s)
else:
temp = d.get(n)
for j in range(len(temp)):
helper(d,s+temp[j],n+1)
dt = {1: ['a','b','c'], 2: ['d','e','f'],3:['g','h','i']}
crossword(dt,'31')
#Output
# ga gb gc ha hb hc ia ib ic
static void Main(string[] args)
{
Dictionary<string, string[]> dict = new Dictionary<string, string[]>();
dict.Add("1", new []{"a","b","c"});
dict.Add("2", new [] { "d", "e","f"});
dict.Add("3", new [] {"g", "h","i"});
string input = "123";//Console.ReadLine();
List<string> results = Mix(input, dict);
Console.WriteLine($"Input: {input}, Output:");
foreach(var s in results)
{
Console.WriteLine(s);
}
}
static List<string> Mix(string input, Dictionary<string, string[]> dict)
{
string key = null;
List<string> results = new List<string>();
List<string> tempResults = null;
string[] keyChars = null;
for(int i = 0; i<input.Length; i++)
{
key = input.Substring(i, 1);
if(!dict.ContainsKey(key)) continue;
keyChars = dict[key];
if(i == 0)
{
results.AddRange(keyChars);
continue;
}
tempResults = new List<string>(results);
results = new List<string>();
foreach(var s in tempResults)
{
foreach(var ss in keyChars)
{
results.Add(s+ss);
}
}
}
return results;
}
static void Main(string[] args)
{
Dictionary<string, string[]> dict = new Dictionary<string, string[]>();
dict.Add("1", new []{"a","b","c"});
dict.Add("2", new [] { "d", "e","f"});
dict.Add("3", new [] {"g", "h","i"});
string input = "123";//Console.ReadLine();
List<string> results = Mix(input, dict);
Console.WriteLine($"Input: {input}, Output:");
foreach(var s in results)
{
Console.WriteLine(s);
}
}
static List<string> Mix(string input, Dictionary<string, string[]> dict)
{
string key = null;
List<string> results = new List<string>();
List<string> tempResults = null;
string[] keyChars = null;
for(int i = 0; i<input.Length; i++)
{
key = input.Substring(i, 1);
if(!dict.ContainsKey(key)) continue;
keyChars = dict[key];
if(i == 0)
{
results.AddRange(keyChars);
continue;
}
tempResults = new List<string>(results);
results = new List<string>();
foreach(var s in tempResults)
{
foreach(var ss in keyChars)
{
results.Add(s+ss);
}
}
}
return results;
}
static void Main(string[] args)
{
Dictionary<string, string[]> dict = new Dictionary<string, string[]>();
dict.Add("1", new []{"a","b","c"});
dict.Add("2", new [] { "d", "e","f"});
dict.Add("3", new [] {"g", "h","i"});
string input = "123";//Console.ReadLine();
List<string> results = Mix(input, dict);
Console.WriteLine($"Input: {input}, Output:");
foreach(var s in results)
{
Console.WriteLine(s);
}
}
static List<string> Mix(string input, Dictionary<string, string[]> dict)
{
string key = null;
List<string> results = new List<string>();
List<string> tempResults = null;
string[] keyChars = null;
for(int i = 0; i<input.Length; i++)
{
key = input.Substring(i, 1);
if(!dict.ContainsKey(key)) continue;
keyChars = dict[key];
if(i == 0)
{
results.AddRange(keyChars);
continue;
}
tempResults = new List<string>(results);
results = new List<string>();
foreach(var s in tempResults)
{
foreach(var ss in keyChars)
{
results.Add(s+ss);
}
}
}
return results;
}
Java solution
private static List<String> mix(String in, Map<String,String[]> map){
List<String> returnList = null;
for (int i = 0; i < in.length(); i++) {
//get the current i
returnList = mix(returnList,Arrays.asList(map.get(""+in.charAt(i))));
}
return returnList;
}
private static List<String> mix(List<String> list1, List<String> list2){
if(list1 == null) return list2;
if(list2 == null) return list1;
List<String> returnList = new ArrayList<>(list1.size()*list2.size());
for(String str1:list1)
for(String str2:list2)
returnList.add(str1+str2);
return returnList;
}
import java.util.List;
import java.util.Vector;
import java.util.Map;
import java.util.HashMap;
public class Mixer {
public static List<String> mix(String in, Map<String, String[]> map) {
List<String> combs = new Vector<String>();
int indexes[] = new int[in.length()];
do {
String word="";
for(int i=0;i<in.length();i++) word += map.get(Character.toString(in.charAt(i)))[indexes[i]];
combs.add(word);
} while(increment(indexes,0) == 0);
return combs;
}
private static int increment(int[] indexes, int order) {
if(order == indexes.length -1 && indexes[order]==2) return -1;
if(++indexes[order] == 3)
{
indexes[order]=0;
return increment(indexes, ++order);
}
return 0;
}
public static void main(String args[]) {
Map<String, String[]> map = new HashMap<String, String[]>();
map.put("1", new String[] { "a", "b", "c" });
map.put("2", new String[] { "c", "d", "e" });
map.put("3", new String[] { "f", "g", "h" });
String in = "12";
List<String> ret = mix(in,map);
for(int i=0;i<ret.size();i++) System.out.println(ret.get(i));
}
}
import java.util.List;
import java.util.Vector;
import java.util.Map;
import java.util.HashMap;
public class Mixer {
public static List<String> mix(String in, Map<String, String[]> map) {
List<String> combs = new Vector<String>();
int indexes[] = new int[in.length()];
do {
String word="";
for(int i=0;i<in.length();i++) word += map.get(Character.toString(in.charAt(i)))[indexes[i]];
combs.add(word);
} while(increment(indexes,0) == 0);
return combs;
}
private static int increment(int[] indexes, int order) {
if(order == indexes.length -1 && indexes[order]==2) return -1;
if(++indexes[order] == 3)
{
indexes[order]=0;
return increment(indexes, ++order);
}
return 0;
}
public static void main(String args[]) {
Map<String, String[]> map = new HashMap<String, String[]>();
map.put("1", new String[] { "a", "b", "c" });
map.put("2", new String[] { "c", "d", "e" });
map.put("3", new String[] { "f", "g", "h" });
String in = "12";
List<String> ret = mix(in,map);
for(int i=0;i<ret.size();i++) System.out.println(ret.get(i));
}
}
This will work for any input , not just for "12"
private static void printAllCombos(String query, Map map) {
char[] arr = query.toCharArray();
Set result = new HashSet<>();
for(int a = 0; a < arr.length ; a++) {
for(int b=a+1; b < arr.length; b++) {
String[] a1 = (String[]) map.get(String.valueOf(arr[a]));
String[] a2 = (String[]) map.get(String.valueOf(arr[b]));
for(int c = 0; c < a1.length ; c++) {
for (int d = 0; d < a2.length; d++) {
result.add(a1[c]+a2[d]);
}
}
}
}
Iterator<String> it = result.iterator();
while(it.hasNext()) {
System.out.println(it.next());
}
}
Python solution:
def phoneNumber(digits):
dic= {'1':'abc','2':'def','3':'ghi','4':'jkl'}
def helper(digits, curr_string, dic, res):
if not digits:
res.append(curr_string)
return
for char in dic[digits[0]]:
helper(digits[1:], curr_string+char, dic, res)
res = []
helper(str(digits), '', dic, res)
print(' possible combination of phone {}'.format(res))
return
def main():
# PhoneNumber
number = "12"
#phoneNumber(number)
public static String [] phoneNumberChars( Map map, String in) {
String [] str1 = (String[]) map.get(String.valueOf(in.charAt(0)));
String [] str2 = (String[])map.get(String.valueOf(in.charAt(1)));
String [] result = new String[str1.length * str2.length];
int index=0;
for(int i=0; i<str1.length;i++) {
for(int j=0; j<str2.length;j++) {
result[index]=str1[i]+str2[j];
index++;
}
}
return result;
}
Scala
object NumberStringCombinations extends App {
val conversion = Map(
'1' -> List('a', 'b', 'c'),
'2' -> List('c', 'd', 'e'),
'3' -> List('f', 'g', 'h'))
def combinations(in: String, agg: String = ""): List[String] = in match {
case "" => List(agg)
case str => conversion(str.head).flatMap(c => combinations(str.tail, agg + c))
}
println(combinations("12"))
}
private List<String> getAllCombinations(String phoneNumber) {
List<String> combinations = new ArrayList<>();
calculateCombination(phoneNumber, 0, new char[phoneNumber.length()], combinations);
return combinations;
}
private void calculateCombination(String phoneNumber,
int phoneNumberIndex,
char[] partialMnemonic,
List<String> mnemonics){
if (phoneNumberIndex == phoneNumber.length()){
// Add combination
mnemonics.add(new String(partialMnemonic));
return;
}
// Calculate all keys
int phoneNumberDigit = phoneNumber.charAt(phoneNumberIndex) - '0';
int letterCount = MAPPING.get(phoneNumberDigit).length;
for (int i=0; i < letterCount; i++){
partialMnemonic[phoneNumberIndex] = MAPPING.get(phoneNumberDigit)[i].charAt(0);
calculateCombination(phoneNumber, phoneNumberIndex + 1, partialMnemonic, mnemonics);
}
}
JavaScript solution.
- Anonymous November 10, 2017