Frequency Patterns
Tags: javascript
Published: 2020-07-19 14:56:59

Last week I had received a coding challenge from a company. Mind you, this is the furthest I've gotten in the interview process since I began my job search 5 months ago. The problem was to create a function that would return `true` or `false` if the given arguments could create a proper binary tree.

I don't know what binary trees are. I've never even heard of them. I did a quick Google search and saw a summary of what they were. I completed the problem in under an hour after I saw I passed the tests. What I didn't know, however, was there were hidden tests after I submitted my work. The company reached out the next day and told me that they would not be moving forward with me, unfortunately. 

I took this is a learning experience. I realize now that since I had gone to a coding boot camp, I probably missed a lot of useful info that someone who got a CS degree didn't. Binary trees possibly being one of them. I did more research and I deduced that I need to learn algorithms and data structures. So, today, I'm going to show you something I learned with the course I'm taking: Frequency Patterns.

Many coding challenges given to developers during interviews follow a pattern. Colt Steele, the person who made the course I'm studying, has narrowed many of them down and frequency patterns are one of the most common. The frequency problem is where you have to count the number of times something shows up. For instance, the anagram challenge. 

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once. Here are some fun anagrams examples: 'Dormitory' and 'dirty room', 'schoolmaster' and 'the classroom', and 'listen' and 'silent'.

Let's create a function that returns either `true` or `false` if two words are an anagram of each other! Note: I know you can solve this by alphabetizing both words and comparing the two, but we're trying to learn a process that applies to many more problems. I'm only using an anagram as an example because it's easy and straightforward.

```js
const anagramCheck = (str1, str2) =>

}

anagramCheck('listen', 'silent')
```

This is our starting point. We know `listen` and `silent` are anagrams of one another so this function should return `true`. We also know that a word with a length of, let's say, six characters, can never be an anagram of a word with a length of 7. The number of characters must be the same! So let's add that check:

```js
const anagramCheck = (str1, str2) =>
  if (str1.length !== str2.length) {
    // must be same length to be valid anagram
        return false;
    }
}

anagramCheck('listen', 'silent')
```

Remember, there are dozens of ways to solve the same problem. The way I'll be showing you how to solve this is by creating an empty `object` and storing the character with the number of times it occurs in the other string — key/value pairs.

If a key/value pair exists inside of our `object`, we will simply increase its occurrence by one. If it doesn't exist, we will instantiate it with the value of one. We can easily do this with a `for` loop:

```js
const anagramCheck = (str1, str2) => {
  if (str1.length !== str2.length) {
    // must be same length to be valid anagram
        return false;
    }

  // object used to store chars and number of occurences
  let lookup = {};

  for (let i = 0; i < str1.length; i++) {
    // if char exists, increase by 1
    // if char doesn't exist, set to 1
    lookup[str1[i]] ? (lookup[str1[i]] += 1) : (lookup[str1[i]] = 1);
  }

}

anagramCheck('listen', 'silent')
```

If we `console.log(lookup)` this is what we would get:

```js
{
  e: 1,
  i: 1,
  l: 1,
  n: 1,
  s: 1,
  t: 1
}
```

These characters all appear in `str1` one time only. Now we create another `for` loop that will be used to subtract characters from `str2` from our `lookup` object. If at any point there is a 0 count from a character *and* our second loop needs us to subtract 1 from it, we return `false` because it wouldn't be a valid anagram. Here's what that looks like:

```js
const anagramCheck = (str1, str2) => {
  if (str1.length !== str2.length) {
    // must be same length to be valid anagram
        return false;
    }

  // object used to store chars and number of occurences
  let lookup = {};

  for (let i = 0; i < str1.length; i++) {
    // if char exists, increase by 1
    // if char doesn't exist, set to 1
    lookup[str1[i]] ? (lookup[str1[i]] += 1) : (lookup[str1[i]] = 1);
  }

  for (let i = 0; i < str2.length; i++) {
    if (!lookup[str2[i]]) {
      // checks if char value is not 0
      return false;
    } else {
      lookup[str2[i]] -= 1;
    }
  }

  return true
}

anagramCheck('listen', 'silent')
```

The first `if` condition inside of our second loop will be `false` if the number is `0`. 0 is a falsy value so it will return `false`. If it does, our function will return false. `Else` it subtracts 1 from our character inside our object. If it passes all of this, our two words are anagrams of one another so we return `true`.

I think this is a great pattern to learn since it can be applied to many different problems. The course I'm learning from can be found [here](https://www.udemy.com/course/js-algorithms-and-data-structures-masterclass/). It's over 20 hours long and covers a lot of material that many people who graduated from a coding bootcamp probably don't know. Also, Udemy goes on sale *very* often so don't ever buy it at full price!