Coding Interview QuestionsInterview Questions and Answers

New 20 Trie Interview Questions

Table of Contents

Introduction

Trie interview questions often test your understanding of a data structure called a trie, which stands for “reTRIEval.” A trie is a tree-like structure used to efficiently store and retrieve strings. It’s particularly useful for tasks like auto-completion and spell-checking. In these questions, you might be asked to implement a trie, perform operations on it, or solve problems using trie-based approaches. Familiarizing yourself with trie operations, such as inserting, searching, and deleting nodes, will help you tackle these interview questions effectively. Remember, the key is to break down the problem into smaller steps and leverage the trie’s unique properties to optimize your solution.

Questions

1. What is a Trie data structure? How does it work?

A Trie (pronounced as “try”) data structure, also known as a prefix tree or digital tree, is a tree-like data structure used to efficiently store a dynamic set of strings or keys. It is particularly useful for applications that involve searching for words or strings with common prefixes, such as in dictionary implementations or autocomplete systems.

Structure and Working of a Trie:

  1. Node Structure: Each node in the trie represents a single character of a string. Nodes are connected to form a tree, where the root node represents an empty string, and each path from the root to a node represents a string.
  2. Children and Links: Each node may have multiple child nodes, one for each possible character in the alphabet or set of characters. Each node contains links to its children, and these links represent the characters needed to traverse the trie from the root to a particular node.
  3. Word Completion: A node in the trie is marked as a word-completion node when it represents the end of a valid word. This helps distinguish complete words from prefixes.
  4. Searching: Searching for a specific word in the trie involves traversing the tree from the root, following the links corresponding to each character of the word. If the complete word exists in the trie, we will reach a word-completion node.
  5. Insertion: Inserting a new word into the trie involves starting from the root and traversing the tree based on the characters of the word. If a character does not have a corresponding child node, a new node is created and linked to its parent node.
  6. Deletion: Deleting a word from the trie involves finding the word in the trie and removing the word-completion marker. If the word is a prefix for other words, the relevant nodes are not deleted but remain in the trie.

Example:

Suppose we have the following set of words: “apple,” “app,” “banana,” and “bat.” A simplified illustration of a trie for these words would look like this:

       (root)
         /
        a
      /   \
     p     b
    /       \
   p         a
  /           \
 l             t
/ \            \
e   p            a
                  \
                   n
                    \
                     a

In this example, the trie efficiently stores the words “apple,” “app,” “banana,” and “bat,” with common prefixes like “app” and “ba.”

2. What are the primary uses of a Trie? Can you provide some real-world examples where Tries are used?

The primary uses of a Trie include:

  • Autocomplete and word suggestion systems
  • Spell checkers and dictionaries
  • IP routing and network routing tables
  • Searching for strings with common prefixes efficiently
  • Storing and retrieving contact information in phonebooks

Real-world examples where Tries are used include:

  • Search engines like Google, where autocomplete suggestions are provided as you type
  • Word processing software for spell checking
  • Network routers for IP address lookup and routing
  • Contact lists in mobile phones for efficient search and retrieval

3. Can you describe the insertion process in a Trie? What is its time complexity?

The insertion process in a Trie involves adding a new word into the data structure. Each character of the word is sequentially inserted, creating a path from the root to the corresponding leaf node. If a node for a character doesn’t exist, it is created during the insertion process. The last node of the word is marked as a terminal node to indicate the completion of the word.

Example of inserting the word “apple” into an empty Trie:

  Root
   |
   a
   |
   p
   |
   p
   |
   l
   |
   e (terminal node)

Time Complexity: The time complexity for inserting a word into a Trie is O(L), where L is the length of the word. This is because the insertion process involves traversing through each character of the word and adding it to the Trie, which takes constant time for each character.

4. Can you describe the search process in a Trie? What is its time complexity?

The search process in a Trie involves finding a specific word or checking if a given prefix exists in the Trie. Starting from the root, each character of the target word (or prefix) is sequentially searched by following the corresponding edges. If, at any point, a character is not found or the search reaches a null node, the word (or prefix) is not present in the Trie.

