DEV Community: Adrian Mejia

What every programmer should know about Synchronous vs. Asynchronous Code

Adrian Mejia — Mon, 01 Jul 2019 17:15:01 +0000

There are multiple ways of handling concurrency on programming languages. Some languages use various threads, while others use the asynchronous model. We are going to explore the latter in detail and provide examples to distinguish between synchronous vs. asynchronous. Btw, What do you think your CPU does most of the time?

Is it working? Nope; It's idle!

Your computer's processor waits for a network request to come out. It idles for the hard drive to spin out the requested data, and it pauses for external events (I/O).

Take a look at the following graph to see the average time this system event takes (in nanoseconds)

As you can see in the chart above, one CPU can execute an instruction every one ns (approx.). However, if are in NYC and you make a request to a website in San Francisco, the CPU will "waste" 157 million cycles waiting for it to come back!

But not everything is lost! You can use that time to perform other tasks if you use a non-blocking (asynchronous) code in your programs! That's exactly what are you going to learn on this post.

⚠️ NOTE: Most programs on your operating system are non-blocking so a single CPU can perform many tasks while it waits for others to complete. Also, modern processors have multiple cores to increase the parallelism.

Synchronous vs. Asynchronous in Node.js

Let's see how we can develop non-blocking code that squeezes out the performance to the maximum.
Synchronous code is also called "blocking" because it halts the program until all the resources are available. However, asynchronous code is also known as "non-blocking" because the program continues executing and doesn't wait for external resources (I/O) to be available.

💡 In computing, input/output or I/O (or io or IO) is the communication between a program and the outside world (file system, databases, network requests, and so on).

We are going to compare two different ways of reading files using a blocking I/O model and then using a non-blocking I/O model.

First, consider the following blocking code.

Synchronous code for reading from a file in Node.js

const fs = require('fs');

console.log('start');

const data = fs.readFileSync('./file.txt', 'utf-8'); // blocks here until file is read
console.log('data: ', data.trim());

console.log('end');

What's the output of this program?

We are using Node's readFileSync.

Sync = Synchronous = Blocking I/O model

Async = Asynchronous = Non-blocking I/O model

That means that the program is going to wait around 23M CPU cycles for your HDD to come back with the content of the file.txt, which is the original message Hello World!.

The output would be:

start
data:  Hello World! 👋 🌍
end

How can make this code non-blocking?

I'm glad you asked. Luckily most Node.js functions are non-blocking (asynchronous) by default.

Actually, Ryan Dahl created Node because he was not happy with the limitations of the Apache HTTP server. Apache creates a thread for each connection which consumes more resources. On the other hand, Node.js combines JavaScript engine, an event loop, and an I/O layer to handle multiple requests efficiently.

As you can see, asynchronous functions can handle more operations while it waits for IO resources to be ready.

Let's see an example of reading from a file using the asynchronous code.

Asynchronous code for reading from a file in Node.js

We can read from the file without blocking the rest of the code like this:

const fs = require('fs');

console.log('start');

fs.readFile('./file.txt', 'utf-8', (err, data) => {
  if (err) throw err;
  console.log('file.txt data: ', data.trim());
});

console.log('end');

What's the output of this program?

See the answer

start
end
file.txt data:  Hello World! 👋 🌍

Many people get surprised by the fact that start and end comes before the data output. 👀

The end comes before the file output because the program doesn't halt and continue executing whatever is next.

That's cool, but does it make a lot of difference? It does, let's bigger files and time it!

Blocking vs. Non-Blocking I/O model Benchmark

For this benchmark, let's read a big file. I just went to my downloads and took the heaviest. (You can try this experiment at home and comment your results)

const fs = require('fs');

console.time('readFileSync');

for (let x = 0; x < 10; x++) {
  const largeFile = fs.readFileSync('/users/admejiar/Downloads/Docker.dmg');
  console.log(`File size#${x}: ${Math.round(largeFile.length / 1e6)} MB`);
}

const data = fs.readFileSync('./file.txt', 'utf-8'); // blocks here until file is read
console.log('file.txt data: ', data.trim());

console.timeEnd('readFileSync');

Notice that we are using console.time which is very nice for benchmarking since it calculates how many milliseconds it took. The output is the following:

File size#0: 523 MB
File size#1: 523 MB
File size#2: 523 MB
File size#3: 523 MB
File size#4: 523 MB
File size#5: 523 MB
File size#6: 523 MB
File size#7: 523 MB
File size#8: 523 MB
File size#9: 523 MB
file.txt data:  Hello World! 👋 🌍
readFileSync: 2572.060ms

It took 2.5 seconds to read all ten files and the file.txt.

Let's try now the same with non-blocking:

const fs = require('fs');

console.time('readFile');

for (let x = 0; x < 10; x++) {
  fs.readFile('/users/admejiar/Downloads/Docker.dmg', (err, data) => {
    if (err) throw err;
    console.log(`File size#${x}: ${Math.round(data.length / 1e6)} MB`);
  });
}

fs.readFile('./file.txt', 'utf-8', (err, data) => {
  if (err) throw err;
  console.log('file.txt data: ', data.trim());
});

console.timeEnd('readFile');

And here is the output:

readFile: 0.731ms
file.txt data:  Hello World! 👋 🌍
File size#7: 523 MB
File size#9: 523 MB
File size#4: 523 MB
File size#2: 523 MB
File size#6: 523 MB
File size#5: 523 MB
File size#1: 523 MB
File size#8: 523 MB
File size#0: 523 MB
File size#3: 523 MB

Wow! Totally random! 🤯

It got to the console.timeEnd in less than a millisecond! The small file.txt came later, and then the large files all in a different order. As you can see non-blocking waits for nobody. Whoever is ready will come out first. Even though it is not deterministic, it has many advantages.

Benchmarking asynchronous code is not as straight forward since we have to wait for all the operations to finish (which console.timeEnd is not doing). We are going to provide a better benchmark when we cover Promises.

Take a look at this picture:

That async programs will take as long the most time-consuming task. It executes tasks in parallel while the blocking model does it in sequence.

Advantages of non-blocking code

Non-blocking code is much more performant. Blocking code waste around 90% of CPU cycles waiting for the network or disk to get the data. Using non-blocking code is a more straightforward way to have concurrency without having to deal with multiple execution threads.

For instance, let's say you have an API server. In the image below, you can see how much more requests you can handle using non-blocking vs. using the blocking code.

As you saw earlier, the blocking API server, attend one request at a time. It serves the request #1, and it idles for the database and then is free to serve the other requests. However, the non-blocking API can take multiple requests while it waits for the database to come back.

Now that you are (hopefully) convinced why writing non-blocking code is necessary, let's see different ways we can manage it. So far, we used callbacks, but there are other ways to handle it.

In JavaScript, we can handle asynchronous code using:

Callbacks
Promises
Async/Await functions
Generators

I'm going to cover each one in a separate post. Follow & stay tuned!

What are your top ten command lines?

Adrian Mejia — Thu, 20 Jun 2019 15:38:01 +0000

Run the following command list to find out!

history | cut -c8- | sort | uniq -c | sort -rn | head -n 10

Mine is the following:

Since I used a lot of aliases, here is the expanded version:

git status (alias gst)
git push (alias ggpush='git push origin "$(git_current_branch)"')
git commit (alias gca='git commit -v -a')
ls (list files current directory)
code . (opening visual studio in the current folder)
git pull (alias ggpull='git pull origin "$(git_current_branch)"')
.. (go back previous directoy)
grunt serve (alias eos='cd "$LOCKHART"/eos && git pull origin "$(git_current_branch)"; grunt serve')
git checkout master (alias gco='git checkout')
grunt karma:... (run unit tests)

How to build a Node.js eCommerce website for free

Adrian Mejia — Mon, 13 May 2019 18:43:24 +0000

Running an online store that sells digital goods is easier than ever. Thanks to generous free plans for developers, you don’t have to spend a dime to run your e-commerce site for a decent amount of users. In this post, I’ll go over how I put together books.adrianmejia.com to sell my eBook.

A 10,000-feet view description would be something like this:

// Detect dark theme var iframe = document.getElementById('tweet-1127918275705413632-692'); if (document.body.className.includes('dark-theme')) { iframe.src = "https://platform.twitter.com/embed/Tweet.html?id=1127918275705413632&theme=dark" }

TL; DR: The e-Commerce site final stack is the following:

Node.js (Backend processing: payment webhooks)
Stripe (Payment gateway)
Heroku (Run server code)
Netlify (Host static files)
Amazon S3 (Host assets)
CircleCI (Test code and generate assets)
Mailgun (emails platform)

This diagram shows how each part interacts with each other:

Automating the generation of the assets (PDF)

I have Github repository where the book docs and code live:

amejiarosario / dsa.js-data-structures-algorithms-javascript

🥞Data Structures and Algorithms explained and implemented in JavaScript + eBook

Data Structures and Algorithms in JavaScript

This is the coding implementations of the DSA.js book and the repo for the NPM package.

In this repository, you can find the implementation of algorithms and data structures in JavaScript. This material can be used as a reference manual for developers, or you can refresh specific topics before an interview. Also, you can find ideas to solve problems more efficiently.

Installation

You can clone the repo or install the code from NPM:

npm install dsa.js

and then you can import it into your programs or CLI

const { LinkedList, Queue, Stack } = require('dsa.js');

For a list of all available data structures and algorithms, see index.js.

Features

Algorithms are an essential…

View on GitHub

Every time I made a change (or somebody in the community), it triggers some process on CI that run all tests and generate a new updated document and store it AWS S3.

Generating assets automatically is useful because I want every buyer to get the latest copy.

Hosting e-Commerce site

I always want to try out new JavaScript/CSS frameworks. However, I resisted the temptation and asked my self: Does a page for selling a book need to be dynamic? Nope. So, it will be more performant if I use plain old CSS and HTML. That’s what I did. Static pages also have the advantage that can be cached and served from a CDN.

I used Netlify to host the static website for free. One single git push will update the site on the domain name of choice (e.g. books.adrianmejia.com). It also uses a global CDN so your page loads faster from anywhere in the world!

Processing Payments

The next part is to add a Buy button. Stripe provides a helpful checkout page that they host themselves and take care of the PCI compliance when dealing with credit cards. So, I used that, and they process the payment for me.

But how do I know if the customer bought my book or got distracted? For that, I need a server that listens for a payment webhook. In the Stripe configuration page, you tell them to send a POST request (webhook) with the customer information when a particular event.

Here is the code for a simple webhook server

const express = require('express');
const bodyParser = require('body-parser');

const app = express();
const port = process.env.PORT || 5000;

app.use(bodyParser.json());

app.listen(port, () => {
  console.log(`Listening for webhooks: http://localhost:${port}`);
});

app.post('/webhook', async (req, res) => {
  const event = req.body;

  res.sendStatus(200);

  if (event.type === 'payment_intent.succeeded') {
    // TODO: send event to RabbitMQ instead of generating the PDF here.
    // It's not good practice to block a request handler with long processes
    const { sendPdfToBuyer } = require('./process-pdf');
    sendPdfToBuyer(event);
  }
});

// all other routes, prevent node crashing for undefined routes
app.route('*', async (req, res) => {
  res.json({ ok: 1 });
});

And that brings us to the next part, the Node.js server to take care of the rest.

Backend processing

I created a Node.js server that listened for webhook requests. When a customer paid for the book an event with the details is sent to this server, and the document pipeline is kicked off.

The server first downloads the book from AWS S3 bucket, where the latest raw document is. Later, the server uses a library that allows to manipulate the PDF and add the buyer’s stamp on the eBook. Finally, the material is attached to and send through email.

async function sendPdfToBuyer(webhookEvent) {
  const email = webhookEvent.data.object.charges.data.map(d => d.billing_details.email).join(', ');
  const pdfUrl = await getLatestPdfUrl();
  const fileName = pdfUrl.split('/').pop();
  const pdfBuffer = await downloadPdf(pdfUrl);
  const stampedPdfPath = await stampedPdfWithBuyerData({ pdfBuffer, email, fileName });
  await sendEmail({ stampedPdfPath, email, fileName });
}

Sending emails

Sending emails was a little trickier than I thought.

DNS settings and authentication

First, I was using my domain name, so I have to set up the DNS settings to make it work. However, I notice all my test emails to myself ended up on the junk mail.

Reading more about the topic I realized that I have to authenticate emails using SPF and DKIM, I still don’t know what they are in details, but they allow email providers (Gmail, Yahoo) to verify you are who you say you are. They are setup also using DNS settings given by the emailing service provides.

I set up the setting initially with Sendgrid but was still getting my emails to the junk folder. I moved to Mailgun and got better results. For some reason, hotmail.com would always reject the emails. As I learned unless you pay for a dedicated IP address the email service provider would use a “shared” IP in many accounts. If for some reason the IP gets a bad reputation then your emails will go to spam folder even if you have never sent an email before! I got this fixed by opening a support ticket and after they changed the IP it was working fine with any address.

Email Templates

The final part related to emails is doing a template. I have never done it before. The difference between HTML for email templates and web pages HTML is that on the email you should embed everything into the message itself. Spam filters don’t like external link loading additional resources. So, every CSS should be inline and has to also be responsible.

Well, there you have it: an e-commerce store that collects the payments and sends digital goods to buyers. Let’s close talking about the cost of maintenance.

Cost of running the e-Commerce store

This is the breakdown of the monthly costs:

Hosting static websites: $0 (if you use Netlify or Github pages)
Payment Gateway: $0 (Stripe will only a 2.9% charge if you sell something otherwise $0)
Node.js server: $0 (Heroku, AWS, Google Cloud and many others have a free plan for developers)
Email Service: $0 (Mailgun and Sendgrid both have free plans. The former allows you to send 10K emails per month)

The total is: $0 / mo.

Note: Like any website, If you want to use a custom domain as I do, you have to pay for it which is about $1/mo.

How can developers reduce stress

Adrian Mejia — Fri, 04 Jan 2019 00:28:50 +0000

Most professions nowadays involve a certain degree of stress. We have deadlines, last minute change of requirements and to deal with customers. On top of that, when you work in front of a computer 8+ hours, additional stressors are added. Your eyes might get dry. Also, the lack of movement might cause you back/neck pain, while your muscles shrink and your belly expands. This post will give you some tips to accomplish your goals without sacrificing your health. I also included some bonus tips for software engineers at the end of the post ;)

Background

There was a time in my life, back in 2015, where I went through severe stress crisis. I was juggling too many things at once: writing my first book, traveling to the USA interviewing for new jobs, getting a work visa, and planning a wedding while keeping up with a full-time job and also the sole programmer on two attempts of startups. It was the busiest time of my life, and my health suffered a lot! I dreamt about source code. Some nights I couldn’t sleep, so I worked instead. I went to the ER multiple times with heart palpitations. I knew I could not keep living in that way.

I’ve been experimenting with different things to see helped and what not. This post is a compilation of the ones that helped. I'll start with general things that apply to anybody working in front of a computer and end with some more specific tips for web and software developers.

Ideas to handle stress

I’ve been incorporating the following techniques, and it had helped me a lot to cope with stress! I hope they can help you, too!

Move 🚶‍♂️

Have you noticed that after a long time sitting your energy levels and concentration starts to drop?

Taking a little break to get some movements is an excellent way to boost your productivity!

Movement => Energy

Take a 5 minutes breaks after 25 minutes of work. You can also do 50/10 minutes of work/break. What matters is that you get some rest to move around and take deep breaths while at it.

The 25/5 minutes of work/break is also known as the Pomodoro technique. There are many apps that I have used to remind me to take a break. As simple as it sounds, it’s easy to get carried away when working on a computer and lose the notion of time.

Note: working out after work doesn't compensate for a long time of uninterrupted sitting. Your muscle and pain cripple in after a couple of hours static. So, you still have to try walking around at least every hour, so your body doesn’t suffer.

Apps I've used...

MacOs

Recess this one of my favorite because it's the simplest and blackout the screen. It keep some stats
Be Focused - Timer similar to `Recess` but also has a list where you can keep track of the time spend on each one.

iOS

Forest This has a timer and some background music that could help you concentrate.

I don't use Android/Windows very often, so if you have suggestions write it down in the comments, and I'll add it here.

Taking breaks can also reduce eye strain. I suffer from dry eyes from time to time. When we stare at a digital screen, we don’t blink as often causing our eyes dryness. There’s also a rule of thumb 20-20-20. It means that every 20 minutes, you look at something of 20 feet away for 20 seconds. At one point I also notice that my eyesight was getting worse, so I also incorporated some eyes exercises during the break. That also helped with the dryness a lot!

Eye exercises I've tried...

Blinking rapidly around 20 times. It helps with the dryness.
Extending my thumb as far and close to my eyes as I can.
Doing circles with thumbs while my eyes follow them. You can also look up and down, and right to left.

Brainstorm 🧠

Have you felt stressed when you get stuck on something for a while? (e.g., No syntax errors and still the code is not working as intended). Well, it’s time to take a step back and put things in perspective. There might be a straighter line to get to your goal. List all the alternatives or different ways you can solve the same problem. Whatever you can think of (don’t label them as “good” or “bad”. Put down the “smart” ideas and especially the “dumb” ones. In the end, choose the ones that you think will work best. Work smarter, not harder!

If you are going to cut a tree is essential to sharpen your ax first and then get to it. Not just will you cut the tree faster but also with less effort. Likewise, it’s vital that you take some time to do a little planning before jumping right into the task in hand. Beware of not overdoing it, set a time limit for this exercise. If you spend all the time sharpening the ax and never cut the tree is not good either ;)

Subtask ✌️

Divide a big task into smaller ones. Completing some small tasks will motivate you to get more done. Also keeps the stress away since you feel you are making progress. Another benefit of sub-tasking is that makes estimations more accurate.

Even the most ambitious projects and tallest buildings started with laying down one block at a time. Likewise, no matter how big your project is when you break it down into smaller pieces, that you make it easier to reason about.

Tackling a small task is less daunting to deal with the project as a whole, so you will be less likely to procrastinate and stress about it.

Prioritize 🎯

Most of us have an endless TODO list where things get added a lot faster than we can check them off. An infinite list of things to do, stress us big time. What if I tell you, that in most cases you only need to complete the 20% of the list to reap 80% of the benefits? 😲🤯

If you can’t do it all, then prioritize. Do what matters the most upfront. 20% of the task might account for 80% of the result (Pareto Principle). Find that critical 20% and execute on that first. For the rest of the list, you can apply the 80/20 principle recursively. Find the next 20% that matters the most and for the rest use Pareto again, delegate or re-evaluate if is still needed.

