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

Design a data structure called **WordDictionary** that  supports the following functionalities:

- **Constructor:** This function will initialize the object.

- **Add Word(word):** This function will store the provided word in the data structure.

- **Search Word(word):** This function will return TRUE if any string in the **WordDictionary** object matches the query word. Otherwise, it will return FALSE. If the query word contains dots, `.`, each dot is free to match any letter of the alphabet.

   For example, the dot in the string ".ad" can have $26$ possible search results like “aad”, “bad”, “cad”, and so on.

- **Get Words():** This function will return all the words in the **WordDictionary** class.

**Constraints:**

* $1 \leq$ `word.length` $\leq 25$

* Words passed to **Add Word()** consist of lowercase English letters.

* Words passed to **Search Word()** consist of `.` or lowercase English letters.

* There will be, at most, three dots in a word passed to **Search Word()**.

* At most, $10^2$ calls will be made to **Add Word()** , **Get Words()**  and **Search Word()**.

# Examples

# 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:



Consider the list ["bin", "pin", "spin", "pint"]. What will be the output of **Search Word("bin")**?

Consider the list [“bin”, “pin”, “spin”, “pint”]. What will be the output of Search Word(“bin”)?

Consider the list ["bin", "pin", "spin", "pint"]. What will be the output of **Search Word("spine")**?

Consider the list [“bin”, “pin”, “spin”, “pint”]. What will be the output of Search Word(“spine”)?

Consider the list ["bin", "pin", "spin", "pint"]. What will be the output of **Get Words()**?

Consider the list [“bin”, “pin”, “spin”, “pint”]. What will be the output of Get Words()?

Consider the list ["bin", "pin", "spin", "pint"]. What will be the output of **Search Word(".in")**?

Consider the list [“bin”, “pin”, “spin”, “pint”]. What will be the output of Search Word(&quot;.in&quot;)?

Design Add and Search Words Data Structure

Design Add and Search Words Data Structure

# 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 **Add Word(word)** function.

# Try it yourself

Implement your solution in `WordDictionary.java` in the following coding playground. The supporting code template provided in `DepthFS.java` is meant to assist in developing your solution to the problem.

public class DepthFS {
    TrieNode root;
    boolean canFind = false;

    public void depthFirstSearch(TrieNode root, String word, int i) {
        // If word found, return TRUE
        if (canFind) {
            return;
        }

        // If node is null, return
        if (root == null) {
            return;
        }

        // If there's only one character in the word, check if it matches the query
        if (word.length() == i) {
            if (root.complete) {
                canFind = true;
            }
            return;
        }

        int index = word.charAt(i) - 'a';
        depthFirstSearch(root.children[index], word, i + 1);
    }
}


// TrieNode template class
public class TrieNode {
  // Empty list of child nodes
  public TrieNode[] children;
  public boolean complete;

  public TrieNode() {
    // Create 26 child nodes for each letter of alphabet
    children = new TrieNode[26];
    // False indicates this node is not the end of a word
    complete = false;
  }
}

import java.util.*;


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

 public void addWord(String word) {
 // Replace this placeholder retrun statement with your code
 return;
 }

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

 public List<String> getWords() {
 // Replace this placeholder retrun statement with your code
 return new ArrayList<String>();
 }
}

Help me debug only the function Design Add and Search Words Data Structure . . 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 constructor, getWords, addWord, searchWord function and the other function(s) invoked in it/them. Do not review extra/helper files or functions not invoked in the solution function constructor, getWords, addWord, searchWord. 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 constructor, getWords, addWord, searchWord. 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 constructor, getWords, addWord, searchWord. 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

Custom

TwoDArray

import ds_v1.DataStructure.DataStructure;

public class Custom extends DataStructure {

    // define class attributes

    private void generateError(String data) {
        System.err.println("Custom is not parsable: " + data);
        System.exit(-1);
    }

    public Custom() {
        // constructor
    }

    public String toString() {
        // override toString() for your data structure
        return "";
    }

    // return value will be passed to user program
    @Override
    public Custom construct(String value, Integer type_of_ds) {
        // parse test case in json string 'value' to your desired data structure
        return new Custom();
    }

    // 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;
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 TwoDArray 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 TwoDArray() {
 // constructor
 }
 
 public TwoDArray(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 TwoDArray 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 TwoDArray(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();
 }

}

def evaluate_results(self) -> object:
        from collections import defaultdict

# TrieNode template class
        class TrieNode():
        
            # Initialize TrieNode instance
            def __init__(self): 
                # Empty list of child nodes
                self.children = []
                # False indicates this node is not the end of a word
                self.complete = False
                # Create 26 child nodes for each letter of alphabet
                for i in range(0, 26):
                     self.children.append(None)



        class WordDictionary:
            # Initialize the root with TrieNode and set 
            # the 'can_find' boolean to FALSE
            def __init__(self):
                self.root = TrieNode()
                self.can_find = False


