DEV Community: Sean Welsh Brown

Installing MongoDB on Windows Subsystem for Linux (WSL) 2

Sean Welsh Brown — Thu, 12 Nov 2020 01:43:17 +0000

MongoDB is one of the most popular databases for modern Web Development, especially for those using JavaScript and JSON in their applications. It fits well into the MERN Stack structure, and provides dynamic and scalable performance across the board.

Windows Subsystem for Linux, or WSL is a service provided to developers that allows a Windows 10 user to have a full Linux kernel installed and running in a virtual machine under the hood, allowing for access to a complete Unix filesystem and command line while continuing to use Windows GUI apps.

While WSL provides a potentially fantastic service for developers (I use it extensively, myself), its nature of being a bit more of an experimental feature can sometimes leave documentation for specific tasks a bit hard to find. It's a Linux terminal, yes, but one running with specific concessions that occasionally make installing applications not as simple as the "Ubuntu installation instructions" might make them seem when you're Googling for a solution.

I'm writing this blog post because I specifically had a little trouble getting MongoDB installed and running on my WSL 2 installation, and wanted to put something out there to help others who might be trying to do the same thing.

Let's get started!

Installing MongoDB

First off, I'm going to assume that you're using Ubuntu as your WSL installation of choice. This is the most popular and commonly used Linux distro, and the one that I have experience with.

My examples will also be using Windows Terminal for my command line interaction, which I highly recommend for WSL. It's lightweight and customizable, and fits great with the workflow.

Step 1.) Update Ubuntu packages

This is just to make sure everything is up to date in your WSL installation. Run sudo apt update in your terminal, enter your Ubuntu password, and let the process finish.

Step 2.) Install MongoDB on the command line

Install the current working package version of MongoDB by typing the following into your terminal:

sudo apt-get install mongodb

Type Y to confirm when prompted, and a big installation process will take place.

Step 3.) Get familiar with MongoDB services

Once the installation is complete, you should now have access to two services on your command line:

mongod
mongo

mongod starts your local database server and runs it on the default port (27017), and mongo runs the MongoDB shell-- allowing you to connect with the database and interact with it manually.

Step 4.) Set up your local database

Now here's the tricky part, where the WSL version of MongoDB gets a little bit funky.

Normally, MongoDB's default directory for the database is /data/db. However, if you run the mongod command to start the server, you'll likely be hit with this error:

MongoDB hasn't created the folder for its database properly, so we're going to have to do it ourselves!

Important to note, for those new to Linux or Unix in general, your default starting place when you open up a new terminal window is ~, which is your home directory. Any new folders or files you create there will show up as ~/code or ~/pictures, etc. This is different from the root directory, which is the actual core of your Linux installation. This is represented by a simple /, and that's the directory where MongoDB is looking for its folders.

This is a small distinction, ~/ versus /, but it makes all the difference in Unix.

To see this in the GUI, this is where the home folder lives in your WSL file structure:

Whereas the root directory lives here:

And this is where we'll need to put the /data/db folder structure.

Step 5.) Creating the folders and permissions

Thankfully the solution is easy, once you know what to do!

Type cd / into your terminal to navigate to your root directory, and type sudo mkdir -p data/db. The -p creates the parent folder(s) as well, if they don't already exist.

The folder now exists in your root directory! But we're not quite done. If you try to run mongod now, you'll hit a new error:

This is because while we've created the folder, we now have to give it administrative write privileges, so that MongoDB can put its data there.

To do this, type sudo chown -R `id -un` data/db. This will recursively give the proper permission to those folders.

Now, type mongod again to start the server, and you're done!

The final line in the terminal should be something like "Waiting for connections on port 27017". Your server is now officially running!

Test it out by running the MongoDB shell with mongo in a separate terminal tab, with the server still running:

If you see the > character at the end, congratulations! You're now officially inside of the MongoDB shell and can interact with your local database.

I'll end the post here, since this was just a tutorial to get MongoDB installed and running properly, and another post on the functionality of Mongo would be a whole lot longer. I encourage you to take a look at their documentation and experiment with what they have to offer-- it's an incredible service, and a lot of fun to use!

I hope this was helpful to other WSL devs out there, and thanks for reading! 😄

Using stopPropagation() to Stop Event Bubbling in JavaScript

Sean Welsh Brown — Thu, 05 Nov 2020 00:57:52 +0000

Events in JavaScript are one of the core features of the language that have given us the modern, reactive internet that we know and love today. They allow us to bring HTML elements to "life", so to speak, letting them listen and observe a user's interaction and respond by firing off a piece of code that has a dynamic effect on the page.

A few examples of commonly used event listeners include onclick, onmouseover, onchange, and many others. These all allow a developer to set an HTML element to "listen" for user interactions, and then carry out a function of block of logic that the developer has defined elsewhere (or inline.) Events don't just stop with these more straightforward examples, of course. Many of JavaScript's in-built window manipulations are built on top of complex events, and would take up an entire blog post on their own!

Today, we're mostly interested in one particular feature of events, and how to control it: Event Bubbling.

What is Event Bubbling?

Let's first set up an example to visualize what Event Bubbling is, and what it does. Imagine you've hypothetically created a web page featuring several nested elements, each of which has an onclick event listener attached to it with a different effect:

<div onclick="alert('I'm a div!')">
  <div onclick="alert('I'm a nested div!')">
    <h1 onclick="alert('I'm an h1 tag!')">
      Hello
    </h1>
  </div>
</div>

Now, let's say this is rendered to the page, and you decide to click on the h1 tag. What do you think will happen?

First, the alert for the h1 tag will pop up. Then, when you close out of that, the alert for the nested div will pop up! And last but not least, the outer div's alert will pop up as well. Why did this happen if you only clicked on the most nested element?

This happens because of Event Bubbling, a feature of JavaScript that causes every action or interaction on a page to "bubble up" through its enclosing elements until it reaches the root of the page, applying that same action to any other event listeners along the way.

Event bubbling happens on almost every event in JavaScript, and is an intentional and desired feature of the language for many reasons. Oftentimes it won't even rise to the attention of a developer or user. However, what if there was a specific occasion where we didn't want an event to bubble up?

Why wouldn't I want events to bubble?

Let's say that you've created an application that features cards displaying relevant information to a user. On each card, you've added an event listener for an onclick effect that will flip the card over and display more information.

In addition, you've added a button that will delete the card from the page (for whatever reason), prompting the user for a confirmation before doing so, which is a key feature that you don't want to compromise on.

Let's take a look at it in (very) simplified code:

<div class="card" onclick="(Flip-over function)">
  <p>(Information)</p>
  <button onclick="(Close function)">X</button>
</div>