Ask 🗣

If you have more on your plate more than you can chew, then share with others. Don’t choke alone. Ask for help. 🙋🏻‍♂️

When you ask for help, the other person usually feels good. You are creating a bond and companionship with that person. However, don’t overdo it! Otherwise, it will have the opposite effect. Before asking for help, you should do your homework. Try to solve it yourself first, google it and struggle with the issue a little while. Write down some questions and where you got stuck (exact error messages, etc.) The other person will appreciate that you are respecting their time and that you are asking detailed questions.

When we neglect our body the proper care, we also can become sick which will take productivity to the floor. The following tips will help our body to cope with stress and keep health.

Drink 🚰

Stay hydrated. Your brain is mostly water so don’t let it dry. A good rule of thumb is to drink half of your weight in ounces (e.g., 170lb -> 85 oz. water).

Your body is a fantastic machine that tries to keep the balance regardless of what we throw at it. It remains a specific temperature when it’s freezing by shivering or sweating when it’s hot. It seeks to maintain the pH of your blood even if you drink too many acidic beverages (sodas, coffee). It tries to keeps your blood sugar on check even after eating a donut or if haven eaten in hours. However, our bodies need the proper nutrients and water to do so. When you don’t hydrate yourself enough, it can’t remove the waste out of your system. So, drink up!

Another way to know if you are hydrated is by monitoring how often your pee (crazy, right?). If you haven’t pee in 3 hours, you need two glasses of water ASAP.

Apps I've used...

iOS

WaterMinder You can track the amount of water that you drink and have reminders.
Pee & See: Water Reminder Alternative method of measuring hydration. Instead of logging the amout of water drank you log how often you pee. If you haven't pee in 3+ hours you will get a reminder to drink more water.

I don't use Android very often, so if you have suggestions write it down in the comments.

Nourish 🥦

How productive are you when you are sick? Exactly! You get almost nothing done and spend your time googling symptoms. On top of that, your stress increases and the deadlines get closer and you unable to make the process. A well-nourished body gets sick less and has more energy. You would be more productive!

Supplement yourself with vitamin C & fruits. Vitamin C helps your body to quickly clear out Cortisol, which is a hormone correlated to stress. It also keeps your immune system healthy. Magnesium from leafy greens helps to relax the muscles among many other benefits.

Foods to eat more regularly...

Nuts
Fish
Vegetable of different colors
Leafy greens
Fruits

Stretch 🙆‍♀️

Prolonged sitting is the new smoke. It might increase your body weight, back, and neck pain. Even if you exercise an hour before/after work, still you are hurting yourself for sitting too long at once. You have to break sitting often.

As discussed before, try to break sitting every 25 minutes or an hour with some stretching session. Our bodies are not designed to stay 8 hours per day sitting still. It was designed to move. Indeed, great ideas happen when you are on the move (showering/walking). If you are stuck with some task, take a little walk, stretch out and might give you some perspective.

Workout 🏋️‍♀️

Move your butt often, get some sweat in your forehead. Working out releases endorphins that increase your sense of well-being.

