HackerRank: Contacts (the tries way)

I recently solved the HackerRank problem called Tries: Contacts without using the tries data structure. You can find a link to that blog here. After learning what the tries data structure is I modified my solution to use it.

The gist of the problem

Create an algorithm to add contacts and be able to find the number of suggestions even when typing partial.

add david                 //adds david to your contacts
add danelle               //adds danelle to your contacts
find da                   //prints 2 as the two contacts we have 
                          stored start with "da"

What is a trie data structure?

A trie data structure is used to store a dynamic set or associative array where the keys are nested and have pointers.

Solution

Enjoyed making this solution very much and will break it down further in the blog.

function check(input){
        //remove number of commands
       input.shift()
        //create store of possible searches
       let store = {}       
              
       input.forEach(command => {
        let splitCommand = command.split(" ")
        let contact = splitCommand[1]
        let instruction = splitCommand[0]       
        //3 means add and 4 means find
        
        //ref to store
        let ref = store
        let letters = contact.split("")
        if(instruction == "add"){
            //ADD               
            for(var i = 0; i < letters.length; i++){               
               if(ref[letters[i]]){
                   ref[letters[i]]["counter"]++                                       
               }else{
                   ref[letters[i]] = {"counter": 1}                                 
               } 
               //change the value of ref
               ref = ref[letters[i]]
            }
         }else if(instruction == "find"){
            //FIND          
            for(var i = 0; i < letters.length; i++){   
               ref = ref[letters[i]]
               if(!ref){                                  
                   break
               }                    
            } 
            ref ? console.log(ref["counter"]) : console.log(0)         
         }           
       })        
    }

Let’s break this problem down into pieces.

Breakdown

We will be testing with this input.

[3, "add david", "add danelle", "find da"]

Step 1

Note the first input is the total number of commands in the array. I didn’t need it so I remove the first item in the the array with “input.shift()”.

["add david", "add danelle", "find da"]

Step 2

Now that our array is cleaned up and only contains commands. We can create our store.

let store = {}

Step 3

Let’s iterate over the list of commands and split each command into pieces. We will also create a reference to our store called “ref”. More on “ref” in a bit. While it’s not necessary we have also created two variables called contact and instruction to make the intent more readable. Finally we need to split our contact into individual letters.

input.forEach(command => {
let splitCommand = command.split(" ")
        let contact = splitCommand[1]
        let instruction = splitCommand[0]
        //3 means add and 4 means find
        
        //ref to store
        let ref = store
        let letters = contact.split("")
}

Step 4

We need conditionals for our instruction in order to determine what we need to do next.

if(instruction == "add"){
//ADD               
}else if(instruction == "find"){
//FIND
}

Step 5 ADD

We need to now add our letters in our store in the appropriate nested order and keep track of how many letters we have encountered.

//ADD
for(var i = 0; i < letters.length; i++){               
  if(ref[letters[i]]){
    ref[letters[i]]["counter"]++                                       
  }else{
    ref[letters[i]] = {"counter": 1}                                 
  } 
  //change the value of ref
  ref = ref[letters[i]]
}

I want us to break this down a bit because this is where half the magic is happening. As we iterate over each letter.

["d", "a", "v", "i", "d"]

If store does not have the key we are creating a object that has a key “counter” with a value of one by setting it using “ref”. Once set we then set “ref” to that key in the object. If the store does have the key then we increment the counter using “ref” in the same way. “ref” is dynamic and is always pointing to the next in our nested object.

Our store should look like this while adding “da” from “david” .

{"d": "counter": 1, "a": {"counter": "1"}}

Step 6 FIND

Our find works very similar to our add.

//FIND
for(var i = 0; i < letters.length; i++){   
  ref = ref[letters[i]]
  if(!ref){                                  
    break
  }                    
}

We iterate over our store using “ref”. If we find the letter then we assign its reference to “ref” and if continue to assign the value will break out of the loop using break.

Step 7

ref ? console.log(ref["counter"]) : console.log(0)

If ref has a have then we print the value of it’s key “counter” else we print 0.

I creating this solution very much. If you find a different approach or would like to provide me with feedback on my solution please do so.

Thanks for reading!

Have a wonderful day!