☕ Tries and BFS

A solution to our last Coding Interview Question on finding the longest word in a dictionary that is made up of other words. Plus, a google interview question on finding a subarray.

Hey Guys,

Interviewing.io is a fantastic resource I wanted to share with you all.

You can book realistic mock interviews with senior FAANG engineers who will give you detailed and actionable feedback on exactly what you need to work on.

Mastering algorithms on LeetCode and system design on SystemsExpert is great, but they don’t prepare you for the pressure and stress that comes from an actual interview setting.

The best part?

You don’t pay anything until you’re hired.

Check them out here.

Special thanks to Interviewing.io for sponsoring Quastor Daily. I’m a user of the service!

Interview Question

You are given two arrays.

One array is a shorter array and has all distinct elements

The other array is longer and can have repeat elements.

Find the shortest subarray in the longer array that contains all the elements in the shortest array.

The items can appear in any order.

Input - [1, 5, 9], [7, 5, 9, 0, 2, 1, 3, 5, 7, 9, 1, 1, 5, 8, 8, 9, 7]

Output - [7, 10]

Explanation - This is the index for the subarray [5, 7, 9, 1] in the larger array.

We’ll send a detailed solution tomorrow, so make sure you move our emails to primary, so you don’t miss them!

Gmail users—move us to your primary inbox

• On your phone? Hit the 3 dots at the top right corner, click "Move to" then "Primary"

• On desktop? Back out of this email then drag and drop this email into the "Primary" tab near the top left of your screen

Apple mail users—tap on our email address at the top of this email (next to "From:" on mobile) and click “Add to VIPs”

Previous Solution

As a refresher, here’s the last question

You are given a dictionary of words.

Write a function that finds the longest word in the dictionary that is made up of other words in the list.

Input: words = ["w","wo","wor","worl","world"]
Output: "world"
Explanation: The word "world" can be built one character at a time by "w", "wo", "wor", and "worl". 

Here’s the question in LeetCode.

Solution

We can solve this question with a Trie (prefix tree).

The basic idea is we create a Trie with all the words in our dictionary.

Then, we can run a Breadth-First Search on our Trie to find the longest possible word.

We first create a TrieNode class that represents the individual nodes in our Trie.

class TrieNode:
    def __init__(self, val = None):
        self.val = val
        self.children = {}
        self.isEnd = None

Then, we create a Trie class.

The constructor for our Trie class is just initializing our Trie’s root node.

class Trie:
    def __init__(self):
        self.root = TrieNode()

Now, we have to write a function to add words into our Trie.

Here’s the code.

    def addWord(self, word):
        node = self.root
        
        for l in word:
            if l not in node.children:
                node.children[l] = TrieNode(l)
            node = node.children[l]
        
        node.isEnd = word

We start at the root node of our Trie.

Then, we go letter by letter in the word we want to add.

We check if the letter is a child in the current node’s children.

If not, we add a new child TrieNode representing our letter.

Then, we can move down to our child letter.

After we’ve inserted all the letters in our word, we mark the last latter’s isEnd variable by changing it to the word itself.

This isEnd variable will be useful for our BFS.

So, now that we have a function to insert words, we can insert all the words in our dictionary inside the Trie.

After we’ve inserted all the words, it’s time to run a BFS on our Trie and find the longest word that is made up of other words in the list.

We’ll start at the root node and look through the root node’s children to find children that are words in our dictionary.

We can tell by looking at the isEnd variable. If the isEnd variable is not None, then that means that the TrieNode represents the end of a word in our dictionary.

So, from our root node we’ll search any child that has an isEnd value.

For each of those nodes, we repeat the process. Search any of that node’s children that has an isEnd value, since those TrieNodes represent the end of words in our dictionary.

On each iteration, we’ll keep track of the longest word we’ve seen by looking at the value of isEnd.

Here’s the code for our BFS.

    def _findLongest(self, node):
        maxWord = node.isEnd if node.isEnd != None else ""
        
        for l in node.children:
            if node.children[l].isEnd != None:
                newWord = self._findLongest(node.children[l])
                if len(newWord) > len(maxWord):
                    maxWord = newWord
                elif len(newWord) == len(maxWord):
                    maxWord = min(newWord, maxWord)      
        
        return maxWord

Here’s the complete Python 3 code for our solution.

Can you analyze the time/space complexity of our solution?

Reply back with your analysis!

We’ll tell you if you’re right/wrong!

---

Want more practice with real FAANG software engineers?

Check out Interviewing.io!

You don’t have to pay anything until you get that job at FAANG!