Design Trie. Solving an Uber Interview Question

I came across this post on how a puzzle landed him a job at Google. This article is about the Data structure he used to solve the problem.

In this article we shall cover :
1> What are Tries trees.
2> Why and how are they used.
3> How to Implement a simple Trie in javascript.

So bisaclly he used a Trie/Suffix Tree to solve the puzzle,

What are Trie ?

Tries are a tree-based Data Structure used to efficiently store string.

How are they used ?

Imagine you're tasked with storing all city names in the United States.

The naive approach would be to get all the city name and store it in an array, but since you're a ninja developer you notice a pattern that might help to reduce the total space required to store names of all cities.

Eg: following is the list of all cities that have prefix "New" in their name.

 "New Albany"                          "New Bedford"
 "New Bern"                            "New Braunfels"
 "New Britain"                         "New Kensington"
 "New London"                          "New Madrid"
 "New Market"                          "New Martinsville"
 "New Mexico"                          "New Milford"
 "New Orleans"                         "New Paltz"
 "New Philadelphia"                    "New Rochelle"
 "New Smyrna Beach"                    "New Ulm"
 "New Windsor"                         "New York"
 "New York City"                       "New Brunswick"
 "New Castle"                          "New Glarus"
 "New Hampshire"                       "New Harmony"
 "New Haven"                           "New Hope"
 "New Iberia"                          "New Jersey"

So instead of repeating "New" everytime, how about compressing it ?

Since "New" is a common prefix, we could remove the "New" from all the words and create a data structure which automatically attaches "New" to cities mentioned above something like :
Eg: for 4 cities, it will look like :

But how about going a step even further?
Since "New Madrid", "New Market" and, "New Martinsville all have "New Ma" in common, let's compress out string even further.

By doing so for each city we reach here :

Have fun building one here

Cities that have the same common prefix are grouped together, this helps in decreasing the space.

And there's more !!!
Searching becomes a lot faster by using tries, how?

Let's simulate a search which is present in both trie and array:

Search is super fast since instead of iterating over an array, within 6 ticks we got to the result.

Search string which isn't present in trie and array:

Within 4 ticks, we could determine if the search string is present or not.

Applications :

Trie are used in many places like autocomplete feature (we shall build this in a next blog), Data Analytics, Gnome Analysis, Spell Checkers etc.

Now that we know what's trie, and why is it useful, let's build one !

Building a Trie

We shall build Trie for: ['abc','abab','babc','cab']

To be a bit more efficient we shall build Trie using Objects to leverage O(1) lookups.

Step 1

Since we're basically building a Tree, we need a root, for Trie, the root will be empty but will store information about its child objects.

class Trie{
    constructor(){
         this.root = {}
    }
}

Step 2:

Now let's iterate through each string in the array ['abc','abab','ba','cab'] and create a tree.

First is 'abc':
We check is 'a' is present in the tree, since root is empty, it's not present so add 'a' to trie, then 'b', then 'c'. Now since we've reached the end of trie, we store the word "abc" to signify that "yes", "abc" is a valid word.

We end up here :

Second "abab".
We repeat the same process, we check is "a" is present, since it is present, we won't create a new node instead go to "a" node, then we check is "b" is present, it's connected to "a" so go to "b" node, then again we check if "a" is present, since no "a" node is connected to "b", we create a new "a" node, connect it to "b" and keep on repeating the operation.

So inserting a string into a Trie boils down to 3 basic steps :

1> If the character isn't connected to node, create a new one and travese.
2> If the character is connected to node, travese it.
3> If it's the end of string, add the string to the leaf of current subtree.

Visualizing :

Let's translate it into code :

  insert(word) {
    let node = this.root;                            
    for (let c of word) {
      if (node[c] == null) node[c] = {};             //if {c} not present, create one
      node = node[c];                                // travese{c} 
    }
    node.isWord = true;                              // add word.
  }

So for each string, start from root and travese.
For each character c, check if object is created, if not then create one and travese it.
At the end we set "abc" to true signifying that, "yes, string with "abc" is possible.

So for ["abc","abab"] our actual trie will look like :

let root = {
  "a":{
    "b":{
      "c":{
        isWord:true
      },
      isWord:false,
      "a":{
        "b":{
          "isWord":true
        },
        isWord:false
      },
      isWord:false
    },
    isWord:false
  },
  isWord: false
}

console.log(root.a);
console.log(root.a.b);
console.log(root.a.b.c);
console.log(root.a.b.c.isWord);
console.log(root.a.b.a);
console.log(root.a.b.a.b);
console.log(root.a.b.a.b.isWord);
console.log(root.a.b.isWord);
console.log(root.a.b.f == null);

Now let's create a function to traverse it, which is similar to inserting:

 traverse(word) {
    let node = this.root;
    for (let c of word) {
      node = node[c];
      if (node == null) return null;
    }
    return node;
  }

For searching, we traveser the the string and in the end we check if "isWord" set to true :

  search(word) {
    const node = this.traverse(word);
    return node != null && node.isWord === true;
  }

putting it all together :

class Trie {
  constructor() {
    this.root = {};
  }

  insert(word) {
    let node = this.root;
    for (let c of word) {
      if (node[c] == null) node[c] = {};
      node = node[c];
    }
    node.isWord = true;
  }

  traverse(word) {
    let node = this.root;
    for (let c of word) {
      node = node[c];
      if (node == null) return null;
    }
    return node;
  }

  search(word) {
    const node = this.traverse(word);
    return node != null && node.isWord === true;
  }
}

I think this article is long enough, next article I will write about how to create a search autocomplete based on Trie.

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/DataStructures/Trie.js