This would all work fine, except for the fact that if you click the "X" button to close the card, the confirmation would pop up but the card would also flip over. This might not be a huge issue, but it might not make sense to how you've designed the card; maybe you haven't included an "x" button on the back of the card, or you think it just looks a bit sloppy.

This is exactly the kind of situation in which you might want to stop the event bubbling that's causing both onclick events to fire off sequentially.

How do we stop Event Bubbling?

Thankfully, the answer is quite simple! We use a method of the Event interface called stopPropagation().

Essentially, stopPropagation() does what the name describes: it stops the propagation of a bubbling event from going further up the tree of elements that it's occurring in.

(It's important to note that stopPropagation() doesn't stop the default action of an element from occurring. In order to do that, you would need a separate method called preventDefault().)

Let's apply this to our example code and see how we might stop the onclick event from propagating. Since we still want the button element to carry out its effect and stop there, we can wrap it in an inline element like span and use stopPropagation() on that to act as a closed door around it:

<div class="card" onclick="(Flip-over function)">
  <p>(Information)</p>
  <span onclick="event.stopPropagation()">
    <button onclick="(Close function)">X</button>
  </span>
</div>

And that's all there is to it! You would now be able to click the button and have its effect fire off without reaching the parent div, keeping both actions separated.

It's worth noting that the same method can be used in other JavaScript libraries and Frameworks like React. Here's the same example using JSX syntax:

<div className="card" onClick={"(Flip-over function)"}>
  <p>(Information)</p>
  <span onClick={e => e.stopPropagation()}>
    <button onClick={"(Close function)"}>X</button>
  </span>
</div>

There's plenty more to learn about Events, Event Bubbling and methods like stopPropagation(), so I encourage you to dive deeper and find more tools to improve your development! This is a relatively simplistic tutorial on a very complex aspect of JavaScript, and there's always more to learn. 😄

Thanks for reading!

How to Determine if a String is a Palindrome (in JavaScript)

Sean Welsh Brown — Wed, 28 Oct 2020 19:09:26 +0000

When it comes to solving problems in an interview setting as a software engineer, few topics come up quite as often as string manipulation. And when it comes to string manipulation, few specific concepts come up as frequently as Palindromes.

What is a Palindrome?

For those who might not know, a Palindrome according to the wikipedia page on the subject is defined as:

...a word, number, phrase, or other sequence of characters which reads the same backward as forward.

Some examples of palindromes in real words are:

racecar
madam
kayak
noon

Though in the context of programming, a palindrome need not even be a real word (or even made up of letters.) Some examples of this type might be:

asdfgfdsa
wrcmmcrw
54645
!020!

And so on.

Why does this come up in technical interviews?

As you'll see when we write our code, palindromes are a very fundamental algorithmic practice topic because they involve multiple concepts that engineers use regularly on the job, such as:

Being able to traverse through and/or manipulate a string.
Knowing how to set multiple pointers and use/move them within a repeating loop.
Understanding how to take something that's simple for a human being to do (see if a word is a palindrome) and explain that to a computer in a set of repeatable instructions.

That last one in particular is a core fundamental of problem solving in computer science. Oftentimes the easiest things for us to do as humans are the hardest things to represent simply and efficiently in code.

How do we implement it in code?

I'm glad you asked!

In the example we'll be going over here, we're going to implement a simple algorithm that will detect if a given string is (or is not) a palindrome. While this may seem like a simple task, understanding it well can give you an advantage when harder palindromic questions are asked in interviews, or when they come up in your own practice.

Think of this solution as more of a building block, or a tool that you'll have in your toolbox to use on more difficult questions, rather than the end of all discussions on palindromes in code.

Let's get down to it!

Step 1: Understand how to solve the problem

Before we code, we should first think through how we might solve this.

When we look at a word or a series of characters as humans, we recognize something as a palindrome by reading through the word up until we hit the "middle" of the word, then see that the second half of the word contains the same letters or characters as the first half.

Think of it like climbing a hill up to the top, and then noticing that the other side of the hill looks exactly the same on the way down.

Trying to do it this way in an algorithm might work if we kept track of the letters we've seen as we step through the string, but we'll realize quickly that there isn't as simple a way to tell the computer what the "middle" of the string is, conceptually, and we'll also need to use extra space to store the first part of the string that we saved on the way there.

An easier way is to think back to that "hill" analogy I mentioned; if both sides of the string are the same on the way up and down, then couldn't we start at both the beginning and the end of the string and work our way to the middle at the same time?

Yes we could! And that's precisely what we'll do in our code.

Step 2: Code it!

Let's start by declaring our function, giving it a name and a parameter for a string to be passed in as an argument:

function isPalindrome(string) {

}

Now, let's create two pointers that we'll use to traverse the string. One will start at the beginning of the string, and the other will start at the end.

We'll name these left and right, but they could be anything you'd like:

function isPalindrome(string) {
  let left = 0;
  let right = string.length - 1;
}

In an example string, these two pointers would start in the following locations:

" racecar "
  ^     ^
 left  right

Now, let's write the loop that we'll do all of our logic inside of. We'll use a while loop here, since we want the loop to continue perpetually until its end-case is met, when we reach the "middle" of the string:

function isPalindrome(string) {
  let left = 0;
  let right = string.length - 1;

  while (left <= right) {

  }
}

This works because we know that if left ever becomes greater than right, that means we've passed the middle of the string and we shouldn't be continuing our loop.

Now we'll implement our core bit of logic, and the incrementing/decrementing of our pointers to traverse the string:

function isPalindrome(string) {
  let left = 0;
  let right = string.length - 1;

  while (left <= right) {
    if (string[left] !== string[right]) return false;
    left++;
    right--;
  }
}

What we're doing here is using a comparison operator to check if the character on the left does not match the character on the right. If this is the case, we know that the string can't be a palindrome, and we immediately return false as our function's output.

If the characters do match, we know we should continue to traverse the string, and we increment the left pointer and decrement the right pointer respectively.

Now, all that's left to do is put in our other return value, if the string is a palindrome:

function isPalindrome(string) {
  let left = 0;
  let right = string.length - 1;

  while (left <= right) {
    if (string[left] !== string[right]) return false;
    left++;
    right--;
  }

return true;
}

The true return value is outside of the while loop, because if we complete the loop without ever returning a false value, that means we've confirmed the string to be a palindrome.

And we're done, woohoo!

If you've read this far, I hope this little tutorial helped in understanding this fundamental bit of algorithmic logic.

While this solution may be very simple, it's important to keep in mind for more complex problems and algorithms where you may need to expand on it, or use it nested further within a greater problem. I can guarantee you that it will show up in your studies or assessments at some point, in some form!

Thanks so much for reading, and happy coding. 😄

Implementing a Bubble Sort Algorithm in JavaScript