Example of searching for the word “apple” in a Trie:

  Root
   |
   a
   |
   p
   |
   p
   |
   l
   |
   e (terminal node)

Searching for “apple” will return true, while searching for “app” (a valid prefix) will also return true.

Time Complexity: The time complexity for searching in a Trie is O(L), where L is the length of the target word or prefix. This is because the search process involves traversing through each character of the word or prefix, which takes constant time for each character.

5. What are the advantages and disadvantages of using a Trie compared to other data structures like hash tables, trees, etc?

Advantages of using a Trie:

  • Efficient search and retrieval of strings with common prefixes
  • Provides autocomplete functionality and efficient word suggestions
  • Supports alphabetical ordering and range queries
  • Can handle large datasets efficiently
  • Well-suited for tasks like spell checking and word processing applications

Disadvantages of using a Trie:

  • Higher memory consumption compared to other data structures
  • Slower for searching exact matches compared to hash tables
  • Limited to storing strings and does not support general-purpose data storage
  • Can be more complex to implement and maintain compared to simpler data structures

6. What is a prefix in a Trie? How would you find all words in a Trie that have a common prefix?

A prefix in a Trie is a sequence of characters that appears at the beginning of one or more words stored in the Trie. For example, in the Trie below, “app” is a common prefix for both “apple” and “appetite”:

  Root
   |
   a
   |
   p
   |
   p
  / \
 l   e (terminal node)
 |   |
 e   t
     |
     i
     |
     t
     |
     e (terminal node)

To find all words in a Trie that have a common prefix, you can perform a traversal of the Trie starting from the node corresponding to the last character of the prefix. During this traversal, you can use Depth-First Search (DFS) to explore all paths from the prefix node and collect the words encountered in the process.

Example code in C++ to find all words with a given prefix:

C++
#include <iostream>
#include <vector>
using namespace std;

struct TrieNode {
    bool isTerminal;
    vector<TrieNode*> children;
    TrieNode() : isTerminal(false), children(26, nullptr) {}
};

class Trie {
public:
    Trie() {
        root = new TrieNode();
    }

    void insert(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            int idx = ch - 'a';
            if (!node->children[idx])
                node->children[idx] = new TrieNode();
            node = node->children[idx];
        }
        node->isTerminal = true;
    }

    vector<string> findAllWithPrefix(string prefix) {
        vector<string> result;
        TrieNode* node = findPrefixNode(prefix);
        if (node)
            findAllWords(node, prefix, result);
        return result;
    }

private:
    TrieNode* root;

    TrieNode* findPrefixNode(string prefix) {
        TrieNode* node = root;
        for (char ch : prefix) {
            int idx = ch - 'a';
            if (!node->children[idx])
                return nullptr;
            node = node->children[idx];
        }
        return node;
    }

    void findAllWords(TrieNode* node, string currentWord, vector<string>& result) {
        if (node->isTerminal)
            result.push_back(currentWord);

        for (int i = 0; i < 26; i++) {
            if (node->children[i]) {
                char ch = 'a' + i;
                findAllWords(node->children[i], currentWord + ch, result);
            }
        }
    }
};

int main() {
    Trie trie;
    trie.insert("apple");
    trie.insert("appetite");
    trie.insert("bat");
    trie.insert("ball");
    
    string prefix = "app";
    vector<string> wordsWithPrefix = trie.findAllWithPrefix(prefix);
    cout << "Words with prefix '" << prefix << "': ";
    for (const string& word : wordsWithPrefix)
        cout << word << " ";
    
    return 0;
}

Output for the given example Trie and prefix “app”:

C++
Words with prefix 'app': apple appetite

7. What is Trie’s space complexity? How can we optimize it?

The space complexity of a Trie depends on the number of unique strings stored in it. In the worst-case scenario, where there are no common prefixes among the strings, the space complexity can be high. It is typically O(n * m), where n is the number of strings and m is the average length of the strings.

