DEV Community

loading...

Frequency Patterns

2spacemilk profile image Mark Harless ・4 min read

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.

const anagramCheck = (str1, str2) =>

}

anagramCheck('listen', 'silent')
Enter fullscreen mode Exit fullscreen mode

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:

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

anagramCheck('listen', 'silent')
Enter fullscreen mode Exit fullscreen mode

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:

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')
Enter fullscreen mode Exit fullscreen mode

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

{
  e: 1,
  i: 1,
  l: 1,
  n: 1,
  s: 1,
  t: 1
}
Enter fullscreen mode Exit fullscreen mode

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:

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')
Enter fullscreen mode Exit fullscreen mode

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. 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!

Discussion

pic
Editor guide