Sean Welsh Brown — Wed, 21 Oct 2020 22:22:06 +0000

Welcome to the third entry in my Sorting Algorithms in JS series here on Dev! I've previously covered both Selection Sort and Insertion Sort in previous posts, so check those out if you'd like to learn more about sorting algorithms in JS.

Intro

In computer science, few tools are used quite as often as sorting algorithms. We rely on them every day as programmers and engineers to sift through data, and they're built into nearly every modern programming language in one way or another.

While using a language's built-in sorting functions may get the job done for most day-to-day work, it's important to understand what's going on under the hood, and what different sorting algorithms are actually doing and why they work the way they do. While it may not come up often, there's always the chance you may be asked to implement or explain a sorting algorithm in a technical interview setting, which is exactly what this post is here to prepare you for!

Today, we'll be looking at Bubble Sort, another one of the main sorting algorithms in Computer Science.

What is Bubble Sort?

The Wikipedia page on Bubble Sort describes the algorithm as follows:

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

The algorithm, which is a comparison sort, is named for the way smaller or larger elements "bubble" to the top of the list.

From the standpoint of an educational tool, Bubble Sort is actually one of the simplest sorting algorithms to comprehend and implement. Unfortunately it's also one of the least efficient, and is almost never used in practical programming applications.

Essentially, the algorithm iterates over an array multiple times (or once, in the edge case of an array already being sorted), comparing each element to the element to the right of it and swapping them so that the greater element is to the right. This essentially "bubbles up" the greatest value to the end of the array each time the iterative loop runs, slowly but surely putting the values in their proper sorted positions.

Here's a helpful visual representation of what happens while the algorithm is running:

As you can see, each iteration swaps greater values to the right multiple times until the greatest value in the array is found, which will then be swapped all the way to the end. Simple, but it gets the job done!

How efficient is it?

Unfortunately, "getting the job done" isn't the only requirement for a sorting algorithm. As I mentioned before, Bubble Sort is notoriously slow and inefficient, relegating it to being mostly used as an educational tool rather than a practical one. Other sorting algorithms like Quick Sort, Heap Sort, or Merge Sort should always be used instead for most practical purposes.

One advantage that Bubble Sort has over other sorting algorithms is that its core logic has a built-in check to see if an array is already sorted, resulting in an O(n) runtime if a sorted array is passed in, since only one iteration through the array will be required. However, this could be considered an edge "best case" rather than a norm, and while other algorithms might take longer to check for an already sorted array, the overall inefficiency of Bubble Sort still loses out.

Bubble Sort has a worst case and average case runtime complexity of O(n^2), and a space complexity of O(n).

How do we implement it?

Now that I've successfully sold you on Bubble Sort (or made you want to steer clear of it forever), let's get down to implementing it in code!

The final JavaScript code will look like this:

function bubbleSort(array) {
  let isSorted = false;
  while (!isSorted) {
    isSorted = true;
    for (let i = 0; i < array.length - 1; i++) {
      if (array[i] > array[i + 1]) {
        [array[i], array[i + 1]] = [array[i + 1], array[i]];
        isSorted = false;
      }
    }
  }
  return array;
}

Let's break it down into pieces.

First off, let's declare the function and our return value (the sorted array, modified in-place):

function bubbleSort(array) {

return array;
}

Next, we'll declare a very important variable, isSorted, and set it to a false boolean value:

function bubbleSort(array) {
  let isSorted = false;

  return array;
}

Now this might seem strange, since we don't know if the passed in array is sorted or not, but it'll quickly make sense. Essentially what we're doing is setting the value to false to start, and using that as a way to escape from the while loop that we'll be putting all of our logic inside of, like so:

function bubbleSort(array) {
  let isSorted = false;
  while (!isSorted) {
    isSorted = true;

  }
return array;
}

As you can see, the while loop is set to continue running as long as !isSorted returns true-- aka as long as isSorted === false.

Every time the loop begins we set the value to true, which will stop the loop from running. How does this help us? Well, in our next step of logic, we'll iterate through the array and set isSorted back to false if we perform any swaps. This means that as long as there is at least one swap performed, the loop will continue running. Finally, on the last iteration through the sorted array, the isSorted value will remain true, and the while loop will end.

Sound a little confusing? Let's see it in code:

function bubbleSort(array) {
  let isSorted = false;
  while (!isSorted) {
    isSorted = true;
    for (let i = 0; i < array.length - 1; i++) {
      if (array[i] > array[i + 1]) {
        [array[i], array[i + 1]] = [array[i + 1], array[i]];
        isSorted = false;
      }
    }
  }
return array;
}

Let's focus in on the section we just added:

for (let i = 0; i < array.length - 1; i++) {
  if (array[i] > array[i + 1]) {
    [array[i], array[i + 1]] = [array[i + 1], array[i]];
    isSorted = false;
  }
}

This for loop iterates through the array up until 1 value before the end (array.length - 1), and compares every element's value to the element directly to the right of it (i + 1.)

If you remember the original description and visualization of the algorithm from earlier, this is the part where we now swap values and "bubble up" elements of the array. In this tutorial we're using JavaScript ES6+ syntax to swap elements using the [a, b] = [b, a] format.

If the value on the left is greater than the value to its right, we swap the two elements and set isSorted to false, since we know that the array isn't fully sorted on this loop through the array.

Now we put it all back together again for the finished algorithm:

function bubbleSort(array) {
  let isSorted = false;
  while (!isSorted) {
    isSorted = true;
    for (let i = 0; i < array.length - 1; i++) {
      if (array[i] > array[i + 1]) {
        [array[i], array[i + 1]] = [array[i + 1], array[i]];
        isSorted = false;
      }
    }
  }
return array;
}

And we're done!

Let's walk through the logic one more time.

We initialize isSorted to false.
Our while loop runs perpetually until isSorted is equal to true, in which case it stops.
Every time the while loop begins, isSorted is set to true, so that if no swaps are performed in the for loop the while loop will end.
In our for loop, we iterate through the entire array and compare values. If a value is greater than its neighbor to the right, we swap the two and proceed (and set isSorted to false.)
We repeat the while loop, iterating through the array multiple times until it's completely sorted, and then return the sorted array.

I recommend looking at this handy visualization again to help lock in the logic:

If you've come this far, thanks so much for reading! I hope this was a helpful tutorial to anyone learning about sorting algorithms, JavaScript, or programming fundamentals in general. 😄

I'll continue working through more sorting algorithms in future posts, so stay tuned!

Implementing a Selection Sort Algorithm in JavaScript

Sean Welsh Brown — Thu, 15 Oct 2020 00:00:14 +0000

Welcome to another entry in my Sorting Algorithms in JS series here on Dev! I've previously covered Insertion Sort in last week's post, so check that out if you're interested.