            # Function to add a new word to the dictionary
            def add_word(self, word):
                n = len(word)
                cur_node = self.root
                for i, val in enumerate(word):
                    index = ord(val) - ord('a')
                    if cur_node.children[index] is None:
                        cur_node.children[index] = TrieNode()
                    cur_node = cur_node.children[index]
                    if i == n - 1:
                        if cur_node.complete:
                            return
                        cur_node.complete = True


            # Function to search for a word in the dictionary
            def search_word(self, word):
                self.can_find = False
                self.search_helper(self.root, word, 0)
                return self.can_find


            def search_helper(self, node, word, i):
                if self.can_find:
                    return
                if not node:
                    return
                if len(word) == i:
                    if node.complete:
                        self.can_find = True
                    return

                if word[i] == '.':
                    for j in range(ord('a'), ord('z') + 1):
                        self.search_helper(node.children[j - ord('a')], word, i + 1)
                else:
                    index = ord(word[i]) - ord('a')
                    self.search_helper(node.children[index], word, i + 1)


            # Function to get all words in the dictionary
            def get_words(self):
                words_list = []
                if not self.root:
                    return []
                return self.dfs(self.root, "", words_list)

            def dfs(self, node, word, words_list):
                if not node:
                    return words_list
                if node.complete:
                    words_list.append(word)

                for j in range(ord('a'), ord('z') + 1):
                    prefix = word + chr(j)
                    words_list = self.dfs(node.children[j - ord('a')], prefix, words_list)
                return words_list

        def main(input_1, input_2):
            result = []
            word_dict = WordDictionary()
            result.append(None)
            for i in range(1, len(input_1)):
                if input_1[i] == "addWord":
                    res = word_dict.add_word(input_2[i][0])
                    result.append(None)
                elif input_1[i] == "searchWord":
                    res = word_dict.search_word(input_2[i][0])
                    result.append(res)
                elif input_1[i] == "getWords":
                    res = word_dict.get_words()
                    if res:
                        res.sort()
                    result.append(res)

            return result
        """
        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
        """
        # 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 String sum (List<String> input_1, TwoDArray input_2) {
 WordDictionary wordDict = new WordDictionary();
 String s1=new String("addWord");
 String s2=new String("searchWord");
 String s3=new String("getWords");
 StringBuilder str1 = new StringBuilder("[");
 str1.append("null, ");
 for(int i = 1; i< input_1.size();i++)
 {
 if(input_1.get(i).equals(s1))
 {
 wordDict.addWord(input_2.value.get(i).get(0));
 str1.append("null");
 }
 else if(input_1.get(i).equals(s2))
 {
 boolean res = wordDict.search(input_2.value.get(i).get(0));
 str1.append(res);
 }
 else if (input_1.get(i).equals(s3)) {
 List<String> res = wordDict.getWords();
 if (res.size() > 0) {
 str1.append("[");
 for (int j = 0; j < res.size(); j++) {
 str1.append("\"").append(res.get(j)).append("\"");
 if (j < res.size() - 1) {
 str1.append(", ");
 }
 }
 str1.append("]");
 } else {
 str1.append("[]");
 }
 }
 if (i < input_1.size() - 1) {
 str1.append(", ");
 }
 }
 str1.append("]");
 
 return str1.toString();
 }
}

PrivateTestCases.yaml

testcases:
 - name: "testcase 1"
   inputs:
   - 1 : ["WordDictionary", "addWord", "addWord", "addWord", "getWords", "searchWord", "searchWord", "searchWord", "searchWord", "getWords"]
   - 2 : [[], ["bad"], ["dad"], ["mad"], [], ["pad"], ["bad"], [".ad"], ["b.."], []]
   output:
   - 1 : ["null", "null", "null", "null", "[bad, dad, mad]", "false", "true", "true", "true", "[bad, dad, mad]"]
 
 - name: "testcase 2"
   inputs:
   - 1 : ["WordDictionary", "addWord", "addWord", "addWord", "getWords", "searchWord"]
   - 2 : [[], ["hello"], ["help"], ["hi"], [], ["h."]]
   output:
   - 1 : ["null", "null", "null", "null", "[hello, help, hi]", "true"]
 
 - name: "testcase 3"
   inputs:
   - 1 : ["WordDictionary", "getWords", "addWord", "addWord", "getWords", "searchWord", "addWord", "addWord", "searchWord", "searchWord", "getWords"]
   - 2 : [[], [], ["apple"], ["grape"], [], ["strawberry"], ["banana"], ["banan"], ["bana.."], ["ba...a"], []]
   output: 
   - 1 : ["null", "[]", "null", "null", "[apple, grape]", "false", "null", "null", "true", "true", "[apple, banan, banana, grape]"]
 
 - name: "testcase 4"
   inputs:
   - 1 : ["WordDictionary", "addWord", "addWord", "addWord", "getWords", "searchWord", "searchWord", "searchWord", "searchWord", "getWords"]
   - 2 : [[], ["ox"], ["box"], ["pox"], [], ["x"], ["b."], ["..x"], ["b.."], []]
   output:
   - 1 : ["null", "null", "null", "null", "[box, ox, pox]", "false", "false", "true", "true", "[box, ox, pox]"]
 
 - name: "testcase 5"
   inputs:
   - 1 : ["WordDictionary", "searchWord", "addWord", "addWord", "getWords", "searchWord"]
   - 2 : [[], ["bad"], ["dgwrgwrgrehehr"], ["erthqethethetqth"], [], ["...hqethethetqth"]]
   output:
   - 1 : ["null", "false", "null", "null", "[dgwrgwrgrehehr, erthqethethetqth]", "true"]


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