Working out your muscles can help you release tension and reduce your mental stress. However, don’t overdo it or it can backfire you. Try to avoid getting injured by doing small progressive changes rather than going too big the first day and then not being able to walk nor shower (I've been there).

Apps I've used...

iOS

Stronglifts 5x5 Weight Lifting I have used this program for 6 months and I have seen very good results. It's simple and have a nice tracker and videos how to do each exercise.

Breath 💨

If you are reading this, it means you are breathing (of course!). However, not all breaths are equal! 👀

Take some profound and slow breaths from time to time. When we are stressed out, we breathe very fast and shallow.

Proper breathing is vital for relaxation. You can avoid/overcome panic attacks. Just sitting relaxed and being aware of your breath when the air goes in and out can cool off your mind, reduce your heartbeats and blood pressure.

Some devices can track when you are tense, focus or calm. Guess how they do it? That’s right with your breathing. I have used Spire. I think it’s useful to receive feedback when I was getting tense and try to take some deep breadth right there.

Devices I've used...

Spire Stone: Stress Management

This one you wear it on your belt or bra. It will capture your breathing. I sometimes forget to wear it or where I left it. But, I learned a couple of things after wearing the device:

How is my breathing per minute when I’m stress/calm/focus. My BPM: I usually do < 14 BPM when calm and > 22 BPM when stressed.
What activities stress me out Location and time when stress

Meditate 🧘‍♀️

Meditation is trending now but still sounds a little strange for some people. It’s not about doing the lotus position you can do it sitting in your office chair, bus, train (but not while driving please). Simply put, meditation is focusing on the “now” because most of the time we get carried away fearing “future” situations that might never happen or worrying about a “past” that we can’t change. All we got is now.

One of the best ways to be present is being aware of your breathing. Breath always in the present. So, the basis of meditation is mindful of your breath, and that alone can be calming.

Apps I've used...

There are many apps that you can use for helping you pick up the habit of being present and relax:

iOS

Breethe: Sleep & Meditation This app has a nice series of guides for beginners. It has a lot of different topics like sleeping, concentration.
Simple Habit - Meditation It has a lot of different topics and also many instructors. Having different voices makes more dynamic.
Calm It's has a lot of free meditations and ambient music.
Headspace: Meditation It has only one instructor you might get bored listening to the same person.

I'm sure there are many other apps for this but this is the ones I've used, and they are in my order of preference.

Play 🎮

After a long session of work, what’s your reward? If you go home to continue working and or doing mentally taxing activities, then you will burn out quickly!

If you don’t rest properly, the next day your focus will be all over the place. Also, the urge to procrastinate will be strong in you. Your mind will be looking for any chance to get a break.

Solution? Have some planned downtime! After some time of work well done, reward yourself with something that you enjoy. Playtime! Do something that put a smile on your face 😊. Do something that makes you laugh 🤣.

Life can’t be all broccoli and no dessert.

Have some fun and plan for it!

Write ✍️

Journaling is one thing that helped me the most to calm my racing mind before going to sleep.

Use journals to write down thoughts, worries, plans, and let your mind run wild. Also, it helps a lot to write down things you are grateful on that day. It would make you feel better when you see written down some things turn out great on that day! Even in the worse days, there are a few things that you can be thankful for.

Like brainstorming doesn’t label your writing as bad or good. Just let it flow and write down what’s on your mind.

Some people do it in the morning like Tim Ferris, I have seen a lot of benefits doing it at night. Find the time that works the best for you.

Tools I've used...

Rocketbook Everlast Reusable Smart Notebook

This nice to avoid getting distracted with phone/table notifications and being able to save your notes digitally!
(evernote/email).
Rocketbook App
This app allows converts picture from your notebook to scans and sends them to your inbox, Evernote/Onenote/Dropbox. It also has some AI to recognize handwriting and transcribe it. It's not perfect but does a decent job if you have clear handwriting.

Sleep 😴

I neglected this one for some time. The truth is that we sometimes think if we sleep less, we would have more time to get stuff done. However, that’s not usually true. Your productivity/creativity decreases so much. If you are well-rested, you can solve problems in much less time.

The science of what happens while we sleep is still ongoing and fascinating. We know that memory consolidation happens while you sleep, your body repair itself, waste is removed from the brain. Your heart rate drops around 20%, and your stress hormones go down. Your nervous systems heal making you more responsive and sharp after a good night sleep.

Also, we have an idea of what happens when we don’t sleep much for a couple of days. We have problems concentrating. The quality of our work decreases and or creativity suffers. You might have headaches, darker shades under your eyes among other things.

Do you know having a good night sleep starts during the day? After a very stressful day or some big event coming up, for most people, it’s hard to sleep well (if at all). That’s why doing breathing exercises through the day helps. Also, taking breaks every 25 or 50 minutes of work. Journaling helps me a lot to calm down my monkey mind jumping all over the place at night.

Apps I've used...

iOS

AutoSleep Tracker for Watch
Keeps track of your sleep automatically. I used with the Apple Watch and works pretty well so far.

Stress management for Software Developers

All the recommendations above could apply to anyone working at an office. In this section, we are going to give some more for people working with technology that changes very fast (like Software Developers).

Information overload 🤯

Innovation in tech is happening at an unprecedented pace, and it will keep accelerating. Don’t feel like to have to learn everything new that comes out. Try to focus on the foundations and principles very well, since they are not changing anytime soon (E.g., Algorithms, Design Patterns, and so on)

If you are a front-end engineer, you notice that new web frameworks pop up in a relatively short time. However, the most popular ones are adopted by the industry and takes a while (a couple of years) to move away when new/“better” ones come along. So, don’t feel pressure if a new shiny tool is all the hype and you don’t know about it.

For backend and DevOps developers, there are paradigm changes from time to time. E.g., from monolith to microservices, from server rendered apps to SPA (single page applications) or hybrids. Also, people are talking about serverless, and the JAM Stack (JavaScript, APIs, and Markup); Docker and Kubernetes; The list keeps growing… Again don't throw everything you are doing and follow the buzzes.

All in all, don’t feel like you need to rearchitect your stack right away and throw what’s working for something new. Prefer battle-tested solution for production environments rather than shiny ones. Don’t follow the hype blindly. Evaluate your use cases carefully have proof of concepts (POC) test them. What worked for Google/Facebook might not necessarily be the right tool for you. You can benchmark multiple solutions before going all in and make a decision based on data rather than hype.

Testing 🐞

Test your code. Unit test and integration/e2e tests are not a nice to have; tests are a must if you want to sleep well at night. Even if your company has a QA team, try to write automated tests. Add test coverage tools and try to keep it as close to 100% as possible. That will reduce you a lot of stress chasing bugs in production and unexpected angry customers.

Refactoring 🛠

I have been battling my perfectionism for years. Every code I see that could be better, I feel the urge to modify it. Initially, I did, and my number of changes got so big that when something broke, it was hard to tell what’s wrong :(

Keep your changes small. It’s easier to review small pull requests (PR) than a large one. Divide significant changes into multiple small ones if it makes sense.

Also, have respect for the working code. There might be smarter ways to solve a task. However, you don’t know if you are going to introduce new bugs.

Try this:

Make it work, first. You should try to add new functionality and make it work. That's it: no refactoring, no clever tricks but lots of tests. Open up a PR and get it merged.
Make it faster, later. Now that we have something working and it has tests; it’s time to get smart and refactor.

That's all I have! Comment below what you do to keep stress low and productivity high.

Self-balanced Binary Search Trees with AVL in JavaScript

Adrian Mejia — Mon, 16 Jul 2018 19:43:11 +0000

Binary Search Trees (BST) is used for many things that we might not be aware of. For instance: in compilers to generate syntax trees, cryptography and in compressions algorithms used in JPG and MP3. However, search trees need to be balanced to be useful. So, we are going to discuss how to keep the BST balanced as you add and remove elements.

In this post, we are going to explore different techniques to balance a tree. We are going to use rotations to move nodes around and the AVL algorithm to keep track if the tree is balanced or needs adjustments. Let's dig in!

You can find all these implementations and more in the Github repo:

amejiarosario / dsa.js-data-structures-algorithms-javascript

🥞Data Structures and Algorithms explained and implemented in JavaScript + eBook

Data Structures and Algorithms in JavaScript

This is the coding implementations of the DSA.js book and the repo for the NPM package.

In this repository, you can find the implementation of algorithms and data structures in JavaScript. This material can be used as a reference manual for developers, or you can refresh specific topics before an interview. Also, you can find ideas to solve problems more efficiently.

Installation

You can clone the repo or install the code from NPM:

npm install dsa.js

and then you can import it into your programs or CLI

const { LinkedList, Queue, Stack } = require('dsa.js');

For a list of all available data structures and algorithms, see index.js.

Features

Algorithms are an essential…

View on GitHub

Let's start by defining what is a "balanced tree" and the pitfalls of an "unbalanced tree".

Balanced vs. Unbalanced Binary Search Tree

As discussed in the previous post the worst nightmare for a BST is to be given numbers in order (e.g. 1, 2, 3, 4, 5, 6, 7, ...).

If we ended up with a tree like the one on the left, we are in trouble because performance will go to the floor. To find out if a node is on the tree or not, you will have to visit every node when the tree is unbalanced. That takes O(n), while if we keep the node balanced in every insertion or deletion, we could have O(log n).

Again, this might not look like a big difference, but when you have a million nodes, the difference is huge! We are talking about visiting 1,000,000 nodes vs. visiting 20!

"Ok, I'm sold. How do I keep the tree balanced?" I'm glad you asked 😉. Well, let's first learn when to tell that a tree is unbalanced.

When a tree is balanced/non-balanced?

Take a look at the following trees and tell which one is balanced and which one is not.

Well, a tree is definately balanced when is a perfect tree (all the levels on the tree have maximum number of nodes). But what about
full trees or complete trees?

The "complete tree" looks somewhat balanced, right? What about the full tree? Well, it starts to get tricky. Let's work on a definition.

A tree is balanced if:

The left subtree height and the right subtree height differ by at most 1.
Visit every node making sure rule #1 is satisfied.

Note: Height of a node is the distance (edge count) from the farthest child to itself.

For instance, if you have a tree with seven nodes:

     10
    /   \
   5    20
  /     / \
 4    15   30
      /
     12

If you check the subtrees' heights (edge counts to the farthest leaf node)
recursively you will notice they never differ by more than one.

10 descendants:
- Left subtree 5 has a height of 1, while right subtree 20 has a height of 2. The difference is one so: Balanced!
20 descendants:
- Left subtree15 has a height of 1, while right subtree 30 has a height of 0. So the diff is 1: Balanced!

On the other hand, take a look at this tree:

Let's check the height of the subtree recursively:

40 descendants:
- Left subtree 35 has a height of 1, while right subtree 60 has a height of 2. The difference is one so: Balanced!
60 descendants:
- Left subtree 50 has a height of 2, while the right subtree (none) has a height of 0. The difference between 2 and 0 is more than one, so: NOT balanced!

Hopefully, now you can calculate balanced and unbalanced trees.

What can we do when we find an unbalanced tree? We do rotations!

If we take the same tree as before and move 50 to the place of 60 we get the following:

      40
    /   \
   35    50
  /     /   \
 25    45    60*

After rotating 60 to the right, It's balanced! Let's learn all about it in the next section.

Tree rotations

Before throwing any line of code, let's spend some time thinking about how to balance small trees using rotations.

Left Rotation

Let's say that we have the following tree with ascending values: 1-2-3

 1*                                        2
  \                                       /  \
   2     ---| left-rotation(1) |-->      1*   3
    \
     3

To perform a left rotation on node 1, we move it down as it's children's (2) left descendant.

This is called single left rotation or Left-Left (LL) rotation.

For the coding part, let's do another example:

 1                                 1
  \                                 \
   2*                                3
    \    --left-rotation(2)->       / \
     3                             2*  4
      \
       4

To define the tree, we are using TreeNode
that we developed in the previous post.

  const n1 = new TreeNode(1);
  const n2 = new TreeNode(2);
  const n3 = new TreeNode(3);
  const n4 = new TreeNode(4);

  n1.right = n2;
  n2.right = n3;
  n3.right = n4;

  const newParent = leftRotation(n2);
  console.log(newParent === n3); // true

In this case, we are rotating 2 to the left. Let's implement the leftRotation function.

tree-rotations.js - leftRotation

function leftRotation(node) {
  const newParent = node.right; // e.g. 3
  const grandparent = node.parent; // e.g. 1

  // make 1 the parent of 3 (previously was the parent of 2)
  swapParentChild(node, newParent, grandparent);

  // do LL rotation
  newParent.left = node; // makes 2 the left child of 3
  node.right = undefined; // clean 2's right child

  return newParent; // 3 is the new parent (previously was 2)
}

Notice that we are using a utility function to swap parents called swapParentChild.

tree-rotations.js - swapParentChild

function swapParentChild(oldChild, newChild, parent) {
  if (parent) {
    const side = oldChild.isParentRightChild ? 'right' : 'left';
    // this set parent child AND also
    parent[side] = newChild;
  } else {
    // no parent? so set it to null
    newChild.parent = null;
  }
}

We are using this function to make 1 the parent of 3. We are going to use it rotation right as well.

Right Rotation

We have the following tree with descending values 4-3-2-1:

      4                                        4
     /                                        /
    3*                                       2
   /                                        /  \
  2       ---| right-rotation(3) |-->      1    3*
 /
1

To perform a right rotation on node 3, we move it down as its child 2's right descendant.

This is called single right rotation or Right-Right (RR) rotation.

The code is pretty similar to what we did on the left rotation:

tree-rotations.js - rightRotation

function rightRotation(node) {
  const newParent = node.left;
  const grandparent = node.parent;

  swapParentChild(node, newParent, grandparent);

  // do RR rotation
  newParent.right = node;
  node.left = undefined;

  return newParent;
}

The rightRotation does the following:

First, we swap 4's child: before it was 3 and after the swap is 2 (line 5).
Later, we make 3 the right child of 2 (line 8) and
Finally, we clean up the 3 right child reference to null (line 9).

Now that know how single rotations work to the left and right we can combine them: left-right and right-left rotations.

Left-Right Rotation

If we insert values on a BST in this order: 3-1-2. We will get an unbalanced tree. To balance the tree, we have to do a leftRightRotation(3).

    3*                                       2*
   /                                        /  \
  1    --| left-right-rotation(3) |->      1    3
   \
    2

Double rotations are a combination of the other two rotations we discussed in (LL and RR):

If we expand the left-right-rotation into the two single rotations we would have:

  3*                          3*
 /                          /                            2
1   -left-rotation(1)->    2    -right-rotation(3)->    /  \
 \                        /                            1    3*
  2                      1

left-rotation(1): We do a left rotation on the nodes' left child. E.g. 1.
right-rotation(3): right rotation on the same node. E.g. 3.

This double rotation is called Left-Right (LR) rotation.

tree-rotations.js - leftRightRotation

function leftRightRotation(node) {
  leftRotation(node.left);
  return rightRotation(node);
}

The code is straightforward since we leverage the leftRotation and rightRotation that we did before.

Right-Left Rotation

When we insert nodes on the following order: 1-3-2, we need to perform a rightLeftRotation(1) to balance the tree.

  1*                           1*
   \                            \                              2
     3   -right-rotation(3)->    2   -left-rotation(1)->      /  \
   /                              \                          1*   3
  2                                3

The code to is very similar to LR rotation:

tree-rotations.js - rightLeftRotation

function rightLeftRotation(node) {
  rightRotation(node.right);
  return leftRotation(node);
}

We know all the rotations needed to balanced any binary tree. Let's go ahead, use the AVL algorithm to keep it balanced on insertions/deletions.

AVL Tree Overview

AVL Tree was the first self-balanced tree invented. It is named after the two inventors Adelson-Velsky and Landis. In their self-balancing algorithm if one subtree differs from the other by at most one, then rebalancing is done using rotations.

We already know how to do rotations from the previous sections; the next step is to figure out the subtree's heights. We are going to call balance factor, the diff between the left and right subtree on a given node.

balanceFactor = leftSubtreeHeight - rightSubtreeHeight

If the balance factor is bigger than 1 or less than -1 then, we know we need to balance that node. We can write the balance function as follows:

tree-rotations.js - balance

function balance(node) {
  if (node.balanceFactor > 1) {
    // left subtree is higher than right subtree
    if (node.left.balanceFactor > 0) {
      rightRotation(node);
    } else if (node.left.balanceFactor < 0) {
      leftRightRotation(node);
    }
  } else if (node.balanceFactor < -1) {
    // right subtree is higher than left subtree
    if (node.right.balanceFactor < 0) {
      leftRotation(node);
    } else if (node.right.balanceFactor > 0) {
      rightLeftRotation(node);
    }
  }
}

Based on the balance factor, there four different rotation that we can do: RR, LL, RL, and LR. To know what rotation to do we:

Take a look into the given node's balanceFactor.
If the balance factor is -1, 0 or 1 we are done.
If the node needs balancing, then we use the node's left or right balance factor to tell which kind of rotation it needs.

Notice that we haven't implemented the node.balanceFactor attribute yet, but we are going to do that next.

One of the easiest ways to implement subtree heights is by using recursion. Let's go ahead and add height-related properties to TreeNode class:

tree-rotations.js - height, leftSubtreeHeight and rightSubtreeHeight

  get height() {
    return Math.max(this.leftSubtreeHeight, this.rightSubtreeHeight);
  }

  get leftSubtreeHeight() {
    return this.left ? this.left.height + 1 : 0;
  }

  get rightSubtreeHeight() {
    return this.right ? this.right.height + 1 : 0;
  }

  get balanceFactor() {
    return this.leftSubtreeHeight - this.rightSubtreeHeight;
  }

To understand better what's going on, let's do some examples.

Tree with one node

Let's start with a single root node:

     40*
   /     \

Since this node doesn't have left nor right children then leftSubtreeHeight and rightSubtreeHeight will return 0.
Height is Math.max(this.leftSubtreeHeight, this.rightSubtreeHeight) which is Math.max(0, 0), so height is 0.
Balance factor is also zero since 0 - 0 = 0.

Tree with multiple nodes

Let's try with multiple nodes:

balanceFactor(45)

As we saw leaf nodes doesn't have left or right subtree, so their heights are 0, thus balance factor is 0.

balanceFactor(50)

leftSubtreeHeight = 1 and rightSubtreeHeight = 0.
height = Math.max(1, 0), so it's 1.
Balance factor is 1 - 0, so it's 1 as well.

balanceFactor(60)

leftSubtreeHeight = 2 and rightSubtreeHeight = 0.
height = Math.max(2, 0), so it's 2.
Balance factor is 2 - 0, so it's 2 and it's UNBALANCED!

If we use our balance function on node 60 that we developed, then it would do a rightRotation on 60 and the tree will look like:

     40
   /   \
  35    50
 /     /   \
25    45    60*

Before the height of the tree (from the root) was 3, now it's only 2.

Let's put all together and explain how we can keep a binary search tree balanced on insertion and deletion.

AVL Tree Insertion and Deletion

AVL tree is just a layer on top of a regular Binary Search Tree (BST). The add/remove operations are the same as in the BST, the only difference is that we run the balance function after each change.

Let's implement the AVL Tree.

avl-tree.js

const BinarySearchTree = require('./binary-search-tree');
const { balanceUptream } = require('./tree-rotations');

class AvlTree extends BinarySearchTree {
  add(value) {
    const node = super.add(value);
    balanceUptream(node);
    return node;
  }

  remove(value) {
    const node = super.find(value);
    if (node) {
      const found = super.remove(value);
      balanceUptream(node.parent);
      return found;
    }

    return false;
  }
}

If you need to review the dependencies here are the links to the implementations:

The balanceUpstream function gets executed after an insertion or deletion.

tree-rotations.js - balanceUptream

function balanceUptream(node) {
  let current = node;
  while (current) {
    balance(current);
    current = current.parent;
  }
}

We go recursively using the balance function on the nodes' parent until we reach the root node.

In the following animation, we can see AVL tree insertions and deletions in action:

You can also check the
test files
to see more detailed examples of how to use the AVL trees.

That's all folks!

Summary

In this post, we explored the AVL tree, which is a particular binary search tree that self-balance itself after insertions and deletions of nodes. The operations of balancing a tree involve rotations, and they can be single or double rotations.

Single rotations:

Left rotation
Right rotation

Double rotations:

Left-Right rotation
Right-Left rotation

You can find all the code developed here in the
Github.
You can star it to keep it handy.

Tree Data Structures Explained with JavaScript

Adrian Mejia — Mon, 11 Jun 2018 22:49:30 +0000

Tree data structures have many uses, and it's good to have a basic understanding of how they work. Trees are the basis for other very used data structures like Maps and Sets. Also, they are used on databases to perform quick searches. The HTML DOM uses a tree data structure to represents the hierarchy of elements. In this post, we are going to explore the different types of trees like a binary tree, binary search trees, and how to implement them.

In the previous post, we explored the Graph data structures, which are a generalized case of trees. Let's get started learning what tree data structures are!

You can find all these implementations and more in the Github repo:

amejiarosario / dsa.js-data-structures-algorithms-javascript

🥞Data Structures and Algorithms explained and implemented in JavaScript + eBook

Data Structures and Algorithms in JavaScript

This is the coding implementations of the DSA.js book and the repo for the NPM package.

In this repository, you can find the implementation of algorithms and data structures in JavaScript. This material can be used as a reference manual for developers, or you can refresh specific topics before an interview. Also, you can find ideas to solve problems more efficiently.

Installation

You can clone the repo or install the code from NPM:

npm install dsa.js

and then you can import it into your programs or CLI

const { LinkedList, Queue, Stack } = require('dsa.js');

For a list of all available data structures and algorithms, see index.js.

Features

Algorithms are an essential…

View on GitHub

Trees: basic concepts

A tree is a data structure where a node can zero or more children. Each node contains a value. Like graphs, the connection between nodes is called edges. A tree is a type of graph, but not all of them are trees (more on that later).

These data structures are called "trees" because the data structure resembles a tree 🌳. It starts with a root node and branch off with its descendants, and finally, there are leaves.

Here are some properties of trees:

The top-most node is called root.
A node without children is called leaf node or terminal node.
Height (h) of the tree is the distance (edge count) between the farthest leaf to the root.
- A has a height of 3
- I has a height of 0
Depth or level of a node is the distance between the root and the node in question.
- H has a depth of 2
- B has a depth of 1

Implementing a simple tree data structure

As we saw earlier, a tree node is just a data structure that has a value and has links to their descendants.

Here's an example of a tree node:

class TreeNode {
  constructor(value) {
    this.value = value;
    this.descendents = [];
  }
}

We can create a tree with 3 descendents as follows:

// create nodes with values
const abe = new TreeNode('Abe');
const homer = new TreeNode('Homer');
const bart = new TreeNode('Bart');
const lisa = new TreeNode('Lisa');
const maggie = new TreeNode('Maggie');

// associate root with is descendents
abe.descendents.push(homer);
homer.descendents.push(bart, lisa, maggie);

That's all; we have a tree data structure!

The node abe is the root and bart, lisa and maggie are the leaf nodes of the tree. Notice that the tree's node can have a different number of descendants: 0, 1, 3, or any other value.

Tree data structures have many applications such as:

Maps
Sets
Databases
Priority Queues
Querying an LDAP (Lightweight Directory Access Protocol)
Representing the Document Object Model (DOM) for HTML on the Websites.

Binary Trees

Trees nodes can have zero or more children. However, when a tree has at the most two children, then it's called binary tree.

Full, Complete and Perfect binary trees

Depending on how nodes are arranged in a binary tree, it can be full, complete and perfect:

Full binary tree: each node has exactly 0 or 2 children (but never 1).
Complete binary tree: when all levels except the last one are full with nodes.
Perfect binary tree: when all the levels (including the last one) are full of nodes.

Look at these examples:

These properties are not always mutually exclusive. You can have more than one:

A perfect tree is always complete and full.
- Perfect binary trees have precisely 2^k - 1\ nodes, where k is the last level of the tree (starting with 1).
A complete tree is not always full.
- Like in our "complete" example, since it has a parent with only one child. If we remove the rightmost gray node, then we would have a complete and full tree but not perfect.
A full tree is not always complete and perfect.

Binary Search Tree (BST)

Binary Search Trees or BST for short are a particular application of binary trees. BST has at most two nodes (like all binary trees). However, the values are in such a way that the left children value must be less than the parent, and the right children is must be higher.

Duplicates: Some BST doesn't allow duplicates while others add the same values as a right child. Other implementations might keep a count on a case of the duplicity (we are going to do this one later).

Let's implement a Binary Search Tree!

BST Implementation

BST are very similar to our previous implementation of a tree. However, there are some differences:

Nodes can have at most, only two children: left and right.
Nodes values has to be ordered as left < parent < right.

Here's the tree node. Very similar to what we did before, but we added some handy getters and setters for left and right children. Notice that is also keeping a reference to the parent and we update it every time add children.

TreeNode.js

const LEFT = 0;
const RIGHT = 1;

class TreeNode {
  constructor(value) {
    this.value = value;
    this.descendents = [];
    this.parent = null;
  }

  get left() {
    return this.descendents[LEFT];
  }

  set left(node) {
    this.descendents[LEFT] = node;
    if (node) {
      node.parent = this;
    }
  }

  get right() {
    return this.descendents[RIGHT];
  }

  set right(node) {
    this.descendents[RIGHT] = node;
    if (node) {
      node.parent = this;
    }
  }
}

Ok, so far we can add a left and right child. Now, let's do the BST class that enforces the left < parent < right rule.

class BinarySearchTree {
  constructor() {
    this.root = null;
    this.size = 0;
  }

  add(value) { /* ... */ }
  find(value) { /* ... */ }
  remove(value) { /* ... */ }
  getMax() { /* ... */ }
  getMin() { /* ... */ }
}

Let's implementing insertion.

BST Node Insertion

To insert a node in a binary tree, we do the following:

If a tree is empty, the first node becomes the root and you are done.
Compare root/parent's value if it's higher go right, if it's lower go left. If it's the same, then the value already exists so you can increase the duplicate count (multiplicity).
Repeat #2 until we found an empty slot to insert the new node.

Let's do an illustration how to insert 30, 40, 10, 15, 12, 50:

We can implement insert as follows:

  add(value) {
    const newNode = new TreeNode(value);

    if (this.root) {
      const { found, parent } = this.findNodeAndParent(value);
      if (found) { // duplicated: value already exist on the tree
        found.meta.multiplicity = (found.meta.multiplicity || 1) + 1;
      } else if (value < parent.value) {
        parent.left = newNode;
      } else {
        parent.right = newNode;
      }
    } else {
      this.root = newNode;
    }

    this.size += 1;
    return newNode;
  }

We are using a helper function called findNodeAndParent. If we found that the node already exists in the tree, then we increase the multiplicity counter. Let's see how this function is implemented:

  findNodeAndParent(value) {
    let node = this.root;
    let parent;

    while (node) {
      if (node.value === value) {
        break;
      }
      parent = node;
      node = ( value >= node.value) ? node.right : node.left;
    }

    return { found: node, parent };
  }

findNodeAndParent goes through the tree searching for the value. It starts at the root (line 2) and then goes left or right based on the value (line 10). If the value already exists, it will return the node found and also the parent. In case that the node doesn't exist, we still return the parent.

BST Node Deletion

We know how to insert and search for value. Now, we are going to implement the delete operation. It's a little trickier than adding, so let's explain it with the following cases:

Deleting a leaf node (0 children)

    30                             30
 /     \         remove(12)     /     \
10      40       --------->    10      40
  \    /  \                      \    /  \
  15  35   50                    15  35   50
  /
12*

We just remove the reference from node's parent (15) to be null.

Deleting a node with one child.

    30                              30
 /     \         remove(10)      /     \
10*     40       --------->     15      40
  \    /  \                            /  \
  15  35   50                         35   50

In this case, we go to the parent (30) and replace the child (10), with a child's child (15).

Deleting a node with two children

    30                              30
 /     \         remove(40)      /     \
15      40*      --------->     15      50
       /  \                            /
      35   50                         35

We are removing node 40, that has two children (35 and 50). We replace the parent's (30) child (40) with the child's right child (50). Then we keep the left child (35) in the same place it was before, so we have to make it the left child of 50.

Another way to do it to remove node 40, is to move the left child (35) up and then keep the right child (50) where it was.

Either way is ok as long as you keep the binary search tree property: left < parent < right.

Deleting the root.

    30*                            50
  /     \       remove(30)      /     \
 15      50     --------->     15      35
        /
       35

Deleting the root is very similar to removing nodes with 0, 1, or 2 children that we discussed earlier. The only difference is that afterward, we need to update the reference of the root of the tree.

Here's an animation of what we discussed.

In the animation, it moves up the left child/subtree and keeps the right child/subtree in place.

Now that we have a good idea how it should work, let's implement it:

  remove(value) {
    const nodeToRemove = this.find(value);
    if (!nodeToRemove) return false;

    // Combine left and right children into one subtree without nodeToRemove
    const nodeToRemoveChildren = this.combineLeftIntoRightSubtree(nodeToRemove);

    if (nodeToRemove.meta.multiplicity && nodeToRemove.meta.multiplicity > 1) {
      nodeToRemove.meta.multiplicity -= 1; // handle duplicated
    } else if (nodeToRemove === this.root) {
      // Replace (root) node to delete with the combined subtree.
      this.root = nodeToRemoveChildren;
      this.root.parent = null; // clearing up old parent
    } else {
      const side = nodeToRemove.isParentLeftChild ? 'left' : 'right';
      const { parent } = nodeToRemove; // get parent
      // Replace node to delete with the combined subtree.
      parent[side] = nodeToRemoveChildren;
    }

    this.size -= 1;
    return true;
  }

Here are some highlights of the implementation:

First, we search if the node exists. If it doesn't, we return false and we are done!
If the node to remove exists, then combine left and right children into one subtree.
Replace node to delete with the combined subtree.

The function that combines left into right subtree is the following:

BinarySearchTree.prototype.combineLeftIntoRightSubtree

  combineLeftIntoRightSubtree(node) {
    if (node.right) {
      const leftmost = this.getLeftmost(node.right);
      leftmost.left = node.left;
      return node.right;
    }
    return node.left;
  }

For instance, let's say that we want to combine the following tree and we are about to delete node 30. We want to mix 30's left subtree into the right one. The result is this:

      30*                             40
    /     \                          /  \
   10      40    combine(30)       35   50
     \    /  \   ----------->      /
     15  35   50                  10
                                   \
                                    15

Now, and if we make the new subtree the root, then node 30 is no more!

Binary Tree Transversal

There are different ways of traversing a Binary Tree depending on the order that the nodes are visited: in-order, pre-order and post-order. Also, we can use the DFSand BFS that we learned from the graph post. Let’s go through each one.

In-Order Traversal

In-order traversal visit nodes on this order: left, parent, right.

BinarySearchTree.prototype.inOrderTraversal

  * inOrderTraversal(node = this.root) {
    if (node.left) { yield* this.inOrderTraversal(node.left); }
    yield node;
    if (node.right) { yield* this.inOrderTraversal(node.right); }
  }

Let's use this tree to make the example:

           10
         /    \
        5      30
      /       /  \
     4       15   40
   /
  3

In-order traversal would print out the following values: 3, 4, 5, 10, 15, 30, 40. If the tree is a BST, then the nodes will be sorted in ascendent order as in our example.

Post-Order Traversal

Post-order traversal visit nodes on this order: left, right, parent.

BinarySearchTree.prototype.postOrderTraversal

  * postOrderTraversal(node = this.root) {
    if (node.left) { yield* this.postOrderTraversal(node.left); }
    if (node.right) { yield* this.postOrderTraversal(node.right); }
    yield node;
  }

Post-order traversal would print out the following values: 3, 4, 5, 15, 40, 30, 10.

Pre-Order Traversal and DFS

In-order traversal visit nodes on this order: parent, left, right.
BinarySearchTree.prototype.preOrderTraversal

  * preOrderTraversal(node = this.root) {
    yield node;
    if (node.left) { yield* this.preOrderTraversal(node.left); }
    if (node.right) { yield* this.preOrderTraversal(node.right); }
  }

Pre-order traversal would print out the following values: 10, 5, 4, 3, 30, 15, 40. This order of numbers is the same result that we would get if we run the Depth-First Search (DFS).

BinarySearchTree.prototype.dfs

  * dfs() {
    const stack = new Stack();

    stack.add(this.root);

    while (!stack.isEmpty()) {
      const node = stack.remove();
      yield node;
      // reverse array, so left gets removed before right
      node.descendents.reverse().forEach(child => stack.add(child));
    }
  }

If you need a refresher on DFS, we covered in details on Graph post.

Breadth-First Search (BFS)

Similar to DFS, we can implement a BFS by switching the Stack by a Queue:

BinarySearchTree.prototype.bfs

  * bfs() {
    const queue = new Queue();

    queue.add(this.root);

    while (!queue.isEmpty()) {
      const node = queue.remove();
      yield node;
      node.descendents.forEach(child => queue.add(child));
    }
  }

The BFS order is: 10, 5, 30, 4, 15, 40, 3

Balanced vs. Non-balanced Trees

So far, we have discussed how to add, remove and find elements. However, we haven't talked about runtimes. Let's think about the worst-case scenarios.

Let's say that we want to add numbers in ascending order.

We will end up with all the nodes on the left side! This unbalanced tree is no better than a LinkedList, so finding an element would take O(n). 😱

Looking for something in an unbalanced tree is like looking for a word in the dictionary page by page. When the tree is balanced, you can open the dictionary in the middle and from there you know if you have to go left or right depending on the alphabet and the word you are looking for.

We need to find a way to balance the tree!

If the tree was balanced, then we could find elements in O(log n) instead of going through each node. Let's talk about what balanced tree means.

If we are searching for 7 in the non-balanced tree, we have to go from 1 to 7. However, in the balanced tree, we visit: 4, 6, and 7. It gets even worse with larger trees. If you have one million nodes, searching for a non-existing element might require to visit all million while on a balanced tree it just requires 20 visits! That's a huge difference!

We are going to solve this issue in the next post using self-balanced trees (AVL trees).

Summary

We have covered much ground for trees. Let's sum it up with bullets:

The tree is a data structure where a node has 0 or more descendants/children.
Tree nodes don't have cycles (acyclic). If it has cycles, it is a Graph data structure instead.
Trees with two children or less are called: Binary Tree
When a Binary Tree is sorted in a way that the left value is less than the parent and the right children is higher, then and only then we have a Binary Search Tree.
You can visit a tree in a pre/post/in-order fashion.
An unbalanced has a time complexity of O(n). 🤦🏻‍
A balanced has a time complexity of O(log n). 🎉

Graph Data Structures Explained in JavaScript

Adrian Mejia — Mon, 14 May 2018 09:19:22 +0000

In this post, we are going to explore non-linear data structures like graphs. Also, we'll cover the central concepts and typical applications.

You are probably using programs with graphs and trees. Let's say for instance that you want to know the shortest path between your workplace and home; you can use graph algorithms to get the answer! We are going to look into this and other fun challenges.

In the previous post, we explore linear data structures like arrays, linked lists, sets, stacks and so on. This one builds on top of what we learned.

You can find all these implementations and more in the Github repo:

amejiarosario / dsa.js-data-structures-algorithms-javascript

🥞Data Structures and Algorithms explained and implemented in JavaScript + eBook

Data Structures and Algorithms in JavaScript

This is the coding implementations of the DSA.js book and the repo for the NPM package.

In this repository, you can find the implementation of algorithms and data structures in JavaScript. This material can be used as a reference manual for developers, or you can refresh specific topics before an interview. Also, you can find ideas to solve problems more efficiently.

Installation

You can clone the repo or install the code from NPM:

npm install dsa.js

and then you can import it into your programs or CLI

const { LinkedList, Queue, Stack } = require('dsa.js');

For a list of all available data structures and algorithms, see index.js.

Features

Algorithms are an essential…

View on GitHub

Here is the summary of the operations that we are going to cover on this post:

	Adjacency List	Adjacency Matrix
addVertex	O(1)	O(\|V\|²)
removeVertex	O(\|V\| + \|E\|)	O(\|V\|²)
addEdge	O(1)	O(1)
removeEdge (using Array)	O(\|E\|)	O(1)
removeEdge (using HashSet)	O(1)	O(1)
getAdjacents	O(\|E\|)	O(\|V\|)
isAdjacent (using Array)	O(\|E\|)	O(1)
isAdjacent (using HashSet)	O(1)	O(1)
Space Complexity	O(\|V\| + \|E\|)	O(\|V\|²)

Graphs Basics

Before we dive into interesting graph algorithms, let's first clarify the naming conventions and graph properties.

A graph is a data structure where a node can have zero or more adjacent elements.

The connection between two nodes is called edge. Nodes can also be called vertices.

The degree is the number of edges connected to a vertex. E.g., the purple vertex has a degree of 3 while the blue one has a degree of 1.

If the edges are bi-directional, then we have an undirected graph. But, if the edges have a direction, then we have a directed graph (or di-graph for short). You can think of it as a one-way street (directed) or two-way street (undirected).

Vertex can have edges that go to itself (e.g., blue node), this is called self-loop.

A graph can have cycles which means that if you traverse through the node, you could get the same node more than once. The graph without cycles is called acyclic graph.

Also, acyclic undirected graphs are called tree. We are going to cover trees in depth in the next post.

Not all vertices have to be connected in the graph. You might have isolated nodes or even separated subgraphs. If all nodes have at least one edge, then we have a connected graph. When all nodes are connected to all other nodes, then we have a complete graph.

For a complete graph, each node should have #nodes - 1 edges. In the previous example, we have seven vertices, so each node has six edges.

Graph Applications

When edges have values/cost assigned to them, we say we have a weighted graph. If the weight is absent, we can assume it's 1.

Weighted graphs have many applications depending on the domain where you need to solve a problem. To name a few:

Airline Traffic (image above)
- Node/vertex = Airport
- Edges = direct flights between two airports
- Weight = miles between two airports
GPS Navigation
- Node = road intersection
- Edge = road
- Weight = time required to go from one intersection to another
Networks routing
- Node = server
- Edge = data link
- Weight = connection speed

In general, graphs have many real-world applications like:

Electronic circuits
Flight reservations
Driving directions
Telcom: Cell tower frequency planning
Social networks. E.g., Facebook uses a graph for suggesting friends
Recommendations: Amazon/Netflix uses graphs to make suggestions for products/movies
Graphs help to plan the logistics of delivering goods

We just learned the basics of graphs and some applications. Let's cover how to represent graphs in JavaScript.

Representing graphs

There are two primary ways of representing a graph:

Adjacency list
Adjacency Matrix

Let's explain it with the following directed graph (digraph) as an example:

We digraph with 4 nodes. When a vertex has a link to itself (e.g. a) is called self-loop.

Adjacency Matrix

The adjacency matrix is one way of representing a graph using a two-dimensional array (NxN matrix). In the intersection of nodes, we add 1 (or other weight) if they are connected and 0 or - if they are not connected.

Using the same example as before, we can build the following adjacency matrix:

  a b c d e
a 1 1 - - -
b - - 1 - -
c - - - 1 -
d - 1 1 - -

As you can see, the matrix list all nodes horizontally and vertically. If there a few connections we called sparse graph if there are many connections (close to the max number of links) we called it dense graph. If all possible connections are reached, then we have a complete graph.

It's essential to notice that for undirected graphs the adjacency matrix will always be symmetrical by the diagonal. However, that's not still the case on a digraph (like our example).

What is the time complexity of finding connections of two vertices?

Querying if two nodes are connected in an adjacency matrix takes a constant time or O(1).

What is the space complexity?

Storing a graph as an adjacency matrix has a space complexity of O(n²), where n is the number of vertices. Also, represented as O(|V|²)

What is the runtime to add a vertex?

The vertices are stored as a V*xV* matrix. So, every time a vertex is added, the matrix needs to be reconstructed to a V+1*xV+1*.

Adding a vertex on an adjacency matrix is O(|V|²)

What about getting the adjacent nodes?

Since the matrix has a VxV matrix, to get all the adjacent nodes to a given vertex, we would have to go to the node row and get all its edges with the other nodes.

In our previous example, let's say we want all the adjacent nodes to b. We have to get the full row where b is with all the other nodes.

  a b c d e
b - - 1 - -

We have to visit all nodes so,

Getting adjacent nodes on an adjacency matrix is O(|V|)

Imagine that you need to represent the Facebook network as a graph. You would have to create a matrix of 2 billion x 2 billion, where most of it would be empty! Nobody would know everybody else just a few thousands at most.

In general, we deal with sparse graphs so the matrix will waste a lot of space. That's why in most implementation we would use an adjacency list rather than the matrix.

Adjacency List

Adjacency List is one of the most common ways to represent graphs. Each node has a list of all the nodes connected to it.

Graphs can be represented as an adjacency list using an Array (or HashMap) containing the nodes. Each of these node entries includes a list (array, linked list, set, etc.) that list its adjacent nodes.

For instance, in the graph above we have that a has a connection to b and also a self-loop to itself. In turn, b has a connection to c and so on:

a -> { a b }
b -> { c }
c -> { d }
d -> { b c }

As you can imagine if you want to know if a node is connected to another node, you would have to go through the list.

Querying if two nodes are connected in an adjacency list is O(n), where n is the number of vertices. Also represented as O(|V|)

What about space complexity?

Storing a graph as an adjacency list has a space complexity of O(n), where n is the sum of vertices and edges. Also, represented as O(|V| + |E|)

Adjacency List Graph HashMap Implementation

The adjacency list is the most common way of representing graphs. There are several ways to implement the adjacency list:

One of them is using a HashMap. The key is the value of the node, and the value is an array of adjacency.

const graph = {
  a: ['a', 'b'],
  b: ['c'],
  c: ['d'],
  d: ['b', 'c']
}

Graph usually needs the following operations:

Add and remove vertices
Add and remove edges

Adding and removing vertices involves updating the adjacency list.

Let's say that we want to remove the vertex b. We could do delete graph['b'];, however, we still have to remove the references on the adjacency list in "d" and "a".

Every time we remove a node, we would have to iterate through all the nodes' list O(|V| + |E|). Can we do better? We will answer that soon, but first, let's *implement our list in a more object-oriented way so we can swap implementations easily.

Adjacency List Graph OO Implementation

Let's start with the Node class that holds the vertex's value and its adjacent vertices. We can also have helper functions for adding and removing nearby nodes from the list.

class Node {
  constructor(value) {
    this.value = value;
    this.adjacents = []; // adjacency list
  }

  addAdjacent(node) {
    this.adjacents.push(node);
  }

  removeAdjacent(node) {
    const index = this.adjacents.indexOf(node);
    if(index > -1) {
      this.adjacents.splice(index, 1);
      return node;
    }
  }

  getAdjacents() {
    return this.adjacents;
  }

  isAdjacent(node) {
    return this.adjacents.indexOf(node) > -1;
  }
}

Notice that adjacent runtime is O(1), while remove adjacent is O(|E|). What if instead of an array we use a HashSet 🧐? It could be O(1). But, let first get it working and later we can make it faster.

Make it work. Make it right. Make it faster.

Ok, now that we have the Node class, let's build the Graph class that can perform operations such as adding/removing vertices and edges.

Graph.constructor

class Graph {
  constructor(edgeDirection = Graph.DIRECTED) {
    this.nodes = new Map();
    this.edgeDirection = edgeDirection;
  }
  // ...
}

Graph.UNDIRECTED = Symbol('directed graph'); // one-way edges
Graph.DIRECTED = Symbol('undirected graph'); // two-ways edges

The first thing that we need to know is if the graph is directed or undirected. That makes a difference when we are adding edges.

Graph.addEdge

To add an edge we need two nodes. One is the source, and the other is the destination.

  addEdge(source, destination) {
    const sourceNode = this.addVertex(source);
    const destinationNode = this.addVertex(destination);

    sourceNode.addAdjacent(destinationNode);

    if(this.edgeDirection === Graph.UNDIRECTED) {
      destinationNode.addAdjacent(sourceNode);
    }

    return [sourceNode, destinationNode];
  }

We add an edge from the source vertex to the destination. If we have an undirected graph, then we also add from target node to source since it's bidirectional.

The runtime of adding an edge from a graph adjacency list is: O(1)

If we try to add an edge and the nodes don't exist, we need to create them first. Let's do that next!

Graph.addVertex

The way we create a node is that we add it to the this.nodes Map. The map store a key/value pair, where the key is the vertex's value while the map value is the instance of the node class. Take a look at line 5-6:

  addVertex(value) {
    if(this.nodes.has(value)) {
      return this.nodes.get(value);
    } else {
      const vertex = new Node(value);
      this.nodes.set(value, vertex);
      return vertex;
    }
  }

If the node already exists we don't want to overwrite it. So, we first check if it already exists and if it doesn't, then we create it.

The runtime of adding a vertex from a graph adjacency list is: O(1)

Graph.removeVertex

Removing a node from the graph, it's a little bit more involved. We have to check if the node to be deleted it's in use as an adjacent node.

  removeVertex(value) {
    const current = this.nodes.get(value);
    if(current) {
      for (const node of this.nodes.values()) {
        node.removeAdjacent(current);
      }
    }
    return this.nodes.delete(value);
  }

We have to go through each vertex and then each adjacent node (edges).

The runtime of removing a vertex from a graph adjacency list is O(|V| + |E|)

Finally, let's remove implement removing an edge!

Graph.removeEdge

Removing an edge is pretty straightforward and similar to addEdge.

  removeEdge(source, destination) {
    const sourceNode = this.nodes.get(source);
    const destinationNode = this.nodes.get(destination);

    if(sourceNode && destinationNode) {
      sourceNode.removeAdjacent(destinationNode);

      if(this.edgeDirection === Graph.UNDIRECTED) {
        destinationNode.removeAdjacent(sourceNode);
      }
    }

    return [sourceNode, destinationNode];
  }

The main difference between addEdge and removeEdge is that:

If the vertices don't exist, we won't create them.
We use Node.removeAdjacent instead of Node.addAdjacent.

Since removeAdjacent has to go through all the adjacent vertices we have the following runtime:

The runtime of removing an edge from a graph adjacency list is O(|E|)

We are going to explore how to search for values from a node.

Breadth-first search (BFS) - Graph search

Breadth-first search is a way to navigate a graph from an initial vertex by visiting all the adjacent nodes first.

Let's see how we can accomplish this in code:

  *bfs(first) {
    const visited = new Map();
    const visitList = new Queue();

    visitList.add(first);

    while(!visitList.isEmpty()) {
      const node = visitList.remove();
      if(node && !visited.has(node)) {
        yield node;
        visited.set(node);
        node.getAdjacents().forEach(adj => visitList.add(adj));
      }
    }
  }

As you can see, we are using a Queue where the first node is also the first node to be visited (FIFO).

We are as well using JavaScript generators, notice the * in front of the function. This generator iterates one value at a time. That's useful for large graphs (millions of nodes) because in most cases you don't need to visit every single node.

This an example of how to use the BFS that we just created:

  const graph = new Graph(Graph.UNDIRECTED);

  const [first] = graph.addEdge(1, 2);
  graph.addEdge(1, 3);
  graph.addEdge(1, 4);
  graph.addEdge(5, 2);
  graph.addEdge(6, 3);
  graph.addEdge(7, 3);
  graph.addEdge(8, 4);
  graph.addEdge(9, 5);
  graph.addEdge(10, 6);

  bfsFromFirst = graph.bfs(first);

  bfsFromFirst.next().value.value; // 1
  bfsFromFirst.next().value.value; // 2
  bfsFromFirst.next().value.value; // 3
  bfsFromFirst.next().value.value; // 4
  // ...

You can find more illustrations of usage in the test cases. Let's move on to the DFS!

Depth-first search (DFS) - Graph search

Depth-first search is another way to navigate a graph from an initial vertex by recursively the first adjacent node of each vertex found.

The iterative implementation of a DFS is identical to the BFS, but instead of using a Queue you use a Stack:

  *dfs(first) {
    const visited = new Map();
    const visitList = new Stack();

    visitList.add(first);

    while(!visitList.isEmpty()) {
      const node = visitList.remove();
      if(node && !visited.has(node)) {
        yield node;
        visited.set(node);
        node.getAdjacents().forEach(adj => visitList.add(adj));
      }
    }
  }

We can test our graph as follow.

  const graph = new Graph(Graph.UNDIRECTED);

  const [first] = graph.addEdge(1, 2);
  graph.addEdge(1, 3);
  graph.addEdge(1, 4);
  graph.addEdge(5, 2);
  graph.addEdge(6, 3);
  graph.addEdge(7, 3);
  graph.addEdge(8, 4);
  graph.addEdge(9, 5);
  graph.addEdge(10, 6);

  dfsFromFirst = graph.dfs(first);
  visitedOrder = Array.from(dfsFromFirst);
  const values = visitedOrder.map(node => node.value);
  console.log(values); // [1, 4, 8, 3, 7, 6, 10, 2, 5, 9]

As you can see the graph is the same on BFS and DFS, however, the order how the nodes were visited is very different. BFS went from 1 to 10 in that order, while DFS went as deep as it could on each node.

Graph Time and Space Complexity

We have seen some of the basic operations of a Graph. How to add and remove vertices and edges. Here's a summary of what we have covered so far:

	Adjacency List	Adjacency Matrix
Space	O(\|V\| + \|E\|)	O(\|V\|²)
addVertex	O(1)	O(\|V\|²)
removeVertex	O(\|V\| + \|E\|)	O(\|V\|²)
addEdge	O(1)	O(1)
removeEdge (using Array)	O(\|E\|)	O(1)
removeEdge (using HashSet)	O(1)	O(1)
getAdjacents	O(\|E\|)	O(\|V\|)
isAdjacent (using Array)	O(\|E\|)	O(1)
isAdjacent (using HashSet)	O(1)	O(1)

As you can see, an adjacency list is faster in almost all operations. The only action that the adjacency matrix will outperform the adjacency list is checking if a node is adjacent to other. However, if we change our implementation from Array to a HashSet, we can get it in constant time as well :)

Summary

As we saw, Graphs can help to model many real-life scenarios such as airports, social networks, internet and so on. We covered some of the most fundamental algorithms such as Breadth-First Search (BFS) and Depth-First Search (DFS). Also, we studied about implementations trade-offs such as adjacency list and matrix. Subscribe to my newsletter and don't miss any of my posts, because there are many other applications that we are going to learn soon, such as finding the shortest path between nodes and different exciting graph algorithms!

Data Structures in JavaScript: Arrays, HashMaps, and Lists

Adrian Mejia — Sat, 28 Apr 2018 23:20:40 +0000

When we are developing software, we have to store data in memory. However, there are many types of data structures, such as arrays, maps, sets, lists, trees, graphs, etc. and choosing the right one for the task can be tricky. So, this series of posts will help you to know the trade-offs, so, you can use the right tool for the job!

On this section, we are going to focus on linear data structures: Arrays, Lists, Sets, Stacks, and Queues.

You can find all these implementations and more in the Github repo:

amejiarosario / dsa.js-data-structures-algorithms-javascript

🥞Data Structures and Algorithms explained and implemented in JavaScript + eBook

Data Structures and Algorithms in JavaScript

This is the coding implementations of the DSA.js book and the repo for the NPM package.

In this repository, you can find the implementation of algorithms and data structures in JavaScript. This material can be used as a reference manual for developers, or you can refresh specific topics before an interview. Also, you can find ideas to solve problems more efficiently.

Installation

You can clone the repo or install the code from NPM:

npm install dsa.js

and then you can import it into your programs or CLI

const { LinkedList, Queue, Stack } = require('dsa.js');

For a list of all available data structures and algorithms, see index.js.

Features

Algorithms are an essential…

View on GitHub

Data Structures Big-O Cheatsheet

The following table is a summary of everything that we are going to cover here.

Bookmark it, pin it or share it, so you have it at hand when you need it.

Click on the **name* to go the section or click on the runtime to go the implementation*

* = Amortized runtime

Name	Insert	Access	Search	Delete	Comments
Array	O(n)	O(1)	O(n)	O(n)	Insertion to the end is `O(1)`. Details here.
HashMap	O(1)	O(1)	O(1)	O(1)	Rehashing might affect insertion time. Details here.
Map (using Binary Search Tree)	O(log(n))	-	O(log(n))	O(log(n))	Implemented using Binary Search Tree
Set (using HashMap)	O(1)	-	O(1)	O(1)	Set using a HashMap implementation. Details here.
Set (using list)	O(n)	-	O(n)	O(n)	Implemented using Binary Search Tree
Set (using Binary Search Tree)	O(log(n))	-	O(log(n))	O(log(n))	Implemented using Binary Search Tree
Linked List (singly)	O(n)	-	O(n)	O(n)	Adding/Removing to the start of the list is `O(1)`. Details here.
Linked List (doubly)	O(n)	-	O(n)	O(n)	Adding/Deleting from the beginning/end is `O(1)`. But, deleting/adding from the middle is `O(n)`. Details here
Stack (array implementation)	O(1)	-	-	O(1)	Insert/delete is last-in, first-out (LIFO)
Queue (naive array impl.)	O(n)	-	-	O(1)	Insert (`Array.shift`) is O(n)
Queue (array implementation)	O(1)	-	-	O(1)	Worst time insert is O(n). However amortized is O(1)
Queue (list implementation)	O(1)	-	-	O(1)	Using Doubly Linked List with reference to the last element.

Note: Binary search trees and trees, in general, will be cover in the next post. Also, graph data structures.

Primitive Data Types

Primitive data types are the most basic elements where all the other data structures are built upon. Some primitives are:

Integers. E.g., 1, 2, 3, ...
Characters. E.g., a, b, "1", "*"
Booleans. E.g., true or false.
Float (floating points) or doubles. E.g., 3.14159, 1483e-2.
Null values. E.g. null

JavaScript specific primitives:

undefined
Symbol
Number

Note: Objects are not primitive since it's a collection of zero or more primitives and other objects.

Array

Arrays are collections of zero or more elements. Arrays are one of the most used data structure because of its simplicity and fast way of retrieving information.

You can think of an array as a drawer where you can store things on the bins.

Array is like a drawer that stores things on bins

When you want to search for something you can go directly to the bin number. That's a constant time operation (O(1)). However, if you forgot what cabinet had, then you will have to open one by one (O(n)) to verify its content until you find what you are looking for. That same happens with an array.

Depending on the programming language, arrays have some differences. For some dynamic languages like JavaScript and Ruby, an array can contain different data types: numbers, strings, words, objects, and even functions. In typed languages like Java/C/C++, you have to predefine the size of the array and the data type. In JavaScript, it would automatically increase the size of the array when needed.

Arrays built-in operations

Depending on the programming language, the implementation would be slightly different.

For instance, in JavaScript, we can accomplish append to end with push and append to the beginning with unshift. But also, we have pop and shift to remove from an array. Let's describe the runtime of some common operations that we are going to use through this post.

Common JS Array built-in functions

Function	Runtime	Description
array.push	O(1)	Insert element to the end of the array
array.pop	O(1)	Remove element to the end of the array
array.shift	O(n)	Remove element to the beginning of the array
array.unshift	O(n)	Insert element(s) to the beginning of the array
array.slice	O(n)	Returns a copy of the array from `beginning` to `end`.
array.splice	O(n)	Changes (add/remove) the array

Insert element on an array

There are multiple ways to insert elements into an array. You can append new data to end, or you can add it to the beginning of the collection.

Let's start with append to tail:

function insertToTail(array, element) {
  array.push(element);
  return array;
}

const array = [1, 2, 3];
console.log(insertToTail(array, 4)); // => [ 1, 2, 3, 4 ]

Based on the language specification, push just set the new value at the end of the array. Thus,

The Array.push runtime is a O(1)

Let's now try appending to head:

function insertToHead(array, element) {
  array.unshift(element);
  return array;
}

const array = [1, 2, 3];
console.log(insertToHead(array, 0)); // => [ 0, 1, 2, 3 ]

What do you think is the runtime of the insertToHead function? Looks the same as the previous one except that we are using unshift instead of push. But, there's a catch! unshift algorithm makes room for the new element by moving all existing ones to the next position in the array. So, it will iterate through all the items and move them.

The Array.unshift runtime is an O(n)

Access an element in an array

If you know the index for the element that you are looking for, then you can access the element directly like this:

function access(array, index) {
  return array[index];
}

const array = [1, 'word', 3.14, {a: 1}];
access(array, 0); // => 1
access(array, 3); // => {a: 1}

As you can see in the code above, accessing an element on an array has a constant time:

Array access runtime is O(1)

Note: You can also change any value at a given index in constant time.

Search an element in an array

If you don't know the index of the data that you want from an array, then you have to iterate through each element on the collection until we find what we are looking for.

function search(array, element) {
  for (let index = 0; index < array.length; index++) {
    if(element === array[index]) {
      return index;
    }
  }
}

const array = [1, 'word', 3.14, {a: 1}];
console.log(search(array, 'word')); // => 1
console.log(search(array, 3.14)); // => 2

Given the for-loop, we have:

Array search runtime is O(n)

Deleting elements from an array

What do you think is the running time of deleting an element from an array?

Well, let's think about the different cases:

You can delete from the end of the array which might be constant time. O(1)
However, you can also remove from the beginning or middle of the collection. In that case, you would have to move all the following elements to close the gap. O(n)

Talk is cheap, let's do the code!

function remove(array, element) {
  const index = search(array, element);
  array.splice(index, 1);
  return array;
}

const array1 = [0, 1, 2, 3];
console.log(remove(array1, 1)); // => [ 0, 2, 3 ]

So we are using our search function to find the elements' index O(n). Then we use the JS built-in splice function which has a running time of O(n). So, we are going to iterate through the list twice, but instead of saying O(2n), for big o notation it's still O(n). Remember from our first post that constants don't matter as much.

We take the worst case scenario:

Deleting an item from an array is O(n).

Array operations time complexity

We can sum up the arrays time complexity as follows:

Array Time Complexities

Operation	Worst
Access (`Array.[]`)	`O(1)`
Insert head (`Array.unshift`)	`O(n)`
Insert tail (`Array.push`)	`O(1)`
Search (for value)	`O(n)`
Delete (`Array.splice`)	`O(n)`

HashMaps

HashMaps has many names like HashTable, HashMap, Map, Dictionary, Associative Arrays and so on. The concept is the same while the implementation might change slightly.

Hashtable is a data structure that maps keys to values

Going back to the drawer analogy, bins have a label rather than a number.

HashMap is like a drawer that stores things on bins and labels them

In this example, if you are looking for the DSA.js book, you don't have to open the bin 1, 2, and 3 to see what's inside. You go directly to the container labeled as "books". That's a huge gain! Search time goes from O(n) to O(1).

In arrays, the data is referenced using a numeric index (relatively to the position). However, HashMaps uses labels that could be a string, number, object or anything. Internally, the HashMap uses an Array, and it maps the labels to array indexes using a hash function.

There are at least two ways to implement a Map:

Array: Using a hash function to map a key to the array index value. A.k.a HashMap. Worst: O(n), Average: O(1)
Binary Search Tree: using a self-balancing binary search tree to look up for values (more on this later). A.k.a TreeMap. Worst: O(log n), Average: O(log n).

We are going to cover Trees & Binary Search Trees, so don't worry about it for now. The most common implementation of Maps is using an array and hash function. So, that's the one we are going to focus on.

HashMap implemented with an array

As you can see in the image, each key gets translated into a hash code. Since the array size is limited (e.g., 10), we have to loop through the available buckets using modulus function. In the buckets, we store the key/value pair, and if there's more than one, we use a collection to hold them.

Now, What do you think about covering each of the HashMap components in details? Let's start with the hash function.

HashMap vs. Array

Why go through the trouble of converting the key into an index and not using an array directly you might ask. Well, the main difference is that the Array's index doesn't have any relationship with the data. You have to know where your data is.

Let's say you want to count how many times words are used in a text. How would you implement that?

You can use two arrays (let's call it A and B). One for storing the word and another for storing how many times they have seen (frequency).
You can use a HashMap. They key is the word, and the value is the frequency of the word.

What is the runtime of approach #1 using two arrays? If we say, the number of words in the text is n. Then we have to search if the word in the array A and then increment the value on array B matching that index. For every word on n we have to test if it's already on array A. This double loop leave use with a runtime of O(n²).

What is the runtime of approach #2 using a HashMap? Well, we iterate through each word on the text once and increment the value if there is something there or set it to 1 if that word is seen for the first time. The runtime would be O(n) which is much more performant than approach #1.

Differences between HashMap and Array

Search on an array is O(n) while on a HashMap is O(1)
Arrays can have duplicate values, while HashMap cannot have duplicated keys (but they can have duplicate values.)
The array has a key (index) that is always a number from 0 to max value, while in a HashMap you have control of the key and it can be whatever you want: number, string, or symbol.

Hash Function

The first step to implement a HashMap is to have a hash function. This function will map every key to its value.

The perfect hash function is the one that for every key it assigns a unique index.

Ideal hashing algorithms allow constant time access/lookup. However, it's hard to achieve a perfect hashing function in practice. You might have the case where two different keys yields on the same index. This is called collision.

Collisions in HashMaps are unavoidable when using an array-like underlying data structure. At some point, data can't fit in a HashMap will reuse data slots. One way to deal with collisions is to store multiple values in the same bucket using a linked list or another array (more on this later). When we try to access the key's value and found various values, we iterate over the values O(n). However, in most implementations, the hash adjusts the size dynamically to avoid too many collisions. So, we can say that the amortized lookup time is O(1). We are going to explain what we mean by amortized runtime later on this post with an example.

Naïve HashMap implementation

A simple (and bad) hash function would be this one:

class NaiveHashMap {

  constructor(initialCapacity = 2) {
    this.buckets = new Array(initialCapacity);
  }

  set(key, value) {
    const index = this.getIndex(key);
    this.buckets[index] = value;
  }

  get(key) {
    const index = this.getIndex(key);
    return this.buckets[index];
  }

  hash(key) {
    return key.toString().length;
  }

  getIndex(key) {
    const indexHash = this.hash(key);
    const index = indexHash % this.buckets.length;
    return index;
  }
}

We are using buckets rather than drawer/bins, but you get the idea :)

We have an initial capacity of 2 (buckets). But, we want to store any number of elements on them. We use modulus % to loop through the number of available buckets.

Take a look at our hash function. We are going to talk about it in a bit. First, let's use our new HashMap!

// Usage:
const assert = require('assert');
const hashMap = new NaiveHashMap();

hashMap.set('cat', 2);
hashMap.set('rat', 7);
hashMap.set('dog', 1);
hashMap.set('art', 8);

console.log(hashMap.buckets);
/*
  bucket #0: <1 empty item>,
  bucket #1: 8
*/

assert.equal(hashMap.get('art'), 8); // this one is ok
assert.equal(hashMap.get('cat'), 8); // got overwritten by art 😱
assert.equal(hashMap.get('rat'), 8); // got overwritten by art 😱
assert.equal(hashMap.get('dog'), 8); // got overwritten by art 😱

This Map allows us to set a key and a value and then get the value using a key. The key part is the hash function. Let's see multiple implementations to see how it affects the performance of the Map.

Can you tell what's wrong with NaiveHashMap before looking to the answer below?

What is wrong with NaiveHashMap is that...

1) Hash function generates many duplicates. E.g.

