Facebook Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




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

public class SubCombinations {
    private static List<String> getCombinations(Map<String, List<String>> map, String s) {
        List<String> result = map.getOrDefault(s, new ArrayList<>());

        for (int i=1; i<s.length(); i++) {
            String word = s.substring(0, i);
            List<String> chars = map.get(word);
            if (chars != null) {
                String rest = s.substring(i, s.length());
                List<String> subs = getCombinations(map, rest);
                for (String ch : chars) {
                    for (String sub : subs) {
                        result.add(ch + sub);
                    }
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println(getCombinations(new HashMap<String, List<String>>() {{
            put("1", Arrays.asList("A", "B", "C"));
            put("2", Arrays.asList("D", "E"));
            put("12", Arrays.asList("X"));
            put("3", Arrays.asList("P", "Q"));
        }}, "123"));
    }
}

- sema638 July 15, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

import java.util.*;

public class Solution {
	public static void main(String[] args) {
		Map<String, String[]> m = new HashMap<String, String[]>();
		m.put("1", new String[] { "A", "B", "C" });
		m.put("2", new String[] { "D", "E" });
		m.put("12", new String[] { "X" });
		m.put("3", new String[] { "P", "Q" });

		String string = "123";

		List<String> keys = new ArrayList<String>(m.keySet());

		List<String> patterns = new ArrayList<String>();
		for (int i = 0; i < keys.size(); i++) {
			if(!string.startsWith(keys.get(i))) {
				continue;
			}
			List<String> keyList = new ArrayList<String>();
			keyList.add(keys.get(i));
			String tmp = string.substring(keys.get(i).length());
			int j = i + 1;
			// checking of 'j' is important, otherwise it will be infinite loop if given string is not found
			while (!tmp.isEmpty() && j < keys.size()) {
				for (; j < keys.size(); j++) {
					if (tmp.startsWith(keys.get(j))) {
						tmp = tmp.substring(keys.get(j).length());
						keyList.add(keys.get(j));
						break;
					}
				}
			}
			if(!stringFound(string,keyList)) {
				continue;
			}
			patterns.addAll(generatePatterns(m, keyList));
		}
		System.out.println(patterns.toString());
	}

	private static List<String> generatePatterns(Map<String, String[]> m, List<String> keyList) {
		List<String> patterns = new ArrayList<String>();
		for(String key: keyList) {
			if (patterns.size() == 0) {
				patterns.addAll(Arrays.asList(m.get(key)));
				continue;
			}
			List<String> tmpPatterns = new ArrayList<String>();
			String[] candidateArr = m.get(key);
			for (String pattern : patterns) {
				for(String candidate : candidateArr) {
					tmpPatterns.add(pattern.concat(candidate));
				}
			}
			patterns = tmpPatterns;
		}
		return patterns;
	}

	private static boolean stringFound(String string, List<String> keyList) {
		String str ="";
		for(String key : keyList) {
			str += key;
		}
		return str.equals(string);
	}
}

- miraj April 01, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package main

import (
	"fmt"
	"strings"
)

func patterns(m map[string][]string, str string) []string {
	res := []string{}
	if len(str) == 0 {
		return []string{""}
	}
	for k := range m {
		if strings.HasPrefix(str, k) {
			for _, kv := range m[k] {
				ends := patterns(m, str[len(k):])
				for _, e := range ends {
					res = append(res, kv+e)
				}
			}
		}
	}
	return res
}

func main() {
	m := map[string][]string{
		"1":  {"A", "B", "C"},
		"2":  {"D", "E"},
		"12": {"X"},
		"3":  {"P", "Q"},
	}
	fmt.Println(patterns(m, "123"))
}

- dmitry.labutin March 30, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class findPattern:
    def __init__(self, indices):
        self.indices = indices

    def compute(self, str):

        if not len(str):
            return {}
        i = 0
        c_ret = set()
        for i,c in enumerate(str):
            if str[0:i+1] in self.indices:
                s = str[0:i+1]
                res = self.compute(str[i+1:])
                for x in self.indices[s]:
                    if not len(res):
                        c_ret.add(x)
                    else:
                        for y in res:
                            c_ret.add(x+y)

        return c_ret




X = {'1': ['A', 'B', 'C'], '2': ['D', 'E'], '12' : ['X'], '3' : ['P', 'Q']}
P = findPattern(X)
print list(P.compute('123'))

- vikalpveer March 31, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>  


std::vector<std::string> collect(std::unordered_map<std::string, std::list<std::string>> & data, const std::string & part)
{
	std::vector<std::string> results;


	for (int i = 1; i <= part.length(); i++) {
		std::string s = part.substr(0, i);

		auto it = data.find(s);
		if (it != data.end()) {


			if (s.length() == part.length()) {
				for (auto && it3 : it->second) {
					results.push_back(it3);
				}
			}
			else {
				std::string h = part.substr(i, part.length() - i);
				std::vector<std::string> sub_results = collect(data, h);
				for (auto && it3 : it->second) {
					for (auto && it2 : sub_results) {
						results.push_back(it3 + it2);
					}
				}
				
			}
		}
		
	}
	return results;
}



int main()
{
	std::unordered_map<std::string, std::list<std::string>> data;
	data["1"].push_back("A");
	data["1"].push_back("B");
	data["1"].push_back("C");

	data["2"].push_back("D");
	data["2"].push_back("E");

	data["12"].push_back("X");

	data["3"].push_back("P");
	data["3"].push_back("Q");


	std::vector<std::string> results = collect(data, "123");

	for (auto && it2 : results) {
		std::cout << it2 << " ";
	}

	return 0;
}

- mamajonok April 02, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class AllPossiblePatterns {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		HashMap<String, char[]> map = new HashMap<>();
		char arr1[]={'A', 'B', 'C'};
		map.put("1", arr1);
		char arr2[]={'D', 'E'};
		map.put("2", arr2);
		char arr3[]={'X'};
		map.put("12", arr3);
		char arr4[]={'P', 'Q'};
		map.put("3", arr4);

		printallpatters(map, "123");
	}

	private static void printallpatters(HashMap<String, char[]> map, String input) {
		// TODO Auto-generated method stub
		List<String> result = new ArrayList<>();
		helper(result, new StringBuffer(), input, map, 0 );
		System.out.println(result);
	}

	private static void helper(List<String> result, StringBuffer temp, String input, 
			HashMap<String, char[]> map,
			int pos) {
		if(pos == input.length()){
			result.add(new String(temp));
			return;
		}

		char branches[] = map.get(String.valueOf(input.charAt(pos)));
		if(branches!=null){
			for(int i=0;i<branches.length;i++) {
				temp.append(branches[i]);
				helper(result, temp, input, map, pos+1);
				temp.deleteCharAt(temp.length()-1);
			}
		}

		if(pos+2 <= input.length()){
			//System.out.println(input.substring(pos, pos+2));
			branches = map.get(input.substring(pos, pos+2));
			if(branches!=null){
				//System.out.println(branches);
				for(int i=0;i<branches.length;i++) {
					temp.append(branches[i]);
					helper(result, temp, input, map, pos+2);
					temp.deleteCharAt(temp.length()-1);
				}
			}
		}

	}
}

- vim April 03, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def get_patterns(digit, s=0):
	values = {'1': ['A', 'B', 'C'],
			  '2': ['D', 'E'],
			  '12': ['X'],
			  '3': ['P', 'Q']}

	if s == len(digit)-1:
		return values.get(digit[s], [])

	res = list()
	for i in range(s, len(digit)-1):
		sub_p = get_patterns(digit, i+1)
		for l1 in sub_p:
			for l2 in values.get(digit[s:i+1], []):
				res.append(l2+l1)
	return res

print(get_patterns('123'))

- CodeDealer April 04, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Inspired by @dmitry.labutin this is a Java version of that solution:

import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;

public class Solution{
    public List<String> patterns(Map<String,String[]> m, String str) {
        List<String> res = new ArrayList<String>();
        if (str.length() == 0){
            return res;
        }
        for (String k : m.keySet()) {
            if (str.startsWith(k)) {
                for(String kv : m.get(k)) {
                    String strSubstr = str.substring(k.length());
                    if((strSubstr.length() == 0)) res.add(kv);
                    else {
                        List<String> ends = patterns(m, strSubstr);
                        for (String e : ends) {
                            res.add(kv+e);
                        }
                    }
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Map<String, String[]> m1 = new HashMap<String, String[]>();
        m1.put("1", new String[]{"A","B","C"});
        m1.put("2", new String[]{"D","E"});
        m1.put("12", new String[]{"X"});
        m1.put("3", new String[]{"P","Q"});

        Solution sol = new Solution();
        List<String> out = sol.patterns(m1,  "123");
        for(String s : out){
            System.out.println(s);
        }
    }
}

- michal.foune April 06, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Scala

object Patterns extends App {
  val transforms = List(
    ("1", "ABC"),
    ("2", "DE"),
    ("3", "PQ"),
    ("12", "X"))

  println(patterns("123"))

  def conversions(str: String, agg: List[String] = List.empty): List[List[String]] = {
    if (str.length == 0) return List(agg)
    transforms.flatMap { case (from, to) =>
      if (str.startsWith(from)) {
        conversions(str.substring(from.length), agg :+ to)
      } else {
        List.empty
      }
    }
  }

  def combinations(lst: List[String], agg: String = ""): List[String] = lst match {
    case "" :: rest => combinations(rest, agg)
    case str :: rest => str.flatMap(c => combinations(rest, agg + c)).toList
    case _ => List(agg)
  }

  def patterns(input: String) = conversions(input).flatMap(combinations(_))
}

- jvmakine April 06, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

input_str = '123'
# input_str = '1'

d = {
    '1' : ['A', 'B', 'C'],
    '2' : ['D', 'E'],
    '12' : ['X'],
    '3' : ['P', 'Q']
}

def permute(res_str, in_str):
    if in_str == '':
        print(res_str)
        return
#     get letter or multiple of them
    for i in range(1, len(in_str)+1):
        key = in_str[:i]
        if key in d:
            # print('key found', key)
            for item in d[key]:    
                permute(res_str + item, in_str[i:])

permute(res_str='',in_str=input_str)

- bojan April 08, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

vector<string> getPermutation(map<string, vector<char>> input, string value) {
    vector<string> values;
    vector<string> result, output;
    string currConcat, currStr;
    int index = 0, len = 1;
    
    result.push_back("");

    while (index < value.length()) {
        if (index + len <= value.length())
            currStr = value.substr(index, len);
        else
            currStr = value.substr(index);
        if (input.find(currStr) != input.end()) {
            vector<char> current = input[currStr];
            vector<string> temp;
            for (char c : current) {
                for (int i = 0; i < result.size(); i++) {
                    string res;
                    res += result[i];
                    res.push_back(c);
                    temp.push_back(res);
                }
            }
            currConcat += currStr;
            result = temp;
        }
        if (currConcat == value) {
            index = 0;
            len++;
            currConcat = "";
            output = result;
            result.clear();
            result.push_back("");
        } else {
            index += len;
        }
    }
    return output;
}

- sue April 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// 123, map 1 - > {A,B,C} 2->{D,E}, 12->{X}, 3->{P,Q}
// AEP...., XP, XQ
vector<string> getPermutation(map<string, vector<char>> input, string value) {
    if (input.find(value) != input.end()) {
        vector<string> result;
        for (auto c : input[value]) {
            string temp;
            temp.push_back(c);
            result.push_back(temp);
        }
        return result;
    }
    vector<string> result;
    for (int i = 1; i < value.length(); i++) {
        vector<string> p1 = getPermutation(input, value.substr(0 ,i));
        vector<string> p2 = getPermutation(input, value.substr(i));
        for (auto c1 : p1) {
            for (auto c2 : p2) {
                string temp (c1 + c2);
                result.push_back(temp);
            }
        }
    }
    return result;
}

- sue April 29, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void recurse(unordered_map<int, string> s, vector<int> indices, int ind, int n, vector<string>& result, string str)
{
	if (ind >= n) return;
	if (ind == 0) str.clear();
	string temp = s.find(indices[ind])->second;
	string::iterator it = temp.begin();

	while (it!=temp.end())
	{
		if (ind == n - 1)
			result.push_back(str + *it);
		recurse(s, indices, ind + 1, n, result, str + *it);
		it++;
	}
		
}

void permutations(unordered_map<int, string> s, vector<int> indices)
{
	string temp;
	int n = indices.size();
	vector<string> result;
	recurse(s, indices, 0, n, result, temp);
	for (auto i : result)
		cout << i << " ";
}


int main() {
	vector<int> indices = {1,2, 3};
	unordered_map<int, string> strs;
	strs.insert({ 1, "ABC" });
	strs.insert({ 2, "DE" });
	strs.insert({ 12, "X" });
	strs.insert({ 3, "PQ" });
	permutations(strs, indices);
	return 0;
}

- aman.bansal4u May 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// javascript solution
let obj = {
  a: ["A", "B", "C"],
  b: ["D", "E"],
  ab: ["X"],
  c: ["Q", "P"]
};

let final = [];

const patterns = (str, prefix='') => {
  if (str === '') {
    if (prefix.length > 0) final.push(prefix);
    return;
  }

  for (let i = 1; i <= str.length; i++) {
    let subprefix = str.slice(0,i);
    if (obj.hasOwnProperty(subprefix)) {
      obj[subprefix].forEach(e => {
        patterns(str.slice(i), prefix + e);
      });
    }
  }
}

patterns('abc');

- rantelo June 09, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

func find(_ digits: [Character]) -> [String] {
    var result = [String]()
    let map = ["1": ["A","B","C"], "2": ["D","E"], "12": ["X"], "3": ["P", "Q"]]
    
    var dp = [[String]](repeating:[String](repeating:"", count: 0), count: digits.count+1)
    dp[0] = []
    
    for i in stride(from: 0, to: digits.count, by: 1) {
        result.removeAll()
        
        if i == 0 {
            //only single
            var chars = map[String(digits[i])]!
            chars.forEach {
                result.append(String($0))
            }
            dp[i+1] = result
        } else {
            var partialResult = dp[i]
            
            //ones
            let ones = map[String(digits[i])]!
            for pr in partialResult {
                for one in ones {
                    result.append(pr + String(one))
                }
            }
            let twoKey = String("\(digits[i-1])\(digits[i])")
            if ["12"].contains(twoKey) {
                var partialResult = dp[i-1]
                let twos = map[twoKey]!
                if i == 1 {
                    twos.forEach {
                        result.append(String($0))
                    }
                } else{
                    for pr in partialResult {
                        for two in twos {
                            result.append(pr + String(two))
                        }
                    }
                }
            }
            dp[i+1] = result
        }
        
    }
    return dp[digits.count]
}

- ar June 20, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

we are in need of the same program with c coding

- jashwant June 28, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package poc;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * 
 * @author Nalin
 *
 */
public class PatternAgain {
	/*
	 * output [adp, adq, aep, aeq, bdp, bdq, bep, beq, cdp, cdq, cep, ceq, xp, xq]
	 */
	public static void main(String[] args) {
		Map<String, List<Character>> map = new HashMap<>();
		map.put("1", Arrays.asList('a', 'b', 'c'));
		map.put("2", Arrays.asList('d', 'e'));
		map.put("12", Arrays.asList('x'));
		map.put("3", Arrays.asList('p', 'q'));

		String s = "123";
		List<String> l = new ArrayList<>();
		char[] arr = s.toCharArray();
		for (char a : arr) {
			l.add(String.valueOf(a));
		}
		Set<List<String>> combinations = new HashSet<>();
		combinations.add(l);
		rec(s, l, combinations);
		
		// all the combinations generated
		List<List<String>> list = new ArrayList<>(combinations);
		List<String> out = new ArrayList<>();
		//combinations.forEach(System.out::println);

		// please bear learning java 8, but it's not very java 8ish, filtering
		// combinations
		list = list.stream().filter((List<String> innerList) -> {
			boolean[] toConsider = { true };
			innerList.stream().forEach(item -> {
				if (!map.containsKey(item)) {
					toConsider[0] = false;
				}
			});
			return toConsider[0];
		}).collect(Collectors.toList());

		// finding all outputs
		sol(out, map, 0, list, 0);
		System.out.println(out);
	}

	private static void sol(List<String> out, Map<String, List<Character>> map, int ind, List<List<String>> list,
			int i) {
		if (i < list.size()) {
			innerSol(list.get(i), 0, map, list.get(i).size(), out, "");
			sol(out, map, ind, list, i + 1);
		}
	}

	private static void innerSol(List<String> combinations, int c, Map<String, List<Character>> map, int size,
			List<String> out, String str) {
		if (c == size) {
			// collect
			out.add(str);
		} else {
			String match = combinations.get(c);
			List<Character> givenChars = map.get(match);
			for (int k = 0; k < givenChars.size(); k++) {
				String nStr = str + givenChars.get(k);
				innerSol(combinations, c + 1, map, size, out, nStr);
			}
		}
	}

	private static void rec(String s, List<String> l, Set<List<String>> combinations) {
		// check for corresponding words with this list

		// variants
		for (int i = 0; i < l.size(); i++) {
			if (i < l.size() - 1) {
				String a = l.get(i);
				String b = l.get(i + 1);
				List<String> nl = new ArrayList<>(l);
				nl.remove(i);
				nl.set(i, a + b);
				combinations.add(nl);
				rec(s, nl, combinations);
			}
		}
	}
}

- Nalin Sharma August 02, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package poc;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * 
 * @author Nalin
 *
 */
public class PatternAgain {
	/*
	 * output [adp, adq, aep, aeq, bdp, bdq, bep, beq, cdp, cdq, cep, ceq, xp, xq]
	 */
	public static void main(String[] args) {
		Map<String, List<Character>> map = new HashMap<>();
		map.put("1", Arrays.asList('a', 'b', 'c'));
		map.put("2", Arrays.asList('d', 'e'));
		map.put("12", Arrays.asList('x'));
		map.put("3", Arrays.asList('p', 'q'));

		String s = "123";
		List<String> l = new ArrayList<>();
		char[] arr = s.toCharArray();
		for (char a : arr) {
			l.add(String.valueOf(a));
		}
		Set<List<String>> combinations = new HashSet<>();
		combinations.add(l);
		rec(s, l, combinations);
		
		// all the combinations generated
		List<List<String>> list = new ArrayList<>(combinations);
		List<String> out = new ArrayList<>();
		//combinations.forEach(System.out::println);

		// please bear learning java 8, but it's not very java 8ish, filtering
		// combinations
		list = list.stream().filter((List<String> innerList) -> {
			boolean[] toConsider = { true };
			innerList.stream().forEach(item -> {
				if (!map.containsKey(item)) {
					toConsider[0] = false;
				}
			});
			return toConsider[0];
		}).collect(Collectors.toList());

		// finding all outputs
		sol(out, map, 0, list, 0);
		System.out.println(out);
	}

	private static void sol(List<String> out, Map<String, List<Character>> map, int ind, List<List<String>> list,
			int i) {
		if (i < list.size()) {
			innerSol(list.get(i), 0, map, list.get(i).size(), out, "");
			sol(out, map, ind, list, i + 1);
		}
	}

	private static void innerSol(List<String> combinations, int c, Map<String, List<Character>> map, int size,
			List<String> out, String str) {
		if (c == size) {
			// collect
			out.add(str);
		} else {
			String match = combinations.get(c);
			List<Character> givenChars = map.get(match);
			for (int k = 0; k < givenChars.size(); k++) {
				String nStr = str + givenChars.get(k);
				innerSol(combinations, c + 1, map, size, out, nStr);
			}
		}
	}

	private static void rec(String s, List<String> l, Set<List<String>> combinations) {
		// check for corresponding words with this list

		// variants
		for (int i = 0; i < l.size(); i++) {
			if (i < l.size() - 1) {
				String a = l.get(i);
				String b = l.get(i + 1);
				List<String> nl = new ArrayList<>(l);
				nl.remove(i);
				nl.set(i, a + b);
				combinations.add(nl);
				rec(s, nl, combinations);
			}
		}
	}
}

- Nalin Sharma August 02, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package poc;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * 
 * @author Nalin
 *
 */
public class PatternAgain {
	/*
	 * output [adp, adq, aep, aeq, bdp, bdq, bep, beq, cdp, cdq, cep, ceq, xp, xq]
	 */
	public static void main(String[] args) {
		Map<String, List<Character>> map = new HashMap<>();
		map.put("1", Arrays.asList('a', 'b', 'c'));
		map.put("2", Arrays.asList('d', 'e'));
		map.put("12", Arrays.asList('x'));
		map.put("3", Arrays.asList('p', 'q'));

		String s = "123";
		List<String> l = new ArrayList<>();
		char[] arr = s.toCharArray();
		for (char a : arr) {
			l.add(String.valueOf(a));
		}
		Set<List<String>> combinations = new HashSet<>();
		combinations.add(l);
		rec(s, l, combinations);
		
		// all the combinations generated
		List<List<String>> list = new ArrayList<>(combinations);
		List<String> out = new ArrayList<>();
		//combinations.forEach(System.out::println);

		// please bear learning java 8, but it's not very java 8ish, filtering
		// combinations
		list = list.stream().filter((List<String> innerList) -> {
			boolean[] toConsider = { true };
			innerList.stream().forEach(item -> {
				if (!map.containsKey(item)) {
					toConsider[0] = false;
				}
			});
			return toConsider[0];
		}).collect(Collectors.toList());

		// finding all outputs
		sol(out, map, 0, list, 0);
		System.out.println(out);
	}

	private static void sol(List<String> out, Map<String, List<Character>> map, int ind, List<List<String>> list,
			int i) {
		if (i < list.size()) {
			innerSol(list.get(i), 0, map, list.get(i).size(), out, "");
			sol(out, map, ind, list, i + 1);
		}
	}

	private static void innerSol(List<String> combinations, int c, Map<String, List<Character>> map, int size,
			List<String> out, String str) {
		if (c == size) {
			// collect
			out.add(str);
		} else {
			String match = combinations.get(c);
			List<Character> givenChars = map.get(match);
			for (int k = 0; k < givenChars.size(); k++) {
				String nStr = str + givenChars.get(k);
				innerSol(combinations, c + 1, map, size, out, nStr);
			}
		}
	}

	private static void rec(String s, List<String> l, Set<List<String>> combinations) {
		// check for corresponding words with this list

		// variants
		for (int i = 0; i < l.size(); i++) {
			if (i < l.size() - 1) {
				String a = l.get(i);
				String b = l.get(i + 1);
				List<String> nl = new ArrayList<>(l);
				nl.remove(i);
				nl.set(i, a + b);
				combinations.add(nl);
				rec(s, nl, combinations);
			}
		}
	}
}

- sharmanalin59 August 02, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple Solution by recursion.
Go character by character on the input number (eg. 123)
In first run we will have current=1, and the mapping for it is ['A', 'B', 'C']
Now, for each of the element in the array we want to get the suffix which if found by doing recursion on the remainder of the input number (substring(i + 1))

Pretty straightforward.

public class GenerateString {
    private static Map<String, char[]> map = new HashMap<>();
    static {
        map.put("1", new char[]{'A', 'B', 'C'});
        map.put("2", new char[]{'D', 'E'});
        map.put("3", new char[]{'P', 'Q'});
        map.put("12", new char[]{'X'});
    }
    public static void main(String[] args) {
        System.out.println(convertToString("123"));
    }

    public static List<String> convertToString(String numStr) {
        List<String> result = new ArrayList<>();
        if(numStr == null || numStr.length() == 0 ) { result.add("");}
        for(int i = 0; i < numStr.length(); i++) {
            String current = numStr.substring(0, i+1);
            if(map.containsKey(current)) {
                char[] chars = map.get(current);
                for(char ch : chars) {
                    for(String t : convertToString(numStr.substring(i + 1))) {
                        result.add(ch + t);
                    }
                }
            }
        }
        return result;
    }
}

- Rishabh Mehan August 24, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple Solution by recursion.
Go character by character on the input number (eg. 123)
In first run we will have current=1, and the mapping for it is ['A', 'B', 'C']
Now, for each of the element in the array we want to get the suffix which if found by doing recursion on the remainder of the input number (substring(i + 1))

Pretty straightforward.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class GenerateString {
    private static Map<String, char[]> map = new HashMap<>();
    static {
        map.put("1", new char[]{'A', 'B', 'C'});
        map.put("2", new char[]{'D', 'E'});
        map.put("3", new char[]{'P', 'Q'});
        map.put("12", new char[]{'X'});
    }
    public static void main(String[] args) {
        System.out.println(convertToString("123"));
    }

    public static List<String> convertToString(String numStr) {
        List<String> result = new ArrayList<>();
        if(numStr == null || numStr.length() == 0 ) { result.add("");}
        for(int i = 0; i < numStr.length(); i++) {
            String current = numStr.substring(0, i+1);
            if(map.containsKey(current)) {
                char[] chars = map.get(current);
                for(char ch : chars) {
                    for(String t : convertToString(numStr.substring(i + 1))) {
                        result.add(ch + t);
                    }
                }
            }
        }
        return result;
    }
}

- rmehan August 24, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashMap;
import java.util.Map;
	
public class EnumeratePatterns {
	public static void main(String[] args){
		// testcase
		Map<String, char[]> dict = new HashMap<String, char[]>();
		dict.put("1", new char[] {'A', 'B', 'C'});
		dict.put("2", new char[] {'D', 'E'});
		dict.put("12", new char[] {'X'});
		dict.put("3", new char[] {'P', 'Q'});
		
		enumerate("123", dict);
   }
   
   public static void enumerate(String inp, Map<String,char[]> dict) {
	  enumerate(inp.toCharArray(), "", 0, inp.length(), dict);
   }
   
   public static void enumerate(char[] inp, String prefix, int begin, int n, Map<String,char[]> dict) {
	   // base case
	   if (begin == n){
		   System.out.println(prefix);
	   }
	   // extend prefix
	   String key = "";
	   for (int i = begin; i < n; i++){
		   if(dict.containsKey(key + inp[i])){
			   key = key + inp[i];
			   char[] values = dict.get(key);
			   for (char c : values){
				   String extendedPrefix = prefix + c;
				   enumerate(inp, extendedPrefix, i+1, n, dict);
			   }
		   }
	   }
   }
}

- just_do_it November 11, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package main

import (
"fmt"
)

var arr = map[string][]string {
"1" : {"A", "B", "C"},
"2" : {"D", "E"},
"12" : {"X"},
"3" : {"P", "Q"},
}

func gen(p string, cur string) {
if p == "" {
fmt.Println(cur)
} else {
for i := 1; i <= len(p); i++ {
for _, n := range arr[p[:i]] {
gen(p[i:], cur + n)
}
}
}
}

func main() {
gen("123", "")
}

- Anonymous April 15, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package main

import (
	"fmt"	
)

var arr = map[string][]string {
	"1" : {"A", "B", "C"}, 
	"2" : {"D", "E"},
	"12" : {"X"},
	"3" : {"P", "Q"},
}

func gen(p string, cur string) {
	if p == "" {
		fmt.Println(cur)
	} else {
		for i := 1; i <= len(p); i++ {
			for _, n := range arr[p[:i]] {
				gen(p[i:], cur + n)
			}
		}	
	}
}

func main() {
	gen("123", "")
}

- xmentex April 15, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package main

import (
	"fmt"	
)

var arr = map[string][]string {
	"1" : {"A", "B", "C"}, 
	"2" : {"D", "E"},
	"12" : {"X"},
	"3" : {"P", "Q"},
}

func gen(p string, cur string) {
	if p == "" {
		fmt.Println(cur)
	} else {
		for i := 1; i <= len(p); i++ {
			for _, n := range arr[p[:i]] {
				gen(p[i:], cur + n)
			}
		}	
	}
}

func main() {
	gen("123", "")
}

- xmentex April 15, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

func getValue(_ input: String) -> [String] {
var nodeList = [Node<Dictionary<String, [[String]]>>]()
var tempArray = [[String]]()
let dictionary = ["1": ["A", "B", "C"], "2": ["D", "E"], "12": ["X"], "3": ["P", "Q"]]

for character in input {
if let values = dictionary[String(character)] {
tempArray.append(values)
}
}
let node = Node(list: [input: tempArray])
nodeList.append(node)

tempArray = [[String]]()
var j = 0
for i in stride(from: 2, to: input.count, by: 2) {
j = i
if let values = dictionary[String(input[input.startIndex ..< input.index(input.startIndex, offsetBy: i)])] {
tempArray.append(values)
}
}
while j < input.count {
j += 1
if let values = dictionary[String(j)] {
tempArray.append(values)
}
}
nodeList.append(Node(list: [input: tempArray]))
var finalArray = [String]()
var resultArray = [String]()
for node in nodeList {
resultArray = [String]()
for values in node.list[input]! {
if resultArray.isEmpty {
resultArray = values
} else {
var temp = [String]()
for value in values {
for result in resultArray {
temp.append("\(result)\(value)")
}
}
resultArray = temp
}
}
finalArray += resultArray
}
return finalArray
}
class Node<T> {
let list: T
init(list: T) {
self.list = list
}
}

- Hussain Shabbir May 28, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my solution, works in all corner cases... well tested

public class ListCombination {

    public static void main(String args[]) {


        Map<String, char[]> input = new HashMap<>();

        input.put("1", new char[]{'A', 'B', 'C'});
        input.put("2", new char[]{'D', 'E'});
        input.put("3", new char[]{'P', 'Q'});
        input.put("12", new char[]{'X'});
        input.put("4", new char[]{'T', 'S'});
        input.put("23", new char[]{'Z', 'N'});
        input.put("34", new char[]{'O', 'M'});
        input.put("234", new char[]{'W', 'Y'});
        input.put("1234", new char[]{'@', '#'});

        String test = "1234";
        try {
            List<String> output = generateCombination(input, test);
            System.out.println(output);



        } catch (InvalidArgument invalidArgument) {
            invalidArgument.printStackTrace();
        }


    }

    private static List<String> generateCombination(Map<String, char[]> input, String test) throws InvalidArgument {

        if (null == input || input.isEmpty() || null == test || test.isEmpty())
            return Collections.EMPTY_LIST;

        //Build list of string that need to traverse recursively
        List<List<String>> considerList = buildConsiderList(input, test);

        return considerList.stream().map(list -> generateCombination(list)).flatMap(Collection::stream).collect(Collectors.toList());

    }

    private static List<List<String>> buildConsiderList(Map<String, char[]> input, String pattern) throws InvalidArgument {

        List<List<String>> toConsider = new LinkedList<>();

        /**
         * Consider of key;
         * Here we use key a loop runner because we could have case where from pattern multiple (off different size) string present in input map,
         * then if we traverse over pattern then we need to generate n^2 sub string and check all of them in map, that corresponding list present or not
         */
        for (String key : input.keySet()) {

            List<String> subListsToConsider = new ArrayList<>();

            //If this key does not include in the first place of the pattern list, then don't consider all list by it
            //Example: Key = 2, pattern=123 -> since 123 does not start with 2, which means all the list by 2 we can't consider since it has to be like 123
            if (!pattern.startsWith(key))
                continue;

            //process for current key array
            char[] current = input.get(key);
            subListsToConsider.add(new String(current));

            //Take the remaining length to consider
            //example key = 1, pattern=123, then remaining is = 23 which we'll consider one by one
            String remainingPattern = pattern.substring(key.length());


            //Case 1: character by character
            //process remaining
            for (int i = 0; i < remainingPattern.length(); i++) {

                //if this does not present in input; input is corrupt
                if (!input.containsKey(String.valueOf(remainingPattern.charAt(i))))
                    throw new InvalidArgument("Input " + pattern + "is invalid");

                char[] temp = input.get(String.valueOf(remainingPattern.charAt(i)));
                subListsToConsider.add(new String(temp));


            }


            //case 2: whole remaining list
            if (remainingPattern.length() > 1 && input.containsKey(remainingPattern)) {
                List<List<String>> withRemaining = new ArrayList<>();
                List<String> rem = new ArrayList<>();
                rem.add(new String(input.get(key)));
                rem.add(new String(input.get(remainingPattern)));

                withRemaining.add(rem);
                toConsider.addAll(withRemaining);
            }

            toConsider.add(subListsToConsider);


        }

        return toConsider;
    }


    private static List<String> generateCombination(List<String> input) {
        List<String> output = new LinkedList<>();

        generateCombination(input, 0, output, "");
        return output;
    }

    private static void generateCombination(List<String> input, int index, List<String> output, String temp) {

        if (temp.length() == input.size()) {
            output.add(temp);
            return;
        }

        String current = input.get(index);

        for (int i = 0; i < current.length(); i++) {
            temp = temp + current.charAt(i);
            generateCombination(input, index + 1, output, temp);
            temp = temp.substring(0, temp.length() - 1);
        }
    }



}

- nitinguptaiit July 11, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

def main():

  X = {'1': ['A', 'B', 'C'], '2': ['D', 'E'], '12' : ['X'], '3' : ['P', 'Q'], '4': ['E', 'F', 'G']}

  num = 1234

  l = [x for x in str(num)]

  li = [X[i] for i in l]

  combiA = []

  for i in range (len(li)):
    for j in range(len(li[i])):
      recCombi(li[i][j],li, combiA, len(li), i+1)
      combiA.clear()

def recCombi(x, l2, combiA, finalLen, index):

    combiA.append(x)

    if (len(combiA) == finalLen):
      print(combiA)
      return

    if(index >= finalLen):
      return    

    i = 0
    j = 1 + index

    for i in range (len(l2[index])):
      recCombi(l2[index][i],l2, combiA, finalLen, j)
      combiA.pop()
    return


    


main()

- Kriti September 27, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

def main():

  X = {'1': ['A', 'B', 'C'], '2': ['D', 'E'], '12' : ['X'], '3' : ['P', 'Q'], '4': ['E', 'F', 'G']}

  num = 1234

  l = [x for x in str(num)]

  li = [X[i] for i in l]

  combiA = []

  for i in range (len(li)):
    for j in range(len(li[i])):
      recCombi(li[i][j],li, combiA, len(li), i+1)
      combiA.clear()

def recCombi(x, l2, combiA, finalLen, index):

    combiA.append(x)

    if (len(combiA) == finalLen):
      print(combiA)
      return

    if(index >= finalLen):
      return    

    i = 0
    j = 1 + index

    for i in range (len(l2[index])):
      recCombi(l2[index][i],l2, combiA, finalLen, j)
      combiA.pop()
    return


    


main()

- Kriti September 27, 2019 | 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