To optimize the space complexity of a Trie, some techniques can be employed:

  • Implementing compressed tries, such as Patricia Tries or Ternary Search Tries, which reduce memory usage by storing common prefixes only once
  • Using techniques like path compression or bitwise tries to further reduce memory usage
  • Implementing adaptive or hybrid data structures that dynamically switch between different representations based on the data characteristics

8. Can you explain the delete operation in a Trie?

The delete operation in a Trie involves removing a word from the data structure. Deleting a word requires traversing the Trie to find the word and then marking the terminal node of the word as non-terminal (if it’s the only occurrence) or completely removing the nodes that are not shared with other words.

The deletion process depends on the following cases:

  1. The word to be deleted is not in the Trie: In this case, no changes are needed as the word is not present.
  2. The word to be deleted is a prefix of another word: Only mark the terminal node as non-terminal. The word is no longer accessible, but its prefix still exists in the Trie.
  3. The word to be deleted shares a prefix with another word: Traverse the Trie and remove nodes from the end of the word until encountering a shared node with another word.
  4. The word to be deleted is the only word sharing a prefix: Remove nodes starting from the root until the last node of the word.

Example of deleting the word “apple” from a Trie:

  Root
   |
   a
   |
   p
   |
   p
  / \
 l   e (terminal node)
 |   |
 e   t
     |
     i
     |
     t
     |
     e (terminal node)

After deleting “apple”:

  Root
   |
   a
   |
   p
  / \
 l   e
 |   
 e   t
     |
     i
     |
     t
     |
     e (terminal node)

In the example above, “appetite” still exists in the Trie, and “app” is still a valid prefix.

9. What is a Suffix Trie? How is it different from a standard Trie and what are its uses?

A Suffix Trie, also known as a Suffix Tree, is a specialized type of Trie that is used to store all the suffixes of a given string. In a Suffix Trie, every path from the root to a leaf node represents a suffix of the original string. It allows for efficient pattern matching and substring searches in linear time.

The main difference between a Suffix Trie and a standard Trie is that a Suffix Trie is built specifically for storing and searching suffixes, while a standard Trie is a more general-purpose data structure for storing and searching strings.

Some common uses of Suffix Tries include:

  • Pattern matching and substring searches in DNA sequencing, text indexing, and search engines
  • Longest common substring and longest repeated substring problems
  • Construction of Burrows-Wheeler Transform for data compression algorithms like bzip2

10. What modifications can be done on a Trie to make it support advanced operations like sorting, priority queue, etc?

To support advanced operations like sorting or priority queue, additional modifications can be made to a Trie, such as:

  • Associating values or metadata with each node to store additional information like frequency, priority, or sorting keys
  • Augmenting the Trie with additional data structures like heap or balanced trees to maintain the desired order or priority
  • Implementing traversal algorithms that utilize the Trie structure to perform sorting or priority-based operations efficiently
  • Building specialized data structures like Trie-based heaps or priority queues that leverage the Trie’s structure to achieve efficient operations

Coding Questions

1. Implement a Trie data structure in your preferred programming language. Include methods for insert, search, and startsWith.

C++
public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (!node.containsKey(c)) {
                node.put(c, new TrieNode());
            }
            node = node.get(c);
        }
        node.setEnd();
    }

    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isEnd();
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private TrieNode searchPrefix(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            if (node.containsKey(c)) {
                node = node.get(c);
            } else {
                return null;
            }
        }
        return node;
    }

    private static class TrieNode {
        private TrieNode[] links;
        private boolean isEnd;

        public TrieNode() {
            links = new TrieNode[26];
        }

        public boolean containsKey(char c) {
            return links[c - 'a'] != null;
        }

        public TrieNode get(char c) {
            return links[c - 'a'];
        }

        public void put(char c, TrieNode node) {
            links[c - 'a'] = node;
        }

        public boolean isEnd() {
            return isEnd;
        }

        public void setEnd() {
            isEnd = true;
        }
    }
}

2. Given a list of strings, write a function that returns all strings with a given prefix using a Trie.