hash('cat') // 3
hash('dog') // 3

This will cause a lot of collisions.

2) Collisions are not handled at all. Both cat and dog will overwrite each other on the position 3 of the array (bucket#1).

3) Size of the array even if we get a better hash function we will get duplicates because the array has a size of 3 which less than the number of elements that we want to fit. We want to have an initial capacity that is well beyond what we need to fit.

Improving Hash Function

The primary purpose of a HashMap is to reduce the search/access time of an Array from O(n) to O(1).

For that we need:

A proper hash function that produces as few collisions as possible.
An array big enough to hold all the required values.

Let's give it another shot to our hash function. Instead of using the length of the string, let's sum each character ascii code.

  hash(key) {
    let hashValue = 0;
    const stringKey = key.toString();

    for (let index = 0; index < stringKey.length; index++) {
      const charCode = stringKey.charCodeAt(index);
      hashValue += charCode;
    }

    return hashValue;
  }

Let's try again:

hash('cat') // 312  (c=99 + a=97 + t=116)
hash('dog') // 314 (d=100 + o=111 + g=103)

This one is better! Because words with the same length has different code.

Howeeeeeeeeever, there's still an issue! Because rat and art are both 327, collision! 💥

We can fix that by offsetting the sum with the position:

  hash(key) {
    let hashValue = 0;
    const stringKey = `${key}`;

    for (let index = 0; index < stringKey.length; index++) {
      const charCode = stringKey.charCodeAt(index);
      hashValue += charCode << (index * 8);
    }

    return hashValue;
  }