Intro

Today, we'll be looking at Selection Sort, another one of the fundamental sorting algorithms in Computer Science.

What is Selection Sort?

The Wikipedia Page of Selection Sort describes the algorithm like so:

Selection sort is an in-place comparison sorting algorithm.
...
The algorithm divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items that occupy the rest of the list.

Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

This might be a bit confusing without a visualization, so here's an animation to help put it all into perspective (I recommend watching it a few times to get a grasp on what's happening):

As we traverse through the array in an initial loop, we push forward through the array with a second pointer in a nested loop at the same time, comparing each value to the starting value (beginning with our first loop's initial index.) If we find a lower value, we set that new value as our new lowest value to be compared against, and continue pushing.

By doing this, we ensure that each time we traverse through the array we will always find the next lowest value. When we reach the end of our second loop, we swap the lowest value with our very first initial index's value, and proceed to the next step.

This could also be done in reverse order, by searching for the largest values, if we were interested in sorting from highest to lowest. It's your choice!

How efficient is it?

Selection Sort, while relatively simple to comprehend and implement, unfortunately lags behind other sorting algorithms like Quick Sort, Heap Sort, and Merge Sort for larger data sets.

However, since Selection Sort functions in-place and requires no auxiliary memory, it does have a space advantage over some other more complicated algorithms.

Generally speaking, Insertion Sort is likely to be a more performant alternative, although Selection Sort is still important to know and understand as a programmer and computer scientist.

Selection Sort has a best case, worst case, and average case runtime complexity of O(n^2), meaning it will always be quadratic in nature.

How do we implement it?

Here's where the fun starts!

Since we're implementing Insertion Sort in JavaScript, we'll be making use of modern ES6+ syntax to handle swapping elements in the array, which will help keep the number of lines of code that we need to write down.

Here's what the final algorithm will look like:

function selectionSort(array) {
  for (let i = 0; i < array.length - 1; i++) {

    let minIndex = i;
    for (let j = i + 1; j < array.length; j++) {
      if (array[j] < array[minIndex]) {
        minIndex = j;
      }     
    }
    [array[i], array[minIndex]] = [array[minIndex], array[i]];
  }
  return array;
}

Let's break this down step by step.

First off, let's declare our function, its return value (the sorted array), and the initial loop in which we'll be doing all of our logic:

function selectionSort(array) {
  for (let i = 0; i < array.length - 1; i++) {

  }
  return array;
}

You might be wondering why we're telling our loop to stop at array.length - 1 rather than the normal array.length. This is because in the next loop, we'll start by comparing i against its neighbor i + 1 in the array. This means we'll need to stop our initial loop one index short of the full array length.

Next we'll declare the variable that will hold the index of our current smallest element, minIndex, and the second loop that will do our comparison work:

function selectionSort(array) {
  for (let i = 0; i < array.length - 1; i++) {

    let minIndex = i;
    for (let j = i + 1; j < array.length; j++) {

    }

  }
  return array;
}

As you can see, this loop starts at i + 1, assigning that value to the pointer j. The minIndex variable is only set to i as a temporary measure, since it will likely be changed within this loop. However, there is the chance that i will in fact be the next smallest value in the unsorted section of the array and will simply stay where it is.

Last but not least, we'll add in the core comparison logic within our nested loop, as well as the ES6 swap that exchanges the two values once the loop completes:

function selectionSort(array) {
  for (let i = 0; i < array.length - 1; i++) {

    let minIndex = i;
    for (let j = i + 1; j < array.length; j++) {
      if (array[j] < array[minIndex]) {
        minIndex = j;
      }     
    }
    [array[i], array[minIndex]] = [array[minIndex], array[i]];
  }
  return array;
}

As we went over back at the top of this tutorial, the core of Selection Sort is the idea of selecting the next lowest value and keeping track of it until we hit the end of the array, then swapping it with the right boundary of the sorted section of the array (our initial i index.)

We do this here by evaluating if array[j] < array[minIndex]. If it is, this means that j should be swapped to the end of our sorted section (unless an even lower value is found.) We do this by setting minIndex = j.

After this loop completes, we will have found the next lowest value in the unsorted section of the array, and will swap it into its proper place using ES6 [a, b] = [b, a] syntax.

And that's it! We've successfully implemented a Selection Sort algorithm in JavaScript. Woohoo!

At this point it's worth revisiting the animation from earlier, that gives a visual representation of everything we just did in code:

If you've come this far, thanks so much for reading! I hope this was a helpful tutorial to anyone learning about sorting algorithms, JavaScript, or programming fundamentals in general.

I'll continue working through more sorting algorithms in future posts, so stay tuned!

Implementing an Insertion Sort Algorithm in JavaScript

Sean Welsh Brown — Wed, 07 Oct 2020 22:27:12 +0000

Today, we'll be looking at Insertion Sort, one of the fundamental sorting algorithms in Computer Science.

What is Insertion Sort?

As the Wikipedia page of the algorithm describes:

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. ... Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

Sorting is typically done in-place, by iterating up the array, growing the sorted list behind it. At each array-position, it checks the value there against the largest value in the sorted list (which happens to be next to it, in the previous array-position checked). If larger, it leaves the element in place and moves to the next. If smaller, it finds the correct position within the sorted list, shifts all the larger values up to make a space, and inserts into that correct position.

This might sound a bit confusing, but here's a helpful visualization of what the algorithm will be doing with data:

As we move through an array of integers, each value will be compared one at a time to the previous integers that come before it, swapping places with each one until it has eventually been inserted into its proper place.

We wind up with two sub arrays as we work through the data, with the left side being sorted and the right side remaining unsorted.

How efficient is it?

Unfortunately Insertion Sort is less efficient in large data sets than more advanced algorithms like Quick Sort, Heap Sort, or Merge Sort, although it does have certain advantages.

Simple to implement, programmatically.
Efficient for small data sets.
Adaptively efficient for data sets that are already mostly sorted.
Functions in-place, taking only constant O(1) space.

The worst case and average case time complexity of Insertion Sort are both O(n2) (quadratic.)

How do we implement it?

Now we're getting to the good part!

Here's what the final algorithm will look like:

function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {
    let j = i;
    while (j > 0 && array[j] < array[j - 1]) {
      [array[j - 1], array[j]] = [array[j], array[j - 1]];
      j--;
    }
  }
return array;
}

Now, let's break it down step by step.

First off, let's declare our function, its return value (the modified array), and the main for loop in which we'll be doing all of our logic:

function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {

  }
return array;
}

We're writing this as a pretty predictable for loop that simply iterates through our entire array. The difference here is that we'll be starting at index 1 instead of the usual 0. This is because we're always going to compare each element to at least the one that comes before it to see if a swap is necessary. Since the 0th element doesn't have a previous one to compare to, we skip it and start at 1.