C++
public List<String> searchByPrefix(String prefix, Trie trie) {
    List<String> result = new ArrayList<>();
    Trie.TrieNode node = trie.searchPrefix(prefix);
    if (node != null) {
        dfs(node, prefix, result);
    }
    return result;
}

private void dfs(Trie.TrieNode node, String prefix, List<String> result) {
    if (node.isEnd()) {
        result.add(prefix);
    }
    for (char c = 'a'; c <= 'z'; c++) {
        if (node.containsKey(c)) {
            dfs(node.get(c), prefix + c, result);
        }
    }
}

3. Given a 2D board and a list of words from the dictionary, find all words in the board. Each word must be constructed from letters of sequentially adjacent cells, where “adjacent” cells are horizontally or vertically neighboring.

C++
public List<String> findWords(char[][] board, String[] words) {
    List<String> result = new ArrayList<>();
    Trie trie = new Trie();
    for (String word : words) {
        trie.insert(word);
    }
    int m = board.length;
    int n = board[0].length;
    boolean[][] visited = new boolean[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            dfs(board, i, j, "", trie, visited, result);
        }
    }
    return result;
}

private void dfs(char[][] board, int i, int j, String currentWord, Trie trie, boolean[][] visited, List<String> result) {
    if (i < 0 || i >= board.length

 || j < 0 || j >= board[0].length || visited[i][j]) {
        return;
    }
    currentWord += board[i][j];
    if (!trie.startsWith(currentWord)) {
        return;
    }
    if (trie.search(currentWord)) {
        result.add(currentWord);
    }
    visited[i][j] = true;
    dfs(board, i - 1, j, currentWord, trie, visited, result);
    dfs(board, i + 1, j, currentWord, trie, visited, result);
    dfs(board, i, j - 1, currentWord, trie, visited, result);
    dfs(board, i, j + 1, currentWord, trie, visited, result);
    visited[i][j] = false;
}

4. Write a function to implement an autocomplete feature using Trie. The function should return all dictionary words that start with the provided input prefix.

C++
public List<String> autocomplete(String prefix, Trie trie) {
    List<String> result = new ArrayList<>();
    Trie.TrieNode node = trie.searchPrefix(prefix);
    if (node != null) {
        dfs(node, prefix, result);
    }
    return result;
}

private void dfs(Trie.TrieNode node, String prefix, List<String> result) {
    if (node.isEnd()) {
        result.add(prefix);
    }
    for (char c = 'a'; c <= 'z'; c++) {
        if (node.containsKey(c)) {
            dfs(node.get(c), prefix + c, result);
        }
    }
}

5. Implement a Trie data structure that supports insertion, deletion, and search operations.

C++
class Trie {
    TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (node.children[c - 'a'] == null) {
                node.children[c - 'a'] = new TrieNode();
            }
            node = node.children[c - 'a'];
        }
        node.isEndOfWord = true;
    }

    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isEndOfWord;
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private TrieNode searchPrefix(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            if (node.children[c - 'a'] == null) {
                return null;
            }
            node = node.children[c - 'a'];
        }
        return node;
    }

    class TrieNode {
        TrieNode[] children;
        boolean isEndOfWord;

        public TrieNode() {
            children = new TrieNode[26];
        }
    }
}

6. Given a string array, find the longest common prefix of all strings. Use a Trie to solve this problem.

C++
public String longestCommonPrefix(String[] strs) {
    Trie trie = new Trie();
    for (String str : strs) {
        trie.insert(str);
    }
    StringBuilder commonPrefix = new StringBuilder();
    Trie.TrieNode node = trie.root;
    while (node != null && !node.isEndOfWord && hasSingleChild(node)) {
        node = node.children[node.children.length - 1];
        commonPrefix.append(node.val);
    }
    return commonPrefix.toString();
}

private boolean hasSingleChild(Trie.TrieNode node) {
    int count = 0;
    for (Trie.TrieNode child :

 node.children) {
        if (child != null) {
            count++;
            if (count > 1) {
                return false;
            }
        }
    }
    return count == 1;
}