Now let's try again, this time with hex numbers so we can see the offset.

// r = 114 or 0x72; a = 97 or 0x61; t = 116 or 0x74
hash('rat'); // 7,627,122 (r: 114 * 1 + a: 97 * 256 + t: 116 * 65,536) or in hex: 0x726174 (r: 0x72 + a: 0x6100 + t: 0x740000)
hash('art'); // 7,631,457 or 0x617274

What about different types?

hash(1); // 49
hash('1'); // 49

hash('1,2,3'); // 741485668
hash([1,2,3]); // 741485668

hash('undefined') // 3402815551
hash(undefined) // 3402815551

Houston, we still have a problem!! Different values types shouldn't return the same hash code!

How can we solve that?

One way is taking into account the key type into the hash function.

  hash(key) {
    let hashValue = 0;
    const stringTypeKey = `${key}${typeof key}`;

    for (let index = 0; index < stringTypeKey.length; index++) {
      const charCode = stringTypeKey.charCodeAt(index);
      hashValue += charCode << (index * 8);
    }

    return hashValue;
  }

Let's test that again:

console.log(hash(1)); // 1843909523
console.log(hash('1')); // 1927012762

console.log(hash('1,2,3')); // 2668498381
console.log(hash([1,2,3])); // 2533949129

console.log(hash('undefined')); // 5329828264
console.log(hash(undefined)); // 6940203017

Yay!!! 🎉 we have a much better hash function!

We also can change the initial capacity of the array to minimize collisions. Let's put all of that together in the next section.

Decent HashMap Implementation

Using our optimized hash function we can now do much better.

We could still have collisions so let's implement something to handle them

Let's make the following improvements to our HashMap implementation:

Hash function that checks types and character orders to minimize collisions.
Handle collisions by appending values to a list. We also added a counter to keep track of them.

class DecentHashMap {

  constructor(initialCapacity = 2) {
    this.buckets = new Array(initialCapacity);
    this.collisions = 0;
  }

  set(key, value) {
    const bucketIndex = this.getIndex(key);
    if(this.buckets[bucketIndex]) {
      this.buckets[bucketIndex].push({key, value});
      if(this.buckets[bucketIndex].length > 1) { this.collisions++; }
    } else {
      this.buckets[bucketIndex] = [{key, value}];
    }
    return this;
  }

  get(key) {
    const bucketIndex = this.getIndex(key);
    for (let arrayIndex = 0; arrayIndex < this.buckets[bucketIndex].length; arrayIndex++) {
      const entry = this.buckets[bucketIndex][arrayIndex];
      if(entry.key === key) {
        return entry.value
      }
    }
  }

  hash(key) {
    let hashValue = 0;
    const stringTypeKey = `${key}${typeof key}`;

    for (let index = 0; index < stringTypeKey.length; index++) {
      const charCode = stringTypeKey.charCodeAt(index);
      hashValue += charCode << (index * 8);
    }

    return hashValue;
  }

  getIndex(key) {
    const indexHash = this.hash(key);
    const index = indexHash % this.buckets.length;
    return index;
  }
}

Let's use it and see how it perform:

// Usage:
const assert = require('assert');
const hashMap = new DecentHashMap();

hashMap.set('cat', 2);
hashMap.set('rat', 7);
hashMap.set('dog', 1);
hashMap.set('art', 8);

console.log('collisions: ', hashMap.collisions); // 2
console.log(hashMap.buckets);
/*
  bucket #0: [ { key: 'cat', value: 2 }, { key: 'art', value: 8 } ]
  bucket #1: [ { key: 'rat', value: 7 }, { key: 'dog', value: 1 } ]
*/

assert.equal(hashMap.get('art'), 8); // this one is ok
assert.equal(hashMap.get('cat'), 2); // Good. Didn't got overwritten by art
assert.equal(hashMap.get('rat'), 7); // Good. Didn't got overwritten by art
assert.equal(hashMap.get('dog'), 1); // Good. Didn't got overwritten by art

This DecentHashMap gets the job done, but, there are still some issues. We are using a decent hash function that doesn't produce duplicate values, and that's great. However, we have two values in bucket#0 and two more in bucket#1. How is that possible?

Since we are using a limited bucket size of 2, we use modulus % to loop through the number of available buckets. So, even if the hash code is different, all values will fit on the size of the array: bucket#0 or bucket#1.

hash('cat') => 3789411390; bucketIndex => 3789411390 % 2 = 0
hash('art') => 3789415740; bucketIndex => 3789415740 % 2 = 0
hash('dog') => 3788563007; bucketIndex => 3788563007 % 2 = 1
hash('rat') => 3789411405; bucketIndex => 3789411405 % 2 = 1

So naturally we have increased the initial capacity but by how much? Let's see how the initial size affects the hash map performance.