Next, we establish a second pointer for our traversal through the array, j:

function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {
    let j = i;
  }
return array;
}

Pointer j is set to the value of i, because as we traverse forward through the array in our for loop, we'll also implement a second while loop in a moment that traverses backward to compare it to each value in the already sorted sub array.

That while loop, and the final step of our algorithm, looks like this:

function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {
    let j = i;
    while (j > 0 && array[j] < array[j - 1]) {
      [array[j - 1], array[j]] = [array[j], array[j - 1]];
      j--;
    }
  }
return array;
}

This is a lot of new code, so let's work through what all 3 lines of it do.

We implement a while loop that will fire off while j is greater than 0 (meaning it hasn't reached the beginning of the array) AND while the value of array[j] is less than array[j - 1]. These two conditions will allow the loop to traverse all the way down the array, swapping values until the starting element has been inserted into its proper place (the element before it being of lesser value.)
We use JavaScript ES6 syntax to swap each element with the element that comes before it, moving the starting element down the array one step at a time.
We decrement the value of j, so that on our next loop we're still swapping the same element that we started with further down.

And that's it! We've now successfuly implemented an Insertion Sort algorithm in JavaScript. Hooray!

This is all a lot to visualize and wrap your head around, so I encourage you to think about the loops and pointers to get a real sense of what's happening-- once it clicks you'll have it locked in for good. I'll re-paste this helpful animation here as well, since I think it helps a lot to visualize what's being done:

If you've come this far, thanks so much for reading! I hope this was a helpful tutorial to anyone learning about sorting algorithms, JavaScript, or programming fundamentals in general.

I'll continue working through more sorting algorithms in future posts, so stay tuned!

Using the "in" Operator in JavaScript

Sean Welsh Brown — Wed, 30 Sep 2020 21:39:56 +0000

In this short tutorial, we'll be going over the "in" operator in JavaScript— what it is, what it does, and how you can implement it in your own JavaScript code.

Ready? Let's get started!

What is an "in" operator, anyway?

I'm glad you asked. In JavaScript, the "in" operator is an inbuilt operator that is used to check whether a property exists in an Object.

When used in an expression, the "in" operator will return a boolean value; true if the property was found in the Object, false if not.

The "in" operator can also be used on an Array, since Arrays are technically Objects in JavaScript. The difference here is that the "in" operator can only be used to find out if a certain index is within an Array, since the values in an array are not properties of the array.

This might sound a little confusing, so let's see it in action.

How do I use the "in" operator?

The syntax is quite simple. The "in" operator has two parameters:

prop (the string or symbol that represents a property name or Array index.)
object (the Object within which you'll be checking to see if it contains the prop.)

In code, it looks like this:

prop in object

With some context:

let obj = { prop1: 1, prop2: 2, prop3: 3 };

"prop1" in obj;
//=> true

"prop2" in obj;
//=> true

"prop5" in obj;
//=> false

As we can see, the first two props are keys in (and thus properties of) the obj Object and return a true boolean, while "prop5" is not a key or property and thus returns false.

Keys in an Object count as properties, since they can be called on the Object directly like so:

let obj = { prop1: 1, prop2: 2, prop3: 3 };

obj.prop1;
//=> 1

obj["prop1"];
//=> 1

This is why the "in" operator can't be used to check for elements/values in an Array, while it can be used to check for properties of the Array Object, like indices or the length property:

let arr = [1, 2, 3, 4, 5];

// These operators check for Array indices, not values:
0 in arr;
//=> true
2 in arr;
//=> true
5 in arr;
//=> false

// This operator checks for a property of the Array Object:
"length" in arr;
//=> true
//=> This returns true because arr.length is a property

How could I use this in a real program?

The "in" operator is mainly helpful for writing readable, human-friendly code when you need to check for the existence of a property or key in an Object.

Let's say that there's a slice of an existing function that checks to see if a key exists in an Object within a for loop, doing one bit of logic if it does, and another bit of logic if it doesn't.

This example doesn't have much context, but bear with me:

let agesOfUsers = {
  18: ["Adam", "Jess"],
  21: ["Mike", "Alex"],
  24: ["Tom"]
};

function getNamesForAge(age) {
  if (age in agesOfUsers) {
    agesOfUsers[age].forEach( user => console.log(user) );
  } else {
    console.log(`No users of age ${age} on record.`);
  }
}

getNamesForAge(18);
//=> Adam
//=> Jess

getNamesForAge(30);
//=> No users of age 30 on record.

For the record, the if statement could also be written like so:

if (!!agesOfUsers[18]) {
  // logic
}

However, there is a great deal of subjective value on making code more human-friendly and readable, especially in a shared codebase. Hence why using the "in" operator is a great option to have!

If you've come this far, thanks so much for reading! I hope this post has been helpful or educational in your JavaScript journey. :)

I'll continue to write tutorials and breakdowns for concepts as I learn them myself, so stay tuned for more in the future!

Implementing a Basic Binary Search Tree in JavaScript

Sean Welsh Brown — Thu, 24 Sep 2020 01:42:59 +0000

When it comes to Data Structures, few are preceded by as much of a reputation as the Binary Search Tree.

While it may not come up quite so often on the job, understanding how a BST functions and how it's built are important fundamentals to understand for technical interviews, and for understanding some deeper aspects of recursion.

What is a Binary Search Tree?

A Binary Search Tree is a variation of a regular Binary Tree, a data structure in which each node has at most two children. What differentiates a Binary Search Tree from a regular Binary Tree is that the value of each left node is less than its parent, while the value of each right node is greater than its parent.

Here's a visualized example:

        10
      /    \
     8     12
    / \   /  \
   4   9 11  15

As you can see, this is a valid Binary Search Tree, because it fulfills the rule of lesser and greater values in the proper positions.

How do we build one?

I'm glad you asked! Let's go through the steps together to build one out in modern JavaScript.

We're going to be building our BST using ES6 Class syntax, and it can actually all be done within one class!

Let's declare it first, and build out our constructor at the same time:

class Node {
  constructor(data) {
   this.data = data;
   this.left = null;
   this.right = null;
  }
}

What we've put into the constructor is everything we need for the actual data of each node in the tree. The node has its own data, passed in as an argument, and has a left node and a right node, both of which are set to null by default. Easy!

Now, let's build out a class method to insert a new node into the tree. Remember, we need to make sure that this method compares the given data against both the left and right values of the current node, as well as properly works its way down the existing tree from the node.

We can do it in two parts, like so:

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }

  insert(data) {
    if (data < this.data && this.left) {
      this.left.insert(data);
    } else if (data < this.data) {
      this.left = new Node(data);
    }

    if (data > this.data && this.right) {
      this.right.insert(data);
    } else if (data > this.data) {
      this.right = new Node(data);
    }
  }
}

