FAANG Interview Recap: Trie Hard Problem

Conquer Trie's hard interview questions asked by FAANG (or MAMAA)

Photo by Jeremy Bishop on Unsplash

Trie is a type of k-ary search tree, a tree data structure for locating specific keys from within a set. It is an important data structure for suggestive search and recommendation.

It is a common but hard FAANG interview question. These questions are often related to char or substring match or search in different non-tree data structures, such as matrix and array. For optimized solutions (that is, able to be accepted by the interviewers), we need to restructure the original data structures into a trie, and then we can solve the problem quickly.

Here let’s use three real examples (interview questions) to see how to employ a trie data structure effectively.

Real Examples

Problem 0: HackerRank No Prefix Set is a typical Trie interview question. Please find the question and optimized solution below:

HackerRank No Prefix Set Solution

Problem 1: HackerRank Contacts problem depends on a Trie implementation, or it is hard to optimize. A Trie DS should be used in its search part (find partial). Please see the problem below.

Contacts | HackerRank

Please find the optimized Java implementation below:

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'contacts' function below.
     *
     * The function is expected to return an INTEGER_ARRAY.
     * The function accepts 2D_STRING_ARRAY queries as parameter.
     */

    public static List<Integer> contacts(List<List<String>> queries) {
    // Write your code here
        List<Integer> res = new ArrayList<>();
        
        // List<String> names = new ArrayList<>();
        Trie trie = new Trie('*');
        trie.cnt = 0;
        for (List<String> query : queries) {
            if (query.get(0).equals("add")) {
                // names.add(query.get(1));
                trie.add(query.get(1));           
            }   
            else if (query.get(0).equals("find")) {
                String q = query.get(1);  
                // int cnt = 0;
                // for (String name : names) {
                //     if (name.startsWith(q)) cnt++;
                // }
                
                res.add(trie.find(q));
            }
        }
        
        return res;    
    }

}

class Trie {
    char c;
    int cnt;
    Trie [] children;
    Trie(char a) {
        c = a;
        cnt = 1;
        children = new Trie[26];
    }
    
    Trie add(char a) {
        if (children[a - 'a'] == null) {
            children[a - 'a'] = new Trie(a);    
        }
        else {
            children[a - 'a'].cnt++;        
        }
            
        return children[a - 'a'];
    }
    
    void add(String s) {
        Trie node = this;
        for (int i = 0; i < s.length(); i++) {
            node = node.add(s.charAt(i));
        }
    }
    
    int find(String s) {
        Trie node = this;
        for (int i = 0; i < s.length(); i++) {
            node = node.children[s.charAt(i) - 'a'];
            if (node != null) {
                if (i == s.length() - 1) {
                    return node.cnt;
                }     
            }
            else 
                break;
        }
        return 0;   
    }
}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int queriesRows = Integer.parseInt(bufferedReader.readLine().trim());

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

        IntStream.range(0, queriesRows).forEach(i -> {
            try {
                queries.add(
                    Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
                        .collect(toList())
                );
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });

        List<Integer> result = Result.contacts(queries);

        bufferedWriter.write(
            result.stream()
                .map(Object::toString)
                .collect(joining("\n"))
            + "\n"
        );

        bufferedReader.close();
        bufferedWriter.close();
    }
}

The core is to search in a Trie DS instead of an array. In the above, you can see the change from array DS (commented out) to Trie DS. The Trie time complexity is O(nlogn). So you can use other DS like a sorted array and then use binary search.

Problem 2: Here will add more in the future, or please leave responses on problems you have.

TL;DR;

So we can see the key to these hard interview questions is how to construct a Trie data structure. And then, we can reduce the complexity from O(n²) to O(nlogn). For these problems, we usually use recursive methods to decrease the code complexity and make it easy to understand. But please do not forget to cache the calculated results if possible, which is called DP (dynamic programming) in algorithms.

This post will be one stop to continue adding more Trie-related questions. So follow me to stay tuned or check back for updates.

Happy coding and inductive solving!

Questions, ideas? Leave comments here. Follow me to be part of the fun problem-solving journey.