Hey guys. This is my first post here so please be gentle! As a soon to be graduating Computer Science student I figured I better brush up on my data structures & algorithms for coding interviews. I have been using HackerRank to practice, but have not notice many quality solutions & explanations in JavaScript. I would like to change that! I will try and post a solution to one of the problems as much as possible. So here goes nothing!
HashTables - Ransom Note Link!
Problem
Essentially you are given a magazine and a note that you want to create from that magazine. The magazine and the note are both arrays of strings. This basically boils down to: Are the strings in the note array present in the magazine array. (Please read the entire problem from the link above)
Things to consider
- You must take into account the frequency of the words in the magazine
- For example: magazine = ['I should really be studying for physics'] note = ['I should really really be studying for physics']
- If you simply checked if every word from the note was included in the magazine you would get Yes. However, the above note requires two 'really's and therefore the correct answer should be no.
My Solution
In my solution I utilized, you guessed it, a hash table (just a plain object in javaScript) to count the frequencies of each word in the magazine.
Enough talk here is the code!
function checkMagazine(magazine, note) {
let magDict = {};
let works = '';
//Populate magDict with words from the magWordArr
for (let i = 0; i < magazine.length; i++){
let word = magazine[i];
magDict[word] = magDict[word] ? magDict[word] + 1 : 1;
}
//Loop through the note and compare with magazine object
for (let i = 0; i < note.length; i++){
//magDict has the word needed for the note
if (!(note[i] in magDict)) {
works = 'No';
break;
} else {
//In the magDict
if (magDict[note[i]] < 1) {
works = 'No'
break;
}
//Subtract one from the number of words in dict
magDict[note[i]] = magDict[note[i]] - 1;
}
}
if (works === '') { works = 'Yes' }
console.log(works);
}
- The first thing that I did was populate magDict with all of the values from the magazine array and keep track of the frequency of the words.
For Example: ive got a lovely bunch of coconuts
{ ive: 1, got: 1, a: 1, lovely: 1, bunch: 1, of: 1, coconuts: 1 }
- I then looped through every word in the note array
- I check to see if that word is included in the magazine object. If it is not, set the "works" flag to 'No' and break the loop as there is no point in continuing the loop.
- If it is in the magazine object check that the frequency is more than 1. If not set the "works" flag to 'No' and then break the loop.
- Happy Path! It is in the magazine object and the frequency is greater than 1. We are going to "use" this word so therefore we want to subtract one from the frequency.
- Finally we are checking if the 'works' flag is still an empty string and if it is changing it to Yes.
Final Thoughts
This is just my solution. This problem could be solved so many different ways. If you solve it yourself leave it in the comments so we can all learn. Also, please feel free to leave your feedback on my solution!
Top comments (2)
function checkMagazine(magazine, note) {
let result = 'Yes';
for (let i = 0; i < note.length; i++) {
const index = magazine.indexOf(note[i]);
if (index === -1) {
result = 'No';
break;
} else {
magazine.splice(index, 1);
}
}
console.log(result);
}
func checkMagazine(magazine: [String], note: [String]) -> Void {
// Write your code here
var isInclude:[Bool] = []
var _magazine: [String] = magazine
}