Essentially this is doing the same thing on both the right and the left.

We're checking to see if our passed in data is less than or greater than the current node's data, and then seeing if a left or right node already exists for the current node.

If not, then we insert this data as a new node in the proper position. If there is a node there already, then we call the insert method again on the left or right node, depending on which direction we're moving in. This repeats the process below, in that child node.

In terms of building a Binary Search Tree, we're basically done now. Yay!

Let's go one step further though and implement one more method to see if a BST contains a certain value:

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }

  insert(data) {
    if (data < this.data && this.left) {
      this.left.insert(data);
    } else if (data < this.data) {
      this.left = new Node(data);
    }

    if (data > this.data && this.right) {
      this.right.insert(data);
    } else if (data > this.data) {
      this.right = new Node(data);
    }
  }

  contains(data) {
    if (this.data === data) {
      return this;
    }

    if (data < this.data && this.left) {
      return this.left.contains(data);
    } else if (data > this.data && this.right) {
      return this.right.contains(data);
    } else {
      return null;
    }
  }
}

We're essentially doing the same thing here that we did above with the insert method.

We compare the given data against the data of the current node, seeing if its less than or greater than, and if a left or right node exists then we call the same contains method on it to check its data and children.

If the value is less than or greater than the current data and no left or right child node exists respectively, then we know the value doesn't exist in the tree and return null.

The key aspect of this method is our "base case", or the first three lines in the function. This checks to see if the current node's data is equal to the value we're searching for, and if so, we've found a match! We can return that node, or any other value we choose to confirm a hit.

And there you have it! We've officially built out a simple, functional Binary Search Tree in JavaScript. I'll explore some further functionalities of a BST in later blog posts that go a bit deeper on other interview questions you may come across involving them.

If you've read this far, thanks so much for taking the time. I hope it's been helpful! :)

Writing a Binary Search Algorithm in JavaScript

Sean Welsh Brown — Thu, 17 Sep 2020 00:52:05 +0000

In computer science, few tools are used quite as often as search algorithms. We rely on them every day as programmers and engineers to sift through data, and they're built into nearly every modern programming language in one way or another.

One of the most important and widely used search algorithms is known as a Binary Search, also known as a half-interval search, logarithmic search, or binary chop. Wikipedia describes the function of a Binary Search as follows:

Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.

Essentially, what we're doing is breaking down the array we're searching through by half each time we iterate our loop, looking at that midpoint, and then comparing it to the target to see if we should break the array by half again to either the left or the right. Following that, we increment or decrement left and right pointers to shrink our window. To visualize it, let's look at an example:

array = [0, 2, 4, 7, 8, 10, 12]
target = 4

         \/ midpoint, not target
[0, 2, 4, 7, 8, 10, 12]
 ^ left              ^ right


   \/ new midpoint, not target
[0, 2, 4, 7, 8, 10, 12]
 ^     ^

      \/ new midpoint, target!
[0, 2, 4, 7, 8, 10, 12]
       ^

This might seem a bit odd at first, but it will quickly make sense the more you consider it (and once we put it into code.)

The key to Binary Search working the way it does, is knowing that the array of integers that we're working in is sorted. This is a necessity, since we're comparing each midpoint to the target and making an assumption that it will be to the left or the right properly when sorted ascendingly.

While this limits opportunities to use Binary Search somewhat, it's often the absolute best search to use when working with sorted data. As a result of its breaking-down-by-half of the array, Binary Search has a best case runtime complexity of O(log n), which is solid as far as search optimization goes.

Time to implement it!

Implementing a Binary Search algorithm is actually quite simple, relative to understanding the core logic, and can be done in as few as 14 or less lines of code.

Let's build it together, line by line!

First off, we'll declare the function and its parameters:

function binarySearch(arr, target) {

}

Next, we'll define our left and right pointers with their initial values. The left pointer will start at the beginning of the array, and the right pointer will start at the end:

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
}

Now we add the core piece of logic for the function: a while loop. This while loop will be comparing the values of the left and right pointers, continuing to run as long as the left is less than or equal to the right.

Essentially this will tell the loop to run until our window is "closed", meaning we broke our array down as small as we could and still couldn't find a target value. We'll add a return value after the loop for this case:

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {

  }

  return "Target Not Found"
  // could also return -1, false, undefined, etc
}

Now we'll work on the loop. First off, we'll declare our midpoint variable and calculate its value, then add our "base case" which will return a value and end the function if the target is found:

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) return mid;
  }

  return "Target Not Found"
  // could also return -1, false, undefined, etc
}

In this version of the algorithm, we're simply returning the index of the target value if it has been found in the array. This return value could be changed to whatever you prefer.

And last but certainly not least, we'll implement the if else statement that checks whether the target is to the left or right of the midpoint, and increments or decrements the pointers accordingly:

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) return mid;

    if (target < arr[mid]) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }

  return "Target Not Found"
  // could also return -1, false, undefined, etc
}

And we're done!

The above code is the finished algorithm, which can be implemented anywhere and everywhere it's deemed appropriate.

Many programming languages have Binary Search built into their syntax, or provide options to implement it more easily, but understanding the core logic of how it functions by breaking down the array into smaller sections and comparing values is incredibly important for technical interviews and for designing your own algorithms to solve specific problems.

If you've come this far, thanks very much for reading! :) I'll continue putting out more tutorials and deep dives on the things I'm learning as a programmer as I go along.

Two Ways to Rotate an Array in JavaScript

Sean Welsh Brown — Wed, 09 Sep 2020 23:34:41 +0000

Sometimes the toughest questions we might be faced with in technical interviews as Software Engineers are the ones that seem simple at first glance.

Often writing a seemingly straightforward array or string algorithm will trip us up, due to us overcomplicating things or simply not knowing some of the more fundamental building blocks of working with those data types.

A question that embodies this perfectly is Rotating an Array.

The Prompt

Let's say you're given an array of numbers (nums), and an integer for how many times to the right that array should be "rotated" (k).

What does this mean? Let's visualize it:

nums = [1, 2, 3, 4, 5]

k = 3
=> [3, 4, 5, 1, 2]

k = 2
=> [4, 5, 1, 2, 3]

k = 1
=> [5, 1, 2, 3, 4]

As you can see, "rotating" an array is simply shifting those values to the right (or left) and putting them back on the opposite end of the array, sort of like rotating a carousel.

Now, how would be go about doing it?

The Solutions

What makes this question a compelling one in an interview setting is that there are multiple ways to solve it, all of which have different effects on runtime and space complexity. It's a good question to see the different ways a candidate goes about solving and explaining a "simple" problem since everyone might do it differently.

