Design Trie. Solving an Uber Interview Question
Tags: computerscience, javascript, tutorial, career
Published: 2020-05-31 02:57:01

I came across <a href="https://dev.to/abahgat/the-programming-puzzle-that-landed-me-a-job-at-google-1pc0">this</a> 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, 

<h2>What are Trie ? </h2>

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

<h2> How are they used ? </h2>
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 <strong> "New" </strong> in their name.
```javascript  
 "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 <strong>"New"</strong> everytime, how about compressing it ? 

Since "New" is a common prefix, we could remove the <strong>"New"</strong> 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 : 
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/trhmanh8a76q2otz6znu.png)

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 :  
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/c0mifv4qv9wx1010giio.PNG)

<small> Have fun building one <a href="https://www.cs.usfca.edu/~galles/visualization/Trie.html" >here</a>

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:
<img src="https://media.giphy.com/media/XdE6rx9QmGYW9WMzpn/source.gif" />
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:
<img src="https://media.giphy.com/media/L0qVJQvjPpRZe3vz3q/source.gif" />
Within 4 ticks, we could determine if the search string is present or not.

<h4>Applications : </h4>
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 !

<h2>Building a Trie</h2>

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. 

<h3>Step 1</h3> 
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.

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

<h3>Step 2:</h3>

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 : ![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/eyn2df1jzh5gkyr3nk6z.png)


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 : 
  
<img src="https://media.giphy.com/media/kDkXGnyNmekIDpQVeo/source.gif" />

Let's translate it into code : 
```javascript
  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 : 
```javascript
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: 

```javascript
 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 : 

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

putting it all together : 
```javascript 
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