Using hashes to compare strings
After Graduating from Flatiron School’s Software Engineering program I knew I would need to sharpen my Algorithm skills. My knowledge of Rails, React and SQL is not enough to get passed a technical interview since many of these test algorithmic thinking skills.
One common problem that I find is the need to compare 2 strings. Specifically, to find out if they have the same characters the same amount of times.
The Anagram Problem
lets look at the words LISTEN and SILENT. How do we know these two words have the same letters just rearranged differently? In other words, how do we find out if these two strings are Anagrams of each other?
The Brute-Force approach
The simplest way we can find anagrams is to look at the letter L on the top and see if we can find the Letter L once in the bottom and draw an arrow. Here’s the above procedure in Ruby code. This simple example assumes each letter only appears once in each word.
Above was an abbreviated version of the brute-force. The include? and index methods run in linear time because they scan the string for the character argument. Since we run both these methods in a enumerable all?, the whole algorithm runs in O(n²)
That’s not so bad right? Well actually if you gave this answer in a code review you would FAIL.
The efficient way
A much better way which runs in O(n) uses a hash table to keep score of each character and how many times it has been found in each string. I call it the “character scoring system” though it’s technically known as “histogramming” or creating a “frequency distribution”. The general idea is you loop through the first string, storing each character as a key in the hash and storing and incrementing a counter as the key’s value. This approach works in the general case where letters can appear multiple times in each word.
Since Hashing is theoretically an O(1) operation, you just decrement the score on your loop through the second string and VIOLA, hashing n characters in constant time = O(n).
Here it is in Ruby code
Give this answer at your next technical interview and you’ll be sure to pass it!
