LinkedIn | Phone Interview | Senior Software Engineer Application

I was asked this question in the interview: Given the standard mapping from English letters to digits on a phone keypad (1 → "" 2 -> a,b,c 3 -> d,e,f 4 -> g,h,i 5 -> j,k,l 6 -> m,n,o 7 -> p,q,r,s 8 -> t,u,v 9 -> w,x,y,z),

write a program that outputs all words that can be formed from any n-digit phone number from the list of given KNOWN_WORDS considering the mapping mentioned above.

KNOWN_WORDS= ['careers', 'linkedin', 'hiring', 'interview', 'linkedgo']

phoneNumber: 2273377 Output: ['careers']

phenoNumber: 54653346 Output: ['linkedin', 'linkedgo']

Solution:

public class WordFinderFromPhoneNumber {

    private static final String[] KEYBOARD = {
        "",     // 0
        "",     // 1
        "abc",  // 2
        "def",  // 3
        "ghi",  // 4
        "jkl",  // 5
        "mno",  // 6
        "pqrs", // 7
        "tuv",  // 8
        "wxyz"  // 9
    }; // Already Given

    private static final List<String> KNOWN_WORDS = Arrays.asList(
        "careers", "linkedin", "hiring", "interview", "linkedgo"
    ); // Already Given

    private TrieNode root;

    public WordFinderFromPhoneNumber() {
        root = new TrieNode();
        buildTrieNode(KNOWN_WORDS);
    }

    public List<String> wordsFromPhoneNumbers(String phoneNumber) {
        List<String> result = new ArrayList<>();
        Map<Character, Set<Character>> digitToCharMap = new HashMap<>();

        for (int i = 2; i <= 9; i++) {
            char digitChar = (char) (i + '0');
            for (char ch : KEYBOARD[i].toCharArray()) {
                digitToCharMap.computeIfAbsent(digitChar, x -> new HashSet<>()).add(ch);
            }
        }

        backtracking(phoneNumber, 0, digitToCharMap, result, root);
        return result;
    }

    private void buildTrieNode(List<String> words) {
        for (String word : words) {
            TrieNode curr = root;
            for (char c : word.toCharArray()) {
                curr.childrens.putIfAbsent(c, new TrieNode());
                curr = curr.childrens.get(c);
            }
            curr.word = word;
        }
    }

    private void backtracking(String digits, int index, Map<Character, Set<Character>> map,
                              List<String> result, TrieNode curr) {
        if (index == digits.length()) {
            if (!curr.word.isEmpty()) {
                result.add(curr.word);
            }
            return;
        }

        char digit = digits.charAt(index);
        if (!map.containsKey(digit)) return;

        for (char letter : map.get(digit)) {
            if (curr.childrens.containsKey(letter)) {
                backtracking(digits, index + 1, map, result, curr.childrens.get(letter));
            }
        }
    }

    private static class TrieNode {
        Map<Character, TrieNode> childrens = new HashMap<>();
        String word = "";
    }
}

Even after giving this solution, got the rejection email.