Learn and practice Tries, Graphs, Cyclic Sort, and Topological Sort patterns to solve coding interview problems.

Grokking the Blind 75 Problems

In this module, we'll explore some advanced data structures and sorting techniques to help us solve challenging coding interview questions. We'll start by mastering two advanced data structures: graphs and tries. Graphs are versatile data structures that tackle complex interconnected problems, while tries offer an elegant solution for scenarios where standard data structures fall short. Next, we’ll explore two advanced sorting algorithms: Cyclic Sort and Topological Sort. Cyclic Sort is used when specific constraints on the input are met, making it the most efficient sorting algorithm in such cases. Topological Sort leverages graph-based algorithms to handle partially ordered elements. We’ll learn to recognize when these advanced sorting techniques are applicable and how to leverage them effectively to solve complex problems. By completing this module, you’ll enhance your problem-solving toolkit and solidify your status as a standout candidate in technical interviews.

Advanced Data Structures and Sorting Techniques

# Statement
Trie is a tree-like data structure used to store strings. The tries are also called **prefix trees** because they provide very efficient prefix-matching operations. Implement a [trie](https://www.educative.io/answers/what-is-a-prefix-tree) data structure with three functions that perform the following tasks:

- **Insert (word):** This inserts a word into the trie.
- **Search (word):** This searches the given word in the trie and returns TRUE, if found. Otherwise, return FALSE.
- **Search prefix (prefix):** This searches the given prefix in the trie and returns TRUE, if found. Otherwise, return FALSE.


**Constraints:**
- $1 \leq$ `word.length`, `prefix.length` $\leq 500$
- The strings consist only of lowercase English letters.
- At most, $10^3$ calls in total will be made to the functions.

# Examples
The **Insert** function does not return anything. The **Search** and **Search prefix** functions return TRUE if the input is found in the trie. Otherwise, they will return FALSE.


# Understand the problem
Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:


Given a trie with the words `[bat, bag, make, broom, bait]`, what will be the output of the following query?

```text
search('bait')

Given a trie with the words <code>[bat, bag, make, broom, bait]</code>, what will be the output of the following query?
<pre><code class="language-text">search('bait')</code></pre>

Given a trie with the words `[bat, bag, make, broom, bait]`, what will be the output of the following query?

```text
search('bagg')

Given a trie with the words <code>[bat, bag, make, broom, bait]</code>, what will be the output of the following query?
<pre><code class="language-text">search('bagg')</code></pre>

Given a trie with the words `[broke, what, home, broom]`, what will be the output of the following query?

```text
search prefix('b')

Given a trie with the words <code>[broke, what, home, broom]</code>, what will be the output of the following query?
<pre><code class="language-text">search prefix('b')</code></pre>

Implement Trie

Implement Trie

# Figure it out!
We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

> **Note**: The game below is only for the **Insert** function.

# Try it yourself
Implement your solution in `Trie.java` in the following coding playground. You will need the provided supporting code to implement your solution.


import java.util. * ;


class Trie {
  
    public Trie() {
        // Write your code here
    }

    // inserting string in trie
    public void insert(String word) {
        // Write your code here
    }

    // searching for a string
    public boolean search(String word) {
        // Replace this placeholder return statement with your code
        return false;
    }

    // searching for a prefix
    public boolean searchPrefix(String prefix) {
        // Replace this placeholder return statement with your code
        return false;
    }
}


import java.util.HashMap;

class TrieNode {
 boolean isWord;
 HashMap<Character, TrieNode> children;

 public TrieNode() {
 this.children = new HashMap<Character, TrieNode>();
 this.isWord = false;
 }
}

Help me debug only the function Implement Trie . . I don't need the corrected code.I don't want explanations or code review. Just provide me the exact and to-the-point error that helps me run the code successfully on the test cases provided.

Please help me understand why this code failed for the last failed test case. Don't give me the corrected code. . If yes, then Just provide me the exact and to-the-point error that helps me run the code successfully on the test cases provided.

Your current task is to review only the insert, search, searchPrefix function and the other function(s) invoked in it/them. Do not review extra/helper files or functions not invoked in the solution function insert, search, searchPrefix. Do not review the code of data structures objects instantiated like a binary tree, linked list, trie, union find, etc., in the solution functions. Just review the solution/algorithm function of the problem. Also, Answer the following questions: Is the Trie pattern used? Take your time and review the code.

Please provide a brief time complexity analysis of the function insert, search, searchPrefix. While calculating time complexity, include the time complexity of built-in Java functions invoked by the code. The Answer should be to the point and in a few lines.

Please provide a brief Space complexity analysis of the function insert, search, searchPrefix. While calculating space complexity, include the space complexity of built-in Java functions invoked by the code. Do not include the space used for the input parameters and the space used for just returning an output(not used as a scratch space). The Answer should be to the point and in a few lines

TwoDList

OneDArray

import ds_v1.DataStructure.DataStructure;
import java.util.*;
import com.fasterxml.jackson.databind.*;

import ds_v1.DataStructure.DataStructure;

import java.io.IOException;
import java.util.ArrayList;
import com.fasterxml.jackson.core.type.TypeReference;

public class TwoDList extends DataStructure {

 // define class attributes
 public ArrayList<ArrayList<String>> value;
 //public ArrayList<ArrayList<Integer>> value1;
 private void generateError(String data) {
 System.err.println("MyCustomDS is not parsable: " + data);
 System.exit(-1);
 }
 public TwoDList() {
 // constructor
 }
 
 public TwoDList(ArrayList<ArrayList<String>> data) {
 // constructor 
 value = new ArrayList<ArrayList<String>>();
 for(int i = 0; i < data.size(); i++)
 {
 value.add(new ArrayList<String>());
 for(int j = 0; j < data.get(i).size(); j++)
 {
 value.get(i).add(data.get(i).get(j));
 }
 }

 }
 

 public String toString() {
 // override toString() for your data structure
 return "";
 }


 private ArrayList<ArrayList<String>> construct_int_arr(String new_value) {
 ArrayList<ArrayList<String>> arr = null;
 try {
 arr = new ObjectMapper().readValue(new_value, new TypeReference<ArrayList<ArrayList<String>>>() {
 });
 } catch (IOException e) {
 }
 return arr;
 }

 // return value will be passed to user program
 @Override
 public TwoDList construct(String new_value3, Integer type_of_ds) {
 // parse test case in json string 'value' to your desired data structure
 ArrayList<ArrayList<String>> value = construct_int_arr(new_value3);
 return new TwoDList(value); 
 }

 // input param contains return value of user program
 @Override
 public String traverse(Object input, Integer type_of_ds) {
 // convert your data structure 'input' to a json string representing a test case output
 return input.toString();
 }

}

import ds_v1.DataStructure.DataStructure;

public class OneDArray extends DataStructure {

    // define class attributes
    private void generateError(String data) {
        System.err.println("OneDArray is not parsable: " + data);
        System.exit(-1);
    }

    public OneDArray() {
        // constructor
    }

    public String toString() {
        // override toString() for your data structure
        return "";
    }

    // return value will be passed to user program
    @Override
    public OneDArray construct(String value, Integer type_of_ds) {
        // parse test case in json string 'value' to your desired data structure
        return new OneDArray();
    }

    // input param contains return value of user program
    @Override
    public String traverse(Object input, Integer type_of_ds) {
        // convert your data structure 'input' to a json string representing a test case output
        return input.toString();

    }

}


def evaluate_results(self) -> object:
        """
        self.__inputs is the list of inputs that are passed as input to function
        self.__actual_output is a list of outputs that is produced by the learner's code
        return : self.__edu__result object
        """
        from collections import defaultdict

        class TrieNode():
            def __init__(self):
                self.children = {}
                self.is_word = False

        class Trie():
            # Constructor to create a trie node.
            def __init__(self):
                self.root = TrieNode()

            # A function to insert a word in trie.
            def insert(self, word):
                node = self.root
                
                for c in word:
                    if c not in node.children:
                        node.children[c] = TrieNode()
                    node = node.children.get(c)
                
                node.is_word = True  

            # A function to search for a word in the trie.
            def search(self, word):
                node = self.root
                
                for c in word:
                    if c not in node.children:
                        return False
                    node = node.children.get(c)

                return node.is_word

            # A function to search for a prefix of a word in the trie.
            def search_prefix(self, prefix):
                node = self.root

                for c in prefix:
                    if c not in node.children:
                        return False
                    node = node.children.get(c)

                return True

        def main(input_1, input_2):
            result = []
            trie_obj = Trie()
            result.append(None)
            for i in range(1, len(input_1)):
                if input_1[i] == "insert":
                    res = trie_obj.insert(input_2[i][0])
                    result.append(None)
                elif input_1[i] == "search":
                    res = trie_obj.search(input_2[i][0])
                    result.append(res)
                elif input_1[i] == "search_prefix":
                    res = trie_obj.search_prefix(input_2[i][0])
                    result.append(res)

            return result

        # multiple outputs will be added at each index respectively for a single test_case
        expected_outputs = []
        inp1 = self.__inputs[0]
        inp2 = self.__inputs[1]
        expected = main(inp1 , inp2)

        # store the 1st expected output that should be displayed to the user 
        expected_outputs.append(expected)
        actual = self.__actual_outputs[0]

        if json.dumps(expected) == json.dumps(actual):
            self.__edu_result.store_result(expected_outputs, TestCaseResult.PASS)
        else:
            self.__edu_result.store_result(expected_outputs, TestCaseResult.FAIL)

        return self.__edu_result


import java.util.*;


public class Main {
 public static List<String> sum (List<String> input_1, TwoDList input_2) {
 List<String> result = new ArrayList<String>();
 Trie trieObj = new Trie();

 result.add(null);
 String s1 = new String("insert"); 
 String s2 = new String("search"); 
 String s3 = new String("search_prefix"); 

 for(int i = 1; i < input_1.size(); i++)
 {
 if(input_1.get(i).equals(s1))
 {
 trieObj.insert(input_2.value.get(i).get(0));
 result.add(null);
 }

 if(input_1.get(i).equals(s2))
 {
 boolean res = trieObj.search(input_2.value.get(i).get(0));
 result.add(Boolean.toString(res));
 }

 if(input_1.get(i).equals(s3))
 {
 boolean res = trieObj.searchPrefix(input_2.value.get(i).get(0));
 result.add(Boolean.toString(res));
 }
 }
 return result;
 }
}

implement-trie (1).yaml

testcases:
  - name: "testcase 1"
    inputs:
    - 1 : ["Trie", "insert", "search", "search", "search_prefix", "insert", "search"]
    - 2 : [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
    output:
    - 1 : [null, null, true, false, true, null, true]

  - name: "testcase 2"
    inputs:
    - 1 : ["Trie", "insert", "insert", "insert", "search_prefix", "insert", "search"]
    - 2 : [[], ["the"],[ "answer"], ["a"], ["t"], ["this"], ["ans"]]
    output: 
    - 1 : [null, null, null, null, true, null, false]

  - name: "testcase 3"
    inputs:
    - 1 : ["Trie", "insert", "search", "search", "search_prefix", "insert", "search"]
    - 2 : [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
    output: 
    - 1 : [null, null, true, false, true, null, true]

  - name: "testcase 4"
    inputs:
    - 1 : ["Trie", "insert", "insert", "search", "search_prefix", "insert", "search_prefix"]
    - 2 : [[], ["hello"], ["hell"], ["he"], ["h"], ["helicopter"], ["heli"]]
    output: 
    - 1 : [null, null, null, false, true, null, true]

  - name: "testcase 5"
    inputs:
    - 1 : ["Trie", "insert", "insert", "insert", "insert", "search", "search_prefix", "search_prefix", "search"]
    - 2 : [[], ["apple"], ["banana"], ["mango"], ["strawberry"], ["ap"], ["ban"], ["x"], ["mango"]]
    output: 
    - 1 : [null, null, null, null, null, false, true, false, true]

def sum(input_1, input_2):
    return input_1+input_2

def validate_inputs(self) -> None:
        """
        Validate inputs passed to the function.
        Store the result using self.store_result(error_msg, status).
        return: void
        """
        def is_valid_2d_array(arr):
            return isinstance(arr, list) and all(isinstance(row, list) and all(isinstance(elem, str) for elem in row) for row in arr)

        def check_param_values(input1):
            if len(input1) == 0:
                return "Inputs can't be empty"
            elif input1[0] != "Trie":
                return "The first input method name should be the Constructor name"
            elif input1.count("Trie") != 1:
                return "Invalid input1: 'Trie' should be written only once"
            elif "insert" not in input1:
                return "At least one 'insert' call is required in the test cases."

            for i in range(1, len(input1)):
                if input1[i] not in ["Trie", "insert", "search", "search_prefix"]:
                    return str(input1[i]) + " arguments are invalid: input method '" + str(input1[i]) + "' does not exist"
            return True

        def validate_input_pairs(input1, input2):
            valid_commands = {"Trie", "insert", "search", "search_prefix"}
            error_messages = []
            trie_created = False
            trie_count = 0
            insert_called = False

            total_insert_calls = sum(1 for cmd in input1 if cmd == "insert")
            total_search_calls = sum(1 for cmd in input1 if cmd == "search")
            total_search_prefix_calls = sum(1 for cmd in input1 if cmd == "search_prefix")

            total_calls = total_insert_calls + total_search_calls + total_search_prefix_calls

            if total_calls > 1000:
                error_messages.append("Exceeded the limit of total calls. Maximum allowed is 1000.")
                return error_messages

            for cmd, arg in zip(input1, input2):
                if cmd not in valid_commands:
                    error_messages.append(f"Invalid command '{cmd}'. Only 'Trie', 'insert', 'search', and 'search_prefix' are allowed.")
                elif cmd == "Trie":
                    trie_count += 1
                    if trie_count > 1 or trie_created or arg:
                        error_messages.append("'Trie' must be the first and called only once, and should have an empty argument list.")
                    trie_created = True
                elif cmd == "insert":
                    insert_called = True  # Set insert_called to True when "insert" is called
                    if not arg or not isinstance(arg, list) or len(arg) != 1 or not isinstance(arg[0], str) or not arg[0].isalpha() or not arg[0].islower() or len(arg[0]) > 500:
                        error_messages.append(f"'{cmd}' must be a lowercase string in the range [1, 500].")
                elif not insert_called:
                    error_messages.append(f"'{cmd}' is not allowed before 'insert' is called.")
                    break
                elif not arg or not isinstance(arg, list) or len(arg) != 1 or not isinstance(arg[0], str) or not arg[0].isalpha() or not arg[0].islower() or len(arg[0]) > 500:
                    error_messages.append(f"'{cmd}' must be a lowercase string in the range [1, 500].")

            return error_messages

        input1, input2 = self.__inputs[0], self.__inputs[1]

        if not is_valid_2d_array(input2):
            self.store_result("Invalid test case! Please recheck the inputs", ValidationFunction.FAIL)
        elif check_param_values(input1) != True:
            self.store_result(check_param_values(input1), ValidationFunction.FAIL)
        elif any(value not in {"Trie", "insert", "search", "search_prefix"} for value in input1):
            self.store_result("Invalid command: only 'Trie', 'insert', 'search', and 'search_prefix' are valid", ValidationFunction.FAIL)
        elif len(input1) != len(input2):
            self.store_result("Mismatch in the number of commands and their corresponding parameters", ValidationFunction.FAIL)
        else:
            errors = validate_input_pairs(input1, input2)
            if errors:
                self.store_result("\n".join(errors), ValidationFunction.FAIL)
            else:
                self.store_result("", ValidationFunction.PASS)


Try to solve the Implement Trie (Prefix Tree) problem.

Trie

Graphs

Topological Sort

Cyclic Sort

Conclusion

Implement Trie

Statement

Examples

Understand the problem

Figure it out!

Try it yourself