If we have an initial capacity of 1. All the values will go into one bucket (bucket#0), and it won't be any better than searching a value in a simple array O(n).

Let's say that we start with an initial capacity set to 10:

const hashMapSize10 = new DecentHashMap(10);

hashMapSize10.set('cat', 2);
hashMapSize10.set('rat', 7);
hashMapSize10.set('dog', 1);
hashMapSize10.set('art', 8);

console.log('collisions: ', hashMapSize10.collisions); // 1
console.log('hashMapSize10\n', hashMapSize10.buckets);
/*
  bucket#0: [ { key: 'cat', value: 2 }, { key: 'art', value: 8 } ],
            <4 empty items>,
  bucket#5: [ { key: 'rat', value: 7 } ],
            <1 empty item>,
  bucket#7: [ { key: 'dog', value: 1 } ],
            <2 empty items>
*/

Another way to see this

As you can see, we reduced the number of collisions (from 2 to 1) by increasing the initial capacity of the hash map.

Let's try with a bigger capacity 💯:

const hashMapSize100 = new DecentHashMap(100);

hashMapSize100.set('cat', 2);
hashMapSize100.set('rat', 7);
hashMapSize100.set('dog', 1);
hashMapSize100.set('art', 8);

console.log('collisions: ', hashMapSize100.collisions); // 0
console.log('hashMapSize100\n', hashMapSize100.buckets);
/*
            <5 empty items>,
  bucket#5: [ { key: 'rat', value: 7 } ],
            <1 empty item>,
  bucket#7: [ { key: 'dog', value: 1 } ],
            <32 empty items>,
  bucket#41: [ { key: 'art', value: 8 } ],
            <49 empty items>,
  bucket#90: [ { key: 'cat', value: 2 } ],
            <9 empty items>
*/

Yay! 🎊 no collision!

Having a bigger bucket size is excellent to avoid collisions, but it consumes too much memory, and probably most of the buckets will be unused.

Wouldn't it be great, if we can have a HashMap that automatically increases its size as needed? Well, that's called rehash, and we are going to do it next!

Optimal HashMap Implementation

If we have a big enough bucket we won't have collisions thus the search time would be O(1). However, how do we know how big a hash map capacity should big? 100? 1,000? A million?

Having allocated massive amounts of memory is impractical. So, what we can do is to have the hash map automatically resize itself based on a load factor. This operation is called Rehash.

The load factor is the measurement of how full is a hash map. We can get the load factor by dividing the number of items by the bucket size.

This will be our latest and greatest hash map implementation:

Optimized Hash Map Implementation

github.com/amejiarosario/dsa.js/blob/master/src/data-structures/maps/hash-maps/hash-map.js

Pay special attention to the rehash method. That's where the magic happens. We create a new HashMap with doubled capacity.

So, testing our new implementation from above ^

const assert = require('assert');
const hashMap = new HashMap();

assert.equal(hashMap.getLoadFactor(), 0);
hashMap.set('songs', 2);
hashMap.set('pets', 7);
hashMap.set('tests', 1);
hashMap.set('art', 8);
assert.equal(hashMap.getLoadFactor(), 4/16);

hashMap.set('Pineapple', 'Pen Pineapple Apple Pen');
hashMap.set('Despacito', 'Luis Fonsi');
hashMap.set('Bailando', 'Enrique Iglesias');
hashMap.set('Dura', 'Daddy Yankee');

hashMap.set('Lean On', 'Major Lazer');
hashMap.set('Hello', 'Adele');
hashMap.set('All About That Bass', 'Meghan Trainor');
hashMap.set('This Is What You Came For', 'Calvin Harris ');

assert.equal(hashMap.collisions, 2);
assert.equal(hashMap.getLoadFactor(), 0.75);
assert.equal(hashMap.buckets.length, 16);

hashMap.set('Wake Me Up', 'Avicii'); // <--- Trigger REHASH

assert.equal(hashMap.collisions, 0);
assert.equal(hashMap.getLoadFactor(), 0.40625);
assert.equal(hashMap.buckets.length, 32);

Take notice that after we add the 12th item, the load factor gets beyond 0.75, so a rehash is triggered and doubles the capacity (from 16 to 32). Also, you can see how the number of collisions improves from 2 to 0!

This implementation is good enough to help us to figure out the runtime of common operations like insert/search/delete/edit.

To sum up, the performance of a HashMap will be given by:

The hash function that every key produces for different output.
Size of the bucket to hold data.

We nailed both 🔨. We have a decent hash function that produces different output for different data. Two distinct data will never return the same code. Also, we have a rehash function that automatically grows the capacity as needed. That's great!

Insert element on a HashMap runtime

Inserting an element on a HashMap requires two things: a key and a value. We could use our DecentHashMap data structure that we develop or use the built-in as follows:

function insert(object, key, value) {
  object[key] = value;
  return object;
}

const object = {};
console.log(insert(hash, 'word', 1)); // => { word: 1 }

In modern JavaScript, you can use Maps.

function insertMap(map, key, value) {
  map.set(key, value);
  return map;
}

const map = new Map();
console.log(insertMap(map, 'word', 1)); // Map { 'word' => 1 }

Note: We are going to use the Map rather than regular Object, since the Map's key could be anything while on Object's key can only be string or number. Also, Maps keeps the order of insertion.

Behind the scenes, the Map.set just insert elements into an array (take a look at DecentHashMap.set). So, similar to Array.push we have that:

Insert an element in HashMap runtime is O(1). If rehash is needed, then it will take O(n)

Our implementation with rehash functionality will keep collisions to the minimum. The rehash operation takes O(n) but it doesn't happen all the time only when is needed.

Search/Access an element on a HashMap runtime

This is the HashMap.get function that we use to get the value associated with a key. Let's evaluate the implementation from DecentHashMap.get):

  get(key) {
    const hashIndex = this.getIndex(key);
    const values = this.array[hashIndex];
    for (let index = 0; index < values.length; index++) {
      const entry = values[index];
      if(entry.key === key) {
        return entry.value
      }
    }
  }

If there's no collision, then values will only have one value and the access time would be O(1). But, we know there will be collisions. If the initial capacity is too small and the hash function is terrible like NaiveHashMap.hash then most of the elements will end up in a few buckets O(n).

HashMap access operation has a runtime of O(1) on average and worst-case of O(n).

Advanced Note: Another idea to reduce the time to get elements from O(n) to O(log n) is to use a binary search tree instead of an array. Actually, Java's HashMap implementation switches from an array to a tree when a bucket has more than 8 elements.

Edit/Delete element on a HashMap runtime

Editing (HashMap.set) and deleting (HashMap.delete) key/value pairs have an amortized runtime of O(1). In the case of many collisions, we could face an O(n) as a worst case. However, with our rehash operation, we can mitigate that risk.

HashMap edits and delete operations has a runtime of O(1) on average and worst-case of O(n).

HashMap operations time complexity

We can sum up the arrays time complexity as follows:

HashMap Time Complexities

Operation	Worst	Amortized	Comments
Access/Search (`HashMap.get`)	`O(n)`	`O(1)`	`O(n)` is an extreme case when there are too many collisions
Insert/Edit (`HashMap.set`)	`O(n)`	`O(1)`	`O(n)` only happens with rehash when the Hash is 0.75 full
Delete (`HashMap.delete`)	`O(n)`	`O(1)`	`O(n)` is an extreme case when there are too many collisions

Sets

Sets are very similar to arrays. The difference is that they don't allow duplicates.

How can we implement a Set (array without duplicates)? Well, we could use an array and check if an element is there before inserting a new one. But the running time of checking if an item is already there is O(n). Can we do better than that? We develop the Map that has an amortized run time of O(1)!

Set Implementation

We could use the JavaScript built-in Set. However, if we implement it by ourselves, it's more logic to deduct the runtimes. We are going to use the optimized HashMap with rehash functionality.

const HashMap = require('../hash-maps/hash-map');

class MySet {
  constructor() {
    this.hashMap = new HashMap();
  }

  add(value) {
    this.hashMap.set(value);
  }

  has(value) {
    return this.hashMap.has(value);
  }

  get size() {
    return this.hashMap.size;
  }

  delete(value) {
    return this.hashMap.delete(value);
  }

  entries() {
    return this.hashMap.keys.reduce((acc, key) => {
      if(key !== undefined) {
        acc.push(key.content);
      }
      return acc
    }, []);
  }
}

We used HashMap.set to add the set elements without duplicates. We use the key as the value, and since hash maps keys are unique we are all set.

Checking if an element is already there can be done using the hashMap.has which has an amortized runtime of O(1). The most operations would be an amortized constant time except for getting the entries which is O(n).

Note: The JS built-in Set.has has a runtime of O(n), since it uses a regular list of elements and checks each one at a time. You can see the Set.has algorithm here

Here some examples how to use it:

const assert = require('assert');
// const set = new Set(); // Using the built-in
const set = new MySet(); // Using our own implementation

set.add('one');
set.add('uno');
set.add('one'); // should NOT add this one twice

assert.equal(set.has('one'), true);
assert.equal(set.has('dos'), false);

assert.equal(set.size, 2);
// assert.deepEqual(Array.from(set), ['one', 'uno']);

assert.equal(set.delete('one'), true);
assert.equal(set.delete('one'), false);
assert.equal(set.has('one'), false);
assert.equal(set.size, 1);

You should be able to use MySet and the built-in Set interchangeably for these examples.

Set Operations runtime

From our Set implementation using a HashMap we can sum up the time complexity as follows (very similar to the HashMap):

Set Time Complexities

Operation	Worst	Amortized	Comments
Access/Search (`Set.has`)	`O(n)`	`O(1)`	`O(n)` is an extreme case when there are too many collisions
Insert/Edit (`Set.add`)	`O(n)`	`O(1)`	`O(n)` only happens with rehash when the Hash is 0.75 full
Delete (`Set.delete`)	`O(n)`	`O(1)`	`O(n)` is an extreme case when there are too many collisions

Linked Lists

Linked List is a data structure where every element is connected to the next one.

The linked list is the first data structure that we are going to implement without using an array. Instead, we are going to use a node which holds a value and points to the next element.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

When we have a chain of nodes where each one points to the next one, then we a Singly Linked list.

Singly Linked Lists

For a singly linked list, we only have to worry about every element having a reference to the next one.

We start by constructing the root or head element.

class LinkedList {
  constructor() {
    this.root = null;
  }

  // ...
}

There are four basic operations that we can do in every Linked List:

addLast: appends an element to the end of the list (tail)
removeLast: deletes element to the end of the list
addFirst: Adds an element to the beginning of the list (head)
removeFirst: Removes an element from the start of the list (head/root)

Adding/Removing an element at the end of a linked list

There are two primary cases:

If the list first (root/head) doesn't have any element yet, we make this node the head of the list.
Contrary, if the list already has items, then we have to iterate until finding the last one and appending our new node to the end.

  addLast(value) { // similar Array.push
    const node = new Node(value);

    if(this.root) {
      let currentNode = this.root;
      while(currentNode && currentNode.next) {
        currentNode = currentNode.next;
      }
      currentNode.next = node;
    } else {
      this.root = node;
    }
  }

What's the runtime of this code? If it is the first element, then adding to the root is O(1). However, finding the last item is O(n).

Now, removing an element from the end of the list has similar code. We have to find the current before last and make its next reference null.

  removeLast() {
    let current = this.root;
    let target;

    if(current && current.next) {
      while(current && current.next && current.next.next) {
        current = current.next;
      }
      target = current.next;
      current.next = null;
    } else {
      this.root = null;
      target = current;
    }

    if(target) {
      return target.value;
    }
  }

The runtime again is O(n) because we have to iterate until the second-last element and remove the reference to the last (line 10).

Adding/Removing an element from the beginning of a linked list

Adding an element to the head of the list is like this:

  addFirst(value) {
    const node = new Node(value);
    node.next = this.first;
    this.first = node;
  }

Adding and removing elements from the beginning is a constant time because we hold a reference to the first element:

  addFirst(value) {
    const node = new Node(value);
    node.next = this.first;
    this.first = node;
  }

As expected, the runtime for removing/adding to the first element from a linked List is always constant O(1)

Removing an element anywhere from a linked list

Removing an element anywhere in the list leverage the removeLast and removeFirst. However, if the removal is in the middle, then we assign the previous node to the next one. That removes any reference from the current node; this is removed from the list:

  remove(index = 0) {
    if(index === 0) {
      return this.removeFirst();
    }

    for (let current = this.first, i = 0; current;  i++, current = current.next) {
      if(i === index) {
        if(!current.next) { // if it doesn't have next it means that it is the last
          return this.removeLast();
        }
        current.previous = current.next;
        this.size--;
        return current.value;
      }
    }
  }

Note that index is a zero-based index: 0 will be the first element, 1 second and so on.

Removing an element anywhere within the list is O(n).

Searching for an element in a linked list

Searching an element on the linked list is very somewhat similar to remove:

  contains(value) {
    for (let current = this.first, index = 0; current;  index++, current = current.next) {
      if(current.value === value) {
        return index;
      }
    }
  }

This function finds the first element with the given value.

The runtime for searching an element in a linked list is O(n)

Singly Linked Lists time complexity

Singly Linked List time complexity per function is as follows.

Operation	Runtime	Comment
`addFirst`	O(1)	Insert element to the beginning of the list
`addLast`	O(n)	Insert element to the end of the list
`add`	O(n)	Insert element anywhere in the list.
`removeFirst`	O(1)	Remove element to the beginning of the list
`removeLast`	O(n)	Remove element to the end of the list
`remove`	O(n)	Remove any element from the list
`contains`	O(n)	Search for an element from the list

Notice that every time we are adding/removing from the last position the operation takes O(n)...

But we could reduce the addLast/removeLast from O(n) to a flat O(1) if we keep a reference of the last element!

We are going to add the last reference in the next section!

Doubly Linked Lists

When we have a chain of nodes where each one points to the next one we a Singly Linked list. When we have a linked list where each node leads to the next and the previous element we a Doubly Linked List

Doubly linked list nodes have double references (next and previous). We are also going to keep track of the list first and the last element.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.previous = null;
  }
}

class LinkedList {
  constructor() {
    this.first = null; // head/root element
    this.last = null; // last element of the list
    this.size = 0; // total number of elements in the list
  }

  // ...
}

Adding and Removing from the start of a list

Adding and removing from the start of the list is simple since we have this.first reference:

  addFirst(value) {
    const node = new Node(value);

    node.next = this.first;

    if(this.first) {
      this.first.previous = node;
    } else {
      this.last = node;
    }

    this.first = node; // update head
    this.size++;

    return node;
  }

Notice, that we have to be very careful and update the previous, size and last.

  removeFirst() {
    const first = this.first;

    if(first) {
      this.first = first.next;
      if(this.first) {
        this.first.previous = null;
      }

      this.size--;

      return first.value;
    } else {
      this.last = null;
    }
  }

What's the runtime?

Adding and removing elements from a (singly/doubly) LinkedList has a constant runtime O(1)

Adding and removing from the end of a list

Adding and removing from the end of the list is a little tricky. If you checked in the Singly Linked List, both operations took O(n) since we had to loop through the list to find the last element. Now, we have the last reference:

  addLast(value) {
    const node = new Node(value);

    if(this.first) {
      let currentNode = this.first;
      node.previous = this.last;
      this.last.next = node;
      this.last = node;
    } else {
      this.first = node;
      this.last = node;
    }

    this.size++;

    return node;
  }

Again, we have to be careful about updating the references and handling special cases such as when there's only one element.

  removeLast() {
    let current = this.first;
    let target;

    if(current && current.next) {
      current = this.last.previous;
      this.last = current;
      target = current.next;
      current.next = null;
    } else {
      this.first = null;
      this.last = null;
      target = current;
    }

    if(target) {
      this.size--;
      return target.value;
    }
  }

Using a doubly linked list, we no longer have to iterate through the whole list to get the 2nd last elements. We can use directly this.last.previous and is O(1).

Did you remember that for the Queue we had to use two arrays? Now, we can change that implementation an use a doubly linked list instead that has an O(1) for insert at the start and deleting at the end.

Adding an element anywhere from a linked list

Adding an element on anywhere on the list leverages our addFirst and addLast functions as you can see below:

  add(value, index = 0) {
    if(index === 0) {
      return this.addFirst(value);
    }

    for (let current = this.first, i = 0; i <= this.size;  i++, current = (current && current.next)) {
      if(i === index) {
        if(i === this.size) { // if it doesn't have next it means that it is the last
          return this.addLast(value);
        }
        const newNode = new Node(value);
        newNode.previous = current.previous;
        newNode.next = current;

        current.previous.next = newNode;
        if(current.next) { current.next.previous = newNode; }
        this.size++;
        return newNode;
      }
    }
  }

If we have an insertion in the middle of the array, then we have to update the next and previous reference of the surrounding elements.

Adding an element anywhere within the list is O(n).

Doubly Linked Lists time complexity

Doubly Linked List time complexity per function is as follows:

Operation	Runtime	Comment
`addFirst`	O(1)	Insert element to the beginning of the list.
`addLast`	O(1)	Insert element to the end of the list.
`add`	O(n)	Insert element anywhere in the list.
`removeFirst`	O(1)	Remove element to the beginning of the list.
`removeLast`	O(1)	Remove element to the end of the list.
`remove`	O(n)	Remove any element from the list
`contains`	O(n)	Search for any element from the list

Doubly linked lists are a significant improvement compared to the singly linked list! We improved from O(n) to O(1) by:

Adding a reference to the previous element.
Holding a reference to the last item in the list.

Removing first/last can be done in constant-time; however, eliminating in the middle of the array is still O(n).

Stacks

Stacks is a data structure where the last entered data is the first to come out. Also know as Last-in, First-out (LIFO).

Let's implement a stack from scratch!

class Stack {
  constructor() {
    this.input = [];
  }

  push(element) {
    this.input.push(element);
    return this;
  }

  pop() {
    return this.input.pop();
  }
}

As you can see is easy since we are using the built-in Array.push and Array.pop. Both have a runtime of O(1).

Let's see some examples of its usage:

  const stack = new Stack();

  stack.push('a');
  stack.push('b');
  stack.push('c');

  stack.pop(); // c
  stack.pop(); // b
  stack.pop(); // a

The first in (a) as the last to get out. We can also implement stack using a linked list instead of an array. The runtime will be the same.

That's all!

Queues

Queues are a data structure where the first data to get in is also the first to go out. A.k.a First-in, First-out (FIFO).
It's like a line of people at the movies, the first to come in is the first to come out.

We could implement a Queue using an array, very similar to how we implemented the Stack.

Queue implemented with Array(s)

A naive implementation would be this one using Array.push and Array.shift:

class Queue {
  constructor() {
    this.input = [];
  }

  add(element) {
    this.input.push(element);
  }

  remove() {
    return this.input.shift();
  }
}

What's the time complexity of Queue.add and Queue.remove?

Queue.add uses array.push which has a constant runtime. Win!
Queue.remove uses array.shift which has a linear runtime. Can we do better than O(n)?

Think a way you can implement a Queue only using Array.push and Array.pop.

class Queue {
  constructor() {
    this.input = [];
    this.output = [];
  }

  add(element) {
    this.input.push(element);
  }

  remove() {
    if(!this.output.length) {
      while(this.input.length) {
        this.output.push(this.input.pop());
      }
    }
    return this.output.pop();
  }
}

Now we are using two arrays rather than one.

const queue = new Queue();

queue.add('a');
queue.add('b');

queue.remove() // a
queue.add('c');
queue.remove() // b
queue.remove() // c

When we remove something for the first time, the output array is empty. So, we insert the content of input backward like ['b', 'a']. Then we pop elements from the output array. As you can see, using this trick we get the output in the same order of insertion (FIFO).

What's the runtime?