def validate_inputs(self) -> None:
 """
 self.__inputs is the list of inputs that are passed as input to function
 store the result using the self.store_result(error_msg, status)
 return : void
 """
 import re
 def is_valid_1d_string_array(arr):
 if not isinstance(arr, list):
 return False # Not a valid 1D array if it's not a list

 return all(isinstance(elem, str) for elem in arr)

 def is_valid_2d_array(arr):
 if not isinstance(arr, list) or not all(isinstance(row, list) for row in arr):
 return False

 for row in arr:
 if any(elem is None or isinstance(elem, bool) for elem in row):
 return False
 if not all(isinstance(elem, str) for elem in row):
 return False

 return True


 def validate_input_pairs(input1, input2):
 error_messages = []
 word_dictionary_flag = False # Flag to track if "WordDictionary" occurs more than once or not at the start
 found_word_dictionary = False # Flag to check if "WordDictionary" exists in the input

 for i, (cmd, arg) in enumerate(zip(input1, input2)):
 if cmd == "WordDictionary":
 if word_dictionary_flag or found_word_dictionary or i != 0:
 error_messages.append("The 'WordDictionary' should only occur once and only at the start.")
 word_dictionary_flag = True
 found_word_dictionary = True

 elif cmd == "addWord":
 if not arg or len(arg) != 1 or not isinstance(arg[0], str) or not all('a' <= ch <= 'z' for ch in arg[0]) or not (1 <= len(arg[0]) <= 25):
 error_messages.append(f"Input2 at index {i} for 'addWord' must contain a single lowercase string with 1 to 25 characters.")

 elif cmd == "searchWord":
 if not arg or len(arg) != 1 or not isinstance(arg[0], str):
 error_messages.append(f"Input2 at index {i} for 'searchWord' must contain a single string.")
 else:
 word = arg[0]
 if not re.match(r'^[a-z.]+$', word):
 error_messages.append(f"Input2 at index {i} for 'searchWord' must be a string of lowercase characters and '.' only.")
 elif word.count('.') > 3:
 error_messages.append(f"Input2 at index {i} for 'searchWord' cannot have more than 3 dots.")
 elif not (1 <= len(word) <= 25):
 error_messages.append(f"Input2 at index {i} for 'searchWord' must contain a word with a length between 1 and 25 characters.")

 else:
 if arg is not None and not isinstance(arg, list):
 error_messages.append(f"Input2 at index {i} for 'WordDictionary' and 'getWords' must be an empty list.")

 if not found_word_dictionary:
 error_messages.append("The 'WordDictionary' should exist in the input.")

 return error_messages




 def total_calls(input1):
 call_count = {
 "WordDictionary": 0,
 "addWord": 0,
 "getWords": 0,
 "searchWord": 0
 }
 for word in input1:
 if word in call_count:
 call_count[word] += 1

 return sum(call_count.values())


 def check_values(array):
 for row in array:
 for value in row:
 if value > 100 or value < -100:
 return False
 return True

 def validate_input1(input1):
 valid_values = {"WordDictionary", "addWord", "getWords", "searchWord"}

 for value in input1:
 if value not in valid_values:
 return False # Invalid input if any element is not in the valid set

 return True # All elements in input1 are valid

 input1 = self.__inputs[0]
 input2 = self.__inputs[1]
 # inputs can be accessed using self.__inputs starting from 0 to len(self.__inputs) - 1
 if not is_valid_1d_string_array(input1):
 self.store_result(("Input 1: Invalid test case."), ValidationFunction.FAIL)
 elif not is_valid_2d_array(input2):
 self.store_result ("Input 2: Invalid test case.", ValidationFunction.FAIL)
 elif not validate_input1(input1):
 self.store_result("Invalid input1. Expected: 'WordDictionary', 'addWord', 'getWords', 'searchWord'.", ValidationFunction.FAIL)
 elif not (2 <= total_calls(input1) <= 1001):
 self.store_result("Maximum calls allowed is in range 2 - 1000.", 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 Design Add and Search Words Data Structure problem.

Trie

Graphs

Topological Sort

Cyclic Sort

Conclusion

Design Add and Search Words Data Structure

Statement

Examples

Understand the problem

Figure it out!

Try it yourself