Hey all! As I continue to search for a job in the tech world I have encountered a fair share of algorithm problems. Playing with leetcode mainly, dabbling with katawars and whatnot. It can be very frustrating to fail them or quite rewarding to accomplish them. The frustration is definitely more often occurring for me at least. The practice is extremely useful though. I have noticed some patterns in some of these algorithm solutions that pop up a lot. Now they might not be as elegant as the 1 line solution, but they work well.
The first one that I have noticed very often is the object mapping pattern. I will demonstrate with a problem that I actually had on a mock technical interview from someone who interviews people often for his company. It is a pretty simple problem and many of you might recognize it.
The problem is as follows: there is a string 'str' that has any amount of characters in it. Find the amount of occurrences of a certain letter target 't'.
This is a pretty simple problem, but it is a foundation for other problems of more complexity. For instance instead of a target letter, you might be putting just integers of the number of occurrences of each letter in an array, or maybe the algorithm wants an object that has the chars as keys and the values being their occurrences (which is exactly what we are going to build here). There are plenty of other different examples, and the more you do algorithms with a similar pattern to this, the more you recognize when you can use this pattern.
Now to get into solving it. The first thing you are going to want to do is create an empty object. This is where we are going to make key value pairs of characters and their amount of occurences. Then depending on how you like to style your code, you can either make create a var to hold the split characters or just go straight into it with a multi liner. If that didn't make sense :
Personally, since there is not that much to it, I generally do the one below. I don't see the point of making the extra variable, but to be honest I don't know if that is necessarily better or not as far as convention or time complexity. For the rest of the pictures though, I am going to use that method. Now what we need to do is form our object.
We start the forEach method which will go over each character in our now split string. The question we want to ask ourselves when making the object is whether or not the character key is already in the object or not. If the character key is not in the object we set its value to 1 because it is our first occurence of the letter. If it is already in the obj we just add one to it because we have already created a key/val pair with a val of one.
There are a couple ways to do this. I am going to be real honest with yall, I have not exactly researched the most optimal way to do this as far as complexity/efficiency. One way to do it is using in. You can say if our object key in object then do this. Or you can just straight up write the conditional -> object[key] ? : do this : do something else.
If you are not familiar with ternary logic, this is just a simple conditional. We are saying here if(obj[c]) { obj[c]++ } else { obj[c] = 1 }. Its just a bit more pretty and we can take advantage of the es6 here to one line it. And thats it! we have our object.
Ah but as you can see, we were looking for just the number of occurences of target 't'. However this object is actually better than that, and we just need to add one more line to give us the target occurence. I am sure you have already figured it out. We just need to check if there is a obj[t] and if so, return its val. Check it out.
Obviously the second part to the ternary could be null or something, but why not make it a bit more explicit so if anyone were to actually use this function it would make a bit more sense. This pattern of object mapping seems to come up all the time. For a couple months a couple buddies and I would do algorithms every day (M-F) for a couple hours and you would be surprised how often we would use object mapping to solve the problems. There are other patterns that I might write about later, but for now, thanks for reading!
Top comments (0)