If the output has already some elements, then the remove operation is constant O(1). When the output arrays need to get refilled, it takes O(n) to do so. After the refilled, every operation would be constant again. The amortized time is O(1).

We can achieve a Queue with a pure constant if we use a LinkedList. Let's see what it is in the next section!

Queue implemented with a Doubly Linked List

We can achieve the best performance for a queue using a linked list rather than an array.

const LinkedList = require('../linked-lists/linked-list');

class Queue {
  constructor() {
    this.input = new LinkedList();
  }

  add(element) {
    this.input.addFirst(element);
  }

  remove() {
    return this.input.removeLast();
  }

  get size() {
    return this.input.size;
  }
}

Using a doubly linked list with the last element reference we achieve an add of O(1). That's the importance of using the right tool for the right job 💪

Summary

We explored most of the linear data structures. We saw that depending on how we implement the data structures there are different runtimes. Go to the top which has a table with all the examples we explored here.

8 time complexities that every programmer should know

Adrian Mejia — Thu, 05 Apr 2018 20:10:09 +0000

We are going to learn the top algorithm's running time that every developer should be familiar with. Knowing these time complexities will help you to assess if your code will scale. Also, it's handy to compare different solutions for the same problem. By the end, you would be able to eyeball different implementations and know which one will perform better.

To clarify some concepts used in the rest of the post:

The time complexity is not about timing how long the algorithm takes. Instead, how many operations are executed.
The number of instructions executed by a program is affected by the size of the input (and how their elements are arranged).
Big O notation is used to classify algorithms using the input size n. E.g. O(n) or O(n²).

Before we dive in, here is the Big O cheatsheet and examples that we are going to cover on this post. Click on them to jump to the implementation. 😉

Big O Notation	Name	Example(s)
O(1)	Constant	# Odd or Even number, # Look-up table
O(log n)	Logarithmic	# Finding element on sorted array with binary search
O(n)	Linear	# Find max element in unsorted array, # Duplicate elements in array with Hash Map
O(n log n)	Linearithmic	# Sorting elements in array with merge sort
O(n²)	Quadratic	# Duplicate elements in array (naïve), # Sorting array with bubble sort
O(n³)	Cubic	# 3 variables equation solver
O(2ⁿ)	Exponential	# Find all subsets
O(n!)	Factorial	# Find all permutations of a given set/string

Now, Let's go one by one and provide code examples!

O(1) - Constant time

O(1) describes algorithms that takes the same amount of time to compute regardless of the input size.

For instance, if a function takes the identical time to process 10 elements as well as 1 million items, then we say that it has a constant growth rate or O(1). Let’s see some cases.

Odd or Even

Find if a number is odd or even.

  function isEvenOrOdd(n) {
    return n % 2 ? 'Odd' : 'Even';
  }

  console.log(isEvenOrOdd(10)); // => Even
  console.log(isEvenOrOdd(10001)); // => Odd

Advanced note: you could also replace n % 2 with the bit AND operator: n & 1. If the first bit (LSB) is 1 then is odd otherwise is even.

It doesn't matter if n is 10 or 10,001, it will execute line 2 one time.

Do not be fool by one-liners. They don't always translate to constant times. You have to be aware of how they are implemented.

If you have a method like Array.sort() or any other array or object methods you have to look into the implementation to determine its running time.

Primitive operations like sum, multiplication, subtraction, division, modulo, bit shift, etc have a constant runtime. This can be shocking!

If you use the schoolbook long multiplication algorithm, it would take O(n²) to multiply two numbers. However, most programming languages limit numbers to max value (e.g. in JS: Number.MAX_VALUE is 1.7976931348623157e+308). So, you cannot operate numbers that yield a result greater than the MAX_VALUE. So, primitive operations are bound to be completed on a fixed amount of instructions O(1) or throw overflow errors (in JS, Infinity keyword).

This example was easy. Let's do another one.

Look-up table

Given a string find its word frequency data.

const dictionary = {the: 22038615, be: 12545825, and: 10741073, of: 10343885, a: 10144200, in: 6996437, to: 6332195 /* ... */};

function getWordFrequency(dictionary, word) {
  return dictionary[word];
}

console.log(getWordFrequency(dictionary, 'the'));
console.log(getWordFrequency(dictionary, 'in'));

Again, we can be sure that even if the dictionary has 10 or 1 million words, it would still execute line 4 once to find the word. However, if we decided to store the dictionary as an array rather than a hash map, then it would be a different story. In the next section, we are going to explore what's the running time to find an item in an array.

Only a hash table with a perfect hash function will have a worst-case runtime of O(1). The perfect hash function is not practical, so there will be some collisions and workarounds leads to a worst-case runtime of O(n). Still, on average the lookup time is O(1).

O(n) - Linear time

Linear running time algorithms are very common. Linear runtime means that the program visits every element from the input.

Linear time complexity O(n) means that as the input grows, the algorithms take proportionally longer to complete.

Some examples:

The largest item on an unsorted array

Let's say you want to find the maximum value from an unsorted array.

function findMax(n) {
  let max;
  let counter = 0;

  for (let i = 0; i < n.length; i++) {
    counter++;
    if(max === undefined || max < n[i]) {
      max = n[i];
    }
  }

  console.log(`n: ${n.length}, counter: ${counter}`);
  return max;
}

How many operations will the findMax function do?

Well, it checks every element from the input n. If the current element is bigger than max it will do an assignment.

Notice that we added a counter so it can help us count how many times the inner block is executed.

If you get the time complexity it would be something like this:

Line 2-3: 2 operations
Line 4: a loop of size n
Line 6-8: 3 operations inside the for-loop.

So, this gets us 3(n) + 2.

Applying the Big O notation that we learn in the previous post, we only need the biggest order term, thus O(n).

We can verify this using our counter. If n has 3 elements:

findMax([3, 1, 2]);
// n: 3, counter: 3

or if n has 9 elements:

findMax([4,5,6,1,9,2,8,3,7])
// n: 9, counter: 9

Now imagine that you have an array of one million items, it will perform one million operations. If we plot it n and findMax running time we will have a graph like a linear equation.

O(n²) - Quadratic time

A function with a quadratic time complexity has a growth rate of n². If the input is size 2, it will do 4 operations. If the input is size 8, it will take 64, and so on.

Here are some code examples of quadratic algorithms:

Has duplicates

You want to find duplicate words in an array. A naïve solution will be the following:

function hasDuplicates(n) {
  const duplicates = [];
  let counter = 0;

  for (let outter = 0; outter < n.length; outter++) {
    for (let inner = 0; inner < n.length; inner++) {
      counter++;

      if(outter === inner) continue;

      if(n[outter] === n[inner]) {
        return true;
      }
    }
  }

  console.log(`n: ${n.length}, counter: ${counter}`);
  return false;
}

Time complexity analysis:

Line 2-3: 2 operations
Line 5-6: double-loop of size n, so n².
Line 7-13: has ~3 operations inside the double-

We get 3n^2 + 2.

Again, when we using Big O notation, we drop all constants and leave the most significant term: n^2. So, it would be O(n^2).

We are using a counter variable to help us verify. The hasDuplicates function has two loops. If we have an input of 4 words, it will execute the inner block 16 times. If we have 9, it will perform counter 81 times and so forth.

hasDuplicates([1,2,3,4]);
// n: 4, counter: 16

and with n size 9:

hasDuplicates([1,2,3,4,5,6,7,8,9]);
// n: 9, counter: 81

Let's see another example.

Bubble sort

We want to sort the elements in an array.

function sort(n) {
  for (let outer = 0; outer < n.length; outer++) {
    let outerElement = n[outer];

    for (let inner = outer + 1; inner < n.length; inner++) {
      let innerElement = n[inner];

      if(outerElement > innerElement) {
        // swap
        n[outer] = innerElement;
        n[inner] = outerElement;
        // update references
        outerElement = n[outer];
        innerElement = n[inner];
      }
    }
  }
  return n;
}

Also, you might notice that for a colossal n, the time it takes to solve the problem increases a lot. Can you spot the relationship between nested loops and the running time? When a function has a single loop, it usually translates to a running time complexity of O(n). Now, this function has 2 nested loops and quadratic running time: O(n²).

O(n^c) - Polynomial time

Polynomial running is represented as O(n^c), when c > 1. As you already saw, two inner loops almost translate to O(n²) since it has to go through the array twice in most cases. Are three nested loops cubic? If each one visit all elements, then yes!

Usually, we want to stay away from polynomial running times (quadratic, cubic, n^c …) since they take longer to compute as the input grows fast. However, they are not the worst.

Triple nested loops

Let's say you want to find the solutions for a multi-variable equation that looks like this:

3x + 9y + 8z = 79

This naive program will give you all the solutions that satisfy the equation where x, y and z < n.

function findXYZ(n) {
  const solutions = [];

  for(let x = 0; x < n; x++) {
    for(let y = 0; y < n; y++) {
      for(let z = 0; z < n; z++) {
        if( 3*x + 9*y + 8*z === 79 ) {
          solutions.push({x, y, z});
        }
      }
    }
  }

  return solutions;
}

console.log(findXYZ(10)); // => [{x: 0, y: 7, z: 2}, ...]

This algorithm has a cubic running time: O(n³).

Note: We could do a more efficient solution but for the purpose of showing an example of a cubic runtime is good enough.

O(log n) - Logarithmic time

Logarithmic time complexities usually apply to algorithms that divide problems in half every time. For instance, let's say that we want to look for a word in an old fashion dictionary. It has every word sorted alphabetically. There are at least two ways to do it:

Algorithm A:

Start at the beginning of the book and go in order until you find the contact you are looking for.

Algorithm B:

Open the book in the middle and check the first word on it.
If the word that you are looking for is alphabetically bigger, then look to the right. Otherwise, look in the left half.

Which one is faster? The first algorithms go word by word O(n), while the algorithm B split the problem in half on each iteration O(log n). This 2nd algorithm is a binary search.

Binary search

Find the index of an element in a sorted array.

If we implement (Algorithm A) going through all the elements in an array, it will take a running time of O(n). Can we do better? We can try using the fact that the collection is already sorted. Later, we can divide in half as we look for the element in question.

function indexOf(array, element, offset = 0) {
  // split array in half
  const half = parseInt(array.length / 2);
  const current = array[half];


  if(current === element) {
    return offset + half;
  } else if(element > current) {
    const right = array.slice(half);
    return indexOf(right, element, offset + half);
  } else {
    const left = array.slice(0, half)
    return indexOf(left, element, offset);
  }
}

const directory = ["Adrian", "Bella", "Charlotte", "Daniel", "Emma", "Hanna", "Isabella", "Jayden", "Kaylee", "Luke", "Mia", "Nora", "Olivia", "Paisley", "Riley", "Thomas", "Wyatt", "Xander", "Zoe"];
console.log(indexOf(directory, 'Hanna'));   // => 5
console.log(indexOf(directory, 'Adrian'));  // => 0
console.log(indexOf(directory, 'Zoe'));     // => 18

Calculating the time complexity of indexOf is not as straightforward as the previous examples. This function is recursive.

There are several ways to analyze recursive algorithms like Master Method which are outside the scope of this post. As a rule of thumb, whenever you see an algorithm dividing the input in half it probably involves some log n runtime. Since the work done outside the recursion is constant, then we have a runtime of O(log n).

O(n log n) - Linearithmic

Linearithmic time complexity it's slightly slower than a linear algorithm but still much better than a quadratic algorithm (you will see a graph comparing all of them at the very end of the post).

Mergesort

What's the best way to sort an array? Before, we proposed a solution using bubble sort that has a time complexity of O(n²). Can we do better?

We can use an algorithm called mergesort to improve it.
This's how it works:

We are going to divide the array recursively until the elements are two or less.
We know how to sort 2 items, so we sort them iteratively (base case).
The final step is merging: we merge in taking one by one from each array such that they are in ascending order.

Here's the code for merge sort:

function sort(n) {
  const length = n.length;
  // base case
  if(length === 1) {
    return n;
  }
  if(length === 2) {
    return n[0] > n[1] ? [n[1], n[0]] : [n[0], n[1]];
  }
  // slit and merge
  const mid = length/2;
  return merge(sort(n.slice(0, mid)), sort(n.slice(mid)));
}

function merge(a = [], b = []) {
  const merged = [];
  // merge elements on a and b in asc order. Run-time O(a + b)
  for (let ai = 0, bi = 0; ai < a.length || bi < b.length;) {
    if(ai >= a.length || a[ai] > b[bi]) {
      merged.push(b[bi++]);
    } else {
      merged.push(a[ai++]);
    }
  }

  return merged;
}

As you can see, it has two functions sort and merge. Merge is an auxiliary function that runs once through the collection a and b, so it's running time is O(n). Sort is a recursive function that splits the array in half each time, the total runtime of the mergesort is O(n log n).

Note: If you want to see the full explanation check out Master Method for mergesort.

O(2ⁿ) - Exponential time

Exponential (base 2) running time means that the calculations performed by an algorithm double every as the input grows.

Subsets of a Set

Finding all distinct subsets of a given set. For instance, let's do some examples to try to come up with an algorithm to solve it:

getSubsets('') // =>  ['']
getSubsets('a') // => ['', 'a']
getSubsets('ab') // => ['', 'a', 'b', 'ab']

Did you notice any pattern?

The first returns have an empty element.
The second case returns the empty element + the 1st element.
The 3rd case returns precisely the results of 2nd case + the same array with the 2nd element b appended to it.

What if you want to find the subsets of abc? Well, it would be exactly the subsets of 'ab' and again the subsets of ab with c appended at the end of each element.

As you noticed, every time the input gets longer the output is twice as long as the previous one. Let's code it op:

function getSubsets(n = '') {
  const array = Array.from(n);
  const base = [''];

  const results = array.reduce((previous, element) => {
    const previousPlusElement = previous.map(el => {
      return `${el}${element}`;
    });
    return previous.concat(previousPlusElement);
  }, base);

  console.log(`getSubsets(${n}) // ${results.slice(0, 15).join(', ')}... `);
  console.log(`n: ${array.length}, counter: ${results.length};`);
  return results;
}

If we run that function for a couple of cases we will get:

getSubsets('') // ...
// n = 0, f(n) = 1;
getSubsets('a') // , a...
// n = 1, f(n) = 2;
getSubsets('ab') // , a, b, ab...
// n = 2, f(n) = 4;
getSubsets('abc') // , a, b, ab, c, ac, bc, abc...
// n = 3, f(n) = 8;
getSubsets('abcd') // , a, b, ab, c, ac, bc, abc, d, ad, bd, abd, cd, acd, bcd...
// n = 4, f(n) = 16;
getSubsets('abcde') // , a, b, ab, c, ac, bc, abc, d, ad, bd, abd, cd, acd, bcd...
// n = 5, f(n) = 32;

As expected, if you plot n and f(n), you will notice that it would be exactly like the function 2^n. This algorithm has a running time of O(2^n).

Note: You should avoid functions with exponential running times (if possible) since they don't scale well. The time it takes to process the output doubles with every additional input size. But exponential running time is not the worst yet; there are others that go even slower. Let's see one more example in the next section.

O(n!) - Factorial time

Factorial is the multiplication of all positive integer numbers less than itself. For instance:

5! = 5 x 4 x 3 x 2 x 1 = 120

It grows pretty quickly:

20! = 2,432,902,008,176,640,000

As you might guess, you want to stay away if possible from algorithms that have this running time!

Permutations

Write a function that computes all the different words that can be formed given a string. E.g.

getPermutations('a') // => [ 'a']
getPermutations('ab') // =>  [ 'ab', 'ba']
getPermutations('abc') // => [ 'abc', 'acb', 'bac', 'bca', 'cab', 'cba' ]

How would you solve that?

A straightforward way will be to check if the string has a length of 1 if so, return that string since you can't arrange it differently.

For strings with a length bigger than 1, we could use recursion to divide the problem into smaller problems until we get to the length 1 case. We can take out the first character and solve the problem for the remainder of the string until we have a length of 1.

function getPermutations(string, prefix = '') {
  if(string.length <= 1) {
    return [prefix + string];
  }

  return Array.from(string).reduce((result, char, index) => {
    const reminder = string.slice(0, index) + string.slice(index+1);
    result = result.concat(getPermutations(reminder, prefix + char));
    return result;
  }, []);
}

If print out the output, it would be something like this:

getPermutations('ab') // ab, ba...
// n = 2, f(n) = 2;
getPermutations('abc') // abc, acb, bac, bca, cab, cba...
// n = 3, f(n) = 6;
getPermutations('abcd') // abcd, abdc, acbd, acdb, adbc, adcb, bacd...
// n = 4, f(n) = 24;
getPermutations('abcde') // abcde, abced, abdce, abdec, abecd, abedc, acbde...
// n = 5, f(n) = 120;

I tried with a string with a length of 10. It took around 8 seconds!

time node ./lib/permutations.js
# getPermutations('abcdefghij') // => abcdefghij, abcdefghji, abcdefgihj, abcdefgijh, abcdefgjhi, abcdefgjih, abcdefhgij...
# // n = 10, f(n) = 3,628,800;
# ./lib/permutations.js  8.06s user 0.63s system 101% cpu 8.562 total

I have a little homework for you...

Can you try with a permutation with 11 characters? ;) Comment below what happened to your computer!

All running complexities graphs

We explored the most common algorithms running times with one or two examples each! They should give you an idea of how to calculate your running times when developing your projects. Below you can find a chart with a graph of all the time complexities that we covered:

Mind your time complexity!

You can find all these examples and more in the Github repo:

amejiarosario / dsa.js-data-structures-algorithms-javascript

🥞Data Structures and Algorithms explained and implemented in JavaScript + eBook

Data Structures and Algorithms in JavaScript

This is the coding implementations of the DSA.js book and the repo for the NPM package.

In this repository, you can find the implementation of algorithms and data structures in JavaScript. This material can be used as a reference manual for developers, or you can refresh specific topics before an interview. Also, you can find ideas to solve problems more efficiently.

Installation

You can clone the repo or install the code from NPM:

npm install dsa.js

and then you can import it into your programs or CLI

const { LinkedList, Queue, Stack } = require('dsa.js');

For a full list of all the exposed data structures and algorithms see.

Features

Algorithms are an…

View on GitHub

How you can change the world by learning Algorithms

Adrian Mejia — Wed, 04 Apr 2018 20:16:07 +0000

As a developer, you have the power to change the world! You can write programs that enable new technologies. For instance, develop software to find an earlier diagnosis of diseases. But, that's not the only way, you might do it indirectly by creating projects that make people more productive and help them free up time to do other amazing things. Whatever you do, it has the potential to impact the community who use it.

