HackerRank: Contacts (the non-tries way)
If you are looking for the tries solution to this problem, click here.
I recently was on HackerRank and saw what appeared to be a simple problem where a user would be able to run a command to add a contact and then be able to type partial names and return a number of suggestions.
Ex:
add john // add contact named "john"
add joey // add contact named "joey"find jo // find contacts that have "jo"2 //return 2 as there are are two contacts that
start with "jo"
Seemed pretty simple but was rated “hard” in difficulty.
First Idea (not the solution, just an idea)
Let’s think how can we solve this problem by first examining our inputs again.
The commands always start with "add" or "find"add john //notice "add" has a length of 3find jo //notice "find" has a length of 4
In this particular scenario, since the input can only start with one of two possible inputs and is always separated by a space we can split each command and check by length.
*** this is obviously not the best way as if other commands where to be added or if a command starts with any three letters it may cause for unexpected behavior ***
"add john".split(" ") // ["add", "john"]
"add john".split(" ") // ["add", "john"]then we can do something like this
if(command[0].length == 3){ //Add}else if(command[1].length == 4){ //Find}
Now that we are able to determine whether the user may be trying to “add” or “find”. Maybe can store the data in an array and if they try to “find” we will iterate through the array and count how many elements may possibly match with what the user is looking for.
//command = ["add", "john"] || ["find", "jo"]let store = []let counter = 0if(command[0].length == 3){ store.push(command[1])}else if(command[1].length == 4){ store.forEach(contact => { if(store.includes(command[1])){ counter++ } })}
When trying this approach many tests timed out as this solution is not efficient.
Second Approach (solution)
As we needed to improve efficiency we needed to change the way the data was stored.
let store = {}
let counter = 0 If we have to constantly iterate over the entire contacts list our algorithm is always going to be inefficient. A different approach would be to store all possible contact suggestions in our store. Let’s see what this would look like.
if(command[0].length == 3){
//Add
let word = "" //create a placeholder
contact.split("").forEach(letter => { //iterate over letters
word += letter //add letter in store
if(store[word]){
store[word]++ //increment if exists
}else{
store[word] = 1 //assign if doesn't exist
}}else if(command[1].length == 4){
//Find
if(store[contact]){
console.log(store[contact])
}else{
console.log(0)
}}
So what’s happening here? We are taking the our contact name and adding them to our store letter by letter.
"john" => "j", "jo", "joh", "john"When adding the contacts we are able now able to determine the number of suggestions and our look up time is much faster now.
Solution
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]
//3 means add and 4 means find
if(splitCommand[0].length == 3){
//ADD
let word = ""
contact.split("").forEach(letter => {
word += letter
if(store[word]){
store[word]++
}else{
store[word] = 1
}
})
}else{
//FIND
if(store[contact]){
console.log(store[contact])
}else{
console.log(0)
}
}
})
}There are tons of different approaches that can be taken. If you come up with a interesting one I’d be happy to take a look at it. Thanks for reading and have a wonderful day.
