Histograms

As I’ve been prepping for technical interviews and dutifully brushing up on my algorithms, I’ve been making great use of the histogram. I wanted to dedicate a blog post to my very helpful new go-to.

So, what is a histogram?

In short, a histogram is a way of displaying numerical data.

This is a rather broad definition and a histograms can take several forms. The visual representation is most commonly a bar graph as it was first conceived by Karl Pearson (https://en.wikipedia.org/wiki/Histogram).

The key is that a histogram represents the frequency of a range of values. See the simple example below:

Source: https://www.shmoop.com/basic-statistics-probability/histograms-examples.html

As you can see the values, test scores in this case, are on the X-axis and the Y-axis shows the frequencies.

In my case, I have created histograms in the form of JavaScript objects (or in some cases Ruby hashes), as a tool for checking the frequencies of values in my data.

For a more specific example, below is code I wrote for the classic Ransom Note coding interview question (https://www.hackerrank.com/challenges/ctci-ransom-note/problem). The problem asks that you evaluate two inputs — a “ransom note” and a “magazine”. It asks that you determine whether or not you can construct the note using the letters or full words contained in the magazine. I my example wrote this to check for full words since I was solving the Hackerrank challenge.

The histogram plays an integral role in my algo.

Here is my complete solution below. It would be useful to write a separate function for creating histogram, not to mention more DRY, but you can see it linearly in this way.

function ransomNote(mag,ran) {
  let magazine = mag.split(" ")
  let ransom = ran.split(" ")
  let magObj = {}
  let ranObj = {}
  let count = 0
  
  for (i=0; i<magazine.length; i++) {
    if (magObj[magazine[i]]) {
      magObj[magazine[i]] += 1
    } else {
      magObj[magazine[i]] = 1
        }
    }
    
  for (j=0; j<ransom.length; j++) {
   if (ranObj[ransom[j]]) {
     ranObj[ransom[j]] += 1
    } else {
     ranObj[ransom[j]] = 1
      }
    }
    
  for (k in ranObj) {
   if (magObj.hasOwnProperty(k) && (magObj[k] >= ranObj[k])) {
     count += ranObj[k]
    }
   }
if (count === ransom.length) {
      console.log("Yes")
  } else {
      console.log("No")
  }
    
}

First we split up the note and magazine inputs into arrays and define objects for our histograms.

let magazine = mag.split(" ")
let ransom = ran.split(" ")
let magObj = {}
let ranObj = {}

If the ransom note was “give me all your money tonight”, this would be the histogram representation of it.

{ give: 1, me: 1, all: 1, your: 1, money: 1, tonight: 1 }

Then, in this simple loop, I iterate through the ransom note to get a count for each word.

for (j=0; j<ransom.length; j++) {
   if (ranObj[ransom[j]]) {
     ranObj[ransom[j]] += 1
    } else {
     ranObj[ransom[j]] = 1
      }
    }

If I do the same and create a histogram for the contents of the magazine (magObj), I can then create a count for each word that the magazine contains enough instances of.

I solved the problem by determining if that count was equal to the length of words in the initial ransom note array.

for (k in ranObj) {
   if (magObj.hasOwnProperty(k) && (magObj[k] >= ranObj[k])) {
     count += ranObj[k]
    }
   }
if (count === ransom.length) {
      console.log("Yes")
  } else {
      console.log("No")
  }

If the magazine contained the words “give me all of your money tonight pretty please”, the function would evaluate “Yes” and you would be good to go.

And there you have it. A histogram saved the day, or in this case, helped carry out a kidnapping.