loading...

The Harmless Ransome Note - Challenge 1

clintdev profile image Clint Maruti ・3 min read

So here I find myself once again in my Software Engineering journey phase - The Job Hunt.

Arguably the most dreaded phase a Junior Software Engineer may find themselves in or even some Seniors out there may be one or two who find themselves having to remind themselves of some concepts of Algorithms and Time Complexity just to nail that interview.

For me, the company that I have been working for decided to downsize its employees because there were just too many and the company's financial status couldn't accommodate them. Now, mind you, the criteria they used for downsizing wasn't in any way based on the productivity of the individual. In fact, we (I was one of them) were the best and most talented. It's just that, how the company works, there weren't enough placement for devs to the available partners at the time.

Embarking on my road to finding another Software Engineer job, I will be starting a series of every algorithm I have faced and conquered. I'm starting from the basics. I am doing this so as to improve my comprehension level, with an approach to teaching what I have learned. Feynman's Technique.

In this first post, I will explain The Harmless Ransom Note Algorithm Challenge. Feel free to pinpoint few mistakes or point me to a good path. I am open to learning more and more.

A Harmless Ransom Note challenge entails comparing two strings. You have to find whether you can make up the first string with words present in the second string. In a more detailed form, Let's say you have a magazine article. You want to create a sentence from the words of the article. If there are no words in the article that can match up your sentence, then the program returns false and vice versa. Hope it makes sense.

To tackle this, we start by creating a function harmlessRansomNote that takes two arguments, a noteText and magazineText.

function harmlessRansomNote(noteText, magazineText){

}
Enter fullscreen mode Exit fullscreen mode

Next, we convert both texts into an array of words using the split method.

function harmlessRansomNote(noteText, magazineText){
   let noteArray = noteText.split(' ')
   let magazineArray = magazineText.split(' ')
}
Enter fullscreen mode Exit fullscreen mode

But wait, before we go any further, what we are doing is comparing two string against each other. But how are we going to do that? So this is how. We are going to use a hash table algorithm to accomplish this. This is going to keep track of every word and how many times its been used. We will create an empty magazine object to keep track of every word in it.

function harmlessRansomNote(noteText, magazineText){
   let noteArray = noteText.split('')
   let magazineArray = magazineText.split('')
   let magazineObj = {}
}
Enter fullscreen mode Exit fullscreen mode

The goal of this is to have every word that is present be presented like this {this: 1}. This will just show how many times this word is present in that array of words.

function harmlessRansomNote(noteText, magazineText){
   let noteArray = noteText.split('')
   let magazineArray = magazineText.split('')
   let magazineObj = {}

   magazineArray.forEach(word => {
      if(!magazineObj[word]) magazineObj[word] = 0;
         magazineObj[word]++
   }
}
Enter fullscreen mode Exit fullscreen mode

Okay, now we have each word with the frequency of its occurrence represented in our hash table.
Next, we will now compare the words in our noteArray to our magazineArray in the hash table and if the word exists, we will subtract the frequency of occurrence of the word.

function harmlessRansomNote(noteText, magazineText){
   let noteArray = noteText.split('')
   let magazineArray = magazineText.split('')
   let magazineObj = {}

   magazineArray.forEach(word => {
      if(!magazineObj[word]) magazineObj[word] = 0;
         magazineObj[word]++
   })

   noteArray.forEach(word =>{
      if(magazineObj[word]) 
         magazine[word]--
   }) 
}
Enter fullscreen mode Exit fullscreen mode

We will define a variable NoteIsPossible setting it to true. We will update this variable to false if there are no words in the magazineObj that match the word in the noteArray hence proving that it's not possible to make a note from the magazine text. I hope it's clear.

function harmlessRansomNote(noteText, magazineText){
   let noteArray = noteText.split('')
   let magazineArray = magazineText.split('')
   let magazineObj = {}

   magazineArray.forEach(word => {
      if(!magazineObj[word]) magazineObj[word] = 0;
         magazineObj[word]++
   })

   let isNotePossible = true

   noteArray.forEach(word =>{
      if(magazineObj[word]) {}
         magazineObj[word]--
      if(magazineObj[word] < 0) {
        isNotePossible = false
      }  else {
        isNotePossible = true
      }
   }) 

   console.log(isNotePossible)
}
Enter fullscreen mode Exit fullscreen mode

Using the array function indexOf(), if the word is not in the magazineArr it returns -1. So to determine if the word is not present we check if the current word is less than 0 index in the array and thus updating our isNotePossible variable.

See you in the next one,

Happy hacking!

Posted on by:

clintdev profile

Clint Maruti

@clintdev

A Machine Learning Engineer

Discussion

pic
Editor guide