Uber Staff SWE Onsite Technical Coding Question ($660k average salary)

Uber’s compensation is excellent at the staff level (Uber calls it “5b”), averaging around $660,000 (~$240,000 base, ~$400,000 stock and $20,000 in bonuses). Of course, such positions are not easy to get. Uber’s technical interviews are usually pretty difficult from what I hear from coworkers and friends who have interviewed there before.

One individual recently did a Uber Staff Software Engineer interview for an iOS role. The coding question this candidate received, however, isn’t too difficult if you have practice with the data structure in question. It’s only tagged as “Medium” on Leetcode, though if you haven’t seen similar questions before, it’s understandable why you’d think it’s quite difficult.

However, the Leetcode editorial (the “approved solution”) is poorly written. Let’s see if we can do better.

Let’s dig into what the question is and where I got the interview question from.

Let’s dig into what the question is and where I got the interview question from.

Here’s the source of the information: https://www.youtube.com/watch?v=RWP9Zmhyv_Q&t=281s.

The candidate says the question is basically https://leetcode.com/problems/design-add-and-search-words-data-structure/description/. This question is tagged as Medium difficulty, though some commenters think it’s deserving of hard difficulty. 😉

Here’s the question:

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

• *WordDictionary() Initializes the object.*
• *void addWord(word) Adds word to the data structure, it can be matched later.*
• *bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.*

Example:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation WordDictionary wordDictionary = new WordDictionary(); wordDictionary.addWord("bad"); wordDictionary.addWord("dad"); wordDictionary.addWord("mad"); wordDictionary.search("pad"); // return False wordDictionary.search("bad"); // return True wordDictionary.search(".ad"); // return True wordDictionary.search("b.."); // return True*

Constraints:

• 1 <= word.length <= 25
• word in addWord consists of lowercase English letters.
• word in search consist of '.' or lowercase English letters.
• There will be at most 2 dots in word for search queries.
• At most 104 calls will be made to addWord and search.

If you have seen a trie before, this question should be screaming to you that you want to use a trie. It’s very similar to the original trie question, just with a wildcard character.

However, if you’ve never used a trie before, please learn how to implement one before proceeding with this. Do https://leetcode.com/problems/implement-trie-prefix-tree/. If you can’t think of how to implement this yourself, it’s fine — read the solution, then memorize how to implement one. I personally did this question 3 or 4 times (spaced repetition) to ensure I could implement this data structure in my sleep.

Then, this question is just modifying how we search our trie data structure.

Let’s start with the easy part: inserting words. This should be the same as your standard trie implementation. We’ll create a Node data structure which stores a letter, whether it’s the end of a word, and a list of children Nodes.

class Node(object):
    def __init__(self, val, is_word=False):
        self.val = val
        self.children = {}
        self.is_word = is_word

    def add_child(self, child_node):
        self.children[child_node.val] = child_node
class WordDictionary(object):
    def __init__(self):
        self.head = Node(None)
    def addWord(self, word):
        """
        :type word: str
        :rtype: None
        """
        curr = self.head
        for w in word:
            if w not in curr.children:
                curr.add_child(Node(w))
            curr = curr.children[w]
        curr.is_word = True

Now let’s think about how to search for a word using a wildcard . character.

First, how do we normally search for a word in a trie when there aren’t wildcards? We’re just running through two conditions:

1. If the current node’s children we’re on doesn’t have the next character we’re looking for, we return False.
2. If the current node’s children has the next character we’re looking for, we fetch the current node’s child node, set that as the new current node, and move onto the next letter in the word.

You can “move onto the next letter in the word” by doing something like word[1:] to slice off the letter you already found, or you can increment an index that tells you the position of the next character you’re looking for.

So how does the wildcard work? If we encounter a . as the next character to search for, we’re basically saying: “Move to the next character, and see if I can find the remaining word using any of my children as the node.”

So we might imagine our code to look something like this:

def search(curr_node, curr_idx, word):
    curr_char = word[curr_idx]
    ...
    if curr_char == '.':
        for child_node in curr_node.children:
            if search(child_node, curr_idx + 1, word):
                return True
...

If it’s not a wildcard, then let’s do the regular exit condition.

def search(curr_node, curr_idx, word):
    curr_char = word[curr_idx]
    
    if curr_char == '.':
        for child_node in curr_node.children:
            if search(child_node, curr_idx + 1, word):
                return True
    elif curr_char not in curr_node.children:
        return False
    ...

And, if it’s not a wildcard, and it is in the children, we can just explore starting from the child.

def search(curr_node, curr_idx, word):
    curr_char = word[curr_idx]
    ...
    if curr_char == '.':
        for child_node in curr_node.children:
            if search(child_node, curr_idx + 1, word):
                return True
    elif curr_char not in curr_node.children:
        return False
    
    return search(curr_node.children[curr_char], curr_idx + 1, word)

Finally, how do we know if we’ve found the word? We’ll just check if our curr_idx is equal to the length of the word, and if the node we’re on is the end of a word.

def search(curr_node, curr_idx, word):
    if curr_idx == len(word):
        return curr_node.is_word

    curr_char = word[curr_idx]
    ...
    if curr_char == '.':
        for child_node in curr_node.children:
            if search(child_node, curr_idx + 1, word):
                return True
    elif curr_char not in curr_node.children:
        return False
    
    return search(curr_node.children[curr_char], curr_idx + 1, word)

Finally, to not modify the provided function, we can rename our search function to search_from_node, and have the original search just call search_from_node with a starting index of 0 and node equal to the head node.

To clean up the code, we can save our word outside of the function. Here’s the final code:

class Node(object):
    def __init__(self, val, is_word=False):
        self.val = val
        self.children = {}
        self.is_word = is_word

    def add_child(self, child_node):
        self.children[child_node.val] = child_node
class WordDictionary(object):
    def __init__(self):
        self.head = Node(None)
    def addWord(self, word):
        """
        :type word: str
        :rtype: None
        """
        curr = self.head
        for w in word:
            if w not in curr.children:
                curr.add_child(Node(w))
            curr = curr.children[w]
        curr.is_word = True
    def search(self, word):
        """
        :type word: str
        :rtype: bool
        """
        self.word = word
        return self.search_from_node(0, self.head)
    def search_from_node(self, idx, node):
        if idx == len(self.word):
            if node.is_word:
                return True
            return False
        cl = self.word[idx]
        if cl == '.':
            for child in node.children.values():
                if self.search_from_node(idx+1, child):
                    return True
        if cl not in node.children:
            return False
        return self.search_from_node(idx+1, node.children[cl])

Hope this was helpful, thanks for reading!