Today, we're going to look at two potential solutions:

A "brute force" approach using .pop() and .unshift() array methods.
A more complex solution using array reversals.

First we'll look at the code, and then break down what's happening in it.

1. Brute Force

const rotateArray1 = function(nums, k) {

  for (let i = 0; i < k; i++) {
      nums.unshift(nums.pop());
  }

  return nums;
}

This is considered the "brute force" approach, because it's essentially the most straightforward way that we're likely to think about the problem at first.

We know that we want to take something off of the end of the array and then put it on the front, and we know we want to do that (k) times, right?

This solution puts that exact direction into code. We run a for loop (k) times, on each pass pop()-ing off the last element of the array and giving it as an argument to unshift() it onto the front of the array. Then we return the array at the end.

The runtime complexity here is O(n * k), as each time we use unshift() JavaScript is re-seating each element in the array under the hood.

The space complexity is O(1), or constant space, since we're modifying the original array in-place. Great!

2. Reversal

const rotateArray2 = function(nums, k) {

  // reverse helper function
  function reverse(arr, start, end) {
    while (start < end) {
      [arr[start], arr[end]] = [arr[end], arr[start]];
      start++;
      end--;
    }
  }

  k %= nums.length;

  reverse(nums, 0, (nums.length - 1));
  reverse(nums, 0, (k - 1));
  reverse(nums, k, (nums.length - 1));

  return nums;
}

This is by far the most interesting solution of the three. This is the kind of algorithm solution you likely wouldn't think of initially, but might come to after thinking about the "bigger picture" for a while.

If you visualize the array being rotated, you'll notice a pattern:

nums = [1, 2, 3, 4, 5]

k = 2
=> [4, 5, 1, 2, 3]

// original array reversed
[5, 4, 3, 2, 1]

// reverse just the first (k) elements
[4, 5, 3, 2, 1]

// see where we're going?

// reverse from (k) to the end
[4, 5, 1, 2, 3]

And you've got the rotated result!

Again, this is a bit of a leap of logic that you might not initially think of, but works perfectly within the bounds we've been set for this problem.

As for our actual solution, what we're doing is establishing a helper function that takes in an array, a start index and an end index, and then uses ES6 syntax to swap the array[start] and array[end] elements before incrementing and decrementing the pointers.

Based off of our example above, we know we need to call this function three times:

Once to reverse the entire array.
Once to reverse from nums[0] to k.
Once to reverse from k to the end.

And we're done!

The runtime complexity here is O(n * 3), since we still need to reverse each element at least once, and we'll be doing that three times.

The space complexity here is, again, a constant O(1). Still great!

There you have it! Two completely different but equally viable solutions to the same problem. The advantage to knowing both is having more potential tools in your toolbox, and being able to answer a problem in different ways if an interviewer asks you to try a different approach.

I hope you've enjoyed reading! :)

Implementing a Simple LRU Cache in JavaScript

Sean Welsh Brown — Thu, 03 Sep 2020 01:43:09 +0000

In your travels as a software engineer, you're likely to come across instances where every possible data structure gets a chance to shine. One in particular doesn't get quite as much spotlight as the others, but can be just as useful (if not more so) in certain situations. That data structure in question is the LRU Cache.

What is an LRU Cache?

An LRU Cache, or Least Recently Used Cache, is a data structure that stores information in the order that it has most recently been added or accessed.

A popular analogy is a clothes rack in a closet: as clothes are worn and hung back up, they go on the right side of the rack. As time goes on, one can easily tell which clothes haven't been worn in a longer period of time by looking at the left side of the rack.

Why would I want to use one?

The main advantage of using an LRU Cache versus other data structures to store information comes in the form of added functionality.

A Cache in computer science terms can be thought of as a block of recently used data stored in a quickly accessible location in memory, resulting in faster performance when that same data is repeatedly pulled up.

If we consider an LRU Cache, it could be useful in an application that has users searching through a database for information. Normally every time a user looks something up, the app would ping its database with a request, taking precious time to do so. If, however, we store the most recently (or most commonly) searched-for items in an LRU cache, we can quickly check to see if the searched-for item exists in the cache, and if so we can retrieve it in significantly less time! Super useful.

Sounds great, how do we build one?

I'm glad you asked! Traditionally LRU Caches are built by combining a Hash Map with a Doubly Linked List, in order to maintain fast lookup of items and retrieval of most-recently-used and least-recently-used items in constant O(1) time.

However, if quickly implementing an LRU Cache from scratch in a small scale project is of interest to you, then one can be built out simply using nothing more than a JavaScript Class and a Map() object, at a cost to retrieval runtime.

The Least/Most Recently Used functionality will remain the same, which in practice is the key aspect of the data structure. If you're interested in learning how to create this version of an LRU Cache, then read on!

1. Establish the Class and Constructor

We'll be building out our LRU Cache using a JavaScript ES6 class, like so:

class LRUCache {

}

Within this class, we'll set a constructor so that every instance of an LRU Cache maintains the same structure. Our cache will take in a capacity as an argument, which will set the maximum size that our cache can grow to before we remove the least recently used item from its storage in order to save space and keep the structure organized.

We'll use this constructor to also establish the cache itself, using a JavaScript Map object:

class LRUCache {
  constructor(capacity) {
    this.cache = new Map();
    this.capacity = capacity;
  } 

}

The reason we're using a Map object here is that JavaScript Maps maintain the order in which keys and values have been inserted. This does most of the work for us!

2. Build out the Get and Put methods of the Cache

Now, we're going to implement our two vital functions within the class: Get and Put, which will retrieve a value and insert a key/value pair into the cache respectively.

Let's start with Get:

class LRUCache {
  constructor(capacity) {
    this.cache = new Map();
    this.capacity = capacity;
  }

  // Implementing Get method
  get(key) {
    if (!this.cache.has(key)) return undefined;

    let val = this.cache.get(key);

    this.cache.delete(key);
    this.cache.set(key, val);

    return val;
  }

}

Let's break down what we just did above.

We check to see if the key exists in our Map. If it doesn't, we return "undefined" (this could be any return value that represents a failed retrieval, such as -1 or an error message.)
Next we declare a variable "val", get the value associated with that key, and assign it to the variable.
We delete that key/value pair from our cache, and then set it again. Since our map keeps the order in which we insert things, this puts our retrieved key/value pair back at the front (most recently used) spot.
We return the value for use in our program wherever this method was called.

And that's all there is to the Get method!

Now, we'll implement our Put method:

class LRUCache {
  constructor(capacity) {
    this.cache = new Map();
    this.capacity = capacity;
  }

  get(key) {
    if (!this.cache.has(key)) return -1;

    let val = this.cache.get(key);

    this.cache.delete(key);
    this.cache.set(key, val);

    return val;
  }