However, these accomplishments are only possible if we write software that is fast and can scale. Learning how to measure your code performance is the goal of this post.

We are going to explore how you can measure your code performance using analysis of algorithms: time complexity and big O notation.

First, let’s see a real story to learn why this is important.

An algorithm that saved millions of lives

During War World II, the Germans used AM radio signals to communicate with troops around Europe. Anybody with an AM frequency radio and some knowledge of Morse code could intercept the message. However, the information was encoded! All the countries that were under attack tried to decode it. Sometimes, they got lucky and were able to make sense of a couple of messages at the end of the day. Unfortunately, the Nazis changed the encoding every single day!

A brilliant mathematician called Alan Turing joined the British military to crack the German "Enigma" code. He knew they would never get ahead if they keep doing the calculations by pen and paper. So after many months of hard work, they built a machine. Unfortunately, the first version of the device took to long to decode a message! So, it was not very useful.

Alan's team found out that every encrypted message ended with the same string: "Heil Hitler" Aha! After changing the algorithm, the machine was able to decode transmissions a lot faster! They used it the info to finish the war quicker and save millions of lives!

The same machine that was going to get shut down as a failure became a live saver. Likewise, you can do way more with your computing resources when you write efficient code. That is what we are going to learn in this post series!

Another popular algorithm is PageRank developed in 1998 by Sergey Brin and Larry Page (Google founders). This algorithm was (and is) used by a Google search engine to make sense of trillions of web pages. Google was not the only search engine. However, since their algorithm returned better results most of the competitors faded away. Today it powers most of 3 billion daily searches very quickly. That is the power of algorithms that scale! 🏋🏻‍

So, why should you learn to write efficient algorithms?

There are many advantages; these are just some of them:

You would become a much better software developer (and get better jobs/income).
Spend less time debugging, optimizing and re-writing code.
Your software will run faster with the same hardware (cheaper to scale).
Your programs might be used to aid discoveries that save lives (maybe?).

Without further ado, let’s step up our game!

What are Algorithms?

Algorithms (as you might know) are steps of how to do some task. For example, when you cook, you follow a recipe to prepare a dish. If you play a game, you are devising strategies to help you win. Likewise, algorithms in computers are a set of instructions used to solve a problem.

Algorithms are instructions to perform a task

There are "good" and "bad" algorithms. The good ones are fast; the bad ones are slow. Slow algorithms cost more money and make some calculations impossible in our lifespan!

We are going to explore the basic concepts of algorithms. Also, we are going to learn how to distinguish “fast” from “slow” ones. Even better, you will be able to “measure” the performance of your algorithms and improve them!

How to improve your coding skills?

The first step to improving something is to measure it.

Measurement is the first step that leads to control and eventually to improvement. If you can’t measure something, you can’t understand it. If you can’t understand it, you can’t control it. If you can’t control it, you can’t improve it. - H. J. Harrington

How do you do "measure" your code? Would you clock "how long" it takes to run? What if you are running the same program on a mobile device or a quantum computer? The same code will give you different results.

To answer these questions, we need to nail some concepts first, like time complexity!

Time complexity

Time complexity (or running time) is the estimated time an algorithm takes to run. However, you do not measure time complexity in seconds, but as a function of the input. (I know it's weird but bear with me).

The time complexity is not about timing how long the algorithm takes. Instead, how many operations are executed. The number of instructions executed by a program is affected by the size of the input and how their elements are arranged.

Why is that the time complexity is expressed as a function of the input? Well, let's say you want to sort an array of numbers. If the elements are already sorted, the program will perform fewer operations. On the contrary, if the items are in reverse order, it will require more time to get it sorted. So, the time a program takes to execute is directly related to the input size and how the elements are arranged.

We can say for each algorithm have the following running times:

Worst-case time complexity (e.g., input elements in reversed order)
Best-case time complexity (e.g., already sorted)
Average-case time complexity (e.g., elements in random order)

We usually care more about the worst-case time complexity (We are hoping for the best but preparing for the worst).

Calculating time complexity

Here's a code example of how you can calculate the time complexity:

Find the smallest number in an array.

/**
 * Get the smallest number on an array of numbers
 * @param {Array} n array of numbers
 */
function getMin(n) {
  const array = Array.from(n);
  let min;

  array.forEach(element => {
    if(min === undefined || element < min) {
      min = element;
    }
  });
  return min;
}

We can represent getMin as a function of the size of the input n based on the number of operations it has to perform. For simplicity, let's assume that each line of code takes the same amount of time in the CPU to execute. Let's make the sum:

Line 6: 1 operation
Line 7: 1 operation
Line 9-13: it is a forEach loop that executes size of n times
- Line 10: 1 operation
- Line 11: this one is tricky. It is inside a conditional. We will assume the worst case where the array is sorted in ascending order. The condition (if block) will be executed each time. Thus, 1 operation
Line 14: 1 operation

All in all, we have 3 operations outside the loop and 2 inside the forEach block. Since the loop goes for the size of n, this leaves us with 2(n) + 3.

However, this expression is somewhat too specific and hard to compare algorithms with it. We are going to apply the asymptotic analysis to simplify this expression further.

Asymptotic analysis

Asymptotic analysis is just evaluating functions as their value approximate to the infinite. In our previous example 2(n) + 3, we can generalize it as k(n) + c. As the value of n grows, the value c is less and less significant, as you can see in the following table:

n (size)	operations	result
1	2(1) + 3	5
10	2(10) + 3	23
100	2(100) + 3	203
1,000	2(1,000) + 3	2,003
10,000	2(10,000) + 3	20,003

Believe it or not, also the constant k wouldn't make too much of a difference. Using this kind of asymptotic analysis we take the higher order element, in this case: n.

Let's do another example so we can get this concept. Let's say we have the following function: 3 n^2 + 2n + 20. What would be the result of using the asymptotic analysis?

3 n^2 + 2n + 20 as n grows bigger and bigger; the term that will make the most difference is n^2.

Going back to our example, getMin, we can say that this function has a time complexity of n. As you can see, we could approximate it as 2(n) and drop the +3 since it does not add too much value as n keep getting bigger.

We are interested in the big picture here, and we are going to use the asymptotic analysis to help us with that. With this framework, comparing algorithms, it is much more comfortable. We can compare running times with their most significant term: n^2 or n or 2^n.

Big-O notation and Growth rate of Functions

The Big O notation combines what we learned in the last two sections about worst-case time complexity and asymptotic analysis.

The letter O refers to the order of a function.

The Big O notation is used to classify algorithms by their worst running time or also referred to as the upper bound of the growth rate of a function.

In our previous example with getMin function, we can say it has a running time of O(n). There are many different running times. Here are the most common that we are going to cover in the next post and their relationship with time:

Growth rates vs. n size:

n	O(1)	O(log n)	O(n)	O(n log n)	O(n²)	O(2ⁿ)	O(n!)
1	< 1 sec	< 1 sec	< 1 sec	< 1 sec	< 1 sec	< 1 sec	< 1 sec
10	< 1 sec	< 1 sec	< 1 sec	< 1 sec	< 1 sec	< 1 sec	4 sec
100	< 1 sec	< 1 sec	< 1 sec	< 1 sec	< 1 sec	40170 trillion years	> vigintillion years
1,000	< 1 sec	< 1 sec	< 1 sec	< 1 sec	< 1 sec	> vigintillion years	> centillion years
10,000	< 1 sec	< 1 sec	< 1 sec	< 1 sec	2 min	> centillion years	> centillion years
100,000	< 1 sec	< 1 sec	< 1 sec	1 sec	3 hours	> centillion years	> centillion years
1,000,000	< 1 sec	< 1 sec	1 sec	20 sec	12 days	> centillion years	> centillion years

Assuming: 1 GHz CPU and that it can execute on average one instruction in 1 nanosecond (usually takes more time). Also, bear in mind that each line might be translated into dozens of CPU instructions depending on the programming language

As you can see, some algorithms are very time-consuming. An input size as little as 100, it is impossible to compute even if we had a 1 PHz (1 million GHz) CPU!! Hardware does not scale as well as software.

In the next post, we are going to explore all of these time complexities with a code example or two!

8 time complexities that every programmer should know

Adrian Mejia ・ 13 min read

#algorithms #javascript #node #beginners

Are you ready to become a super programmer and scale your code?!

Check out the Github repo for more examples:

amejiarosario / dsa.js

Data Structures and Algorithms explained and implemented in JavaScript

Data Structures and Algorithms in JavaScript

This repository covers the implementation of the classical algorithms and data structures in JavaScript.

Usage

You can clone the repo or install the code from NPM:

npm install dsa.js

and then you can import it into your programs or CLI

const { LinkedList, Queue, Stack } = require('dsa.js');

For a full list of all the exposed data structures and algorithms see.

Book

You can check out the dsa.js book that goes deeper into each topic and provide additional illustrations and explanations.

Algorithmic toolbox to avoid getting stuck while coding.
Explains data structures similarities and differences.
Algorithm analysis fundamentals (Big O notation, Time/Space complexity) and examples.
Time/space complexity cheatsheet.

Data Structures

We are covering the following data structures.

Linear Data Structures

Arrays: Built-in in most languages so not implemented here. Array Time complexity
Linked Lists…

View on GitHub

Getting started with Node.js modules: require, exports, imports and beyond

Adrian Mejia — Fri, 12 Aug 2016 20:30:23 +0000

Getting started with Node.js modules: require, exports, imports, and beyond.

Modules are a crucial concept to understand Node.js projects. In this post, we cover Node modules: require, exports and, the future import.

Node modules allow you to write reusable code. You can nest them one inside another. Using the Node Package Manager (NPM), you can publish your modules and make them available to the community. Also, NPM enables you to reuse modules created by other developers.

We are using Node 12.x for the examples and ES6+ syntax. However, the concepts are valid for any version.

In this section, we are going to cover how to create Node modules and each one of its components:

Require
Exports
Module (module.exports vs. export)
Import

Require

require are used to consume modules. It allows you to include modules in your programs. You can add built-in core Node.js modules, community-based modules (node_modules), and local modules.

Let's say we want to read a file from the filesystem. Node has a core module called 'fs':

const fs = require('fs');

fs.readFile('./file.txt', 'utf-8', (err, data) => {
  if(err) { throw err; }
  console.log('data: ', data);
});

As you can see, we imported the "fs" module into our code. It allows us to use any function attached to it, like "readFile" and many others.

The require function will look for files in the following order:

Built-in core Node.js modules (like fs)
NPM Modules. It will look in the node_modules folder.
Local Modules. If the module name has a ./, / or ../, it will look for the directory/file in the given path. It matches the file extensions: *.js, *.json, *.mjs, *.cjs, *.wasm and *.node.

Let's now explain each in little more details with

Built-in Modules

When you install node, it comes with many built-in modules. Node comes with batteries included ;)

Some of the most used core modules are:

fs: Allows you to manipulate (create/read/write) files and directories.
path: utilities to work with files and directories paths.
http: create HTTP servers and clients for web development.
url: utilities for parsing URLs and extracting elements from it.

These you don't have to install it, you can import them and use them in your programs.

NPM Modules

NPM modules are 3rd-party modules that you can use after you install them. To name a few:

lodash: a collection of utility functions for manipulating arrays, objects, and strings.
request: HTTP client simpler to use than the built-in http module.
express: HTTP server for building websites and API. Again, simpler to use than the built-in http module.

These you have to install them first, like this:

npm install express

and then you can reference them like built-in modules, but this time they are going to be served from the node_modules folder that contains all the 3rd-party libraries.

const express = require('express');

Creating your own Nodejs modules

If you can't find a built-in or 3rd-party library that does what you want, you will have to develop it yourself.
In the following sections, you are going to learn how to do that using exports.

Exports

The exports keyword gives you the chance to "export" your objects and methods. Let's do an example:

const PI = 3.14159265359;

exports.area = radius => (radius ** 2) * PI;
exports.circumference = radius => 2 * radius * PI;

In the code below, we are exporting the area and circumference functions. We defined the PI constant, but this is only accessible within the module. Only the elements associated with exports are available outside the module.

So, we can consume it using require in another file like follows:

const circle = require('./circle');

const r = 3;
console.log(`Circle with radius ${r} has
  area: ${circle.area(r)};
  circumference: ${circle.circumference(r)}`);

Noticed that this time we prefix the module name with ./. That indicates that the module is a local file.

Module Wrapper

You can think of each Node.js module as a self-contained function like the following one:

Module Wrapper:

(function (exports, require, module, __filename, __dirname) {
  module.exports = exports = {};

  // Your module code ...

});

We have already covered exports and require. Notice the relationship between module.exports and exports. They point to the same reference. But, if you assign something directly to exports you will break its link to module.exports — more on that in the next section.

For our convenience __filename and __dirname are defined. They provide the full path to the current file and directory. The latter excludes the filename and prints out the directory path.

For instance, for our ./circle.js module, it would be something like this:

__filename: /User/adrian/code/circle.js
__dirname: /User/adrian/code

Ok, we have covered exports, require, __filename, and __dirname. The only one we haven't covered is module. Let's go for it!

Module.exports vs. Exports

The module is not global; it is local for each module. It contains metadata about a module like id, exports, parent, children, and so on.

exports is an alias of module.exports. Consequently, whatever you assign to exports is also available on module.exports. However, if you assign something directly to exports, then you lose the shortcut to module.exports. E.g.

class Cat {
  makeSound() {
    return `${this.constructor.name}: Meowww`;
  }
}

// exports = Cat; // It will not work with `new Cat();`
// exports.Cat = Cat; // It will require `new Cat.Cat();` to work (yuck!)
module.exports = Cat;

Try the following case with exports and then with module.exports.

const Cat = require('./cat');

const cat = new Cat();
console.log(cat.makeSound());

To sum up, when to use module.exports vs exports:

Use exports to:

Export named function. e.g. exports.area, exports.circumference.

Use module.exports to:

If you want to export an object, class, function at the root level (e.g. module.exports = Cat)
If you prefer to return a single object that exposes multiple assignments. e.g.module.exports = {area, circumference};

Imports

Starting with version 8.5.0+, Node.js supports ES modules natively with a feature flag and new file extension *.mjs.

For instance, our previous circle.js can be rewritten as circle.mjs as follows:

circle.mjs

const PI = 3.14159265359;

export function area(radius) {
  return (radius ** 2) * PI;
}

export function circumference(radius) {
  return 2 * radius * PI;
}

Then, we can use import:

main.mjs

import { area, circumference } from './circle.mjs';

const r = 3;

console.log(`Circle with radius ${r} has
  area: ${area(r)};
  circunference: ${circumference(r)}`);

And, finally you can run it using the experimental module feature flag:

node --experimental-modules main.mjs

If you don't like experimental modules, another alternative is to use a transpiler. That converts modern JavaScript to older versions for you. Good options are TypeScript, Babel, and Rollup.

Troubleshooting `import` and `require` issues

Experimental Flag

If you don't use the experimental flag node --experimental-modules and you try to use import you will get an error like this:

internal/modules/cjs/loader.js:819
  throw new ERR_REQUIRE_ESM(filename);
  ^

Error [ERR_REQUIRE_ESM]: Must use import to load ES Module: bla bla blah

File extension .mjs vs .js (or .cjs)

If you have a *.mjs file you cannot use require or it will throw and error (ReferenceError: require is not defined).
.mjs is for import ECMAScript Modules and .js is for regular require modules.

However, with *.mjs you can load both kinds of modules!

import { area, circumference } from './circle.mjs';
import Cat from './cat.js';

const r = 3;
console.log(`Circle with radius ${r} has
  area: ${area(r)};
  circumference: ${circumference(r)}`);

const cat = new Cat();
console.log(cat.makeSound());

Notice that cat.js is using commonJS modules.

Summary

We learned about how to create Node.js modules and used it in our code. Modules allow us to reuse code easily. They provide functionality that is isolated from other modules. The require function is used to load modules. The exports and module.exports allow us to define what parts of our code we want to expose. We also explored the difference between module.exports and exports. Finally, we took a quick pick about what's coming up for modules using imports.

DEV Community: Adrian Mejia

What every programmer should know about Synchronous vs. Asynchronous Code

Synchronous vs. Asynchronous in Node.js

Synchronous code for reading from a file in Node.js

Asynchronous code for reading from a file in Node.js

Blocking vs. Non-Blocking I/O model Benchmark

Advantages of non-blocking code

What are your top ten command lines?

How to build a Node.js eCommerce website for free

Automating the generation of the assets (PDF)

amejiarosario / dsa.js-data-structures-algorithms-javascript

🥞Data Structures and Algorithms explained and implemented in JavaScript + eBook

Data Structures and Algorithms in JavaScript

Table of Contents

Installation

Features

Hosting e-Commerce site

Processing Payments

Backend processing

Sending emails

DNS settings and authentication

Email Templates

Cost of running the e-Commerce store

How can developers reduce stress

Background

Ideas to handle stress

Move 🚶‍♂️

Brainstorm 🧠

Subtask ✌️

Prioritize 🎯

Ask 🗣

Drink 🚰

Nourish 🥦

Stretch 🙆‍♀️

Workout 🏋️‍♀️

Breath 💨

Meditate 🧘‍♀️

Play 🎮

Write ✍️

Sleep 😴

Stress management for Software Developers

Information overload 🤯

Testing 🐞

Refactoring 🛠

Self-balanced Binary Search Trees with AVL in JavaScript

amejiarosario / dsa.js-data-structures-algorithms-javascript

🥞Data Structures and Algorithms explained and implemented in JavaScript + eBook

Data Structures and Algorithms in JavaScript

Table of Contents

Installation

Features

Balanced vs. Unbalanced Binary Search Tree

When a tree is balanced/non-balanced?

Tree rotations

Left Rotation

Right Rotation

Left-Right Rotation

Right-Left Rotation

AVL Tree Overview

Tree with one node

Tree with multiple nodes

AVL Tree Insertion and Deletion

Summary

Tree Data Structures Explained with JavaScript

amejiarosario / dsa.js-data-structures-algorithms-javascript

🥞Data Structures and Algorithms explained and implemented in JavaScript + eBook

Data Structures and Algorithms in JavaScript

Table of Contents

Installation

Features

Trees: basic concepts

Implementing a simple tree data structure

Binary Trees

Full, Complete and Perfect binary trees

Binary Search Tree (BST)

BST Implementation

BST Node Insertion

BST Node Deletion

Binary Tree Transversal

Balanced vs. Non-balanced Trees

O(n²) - Quadratic time

O(n^c) - Polynomial time