7. Implement a spell checker using a Trie. The spell checker should highlight words that are not present in a predefined dictionary.

C++
public class SpellChecker {
    Trie dictionary;

    public SpellChecker(String[] words) {
        dictionary = new Trie();
        for (String word : words) {
            dictionary.insert(word);
        }
    }

    public List<String> checkSpelling(String sentence) {
        List<String> misspelledWords = new ArrayList<>();
        String[] words = sentence.split(" ");
        for (String word : words) {
            if (!dictionary.search(word.toLowerCase())) {
                misspelledWords.add(word);
            }
        }
        return misspelledWords;
    }
}

8. Given many words, words[i] has weight[i]. Design a class WordFilter that supports one function, WordFilter.f(String prefix, String suffix). It will return the word with the given prefix and suffix with the maximum weight.

C++
class WordFilter {
    Trie trie;

    public WordFilter(String[] words, int[] weights) {
        trie = new Trie();
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            for (int j = 0; j <= word.length(); j++) {
                String prefix = word.substring(0, j);
                for (int k = 0; k <= word.length(); k++) {
                    String suffix = word.substring(k);
                    String key = suffix + "#" + prefix;
                    trie.insert(key, weights[i]);
                }
            }
        }
    }

    public int f(String prefix, String suffix) {
        String key = suffix + "#" + prefix;
        return trie.search(key);
    }
}

class Trie {
    TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word, int weight) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (node.children[c - 'a'] == null) {
                node.children[c - 'a'] = new TrieNode();
            }
            node = node.children[c - 'a'];
            node.weight = weight;
        }
    }

    public int search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null ? node.weight : -1;
    }

    private TrieNode searchPrefix(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            if (node.children[c - 'a'] == null) {
                return null;
            }
            node = node.children[c - 'a'];
        }
        return node;
    }

    class TrieNode {
        TrieNode[] children;
        int weight;

        public TrieNode() {
            children = new TrieNode[26];
            weight = 0;
        }
    }
}

9. Implement a Suffix Trie and include methods for constructing the suffix trie and for checking if a string is a suffix in the suffix trie.

C++
class SuffixTrie {
    SuffixTrieNode root;

    public SuffixTrie(String word) {
        root = new SuffixTrieNode();
        for (int i = 0; i < word.length(); i++) {
            insertSuffix(root, word.substring(i), i);
        }
    }

    private void insertSuffix(SuffixTrieNode node, String suffix, int index) {
        if (suffix.isEmpty()) {


            node.isEndOfWord = true;
            node.index = index;
            return;
        }
        char c = suffix.charAt(0);
        SuffixTrieNode child = node.children[c - 'a'];
        if (child == null) {
            child = new SuffixTrieNode();
            node.children[c - 'a'] = child;
        }
        insertSuffix(child, suffix.substring(1), index);
    }

    public boolean isSuffix(String suffix) {
        SuffixTrieNode node = searchSuffix(root, suffix);
        return node != null && node.isEndOfWord;
    }

    private SuffixTrieNode searchSuffix(SuffixTrieNode node, String suffix) {
        if (suffix.isEmpty()) {
            return node;
        }
        char c = suffix.charAt(0);
        SuffixTrieNode child = node.children[c - 'a'];
        if (child == null) {
            return null;
        }
        return searchSuffix(child, suffix.substring(1));
    }

    class SuffixTrieNode {
        SuffixTrieNode[] children;
        boolean isEndOfWord;
        int index;

        public SuffixTrieNode() {
            children = new SuffixTrieNode[26];
            isEndOfWord = false;
            index = -1;
        }
    }
}

10. You are designing a search engine. In your search engine, you have stored all words of a dictionary in your database. Now, you want to design an algorithm that will be given an incomplete word (prefix), it will find the word in your database, and if it exists in your database, it will return true else false. Design this algorithm.

C++
public class SearchEngine {
    Trie dictionary;

    public SearchEngine(String[] words) {
        dictionary = new Trie();
        for (String word : words) {
            dictionary.insert(word);
        }
    }