  // Implementing Put method
  put(key, value) {
    this.cache.delete(key);

    if (this.cache.size === this.capacity) {
      this.cache.delete(this.cache.keys().next().value);
      this.cache.set(key, value);
    } else {
      this.cache.set(key, value);
    }
  }

}

Let's break it down into steps:

The first line checks if the key already exists in the Map and deletes it if so; calling .delete() either deletes the key/value pair if it exists OR returns undefined and continues if it doesn't.
If our cache is currently at its maximum capacity ( cache.size === this.capacity ), we delete our least recently used key/value pair by using this.cache.keys().next().value to get the first key of the Map using an iterator object and passing it as an argument to this.cache.delete() . We then set a new key/value pair in the cache using the arguments passed into the Put method.
If we're not currently at maximum capacity, we simply add the new key/value pair as normal.

And there's our Set method!

3. Implement getLeastRecent and getMostRecent methods

At this point we've created the fundamental functionality of an LRU Cache, but there's one step to go in order to have a complete data structure. We might want to retrieve the Least Recently Used (LRU) or Most Recently Used (MRU) values!

In order to do so, we're going to convert our Map into an array, then retrieve the first (LRU) and last (MRU) values of the array respectively:

class LRUCache {
  constructor(capacity) {
    this.cache = new Map();
    this.capacity = capacity;
  }

  get(key) {
    if (!this.cache.has(key)) return -1;

    let val = this.cache.get(key);

    this.cache.delete(key);
    this.cache.set(key, val);

    return val;
  }

  put(key, value) {
    this.cache.delete(key);

    if (this.cache.size === this.capacity) {
      this.cache.delete(this.cache.keys().next().value);
      this.cache.set(key, value);
    } else {
      this.cache.set(key, value);
    }
  }

  // Implement LRU/MRU retrieval methods
  getLeastRecent() {
    return Array.from(this.cache)[0];
  }

  getMostRecent() {
    return Array.from(this.cache)[this.cache.size - 1];
  }

}

And there we go! If you wanted to, you could use this same Array-from-Map concept to find second-least-recently-used, third-most-recently-used, etc.

That's our LRU Cache!

If you've read this far, thanks so much for taking the time to check out my post!

I hope it's been helpful to those of you trying to learn and understand data structures, or those of you trying to implement them in JavaScript. 😄

Using JavaScript's BigInt Data Type

Sean Welsh Brown — Wed, 26 Aug 2020 21:19:08 +0000

As all web developers come to know, JavaScript is a bit of an odd language with all sorts of interesting quirks in the way it compiles and functions behind the scenes.

One of the more interesting aspects of the language is the fact that it until very recently it has only used one data type for storing numbers: a Number object. This object doesn't specify between integers and floats the way many other languages do, but rather stores them all the same under the hood in double-precision 64 bit floating-point format.

However, as of the most recent versions of JavaScript's ECMA specification, there is now another method for storing and using numbers: the BigInt object.

Why do we need it?

The problem with the way JavaScript stores its numbers is that an overflow occurs when very large integers are stored, causing automatic rounding and accuracy issues.

A Number object in JavaScript can only safely store an integer between:

-9007199254740991 (-(2⁵³-1))

And:

9007199254740991 (2⁵³-1)

The overflow inaccuracy effect can be seen by console.logging the following:

console.log(9999999999999999);
// => 10000000000000000

Or:

// note the final digits
console.log(9007199254740992 === 9007199254740993);
// => true

This might seem like something that wouldn't be much of an issue in most small scale programming or web development workflows. But as JavaScript becomes more and more popular as a back end language, and as more databases and logic are written using the language, the issue of maximum safe integers became common enough for the maintainers of the language's international standard to solve the problem natively.

Here comes BigInt!

Traditionally JavaScript developers have found ways to work around issues with maximum integer sizes, such as interpolating large integers into strings and storing them that way, or by using open source libraries built my other devs.

Thanks to the introduction of BigInt however, the problem has officially been taken care of within the language itself.

To create a BigInt object, one need only append an "n" to the end of an unsafe integer, or wrap the integer in a "BigInt()" constructor, like so:

let largeNum1 = 9007199254740995n
// or
let largeNum2 = BigInt("9007199254740995")
// note that the integer is being parsed as a string,
// otherwise rounding may occur

And you're done!

Arithmetic on BigInt objects may be done using the following simple operators: +, -, *, /, **, and %.

It's worth noting that built in methods using the Math object in JavaScript will not work with BigInts, and that any arithmetic being done between a BigInt and a regular Number will not work— the Number must first be coerced into a BigInt as well.

Deeper information on the BigInt object can be found on the MDN WebDocs page: BigInt - JavaScript | MDN.

Can you give me a practical example of a BigInt use case?

Absolutely!

Let's say you're solving a problem involving Linked Lists in which you'd like to pull the values of two Lists, concatenate them into integers, add them together, and then return the sum.

Your solution might look like the following:

const addTwoNumbers = function(l1, l2) {

    // Helper method to concatenate list values
    function getNum(node) {
        let string = "";
        while (node) {
            string += node.val;
            node = node.next;
        }
        return string;
    }

    let l1Num = getNum(l1);
    let l2Num = getNum(l2);

    let sum = (parseInt(l1Num) + parseInt(l2Num));

    return sum;
};

With the following input case (imagine that each element in the array is the node value of a Linked list):

[7,2,4,3]
[5,6,4,2]

You would get the expected value of 7,243 + 5,642 = 12,885. Great!

However, with an input case like:

[2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,9]
[5,6,4,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,2,4,3,9,9,9,9]

Those numbers are HUGE!

If we try to simply parse those concatenated strings into integers using parseInt() the way we did before, our accuracy will be completely gone and our solution will be unusable in production.

In a case like this, BigInt is the perfect tool to use. We can slightly alter our solution to use the BigInt parsing syntax instead of parseInt(), like so:

const addTwoNumbers = function(l1, l2) {

    // Helper method to concatenate list values
    function getNum(node) {
        let string = "";
        while (node) {
            string += node.val;
            node = node.next;
        }
        return string;
    }

    let l1Num = getNum(l1);
    let l2Num = getNum(l2);

    // note the difference \/ !
    let sum = (BigInt(l1Num) + BigInt(l2Num));

    return sum;
};

And now we'll have an accurately calculated total!

Some extra logic could be implemented to coerce a value back to a Number object if it's less than the maximum safe integer size, so that this solution would work for all data sizes.

If you've come this far, thanks for reading! I hope you've enjoyed learning a bit about JavaScript's BigInt data type.

Again, I highly recommend reading the MDN WebDocs page on BigInt for more information if you're interested in implementing them in a project, or learning more in the future.