Learn and practice Tries, Graphs, Custom Data Structures, and Topological Sort patterns to solve coding interview problems.

Grokking Grind 75 in Python: Mastery through Coding Patterns

Mastering advanced data structures and sorting techniques is key to efficiently solving challenging coding interview questions. This module explores various patterns that demonstrate the use of advanced data structures, including Trie for efficient data storage, graph traversal for modeling relationships, Custom Data Structures for tailored problem-solving, and Topological Sort for ordering elements. These patterns enhance data organization, optimization, and efficiency in problem-solving.

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.py` in the following coding playground. You will need the provided supporting code to implement your solution.


from trie_node import *


class Trie():
    def __init__(self):
        # Write your code here
        pass
    
    # inserting string in trie
    def insert(self, string):
        # Write your code here
        pass
    
    # searching for a string
    def search(self, string):

        # Replace this placeholder return statement with your code
        return False
    
    # searching for a prefix
    def search_prefix(self, prefix):

        # Replace this placeholder return statement with your code
        return False


class TrieNode():
    def __init__(self):
        self.children = {}
        self.is_word = False

# Quick Fix\nYou are Edward, a Senior Software Engineer who specializes in coding interview patterns, data structures and algorithms, and is great at debugging issues in code.\n\n- Edward, please keep in mind that you do not have to print the data of the placeholders. Also, do not mention anything about yourself.\n\nEdward, you are given the following data in the placeholders:\n- Function name: `__init__, insert, search, search_prefix`\n- Candidate's submitted solution code: USER_CODE\n- Error: ERROR_DESCRIPTION\n- Failed test case: FAILED_TEST_CASE\n- Coding language: `Python`\n\n- Edward, your task is to understand the type of error that is occurring in the coding language provided.\n- Once you've understood the error as per the error’s description, and why the test case failed, you will suggest how the candidate can improve their solution code to fix the error.\n- Edward, you will not give the corrected code, just a hint on what the error tells, and how to fix it.\n- Edward, please limit your response strictly to 100 words. No more words than the limit.

# Review Code\nEdward, your current task is to review the `__init__, insert, search, search_prefix` function(s) and the other function(s) invoked in it/them.\n\n-Take your time and review the candidate's solution code.\n- Do not review any extra/helper files or functions not invoked in the solution function `__init__, insert, search, search_prefix`.\n- Do not review the code of data structure 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. \n- Also, if the solution code doesn’t use the coding pattern stated above, then please encourage the candidate to reattempt the problem using that pattern corectly.

# Review time complexity\n- Please provide a brief time complexity analysis of the function(s) `__init__, insert, search, search_prefix`. \n- While calculating time complexity, include the time complexity of built-in Python functions invoked by the code. \n- The answer should be to the point in approximately 60 words.

# Review space complexity\n- Please provide a brief space complexity analysis of the function(s) `__init__, insert, search, search_prefix`. \n- While calculating space complexity, include the space complexity of built-in Python functions invoked by the code. \n- 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). \n- The answer should be to the point in approximately 60 words.

TwoDArray

convert

import sys
import json

sys.path.append("../ds_v1")
from data_structure import DataStructure

# throw parsing errors for incorrect test case format
def parsingError(element_string, error_message):
    sys.stderr.write(f"Parsing Error: {element_string} {error_message}")
    exit()


# className: MyCustomDS
class TwoDArray(DataStructure):
    def __init__(self):
        # constructor
        pass

    def __str__(self):
        # override print() for your data structure
        pass

    # return value will be passed to user program
    def construct(self, value: str, type_of_arr: int) -> any:
        # parse test case in json string 'value' to your desired data structure
        parse_list = json.loads(value)
        return parse_list

    # input param contains return value of user program
    def traverse(self, input: any, type_of_arr: int) -> str:
        # TwoDArray your data structure 'input' to a json string representing a test case output
        return json.dumps(input)


import sys
import json

sys.path.append("../ds_v1")
from data_structure import DataStructure

# throw parsing errors for incorrect test case format
def parsingError(element_string, error_message):
    sys.stderr.write(f"Parsing Error: {element_string} {error_message}")
    exit()


# className: MyCustomDS
class convert(DataStructure):
    def __init__(self):
        # constructor
        pass

    def __str__(self):
        # override print() for your data structure
        pass

    # return value will be passed to user program
    def construct(self, value: str, type_of_arr: int) -> any:
        # parse test case in json string 'value' to your desired data structure
        parse_list = json.loads(value)
        return parse_list

    # input param contains return value of user program
    def traverse(self, input: any, type_of_arr: int) -> str:
        # convert your data structure 'input' to a json string representing a test case output
        return json.dumps(input)


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


from trie import *
from trie_node import *

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

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.

Graphs

Trie

Custom Data Structures

Topological Sort

Conclusion

Implement Trie

Statement

Examples

Understand the problem

Figure it out!

Try it yourself