Facebook Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




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

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


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