    public boolean searchWord(String prefix) {
        return dictionary.search(prefix);
    }
}

MCQ Questions

1. What is a Trie data structure?

a) A type of binary tree
b) A type of hash table
c) A type of linked list
d) A type of tree-based data structure

Answer: d) A type of tree-based data structure

2. Which of the following operations can be performed efficiently on a Trie?

a) Insertion
b) Deletion
c) Search
d) All of the above

Answer: d) All of the above

3. What is the time complexity for searching a key in a Trie?

a) O(1)
b) O(log N)
c) O(N)
d) O(M), where M is the length of the key

Answer: d) O(M), where M is the length of the key

4. In a Trie, each node represents:

a) A character
b) A complete word
c) A prefix of a word
d) A leaf node

Answer: c) A prefix of a word

5. Which data structure is commonly used to implement the Trie?

a) Linked list
b) Stack
c) Array
d) Queue

Answer: c) Array

6. What is the space complexity of a Trie?

a) O(1)
b) O(log N)
c) O(N)
d) O(M), where M is the total number of characters in all the keys

Answer: d) O(M), where M is the total number of characters in all the keys

7. Which of the following statements about Tries is true?

a) Tries are only used for string matching
b) Tries are not suitable for large datasets
c) Tries can be used for autocomplete and spell checking
d) Tries cannot handle variable-length keys

Answer: c) Tries can be used for autocomplete and spell checking

8. In a Trie, how many children can a node have?

a) At most one child
b) At most two children
c) At most four children
d) Any number of children

Answer: d) Any number of children

9. Which of the following is not a common application of Tries?

a) Spell checking
b) IP routing
c) Autocomplete
d) Database indexing

Answer: b) IP routing

10. Which of the following operations is not typically supported by Tries?

a) Minimum key retrieval
b) Maximum key retrieval
c) Range queries
d) Union operation

Answer: d) Union operation

11. In a Trie, what does the leaf node represent?

a) A character
b) A complete word
c) A prefix of a word
d) A parent node

Answer: b) A complete word

12. What is the main advantage of using a Trie over other data structures for string storage and retrieval?

a) Constant time complexity for all operations
b) Efficient memory utilization
c) Built-in support for sorting
d) Easy implementation

Answer: b) Efficient memory utilization

13. Which of the following is a drawback of using Tries?

a) High memory usage for large datasets
b) Slow insertion and deletion operations
c) Limited support for different character encodings
d) Inefficient search performance

Answer: a) High memory usage for large datasets

14. Which of the following is a common optimization technique used in Tries?

a) Path compression
b) Hashing
c) Dynamic programming
d) Memoization

Answer: a) Path compression

15. What is the purpose of the “null” character in a Trie?

a) It represents the end of a word
b) It represents an empty node
c) It serves as a separator between keys
d) It is used for error handling

Answer: a) It represents the end of a word

16. Which of the following operations on a Trie can have a time complexity of O(N), where N is the total number of keys?

a) Insertion
b) Deletion
c) Search
d) None of the above

Answer: d) None of the above

17. Which data structure is commonly used to implement the child nodes in a Trie?

a) Linked list
b) Stack
c) Array
d) Queue

Answer: c) Array

18. In a Trie, how are the keys stored?

a) As individual characters
b) As concatenated strings
c) As binary strings
d) As integer values

Answer: a) As individual characters

19. Which of the following operations can be performed efficiently on a Trie?

a) Finding the kth smallest key
b) Finding the median key
c) Finding the maximum common prefix
d) Finding the highest frequency key

Answer: c) Finding the maximum common prefix

20. Which of the following statements about Tries is false?

a) Tries are a type of tree-based data structure
b) Tries are commonly used for dictionary implementations
c) Tries can be used for efficient pattern matching
d) Tries can only store lowercase letters

Answer: d) Tries can only store lowercase letters

Related Articles

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to top button

Table of Contents

Index
Becoming a Full Stack Developer in 2023 How to Become a Software Engineer in 2023
Close

Adblock Detected

Please consider supporting us by disabling your ad blocker!