JavaScript: Order words in string based on frequency
I came across the following code challenge in a technical interview, that allowed me to review some of the basics of JavaScript problem solving, and was also advanced enough to walk away learning something new.
Write this function: Given a string, return a new string with all words in the order of most to least frequent.
For example, the input: "this is a this a a a string" should output:"a this string is"
Phase I: Counting
Looking at this problem, the first instinct is to first count the words found in the string, we can do this in JavaScript by creating an object with the words as keys, and the number of occurrences it is found in the string as the value.
We do this by iterating through an array of words and checking if the current word exists as a key in an object if it doesn’t exist the value should be set to one, if not, increase the value by one.
We would first declare an empty object that we will build out while iterating through the words in the string:
let frequentObj = {};Iterating over the string itself would leave us iterating over the letters, we would need to create an array from the string so we can iterate over the words, doing so is straightforward:
let stringArray = string.split(' ');We can then implement the iteration described above to create an object of words and their total number of occurrences in the string:
for (let i = 0; i < stringArray.length; i++) {
let word = stringArray[i];
if (frequentObj[word]) {
frequentObj[word]++;
} else {
frequentObj[word] = 1;
}
}Another way to achieve this functionality is by using the reduce method like so:
let frequentObj = stringArray.reduce((allWords, word) => {
if (allWords[word]) {
allWords[word]++;
} else {
allWords[word] = 1;
}
return allWords;
}, {});In the above examples, bracket notation is used to check if the word exists as a key in the object since we’re using a variable in the conditional to access a property in the object. Dot notation would only work if we were using the literal key.
Phase II: Sorting
The next challenge is to figure out how to use this object to our advantage. If only there was a way to sort this object by its values from highest to lowest.
Unfortunately, there isn’t, but there is a neat trick we can work with.
Object.entries() can accept an object as an argument and will return an array of the key and values in the object as nested arrays.
let nestedKeyValues = Object.entries(frequentObj);Once we have this array we can begin seeing the solution to this problem. We now have to sort through this array using the second element in the nested array to determine its order.
let sortedNestedKeyValues = nestedKeyValues.sort((a, b)) {
if (a[1] > b[1]) {
return 1;
} else if (a[1] < b[1]) {
return -1;
} else {
return 0;
}
}The above describes the sorting in elaborate fashion, when the first element is greater than the second return 1, less than return -1, and if the same return 0.
A shorter sort method might look like this:
let sortedNestedKeyValues = array.sort((a, b) => a[1] - b[1]);Since we are comparing numbers, we can return the result of subtracting the second number from the first, which would order the array in ascending order, using the arrow function as above we don’t have to have to use the return keyword or the statement brackets because we are returning one line of code.
Phase III: Putting it together
We’re getting close, we now have a sorted nested array with the words and values, but all we need are the words from these nested arrays:
let sortedWords = sortedNestedKeyValues.map((arr) => {
return arr[0]
}Interesting! Taking a look at the output we now have an array of words sorted from least frequent to most frequent, ascending order, but the deliverable requires the opposite. We can use the reverse function to have the array display in the desired order: sortedWords.reverse()
Or, we can refactor our sort method from above to display the output in the reverse order from highest to lowest:
let sortedNestedKeyValues = nestedKeyValues.sort((a, b)) {
if (a[1] < b[1]) {
return 1;
} else if (a[1] > b[1]) {
return -1;
} else {
return 0;
}
}// alternatively:let sortedNestedKeyValues = array.sort((a, b) => b[1] - a[1]);
We have finally reached our destination with the simple transformation of the array to a string: array.join(' ');
Don’t forget to return or console.log the output and Congratulations!
Imperative vs Declarative
You will notice that this solution uses a mostly imperative programming approach, meaning it explains the logical process step by step, how the output comes to be.
A declarative approach would focus more on what needs to get done over how it gets done, returning to our initial iteration to build our object, we can have this refactored using a declarative approach:
stringArray.forEach(word => object[word] ? object[word]++ : object[word] = 1)We eliminated the logic describing the iteration that the imperative way using a for loop requires, we also use arrow function syntax and a ternary operator to handle the conditional since there only two possible options, does it exist in the object or not; thereby minimizing the code to one line.
Summary
Here’s the complete code using the imperative approach:
Here’s the same logic using the declarative paradigm:
You can also chain the methods together if you don’t mind less readable code:
Thanks for reading and Happy Coding!
