What’s a Priority Queue (PQ)?

A priority queue is a data structure that extends the queue by a priority dimension. Let’s expand both terms. The queue is a list of elements taken in the same order as they arrived. For instance, a line of people waiting to pay at the Supermarket behaves like a queue: first-in, first-served, or FIFO (first in, first out).

The priority queue adds a priority to each element’s value. If we go back to the example of a line of people in a supermarket. You can add preferred lanes, for example, Seniors (65+ years old) and pregnant women. If you have Seniors in the line, you will take them first, even if other people arrived before them. That’s what a priority queue (PQ) does. If all elements in a PQ have the same priority, then it will behave like a regular queue.

Why a priority queue? Can’t we just have different queues for each priority? That only works if you have a few priorities, but sometimes you have infinite possibilities (e.g., the distance between two points, ETA, etc.). Later in this post, we will explore how we can implement an efficient solution for these cases.

What is a priority queue good for? / Applications

There are many real-world applications for priority queues, such as:

• System to triage hospital patients and attend them by their severity order.
• Forward network packages in order of urgency (e.g., “real-time video call” should go before “time sync checks,” so to speak)
• Scheduling tasks in a system: “critical” goes before “shadow drawing” for instance.
• Asynchronous control flows like firing events (or notifying observers) in a certain order.
• Keeping track of top k elements efficiently
• Keeping track of median numbers in constant time
• Used in some graph algorithms like Dijkstra for finding the shortest path between two points. The distance among points is used as a priority.

Some priority queue JavaScript implementations on the wild:

• closure-library: heap.js, priorityqueue.js
• dsa.js: heap.js, priority-queue.js, min-heap.js, max-heap.js
• async : priorityQueue.js, Heap.js.
• datastructures-js: heap.js, priorityQueue.js

This tutorial will start with a simple implementation and then build it to a robust implementation while making it easy to follow.

Implementing a Priority Queue (PQ) in JavaScript

JavaScript standard doesn’t provide a default implementation that we can use. So, we are going to define our own. But, even if you use another language that has it in their standard API, it’s still good to know how it works so you can reason about the time complexity of their operations.

Without any further ado, let’s get to it!

Priority Queue operations

As always, there are many ways to solve the same problem. We are going to brainstorm some approaches along with their pros and cons. Yes, there’s never a perfect approach. However, we can learn to analyze the trade-offs and how we can improve our algorithms better.

The essential operations of the priority queue are:

• enqueue: insert elements on the queue
• dequeue: remove elements from the queue in the same order they were inserted.

Priority queue usually has a comparison function. Since our data could be simple (just an array of numbers where the value and priority are the same) or compound, where we have multiple fields (e.g. the priority could be the age of a student object). The comparator function tells our PQ what we can use as a priority. Here’s an example:

1
2
3
4
5
6
7
8

const pq= new PriorityQueue((x, y) => y.age - x.age);
pq.enqueue({ name: 'Maria', age: 23 });
pq.enqueue({ name: 'Nushi', age: 42 });
pq.enqueue({ name: 'Jose', age: 32 });

pq.dequeue(); // { name: 'Nushi', age: 42 }
pq.dequeue(); // { name: 'Jose', age: 32 }
pq.dequeue(); // { name: 'Maria', age: 23 }

As you can see, the comparator function dequeue elements with the highest age first. This is called a Max-PQ. We can invert the minuend and subtrahend to get a Min-PQ. Another possibility to use the name as a priority.

Now that we have a general idea of how a PQ API works let’s explore how we can implement it.

Naive: Priority Queue implemented using Array + Sorting

You can implement a regular queue using an array or linked list. However, priority queues have a new dimension: It needs to sort elements by priority. So, can we just sort a regular array queue every time we insert a new element? Yes, we can! But let’s see how it will perform.

Enqueue

Every time we insert a new element, we need to sort the elements. That’s O(n log n).

Complexity

• Time: O(n log n), insertion into an array is constant but sorting takes n log n.
• Space: O(n), the space used in memory will grow proportionally to the number of elements in the queue.

Here’s the implementation of the Enqueue method:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class NaivePQ {
  constructor(comparator = (a, b) => a - b) {
    this.array = [];
    this.comparator = comparator;
  }

  /**
   * Insert element
   * @runtime O(n log n)
   * @param {any} value
   */
  add(value) {
    this.array.push(value);
    this.array.sort(this.comparator);
  }

 //...
}

Dequeue

Dequeue removes elements from the PQ. We need to find the element with the highest priority and then return that. The highest number will be first element, so that’s O(1) operation. However, we need to move the rest of the elements to fill the gap. That’s O(n).

Complexity

• Time: O(n), finding the top element.
• Space: O(n), space is technically O(n-1). However, we just care about the “higher order” term, so O(n).

1
2
3
4
5
6
7
8
9

/**
 * Retrieves and removes the head or returns null if this Heap is empty.
 * @runtime O(n)
 */
remove() {
  if (!this.size) return null;
  const value = this.array.shift(); // remove element
  return value;
}

Improving PQ implementation

Can we do better? We could do nothing after insertion O(1) and then delegate the finding of the element with the highest priority to dequeue (if max-heap). That would be O(n).

O(n) as time complexity is not bad. It’s better than sorting all elements on every insertion O(n log n). Still, how can we improve this? If we use a data structure that keeps the max element at the top in less than O(n), that would be great! Good news, that’s what a heap is for!

Priority Queue implemented using a Heap

A heap is a tree data structure that keeps to max or min element at the root. So you can have a max-heap or min-heap. Regardless, they have two basic operations: insert and remove.

Conceptually the heaps can be represented as a complete binary tree. With the following rules or invariants:

1. The parent node should be smaller (or equal) than the two children for a Min-Heap. For a max-heap is the opposite, the parent node should be bigger (or equal) than the two children.
2. The binary tree should be complete (all levels are completely filled. The only exception is the last level which might not be full, but the ones filled comes from left to right without gaps)

Even though a heap is conceptually a binary tree, it can be implemented using an array since it’s a complete tree. The first element on the array is the root. The following two elements are the root’s children, the 4th and 5th elements are the 2nd element’s children, and so on.

You can calculate the following formula to translate tree to array:

• parent(i) = Math.ceil(i / 2 - 1)
• leftChild(i) = 2 * i + 1
• rightChild2(i) = 2 * i + 2

What’s the time complexity of heaps and Priority Queue?

Again the PQ has two primary operations: enqueue and dequeue. So, let’s see how we can do this with a heap.

Enqueue

The algorithm to insert an element in a heap is as follows:

1. Insert the element into the next empty position (tail).
2. From that position, “bubble up” the element to keep the min-heap invariant “parent should be smaller than any children” (the opposite if max-heap). If the invariant is broken, fix it by swapping the node with its parent and repeat the process all the way to the root node if necessary.

Here’s an implementation of the Heap. Also we are using a comparator function so we can define the priority.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Heap {
  constructor(comparator = (a, b) => a - b) {
    this.array = [];
    this.comparator = (i1, i2) => comparator(this.array[i1], this.array[i2]);
  }

  /**
   * Insert element
   * @runtime O(log n)
   * @param {any} value
   */
  add(value) {
    this.array.push(value);
    this.bubbleUp();
  }

  /**
   * Move new element upwards on the Heap, if it's out of order
   * @runtime O(log n)
   */
  bubbleUp() {
    let index = this.size - 1;
    const parent = (i) => Math.ceil(i / 2 - 1);
    while (parent(index) >= 0 && this.comparator(parent(index), index) > 0) {
      this.swap(parent(index), index);
      index = parent(index);
    }
  }
}

This algorithm can keep a heap sorted in O(log n) because it only visits half of the tree at most.

“Why log n?“**,** you asked.

Because that’s the maximum number of swaps that you would have to bubble up the newly inserted element.

Complexity:

• Time: O(log n), in the worst case, you will have to bubble up the inserted element up to the root of the tree. These will involve log n swaps, where n is the total number of nodes.
• Space: O(n)

Dequeue

The algorithms for dequeuing an element from a PQ is the following:

1. Remove the root element
2. Since the root element is gone, you need to fill the hole by promoting a child to take its place. This process is called “heapify” or bubbleDown. You choose the child that has the min value for min-heap (or max value for max-heap). You do this recursively until you found a leaf (node without children).

Complexity:

• Time: O(log n), The maximum number of swaps is given by the tree’s height, which is log n.
• Space: O(n).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

/**
 * Retrieves and removes the head of this Heap or returns null if this Heap is empty.
 * @runtime O(log n)
 */
remove(index = 0) {
  if (!this.size) return null;
  this.swap(index, this.size - 1); // swap with last
  const value = this.array.pop(); // remove element
  this.bubbleDown(index);
  return value;
}

/**
 * After removal, moves element downwards on the Heap, if it's out of order
 * @runtime O(log n)
 */
bubbleDown(index = 0) {
  let curr = index;
  const left = (i) => 2 * i + 1;
  const right = (i) => 2 * i + 2;
  const getTopChild = (i) => (right(i) < this.size
    && this.comparator(left(i), right(i)) > 0 ? right(i) : left(i));

  while (left(curr) < this.size && this.comparator(curr, getTopChild(curr)) > 0) {
    const next = getTopChild(curr);
    this.swap(curr, next);
    curr = next;
  }
}

You can find the full implementation at: https://github.com/amejiarosario/dsa.js-data-structures-algorithms-javascript/blob/master/src/data-structures/heaps/heap.js

Summary

In these post we learned about the usages of a priority queue and how to implement it with an array+sorting and using array-based heap. We also explored it’s time complexity for each implementation so we can verify that the heap implementation is more efficient.

In this article you will learn:

1. 10 steps to avoid getting stuck during coding questions in interviews
2. How to translate a maze or some “real life” problems into a graph.
3. How to solve problems using Graph traversing algorithms such as Breadth-First Search (BFS) or Depth-First Search.
4. When can you use only BFS or DFS or both?

Graph Representations

A Graph can be represented in many ways depending on the problem as a class, Map + Array/Set, implicit graph or adjacency matrix.

TL;DR: When building reusable libraries, you can go with the Graph class implementation. However, when solving a problem quickly (during interviews or one-off problems), go with the implicit implementation if possible or Map+Array representation if you need to build the graph upfront. Don’t use adjacency matrix since it usually uses more memory than other alternatives.

Graph as a Class

You can use OOP to represent graphs, like this:

1
2
3
4
5
6
7
8
9
10
11
12
13

class Graph {
  constructor() { /* ... */ }

  addVertex(value) { /* ... */ }
  removeVertex(value) { /* ... */ }
  addEdge(source, destination) { /* ... */ }
  removeEdge(source, destination) { /* ... */ }

  areAdjacents(source, destination) { /* ... */ }
  areConnected(source, destination) { /* ... */ }
  findPath(source, destination, path = new Map()) { /* ... */ }
  findAllPaths(source, destination, path = new Map()) { /* ... */ }
}

Graph as a class:

• Very useful for creating libraries or reusable algorithms (find a path, are connected, etc.).
• OOP Style.
• Might be time consuming to implement during coding interviews.

Graph as Map + Array

Other way to represent graph is like an Map + Array:

1
2
3
4
5

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

ES6+ Map:

1
2
3
4
5

const graph = new Map([
  ['a', ['b', 'c']],
  ['b', ['c']],
  ['c', []],
]);

Graph as a HashMap:

• Very quick to implement
• Might not be reusable since it’s tailor to the specific problem in hand.
• Build the entire graph before solving the problem.

Implicit Graph

Some times you don’t have to build a graph upfront. You can calculate adjacent nodes as you go.

For instance, this a template for finding a node in an implicit graph using BFS:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

function bfs(target) {
  const queue = [[0, 0]]; // 1. Initialize queue with Node and current distance 0
  const seen = new Set(0); // 2. Initialize set

  for (const [current, distance] of queue) { // 3. Loop until the queue is empty
    if (current === target) return distance; // 4. Check dequeued is solution
    for (const [neighbor, currDist] of getNeighbors(node)) { // 5. Get next possible moves (neighbor nodes)
      if (seen.has(neighbor) continue; // 6. Skip seen nodes
      seen.add(neighbor); // 7. Mark next node as seen.
      queue.push([neighbor, currDist + 1]); // 8. Add neighbor to queue and increase the distance.
    }
  }

  return -1; // 9. If you didn't find the answer, return something like -1/null/undefined.
}

function getNeighbors(node) {
  // TODO: implement based on the problem.
}

Graph on the go:

• Quick to implement
• Might not be reusable since it’s tailor to the specific problem in hand.
• It doesn’t need to build the complete graph up-front; it will discover adjacent nodes as it goes.

Let’s do some examples of each one so we can drive these concepts home!

Solving graph problems

Let’s see how you can use the afore mention implementations to solve real interview questions.

Explicit Graph Structure (Map + Array)

Let’s say you are working for a genealogy company, and you need to find if two people are related given a family tree (graph).

In this case, we can translate the family tree into a graph, where the nodes are the people, and the edges are their relationships (Father/Mother, Son/Daugther, etc.)

Let’s take a family for instance and represent it as a graph:

The Simpson Family Tree Example

This might be something like this:

1 2 3 4

// people: nodes = ["Bart", "Homer", "Marge", "Lisa", "Moe", "Herb", "Abraham", "Mona", "Selma", "Clancy", "Jackie", "Bob"]; // relationships: edges = [["Bart","Homer"],["Bart","Marge"],["Lisa","Homer"],["Lisa","Marge"],["Herb","Abraham"],["Herb","Mona"],["Homer","Abraham"],["Homer","Mona"],["Selma","Clancy"],["Selma","Jackie"],["Marge","Clancy"],["Marge","Jackie"],["Bob","Herb"]];

Interview Question: Given a graph (nodes and edges) and queries return for each query element true if they are related or false if they are not.

Example 1:

• Input:

  1 2 3

  nodes = ["Bart", "Homer", "Moe"] edges = [["Bart","Homer"]] queries = [["Bart","Homer"], ["Bart","Moe"]];

• Output:

  1	[true, false]

  Bart and Homer are related, so the first element is true; Bart and Moe are NOT related, so the 2nd element is false.

• Function signature:

1
2
3

function findRelated(nodes: any[], edges: [any, any][], queries: [any, any][]): boolean[] {
  // TODO: Implement
}

Here are some ideas on how to solve this problem:

• We need to traverse the graph from a starting point to a destination.
• If there’s a path, the two people are related (e.g., Home and Bart)
• If no path is found, then the two people are NOT related (e.g., Bart and Moe).
• We can solve this problem by using DFS or BFS.

Do you want to give it a try before looking at the solution? When you are ready, hit run!

function findRelated(nodes, edges, queries) {
  // Write your code here
}

// or here ;)

// ---------------------
// ------- Tests -------
// ---------------------
const assert = require('assert');
let nodes, edges, queries, expected;

// TEST 1
nodes = ["Bart", "Homer", "Marge", "Lisa", "Moe"]; // people
edges = [["Bart","Homer"],["Bart","Marge"],["Lisa","Homer"],["Lisa","Marge"]]; // relationships
queries = [['Bart', 'Lisa'], ['Homer', 'Moe']]; // questions
expected = [true, false];
assert.deepEqual(findRelated(nodes, edges, queries), expected);

// TEST 2
nodes = [1,2,3,4,5];
edges = [[1,2],[1,3],[2,5]];
queries = [[1, 1], [1, 2], [1, 4], [1, 5]];
expected = [true, true, false, true];
assert.deepEqual(findRelated(nodes, edges, queries), expected);

// TEST 3
nodes = ["Bart", "Homer", "Marge", "Lisa", "Moe", "Herb", "Abraham", "Mona", "Selma", "Clancy", "Jackie", "Bob"];
edges = [["Bart","Homer"],["Bart","Marge"],["Lisa","Homer"],["Lisa","Marge"],["Herb","Abraham"],["Herb","Mona"],["Homer","Abraham"],["Homer","Mona"],["Selma","Clancy"],["Selma","Jackie"],["Marge","Clancy"],["Marge","Jackie"],["Bob","Herb"]];
queries = [['Bart', 'Lisa'], ['Homer', 'Moe'], ['Lisa', 'Bob'], ['Bart', 'Selma'], ['Moe', 'Lisa']];
expected = [true, false, true, true, false];
assert.deepEqual(findRelated(nodes, edges, queries), expected);

console.log('All tests passed! 👏 🎂');

Here’s my solution to this problem…

1
2
3
4
5
6
7
8
9

function findRelated(nodes, edges, queries) {
  const graph = nodes.reduce((map, node) => map.set(node, []), new Map());
  edges.forEach(([u, v]) => {
    graph.get(u).push(v);
    graph.get(v).push(u); // undirected graph (2-ways)
  });

  return queries.map(([u, v]) => isRelated(graph, u, v));
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

function isRelated (graph, start, target) {
    const queue = [start];
    const seen = new Set([start]);

    for (let node of queue) {
        if (node === target) return true;
        graph.get(node).forEach(adj => {
            if (seen.has(adj)) return;
            seen.add(adj);
            queue.push(adj);
        });
    }
    return false;
}

1
2
3
4
5
6

function isRelated (graph, node, target, seen = new Set()) {
    if (node === target) return true;
    if (seen.has(node)) return false;
    seen.add(node);
    return graph.get(node).some(adj => isRelated(graph, adj, target, seen));
}

As you can see, we can either use a BFS or DFS approach to solve the problem. Not all questions are like that. In the next example, you will see that one of them leads to a more optimal solution than the other.

Implicit Graph: Build and Traverse as you go

Let’s solve this example of a combination lock.

You have a combination lock. It has 4 wheels that go from 0 to 9. Your job is to find the minimum amount of wheel turns to get to a target combination. The starting point is always 0000. However, there are several combinations that you have to avoid: deadends. If you get into a dead-end, the wheels will not turn anymore. If the target combination is impossible to reach return -1, otherwise return the minimum number of wheel turns.

Examples 1:

• Input: deadends = [“8888”], target = “0109”
• Output: 2
• Explanation: 0000 -> 0009 -> 0109

Examples 2:

• Input: deadends = [“8887”,”8889”,”8878”,”8898”,”8788”,”8988”,”7888”,”9888”], target = “8888”
• Output: -1
• Explanation: We can’t reach without crossing a deadend.

Do you want to give it a try?

function openLock(deadends, target) {
  // your code goes here!
}

// ---------------------
// ------- Tests -------
// ---------------------
const assert = require('assert');
let deadends, target;

deadends = ['8888'];
target = '0109';
assert.deepEqual(openLock(deadends, target), 2, 'Test #1');

deadends = ['8887','8889','8878','8898','8788','8988','7888']
target = '8888';
assert.deepEqual(openLock(deadends, target), 8, 'Test #2');

console.log('All tests passed! 👏 🥦');

Solution for open the lock

We could solve the problem using DFS or BFS. However, BFS is much more performant… why? We are looking for a minimum amount of turns. As soon as BFS found the target, that is guaranteed to be the minimum. However, that’s not the case for DFS. It goes deep and might found a solution quicker, but it might not be the minimum amount of turns. With DFS, we have to traverse ALL possibilities to see which path to the target is the shortest.

Here’s the BFS solution

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

function openLock(deadends, target) { const stop = new Set(deadends); const queue = [['0000', 0]]; const seen = new Set(['0000']); for (const [current, turns] of queue) { if (stop.has(current)) continue; if (current === target) return turns; for (const next of getNextTurns(current)) { if (seen.has(next)) continue; seen.add(next); queue.push([next, turns + 1]); } } return -1; }; function getNextTurns (str) { return Array.from(str).reduce((arr, char, i) => arr.concat( `${ str.slice(0, i) }${ (Number(char) + 1) % 10 }${ str.slice(i+1) }`, `${ str.slice(0, i) }${ (Number(char) + 9) % 10 }${ str.slice(i+1) }`, ), []); }

We will generate around 8 combinations on each step, and these 8 combinations create 7 more each one (we skip seen nodes) and so on.

If you want to see more levels of combination take a look here: combinations graph up to 3 levels

Breadth-First-Search (BFS) vs Depth-First-Search (DFS)

The most common graph traversal algorithms are breadth-first-search (BFS) and depth-first-search (DFS). BFS covers all cases adjacent paths nearby and then expand, while DFS goes deep on one way and only comes back when there’s nowhere else to go.

Breadth-First-Search (BFS)	Depth-First-Search (DFS)

In the pictures above, you can see that BFS goes level by level, while DFS goes as deep as it can in a branch.

In general, you want to use DFS when…

• The solutions are far away from the starting point.
• If the graph/tree/maze might be wide but not too deep (e.g., graph is finite).
• There are too many adjacent nodes to be practical for BFS.
• Usually used for game simulations where the number of possible moves is massive. DFS make a decision, then explore all paths through this decision. And if this decision leads to a win situation, we stop.
• Real-world applications of DFS: topological sorting (use for scheduling a sequence of jobs or tasks based on their dependencies), spreadsheets, build systems, data serialization, etc.

You want to use BFS when…

• The solution is near to the starting point.
• If the graph/tree/maze is extremely deep but not too wide (e.g., the graph might be infinite).
• The number of adjacent nodes is limited. (e.g., for our case, each cell has 8 next possible moves)
• Usually used for finding the shortest path between two nodes.
• Real-world applications of BFS: anything that can benefit from finding the shortest path, such as GPS Navigation systems (Google Maps), Peer to peer (P2P) applications such as the torrent clients. Other usages are web crawlers, social networks, etc.

Since the board is infinite, DFS won’t work for us. If it chooses a path that doesn’t contain the target location, it will never find an end. So, BFS is the right approach here!

Steps to solve algorithmic questions on interviews

In these section, we are going to practice some real interview questions. First, we are going to introduce 10 steps to avoid you getting in stuck in an interview. Finally, we are going to cover some examples. The only way to get better at it is through Practice, Practice, and more Practice.

Ten steps to avoid getting stuck

1. 👂 Listen/read carefully and repeat the question out loud (in your own words).
2. 🗣 Ask clarifying questions to help understand the problem better.
3. 🎨 Create 2-3 examples and draw diagrams about the problem.
4. 💪 Find a brute force solution as soon as possible (how would you do it manually). But don’t implement it yet!
5. 🎯 Determine what’s the best time complexity, theoretically. E.g. O(n) or O(m * n), etc.
6. 🧠 Brainstorm different approaches (Think out loud). State the runtime (Big O) of each one.
7. 📝 Let’s CODE: Implement the best approach you have so far (or the brute force, better something than nothing) while following a simple and short example. You can write the code while testing multiple cases at once to save time.
8. 🏃‍♂️ DRY RUN: Test your implementation on your mind. Imagine you are the compiler, and you have to tell the output of EACH LINE. Make fixes as needed. (For some companies, the code execution is disabled (Facebook), and others use a Google Doc (Google), so it’s vital to learn to test the code in your mind.)
9. 💻 RUN YOUR CODE if allowed
10. 🐛 Fix issues as they emerge and repeat previews steps if necessary.

Interview Questions for Practice

Here are some exercises for you to practice the ten steps and the solutions to some. These steps are especially necessary when you are not given the function signature nor examples. Sometimes, you have to figure them out by asking questions.

Let’s do a simulation!

Chess Knight Problem ♞

Given an infinite chessboard, find out how many moves does the knight needs to reach a given square on the board.

Asking Clarifying questions

Once you understand the statement, the first thing you need to do before doing any code is to ask clarifying questions. Try to come up with some questions you would ask before looking at my clarifying questions below.

After you ask some clarifying questions, the next step is to come up with some examples. Before you write any code, try to identify edge cases and possible scalability problems. Examples are critical to your success! Let’s draw a board with some possible target positions.

The first case, T1, is in the best-case scenario. It’s just one hop away; the second case is compelling because you have to move away from the starting point and then come back. The other two cases are just far away destinations.

Now that you have some examples, it’s time to brainstorm approaches! No coding yet!

If you are familiar with graphs, you might notice that this can be seen as a graph problem. The starting position can be seen as a node, and then each of the next 8 locations are the adjacent nodes.

So basically, once we have a starting point and adjacent nodes that we can visit, this can be solved using a graph traversal algorithm.

Solution

First, give it a try yourself before looking at my answer, but don’t spin your wheels for too long. If you haven’t get it working after 35 minutes, take a peek at the answer. Then try again on your own.

/**
 * Given an infinite chessboard, find out how many moves does
 * the knight needs to reach a given square coordinate on the board.
 *
 * @param {Number} dx - Destination x coordinate
 * @param {Number} dy - Destination y coordinate
 * @returns {Number} minimum number of moves to reach target
 */
function knightMoves(dx, dy) {
    // write your awesome code here!
}

// ---------------------
// ------- Tests -------
// ---------------------
const assert = require('assert');

assert.equal(knightMoves(0, 0), 0, 'finds t0');
assert.equal(knightMoves(1, 2), 1, 'finds t1');
assert.equal(knightMoves(0, 1), 3, 'finds t2');
assert.equal(knightMoves(6, -6), 4, 'finds t3');
assert.equal(knightMoves(0, 7), 5, 'finds t4');
assert.equal(knightMoves(170, 123), 99, 'finds far far away galaxies');

console.log('Congrats! 👏👏👏  All tests passed! 🎂');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

function knightMoves(dx, dy) { // destination x and y
  const queue = [[[0, 0], 0]];
  const seen = new Set([0, 0].toString());

  for (const [[x, y], moves] of queue) { // current x and y
    if (x === dx && y === dy) return moves;
    const next = [1, -1].map((i) => [2, -2].map((j) => [[x + i, y + j], [x + j, y + i]])).flat(2);
    for (const [nx, ny] of next) { // next x and y
      if (seen.has([nx, ny].toString())) continue;
      seen.add([nx, ny].toString());
      queue.push([[nx, ny], moves + 1]);
    }
  }

  return -1;
}

1
2
3
4
5
6
7

const s = new Set();

s.add([0, 0]);
console.log(s.has([0, 0])); // false 🙀

s.add([0, 0].toString());
console.log(s.has([0, 0].toString())); // true 👍

1
2

const next = [[x + 1, y + 2], [x + 2, y + 1], [x + 2, y - 1], [x + 1, y - 2], [x - 1, y - 2], [x - 2, y - 1], [x - 2, y + 1], [x - 1, y + 2]];
// for x=0, y=0: [[1,2],[2,1],[2,-1],[1,-2],[-1,-2],[-2,-1],[-2,1],[-1,2]]

1
2

const next = [1, -1].map((i) => [2, -2].map((j) => [[x + i, y + j], [x + j, y + i]])).flat(2);
// for x=0, y=0: [[1,2],[2,1],[2,-1],[1,-2],[-1,-2],[-2,-1],[-2,1],[-1,2]]

1
2

const next = [1, -1].reduce((a, i) => [2, -2].reduce((b, j) => [...b, [x + i, y + j], [x + j, y + i]], a), []);
// for x=0, y=0: [[1,2],[2,1],[2,-1],[1,-2],[-1,-2],[-2,-1],[-2,1],[-1,2]]

How did you do? Paste your solution and questions in the comments section!

Most BFS problems follow the same pattern:

1. Initialize queue
2. Initialize set to keep track of the visited positions.
3. Loop until the queue is empty or you find a solution.
4. Dequeue element from the queue and check if it’s a solution.
5. If it’s not part of the solution, move to get the next possible moves (neighbor nodes).
6. Skip seen nodes.
7. Mark the next node, as seen.
8. Add neighbors to queue and increase the distance.
9. If you didn’t find the answer, return something like -1/null/undefined.

BFS Template

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

function bfs(target) {
  const queue = [[0, 0]]; // 1. Initialize queue with Node and current distance 0
  const seen = new Set(0); // 2. Initialize set

  for (const [current, distance] of queue) { // 3. Loop until the queue is empty
    if (current === target) return distance; // 4. Check dequeued is solution
    for (const [neighbor, currDist] of getNeighbors(node)) { // 5. Get next possible moves (neighbor nodes)
      if (seen.has(neighbor) continue; // 6. Skip seen nodes
      seen.add(neighbor); // 7. Mark next node as seen.
      queue.push([neighbor, currDist + 1]); // 8. Add neighbor to queue and increase the distance.
    }
  }

  return -1; // 9. If you didn't find the answer, return something like -1/null/undefined.
}

function getNeighbors(node) {
  // TODO: implement based on the problem.
}

Here’s another exercise to practice

Maze Path

You have a ball at a starting point, that can roll up, down, left and right. However, the ball won’t stop rolling until it hits a wall. Your task is to check if there’s a path from start to destination. You may assume that the borders of the maze are all walls.

The maze is represented in a grid (2d array):

• Walls are represented as 1.
• Empty spaces are 0.

E.g.:

start = [ 0, 4 ]
end = [ 4, 4 ]
maze = [
  [ 0, 0, 1, 0, 0 ],
  [ 0, 0, 0, 0, 0 ],
  [ 0, 0, 0, 1, 0 ],
  [ 1, 1, 0, 1, 1 ],
  [ 0, 0, 0, 0, 0 ]
]

Give it a try!

/**
 * You have a ball at a starting point that can roll up, down, left and right.
 * However, the ball won't stop rolling until it hits a wall.
 * Your tasks is to check if there's a path from start to destination
 * You may assume that the borders of the maze are all walls.
 *
 * @param {number[][]} maze - 2D array where 1 = wall and 0 = empty.
 * @param {number[]} start - [row, col] of the starting point
 * @param {number[]} destination - [row, col] target destination
 * @return {boolean}
 */
function hasPath(maze, start, destination) {

};

// --- testing ---

const assert = require('assert');

assert.equal(hasPath([
  [ 0 ]
], [0, 0], [0, 0]), true, 'should pass case #1');

assert.equal(hasPath([
  [ 1 ]
], [0, 0], [0, 0]), false, 'should pass case #2');

assert.equal(hasPath([
  [ 0, 0, 0 ]
], [0, 0], [0, 2]), true, 'should pass case #3');

assert.equal(hasPath([
    [ 0, 0, 0 ],
], [0, 0], [0, 1]), false, 'should pass case #4');

assert.equal(hasPath([
  [ 0, 1, 0 ],
], [0, 0], [0, 2]), false, 'should pass case #5');

assert.equal(hasPath([
  [ 0, 1, 0 ],
  [ 0, 0, 0 ],
], [0, 2], [0, 0]), true, 'should pass case #6');

assert.equal(hasPath([
  [ 0, 0, 1, 0, 0 ],
  [ 0, 0, 0, 0, 0 ],
  [ 0, 0, 0, 1, 0 ],
  [ 1, 1, 0, 1, 1 ],
  [ 0, 0, 0, 0, 0 ]
], [ 0, 4 ], [ 3, 2 ]), false, 'should pass case #7');

assert.equal(hasPath([
  [ 0, 0, 1, 0, 0 ],
  [ 0, 0, 0, 0, 0 ],
  [ 0, 0, 0, 1, 0 ],
  [ 1, 1, 0, 1, 1 ],
  [ 0, 0, 0, 0, 0 ]
], [ 0, 4 ], [ 4, 4 ]), true, 'should pass case #8');

console.log('Congrats! 👏👏👏  All tests passed! 🍎');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

function hasPath(maze, start, dest) {
  const queue = [[start, 0]];
  const seen = new Set([start.join()]);
  const directions = [[0,1], [0,-1], [1,0], [-1,0]]; // right, left, down and up.

  for (let [[r, c], dist] of queue) {
    if (r === dest[0] && c === dest[1] && maze[r] && maze[r][c] === 0) return true;

    for (let [dr, dc] of directions) {
      let nr = r, nc = c; // IMPORTANT: reset coordinates
      while (maze[nr + dr] && maze[nr + dr][nc + dc] === 0) {
          nr += dr;
          nc += dc;
      }
      if (seen.has([nr, nc].join())) continue;
      seen.add([nr, nc].join());
      queue.push([[nr, nc], dist + 1]);
    }
  }

  return false;
};

How did you do? Feel free to ask me any questions below!

REST API with Node.js

We are going to use express-generator and create a folder called server.

First, install the generator packages:

1

npm i -g express-generator

Note: You should have Node and NPM/Yarn installed.

REST API using ExpressJS

Now let’s scaffold the App using the generator:

1

express server -e

Let’s install all its dependencies on the server folder:

1

cd server && npm i

and now let’s make sure it’s working:

1

npm start

Go to localhost on port 3000 and make sure you can see a “Welcome to Express.”

http://localhost:3000/

Changes: a3fcacd - REST API using ExpressJS: scaffold

Creating a host alias for the server

We want to run the server to work regardless of the environment where we run it. (It will be useful for Docker later on)

For that we can create an alias by editing the hosts:

• Windows: c:\windows\system32\drivers\etc\hosts
• Linux/Mac: /etc/hosts

Once you can open the file, you drop the following line at the end:

1

127.0.0.1 server

Now you should be able to access the server by visiting:

http://server:3000/

(If you have trouble editing the host file, take a look here)

Creating API routes and responding to requests

Now we are going to create a new route:

1

/api/todos[/:id]

This route will get all our todos, update, and delete them.

Create a new router file called todos in the following path:

1

touch server/routes/todos.js

and add this initial content:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

const express = require('express');
const router = express.Router();

const TODOS = [
  { title: 'Create API to get this list', isDone: true },
  { title: 'Connect API with Angular', isDone: true },
  { title: 'Connect server with mongo', isDone: false },
  { title: 'Publish app', isDone: false },
];

/* GET /api/todos */
router.get('/', async (req, res) => {
  try {
    res.json(TODOS);
  } catch (error) {
    res.status(500).json({ error });
  }
});

module.exports = router;

All this is doing is replying to the GET commands and returning a hard-coded list of todos. We will replace it later to get data from mongo instead.

Then we need to register the route as follows:

1
2
3
4
5

var todosRouter = require('./routes/todos');

// ...

app.use('/api/todos', todosRouter);

The method use registers the new path /api/todos. When we get any call on this path, our todosRouter will handle it.

You can restart your server or use nodemon to pick up changes and refresh the browser.

1
2

## npm i -g nodemon
nodemon server/bin/www

That should get your server running. Now you can see it in action using cURL:

1
2

curl -XGET server:3000/api/todos
## curl -XGET localhost:3000/api/todos

This command should get you all the lists in JSON format!

In the next step, we will query the server using Angular instead of curl. After that, we will complete the rest of the operations (update, delete, create).

6f8a502 - Creating API routes and responding to requests

Connecting REST API with Angular App.

Let’s now prepare our angular App to use the server API that we just created.

As you might know, when you run ng serve, it will trigger a development server. However, our API is an entirely different server. To be able to connect the two, we need to create a proxy.

Creating a proxy in Angular to talk to the API server

Let’s create a new file that will tell Angular when to look for specific HTTP paths. In this case, we are going to defer all /api to our express server.

1
2
3
4
5
6

{
  "/api": {
    "target": "http://server:3000",
    "secure": false
  }
}

(This will need the host alias from the step before)

Then, we have to tell Angular to load this file when we are serving the App. We are going to do that in the angular.json file.

If you are using the same version of angular CLI, you need to insert this on line 71:

1

"proxyConfig": "src/proxy.conf.json"

For some context, here are the surrounding elements:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

{
  "$schema": "./node_modules/@angular/cli/lib/config/schema.json",
  // ...
  "projects": {
    "Todos": {
      // ...
      "architect": {
        // ...
        "serve": {
          "builder": "@angular-devkit/build-angular:dev-server",
          "options": {
            "browserTarget": "Todos:build",
            "proxyConfig": "src/proxy.conf.json"  // <-- Insert this line
          },
          // ...
        },
        // ...
      }
    }},
  "defaultProject": "Todos"
}

Now our App will pass all requests that start with /api to http://localhost:3000 (or whatever path you specified on the proxy.conf).

Next, we are going to make use of these new routes!

e81ddb8 - Creating a proxy in Angular to talk to the API server

Using HTTP Client to talk to the server

To talk to the server, we are going to use the HttpClient module.

Let’s go to the app.module and let’s import it:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

import { HttpClientModule } from '@angular/common/http';

// ...

@NgModule({
  declarations: [
    AppComponent,
    TodoComponent
  ],
  imports: [
    BrowserModule,
    AppRoutingModule,
    FormsModule,
    RouterModule.forRoot(routes),
    HttpClientModule, // <---- import module
  ],
  providers: [],
  bootstrap: [AppComponent]
})
export class AppModule { }

Now that the HttpClient is available in our App let’s add it to the service and make use of it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

import { HttpClient } from '@angular/common/http';

//...

const API = '/api/todos';

//...

@Injectable({
  providedIn: 'root'
})
export class TodoService {

  constructor(private http: HttpClient) { }

  get(params = {}) {
    return this.http.get(API, { params });
  }

  // ...

We change the TodoService.get to use HTTP client. However, the component was responding to a Promise, and the HTTP.get returns an Observable. So, let’s change it.

Change the getTodos method from the old one to use this one that handles an observable.

1
2
3
4
5
6

getTodos(query = '') {
  return this.todoService.get(query).subscribe(todos => {
    this.todos = todos;
    this.activeTasks = this.todos.filter(todo => !todo.isDone).length;
  });
}

The main difference is that instead of a .then, we are using .subscribe. Everything else remains the same (for now).

That’s it, let’s test it out!

Run these commands on your terminal:

1
2

## run node server
nodemon server/bin/www

on another terminal session run also:

1
2

## run angular App
ng serve

Once you have both running, you can go to http://localhost:4200/all, and you can verify that it’s coming from your server!

If you are running nodemon, you can change the TODOS on server/routes/todos.js and refresh the browser, and see how it changes.

But, we don’t want to have hard-coded tasks. Let’s create a proper DB with Mongo.

Setting up MongoDB

It’s time to get MongoDB up and running. If don’t have it installed, you have a couple of options:

1
2

brew tap mongodb/brew
brew install mongodb-community

We are going to use Docker since it’s an excellent way to have everything running together with one command. Also, you can deploy it to the cloud and scale it quickly.

Dockerizing the MEAN stack

Let’s get everything running (Node Server, Angular, and Mongo). We will create a docker-compose file, which is going to list all our services, and we can run them all at once.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

version: "3.7"

services:
  app:
    image: node:lts-alpine
    working_dir: /app
    volumes:
      - ./:/app
    ports:
      - 4200:4200
    # --host 0.0.0.0 to listen to all the interfaces from the container (dev env)
    command: >
      sh -c "npm install &&
             npx ng serve --host 0.0.0.0"

  server:
    image: node:lts-alpine
    working_dir: /server
    volumes:
      - ./server:/server
    # port 3000 has to match src/proxy.conf.json
    ports:
      - 3000:3000
    depends_on:
      - mongo
    environment:
      MONGO_HOST: mongo
    command: >
      sh -c "npm i -g nodemon && npm install && nodemon ./bin/www"

  mongo:
    image: mongo

All right, now we can get the whole full-stack App running with one command:

1

docker-compose up --build

NOTE: close other terminals running a web server so the ports don’t conflict. The docker-compose command will create 3 containers for our Angular App, Node Server, and Mongo DB. You can also see all the logs in one place.

After you wait a minute or so, you should be able to open the App on http://localhost:4200/.

Now we can make use of mongo. Keep docker-compose running and now let’s remove the hard-coded tests and use the database.

0763db0 - docker compose

Creating MongoDB schema with Mongoose

Let’s install Mongoose, which is a library for managing MongoDB from Node.js.

1

cd server && npm i mongoose@5.9.18

NOTE: make sure you installed it on the ./server/package.json, rather than the client-side packages ./packages.json.

The first thing we need to do is to connect to Mongo when our server starts. Go to server/app.js and add the following code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

const mongoose = require('mongoose');

// connect to db
const user = process.env.MONGO_USER;
const mongoPort = process.env.MONGO_PORT || 27017;
const mongoHost = process.env.MONGO_HOST || 'localhost';
const auth = user ? `${user}:${process.env.MONGO_PASS}@` : '';
const DB_STRING = `mongodb://${auth}${mongoHost}:${mongoPort}/todos`;

console.log(`Running node ${process.version}...`);
console.log(`Connecting to DB... ${DB_STRING}`);

const config = { useNewUrlParser: true, useUnifiedTopology: true};
mongoose.connect(DB_STRING, config)
  .then(() => console.log(`Connected!`))
  .catch(console.error);

15f6e25 - add db string to connect to mongo

We can pass some ENV variables like MONGO_HOST. If we run it locally, it will use localhost, but if you run it on Docker, we want to pass a hostname. You can see that in the docker-compose.yml file.

Now, let’s define our data model for Mongo. Let’s create a folder models inside server and add a file called “todos.js”.

1
2
3
4
5
6
7
8
9
10
11
12

const mongoose = require('mongoose');

const { Schema, model } = mongoose;

const TodoSchema = new Schema({
  title: String,
  isDone: Boolean,
  notes: String,
  updated_at: { type: Date, default: Date.now },
});

module.exports = model('Todo', TodoSchema);

The new schema is defining what fields we want to store and what the types are. The updated_at will update automatically when we create a new todo.

436b0ad - npm i mongoose

b2674f3 - Creating MongoDB schema with Mongoose

Adding all the API routes to modify data in the DB

Let’s add all the routes to create, read, update, and delete data from Mongo.

The Mongoose library provides some convenient methods to do CRUD operations:

• ** Todo.find**: find data matching a given query. ({}, get all, while {isDone: true} get only completed tasks).
• ** Todo.create**: Create a new todo
• ** Todo.findByIdAndUpdate**: Find Todo by given id and update its content.
• ** Todo.findByIdAndDelete**: Find Todo by given id and delete it.
• ** Todo.deleteMany**: Delete everything matching a given query.

Here are the routes by their matching HTTP verb (GET, PUT, POST, DELETE). In the next sections, we will test all these routes and go over some more details.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

const express = require('express');
const router = express.Router();

const Todo = require('../models/todo');

/* GET /api/todos */
router.get('/', async (req, res) => {
  try {
    const list = await Todo.find(req.query);
    res.json(list);
  } catch (error) {
    res.status(500).json({ error });
  }
});

/* POST /api/todos */
router.post('/', async (req, res) => {
  try {
    const todo = await Todo.create(req.body);
    res.json(todo);
  } catch (error) {
    res.status(500).json({ error });
  }
});

/* PUT /api/todos/:id */
router.put('/:id', async (req, res) => {
  try {
    const options = { new: true };
    const todo = await Todo.findByIdAndUpdate(req.params.id, req.body, options);
    res.json(todo);
  } catch (error) {
    res.status(500).json({ error });
  }
});

/* DELETE /api/todos/:id */
router.delete('/:id', async (req, res) => {
  try {
    const todo = await Todo.findByIdAndDelete(req.params.id);
    res.json(todo);
  } catch (error) {
    res.status(500).json({ error });
  }
});

// Beaware: it can delete all data from db if body is empty (DON'T expoose deleteMany in PRODUCTION!)
/* DELETE /api/todos */
router.delete('/', async (req, res) => {
  try {
    const todo = await Todo.deleteMany(req.body);
    res.json(todo);
  } catch (error) {
    res.status(500).json({ error });
  }
});

module.exports = router;

We added many routes to this step. Take your time to go through them. In the next section, we will test them using curl and then integrated them with Angular.

f4f2281 - Adding all all the API routes to modify data in DB

Testing the API CRUD operations

Since we installed a new package, mongoose, we have to run npm install in the docker containers. Otherwise, file changes are picked up automatically, and you don’t need to restart.

Stop docker-compose and start it again docker-compose up --build.

Creating a new task and getting lists

You can create a new task using the following command:

1

curl -XPOST server:3000/api/todos -H "Content-Type: application/json" -d '{"title": "CRUD API", "isDone": false}'

Now, let’s see if it’s there:

1

curl -XGET server:3000/api/todos

You should have got something like this:

1

[{"_id":"5edc2a6d0c41d60054ad715f","title":"CRUD API","isDone":false,"updated_at":"2020-06-06T23:44:45.966Z","__v":0}]⏎

You can also check Angular on http://localhost:4200/all. The new task should be there!

Update data with PUT method

If you remember from your routes file, we are using the method PUT to update tasks.

1
2
3
4
5
6
7
8
9
10

/* PUT /api/todos */
router.put('/:id', async (req, res) => {
  try {
    const options = { new: true };
    const todo = await Todo.findByIdAndUpdate(req.params.id, req.body, options);
    res.json(todo);
  } catch (error) {
    res.json(500, { error });
  }
});

By default findByIdAndUpdate returns the original document. We are passing { new: true } so we can return the updated document.

For updating a task you need the _id. You can get it from the previous step, when we listed all the tasks. For my case the _id is 5edc2a6d0c41d60054ad715f, find yours and replace it in the next command:

1

curl -XPUT server:3000/api/todos/5edc2a6d0c41d60054ad715f -H "Content-Type: application/json" -d '{"title": "Finish PUT API", "isDone": true, "note": "New Field"}'

As you can see in the last update, we can modify existing fields and add new values like the note field.

Erasing data with the DELETE method

For our todo route, we also defined the DELETE method. Similar to the update, we need to pass and id.

1
2
3
4
5
6
7
8
9

/* DELETE /api/todos */
router.delete('/:id', async (req, res) => {
  try {
    const todo = await Todo.findByIdAndDelete(req.params.id);
    res.json(todo);
  } catch (error) {
    res.status(500).json({ error });
  }
});

Again, remember to replace the next call with yout _id:

1

curl -X DELETE server:3000/api/todos/5edc2a6d0c41d60054ad715f

If you check the UI, all tasks will be gone: http://localhost:4200/all.

As much fun as curl is, let’s move on and complete all these functionalities in Angular.

Angular Service to talk to the server

There are two main changes that we need to make in other to use the API server.

1. We need to change the TodoService service to use HTTP client.
2. Change the TodoComponent component to use the methods.

Angular service using the HTTP client

In the following code, we are using the HTTP client, to make the appropriate calls:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

import { Injectable } from '@angular/core';
import { HttpClient } from '@angular/common/http';

export interface ITodo {
  _id?: string;
  title: string;
  isDone: boolean;
  notes: string;
  update_at: string;
  editing ?: boolean;
}

const API = '/api/todos';

@Injectable({
  providedIn: 'root'
})
export class TodoService {
  constructor(private http: HttpClient) { }

  get(params = {}) {
    return this.http.get(API, { params });
  }

  add(data: ITodo) {
    return this.http.post(API, data);
  }

  put(changed: ITodo) {
    return this.http.put(`${API}/${changed._id}`, changed);
  }

  toggle(selected: ITodo) {
    selected.isDone = !selected.isDone;
    return this.put(selected);
  }

  delete(selected: ITodo) {
    return this.http.delete(`${API}/${selected._id}`);
  }

  deleteCompleted(body = { isDone: true }) {
    return this.http.request('delete', `${API}`, { body });
  }
}

The Todo service matches the HTTP verbs that we used in curl and passes the payloads.

Let’s now change the TodoComponent that goes along with these changes.

a93291c - Angular service using HTTP client

Angular TodoComponet updates

Here’s what your component should look like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

import { Component, OnInit } from '@angular/core';
import { ActivatedRoute } from '@angular/router';

import { TodoService, ITodo } from './todo.service';

@Component({
  selector: 'app-todo',
  templateUrl: './todo.component.html',
  styleUrls: ['./todo.component.scss'],
  providers: [TodoService]
})
export class TodoComponent implements OnInit {
  public todos: ITodo[];
  public activeTasks: number;
  public newTodo: string;
  public path: string;
  public mapToQuery = {
    all: {},
    active: { isDone: false },
    completed: { isDone: true },
  };
  constructor(private todoService: TodoService, private route: ActivatedRoute) { }

  ngOnInit() {
    this.route.params.subscribe(params => {
      this.path = params.status;
      this.getTodos(this.path);
    });
  }

  addTodo() {
    this.todoService
      .add({ title: this.newTodo, isDone: false } as unknown as ITodo)
      .subscribe(() => {
        this.getTodos();
        this.newTodo = ''; // clear input form value
      });
  }

  getTodos(route = 'all') {
    const query = this.mapToQuery[route];
    return this.todoService
      .get(query)
      .subscribe((todos: ITodo[]) => {
        this.todos = todos;
        this.activeTasks = this.todos.filter(todo => !todo.isDone).length;
      });
  }

  updateTodo(todo: ITodo, newValue: string) {
    todo.title = newValue;
    return this.todoService.put(todo).subscribe(() => this.getTodos());
  }

  destroyTodo(todo: ITodo) {
    this.todoService.delete(todo).subscribe(() => this.getTodos());
  }

  toggleTodo(todo: ITodo) {
    this.todoService.toggle(todo).subscribe(() => this.getTodos());
  }

  clearCompleted() {
    this.todoService.deleteCompleted().subscribe(() => this.getTodos());
  }
}

Let’s go over each part in the next sections.

Sending Queries with HTTP GET

In the component, one the first thing we do is check the route params (path):

1
2
3
4
5
6

ngOnInit() {
  this.route.params.subscribe(params => {
    this.path = params['status'];
    this.getTodos(this.path);
  });
}

When you click on the buttons All, Active, and Completed, that will trigger a route change.

To recap, these buttons use the router link. So, every time you click on them, they will change the URL.

1
2
3
4
5
6
7
8
9
10
11

<ul class="filters">
  <li>
    <a [routerLink]="['/all']" [class.selected]="path === 'all'">All</a>
  </li>
  <li>
    <a [routerLink]="['/active']" [class.selected]="path === 'active'">Active</a>
  </li>
  <li>
    <a [routerLink]="['/completed']" [class.selected]="path === 'completed'">Completed</a>
  </li>
</ul>

After we change the URL, the next thing we do is to call getTodos. Let’s see that next.

Get all todos

We can get all services using the following:

1
2
3
4
5
6
7
8
9

getTodos(route = 'all') {
  const query = this.mapToQuery[route];
  return this.todoService
    .get(query)
    .subscribe((todos: ITodo[]) => {
      this.todos = todos;
      this.activeTasks = this.todos.filter(todo => !todo.isDone).length;
    });
}

We this.todoService.get will issue an HTTP get and retrieve all the tasks from the database and update the todos. It also updates the number of active tasks (the ones that are not done).

The getTodos receives an argument (route) with the path that will be one of these: all, active, or complete. However, MongoDB doesn’t understand these words. We have to map it (mapToQuery) to something a proper query like { isDone: true }. This MongoDB will understand.

e33d540 - Angular TodoComponet updates

Modifying the todos

All the other operations, like the update, clear, toggle, are very similar. They trigger an action and then call getTodos, so the UI is up to date with the latest changes.

That’s all!

NOTE: I’d like this post to be up-to-date with the most common use cases for promises. If you have a question about promises and it’s not answered here. Please, comment below or reach out to me directly @iAmAdrianMejia. I’ll look into it and update this post.

Related Posts:

1. Async vs Sync in JavaScript
2. JavaScript Callbacks
3. JavaScript Promises (this one)

JavaScript Promises

A promise is an object that allows you to handle asynchronous operations. It’s an alternative to plain old callbacks.

Promises have many advantages over callbacks. To name a few:

• Make the async code easier to read.
• Provide combined error handling.
• Better control flow. You can have async actions execute in parallel or series.

Callbacks tend to form deeply nested structures (a.k.a. Callback hell). Like the following:

1
2
3
4
5
6
7
8
9

a(() => {
  b(() => {
    c(() => {
      d(() => {
        // and so on ...
      });
    });
  });
});

If you convert those functions to promises, they can be chained producing more maintainable code. Something like this:

1
2
3
4
5
6

Promise.resolve()
  .then(a)
  .then(b)
  .then(c)
  .then(d)
  .catch(console.error);

As you can see, in the example above, the promise object exposes the methods .then and .catch. We are going to explore these methods later.

How do I convert an existing callback API to promises?

We can convert callbacks into promises using the Promise constructor.

The Promise constructor takes a callback with two arguments resolve and reject.

• Resolve: is a callback that should be invoked when the async operation is completed.
• Reject: is a callback function to be invoked when an error occurs.

The constructor returns an object immediately, the promise instance. You can get notified when the promise is “done” using the method .then in the promise instance. Let’s see an example.

Wait, aren’t promises just callbacks?

Yes and no. Promises are not “just” callbacks, but they do use asynchronous callbacks on the .then and .catch methods. Promises are an abstraction on top of callbacks that allows you to chain multiple async operations and handle errors more elegantly. Let’s see it in action.

Promises anti-pattern (promise hell)

Before jumping into how to convert callbacks to promises, let’s see how NOT to it.

Please don’t convert callbacks to promises from this:

1
2
3
4
5
6
7
8
9

a(() => {
  b(() => {
    c(() => {
      d(() => {
        // and so on ...
      });
    });
  });
});

To this:

1
2
3
4
5
6
7
8
9

a().then(() => {
  return b().then(() => {
    return c().then(() => {
      return d().then(() =>{
        // ⚠️ Please never ever do to this! ⚠️
      });
    });
  });
});

Always keep your promises as flat as you can.

It’s better to do this:

1
2
3
4

a()
  .then(b)
  .then(c)
  .then(d)

Let’s do some real-life examples! 💪

Promesifying Timeouts

Let’s see an example. What do you think will be the output of the following program?

const promise = new Promise((resolve, reject) => {
  setTimeout(() => {
    resolve('time is up ⏰');
  }, 1e3);

  setTimeout(() => {
    reject('Oops 🔥');
  }, 2e3);
});

promise
  .then(console.log)
  .catch(console.error);

Is the output:

1
2

time is up ⏰
Oops! 🔥

or is it

1

time is up ⏰

?

It’s the latter, because

When a promise it’s resolved, it can no longer be rejected.

Once you call one method (resolve or reject) the other is invalidated since the promise in a settled state. Let’s explore all the different states of a promise.

Promise states

There are four states in which the promises can be:

• ⏳ Pending: initial state. Async operation is still in process.
• ✅ Fulfilled: the operation was successful. It invokes .then callback. E.g., .then(onSuccess).
• ⛔️ Rejected: the operation failed. It invokes the .catch or .then ‘s second argument (if any). E.g., .catch(onError) or .then(..., onError)
• 😵 Settled: it’s the promise final state. The promise is dead. Nothing else can be resolved or rejected anymore. The .finally method is invoked.

Promise instance methods

The Promise API exposes three main methods: then, catch and finally. Let’s explore each one and provide examples.

Promise then

The then method allows you to get notified when the asynchronous operation is done, either succeeded or failed. It takes two arguments, one for the successful execution and the other one if an error happens.

1

promise.then(onSuccess, onError);

You can also use catch to handle errors:

1

promise.then(onSuccess).catch(onError);

Promise chaining

then returns a new promise so you can chain multiple promises together. Like in the example below:

1
2
3
4

Promise.resolve()
  .then(() => console.log('then#1'))
  .then(() => console.log('then#2'))
  .then(() => console.log('then#3'));

Promise.resolve immediately resolves the promise as successful. So all the following then are called. The output would be

1
2
3

then#1
then#2
then#3

Let’s see how to handle errors on promises with then and catch.

Promise catch

Promise .catch the method takes a function as an argument that handles errors if they occur. If everything goes well, the catch method is never called.

Let’s say we have the following promises: one resolves or rejects after 1 second and prints out their letter.

1
2
3
4

const a = () => new Promise((resolve) => setTimeout(() => { console.log('a'), resolve() }, 1e3));
const b = () => new Promise((resolve) => setTimeout(() => { console.log('b'), resolve() }, 1e3));
const c = () => new Promise((resolve, reject) => setTimeout(() => { console.log('c'), reject('Oops!') }, 1e3));
const d = () => new Promise((resolve) => setTimeout(() => { console.log('d'), resolve() }, 1e3));

Notice that c simulates a rejection with reject('Oops!')

1
2
3
4
5
6

Promise.resolve()
  .then(a)
  .then(b)
  .then(c)
  .then(d)
  .catch(console.error)

The output is the following:

In this case, you will see a, b, and the error message on c. The function` will never get executed because the error broke the sequence.

Also, you can handle the error using the 2nd argument of the then function. However, be aware that catch will not execute anymore.

1
2
3
4
5
6

Promise.resolve()
  .then(a)
  .then(b)
  .then(c)
  .then(d, () => console.log('c errored out but no big deal'))
  .catch(console.error)

As you can see the catch doesn’t get called because we are handling the error on the .then(..., onError) part. d is not being called regardless. If you want to ignore the error and continue with the execution of the promise chain, you can add a catch on c. Something like this:

1
2
3
4
5
6

Promise.resolve()
  .then(a)
  .then(b)
  .then(() => c().catch(() => console.log('error ignored')))
  .then(d)
  .catch(console.error)

Now’dgets executed!! In all the other cases, it didn't. This earlycatch` is not desired in most cases; it can lead to things falling silently and make your async operations harder to debug.

Promise finally

The finally method is called only when the promise is settled.

You can use a .then after the .catch, in case you want a piece of code to execute always, even after a failure.

1
2
3
4
5
6
7

Promise.resolve()
  .then(a)
  .then(b)
  .then(c)
  .then(d)
  .catch(console.error)
  .then(() => console.log('always called'));

or you can use the .finally keyword:

1
2
3
4
5
6
7

Promise.resolve()
  .then(a)
  .then(b)
  .then(c)
  .then(d)
  .catch(console.error)
  .finally(() => console.log('always called'));

Promise class Methods

There are four static methods that you can use directly from the Promise object.

• Promise.all
• Promise.reject
• Promise.resolve
• Promise.race

Let’s see each one and provide examples.

Promise.resolve and Promise.reject

These two are helper functions that resolve or reject immediately. You can pass a reason that will be passed on the next .then.

1
2
3

Promise.resolve('Yay!!!')
  .then(console.log)
  .catch(console.error)

This code will output Yay!!! as expected.

1
2
3

Promise.reject('Oops 🔥')
  .then(console.log)
  .catch(console.error)

The output will be a console error with the error reason of Oops 🔥.

Executing promises in Parallel with Promise.all

Usually, promises are executed in series, one after another, but you can use them in parallel as well.

Let’s say are polling data from 2 different APIs. If they are not related, we can do trigger both requests at once with Promise.all().

For this example, we will pull the Bitcoin price in USD and convert it to EUR. For that, we have two independent API calls. One for BTC/USD and other to get EUR/USD. As you imagine, both API calls can be called in parallel. However, we need a way to know when both are done to calculate the final price. We can use Promise.all. When all promises are done, a new promise will be returning will the results.

const axios = require('axios');

const bitcoinPromise = axios.get('https://api.coinpaprika.com/v1/coins/btc-bitcoin/markets');
const dollarPromise = axios.get('https://api.exchangeratesapi.io/latest?base=USD');
const currency = 'EUR';

// Get the price of bitcoins on
Promise.all([bitcoinPromise, dollarPromise])
  .then(([bitcoinMarkets, dollarExchanges]) => {
    const byCoinbaseBtc = d => d.exchange_id === 'coinbase-pro' && d.pair === 'BTC/USD';
    const coinbaseBtc = bitcoinMarkets.data.find(byCoinbaseBtc)
    const coinbaseBtcInUsd = coinbaseBtc.quotes.USD.price;
    const rate = dollarExchanges.data.rates[currency];
    return rate * coinbaseBtcInUsd;
  })
  .then(price => console.log(`The Bitcoin in ${currency} is ${price.toLocaleString()}`))
  .catch(console.log);

As you can see, Promise.all accepts an array of promises. When the request for both requests are completed, then we can proceed to calculate the price.

Let’s do another example and time it:

1
2
3
4
5
6
7
8
9
10

const a = () => new Promise((resolve) => setTimeout(() => resolve('a'), 2000));
const b = () => new Promise((resolve) => setTimeout(() => resolve('b'), 1000));
const c = () => new Promise((resolve) => setTimeout(() => resolve('c'), 1000));
const d = () => new Promise((resolve) => setTimeout(() => resolve('d'), 1000));

console.time('promise.all');
Promise.all([a(), b(), c(), d()])
  .then(results => console.log(`Done! ${results}`))
  .catch(console.error)
  .finally(() => console.timeEnd('promise.all'));

How long is it going to take to solve each of these promises? 5 seconds? 1 second? Or 2 seconds?

You can experiment with the dev tools and report back your results ;)

Promise race

The Promise.race(iterable) takes a collection of promises and resolves as soon as the first promise settles.

1
2
3
4
5
6
7
8
9
10

const a = () => new Promise((resolve) => setTimeout(() => resolve('a'), 2000));
const b = () => new Promise((resolve) => setTimeout(() => resolve('b'), 1000));
const c = () => new Promise((resolve) => setTimeout(() => resolve('c'), 1000));
const d = () => new Promise((resolve) => setTimeout(() => resolve('d'), 1000));

console.time('promise.race');
Promise.race([a(), b(), c(), d()])
  .then(results => console.log(`Done! ${results}`))
  .catch(console.error)
  .finally(() => console.timeEnd('promise.race'));

What’s the output?

It’s b! With Promise.race only the fastest gets to be part of the result. 🏁

You might wonder: _ What’s the usage of the Promise race?_

I haven’t used it as often as the others. But, it can come handy in some cases like timing out promises and batching array of requests.

Timing out requests with Promise race

1
2
3
4
5
6

Promise.race([
  fetch('http://slowwly.robertomurray.co.uk/delay/3000/url/https://api.jsonbin.io/b/5d1fb4dd138da811182c69af'),
  new Promise((resolve, reject) => setTimeout(() => reject(new Error('request timeout')), 1000))
])
.then(console.log)
.catch(console.error);

If the request is fast enough, then you have the result.

1
2
3
4
5
6

Promise.race([
  fetch('http://slowwly.robertomurray.co.uk/delay/1/url/https://api.jsonbin.io/b/5d1fb4dd138da811182c69af'),
  new Promise((resolve, reject) => setTimeout(() => reject(new Error('request timeout')), 1000))
])
.then(console.log)
.catch(console.error);

Promises FAQ

This section covers tricks and tips using all the promises methods that we explained before.

Executing promises in series and passing arguments

This time we are going to use the promises API for Node’s fs and we are going to concatenate two files:

1
2
3
4
5
6
7

const fs = require('fs').promises; // requires node v8+

fs.readFile('file.txt', 'utf8')
  .then(content1 => fs.writeFile('output.txt', content1))
  .then(() => fs.readFile('file2.txt', 'utf8'))
  .then(content2 => fs.writeFile('output.txt', content2, { flag: 'a+' }))
  .catch(error => console.log(error));

In this example, we read file 1 and write it to the output file. Later, we read file 2 and append it to the output file again. As you can see, writeFile promise returns the content of the file, and you can use it in the next then clause.

How do I chain multiple conditional promises?

You might have a case where you want to skip specific steps on a promise chain. You can do that in two ways.

const a = () => new Promise((resolve) => setTimeout(() => { console.log('a'), resolve() }, 1e3));
const b = () => new Promise((resolve) => setTimeout(() => { console.log('b'), resolve() }, 2e3));
const c = () => new Promise((resolve) => setTimeout(() => { console.log('c'), resolve() }, 3e3));
const d = () => new Promise((resolve) => setTimeout(() => { console.log('d'), resolve() }, 4e3));

const shouldExecA = true;
const shouldExecB = false;
const shouldExecC = false;
const shouldExecD = true;

Promise.resolve()
  .then(() => shouldExecA && a())
  .then(() => shouldExecB && b())
  .then(() => shouldExecC && c())
  .then(() => shouldExecD && d())
  .then(() => console.log('done'))

If you run the code example, you will notice that only a and d are executed as expected.

An alternative way is creating a chain and then only add them if

1
2
3
4
5
6
7
8

const chain = Promise.resolve();
if (shouldExecA) chain = chain.then(a);
if (shouldExecB) chain = chain.then(b);
if (shouldExecC) chain = chain.then(c);
if (shouldExecD) chain = chain.then(d);

chain
  .then(() => console.log('done'));

How to limit parallel promises?

To accomplish this, we have to throttle Promise.all somehow.

Let’s say you have many concurrent requests to do. If you use a Promise.all that won’t be good (especially when the API is rate limited). So, we need to develop and function that does that for us. Let’s call it promiseAllThrottled.

1
2
3
4
5
6
7
8

// simulate 10 async tasks that takes 5 seconds to complete.
const requests = Array(10)
  .fill()
  .map((_, i) => () => new Promise((resolve => setTimeout(() => { console.log(`exec'ing task #${i}`), resolve(`task #${i}`); }, 5000))));

promiseAllThrottled(requests, { concurrency: 3 })
  .then(console.log)
  .catch(error => console.error('Oops something went wrong', error));

The output should be something like this:

So, the code above will limit the concurrency to 3 tasks executing in parallel. This is one possible implementation of promiseAllThrottled using Promise.race to throttle the number of active tasks at a given time:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

/**
 * Similar to Promise.all but a concurrency limit
 *
 * @param {Array} iterable Array of functions that returns a promise
 * @param {Object} concurrency max number of parallel promises running
 */
function promiseAllThrottled(iterable, { concurrency = 3 } = {}) {
  const promises = [];

  function enqueue(current = 0, queue = []) {
    // return if done
    if (current === iterable.length) { return Promise.resolve(); }
    // take one promise from collection
    const promise = iterable[current];
    const activatedPromise = promise();
    // add promise to the final result array
    promises.push(activatedPromise);
    // add current activated promise to queue and remove it when done
    const autoRemovePromise = activatedPromise.then(() => {
      // remove promise from the queue when done
      return queue.splice(queue.indexOf(autoRemovePromise), 1);
    });
    // add promise to the queue
    queue.push(autoRemovePromise);

    // if queue length >= concurrency, wait for one promise to finish before adding more.
    const readyForMore = queue.length < concurrency ? Promise.resolve() : Promise.race(queue);
    return readyForMore.then(() => enqueue(current + 1, queue));
  }

  return enqueue()
    .then(() => Promise.all(promises));
}

The promiseAllThrottled takes promises one by one. It executes the promises and adds it to the queue. If the queue is less than the concurrency limit, it keeps adding to the queue. Once the limit is reached, we use Promise.race to wait for one promise to finish so we can replace it with a new one. The trick here is that the promise auto removes itself from the queue when it is done. Also, we use race to detect when a promise has finished, and it adds a new one.

Related Posts:

1. Async vs Sync in JavaScript
2. JavaScript Callbacks
3. JavaScript Promises (this one)

This post assumes you know the difference between synchronous and asynchronous code.

JavaScript is an event-driven language. Instead of waiting for things to happen, it executes while listening for events. The way you respond to an event is using callbacks.

Related Posts:

1. Async vs Sync in JavaScript
2. JavaScript Callbacks (this one)
3. JavaScript Promises

JavaScript callbacks

A callback is a function that is passed as an argument to another function.

Callbacks are also known as higher-order function.

An example of a callback is the following:

1
2
3
4
5
6

const compute = (n1, n2, callback) => callback(n1, n2);
const sum = (n1, n2) => n1 + n2;
const product = (n1, n2) => n1 * n2;

console.log(compute(5, 3, sum));     // ↪️  8
console.log(compute(5, 3, product)); // ↪️  15

As you can see the function compute takes two numbers and a callback function. This callback function can be sum, product and any other that you develop that operates two numbers.

Callback Advantages

Callbacks can help to make your code more maintainable if you use them well. They will also help you to:

• Keep your code DRY (Do Not Repeat Yourself)
• Implement better abstraction where you can have more generic functions like compute that can handle all sorts of functionalities (e.g., sum, product)
• Improve code readability and maintainability.

So far, we have only seen callbacks that are executed immediately; however, most of the callbacks in JavaScript are tied to an event like a timer, API request or reading a file.

Asynchronous callbacks

An asynchronous callback is a function that is passed as an argument to another function and gets invoke zero or multiple times after certain events happens.

It’s like when your friends tell you to call them back when you arrive at the restaurant. You coming to the restaurant is the “event” that triggers the callback. Something similar happens in the programming world. The event could be you click a button, a file is loaded into memory, and request to a server API, and so on.

Let’s see an example with two callbacks:

1
2

const id = setInterval(() => console.log('tick ⏰'), 1e3);
setTimeout(() => clearInterval(id), 5e3);

First, you notice that we are using anonymous functions (in the previous example, we were passing the named functions such as sum and product). The callback passed to setInterval is triggered every second, and it prints tick. The second callback is called one after 5 seconds. It cancels the interval, so it just writes tick five times.

Callbacks are a way to make sure a particular code doesn’t execute until another has already finished.

The console.log('tick') only gets executed when a second has passed.

The functions setInterval and setTimeout callbacks are very simple. They don’t provide any parameters on the callback functions. But, if we are reading from the file system or network, we can get the response as a callback parameter.

Callback Parameters

The callback parameters allow you to get messages into your functions when they are available. Let’s say we are going to create a vanilla server on Node.js.

1
2
3
4
5
6
7
8
9
10
11
12
13

const http = require('http');

const port = 1777;
const host = '127.0.0.1';

const proxy = http.createServer((req, res) => {
  res.writeHead(200, { 'Content-Type': 'text/plain' });
  res.end(`Hello World from Node! You used url "${req.url}"\r\n`);
});

proxy.listen(port, host, () => {
  console.log(`Server running on http://${host}:${port}`);
});

We have two callbacks here. The http.createServer‘s callback sends the parameters (req)uest and (res)ponse every time somebody connects to the server.

You can test this server using curl (or browser)

1

curl 127.0.0.1:1777/this/is/cool

There you have it! An HTTP server that replies to everyone that connects to it using a callback. But, What would happen if there’s an error? Let’s see how to handle that next.

Handling errors with Node.js callbacks

Some callbacks send errors on the first parameter and then the data (callback(error, data)). That’s very common in Node.js API. Let’s say we want to see all the directories on a given folder:

1
2
3
4
5
6

const fs = require('fs');

fs.readdir('/Users/adrian/Code', (error, files) => {
  if (error) { console.error(error); }
  console.log(files);
});

As you notice, the first parameter will have an error message. If you run it, you would probably have the error message (unless you have the same name and directory).

1
2
3
4
5
6

{ [Error: ENOENT: no such file or directory, scandir '/Users/noAdrian/Code']
  errno: -2,
  code: 'ENOENT',
  syscall: 'scandir',
  path: '/Users/noAdrian/Code' }
undefined

So that’s how you handle errors, you check for that parameter. But (there’s always a but) what if I need to do multiple async operations. The easiest way (but not the best) is to have a callback inside a callback:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

const fs = require('fs');

const dir = '/Users/adrian/Code';

function printFilesSize(basePath) {
  fs.readdir(basePath, (err, files) => {
    if (err) {
      console.log(`Error finding files: ${err}`);
    } else {
      files.forEach((filename) => {
        const filePath = `${basePath}/${filename}`;

        fs.lstat(filePath, (err, stat) => {
          if (err) { console.error(err); }
          if (stat.isFile()) {
            console.log(filePath, stat.size.toLocaleString());
          }
        });
      });
    }
  });
}

printFilesSize(dir);

As you can see, this program will first read files in a directory and then check the file size of each file, and if it’s a directory, it will be omitted.

When callbacks are nested too many levels deep, we call this callback hell! 🔥 Or the pyramid of doom ⚠️

Because they are hard to maintain, how do we fix the callback hell? Read on!

Callback Hell problem and solutions

Callback hell is when you have too many nested callbacks.

1
2
3
4
5
6
7

a(() => {
  b(() => {
    c(() => {
      d();
    });
  });
});

To make your code better, you should:

1. Keep you code shallow (avoid too many nested functions): keep your code at 1-3 indentation levels.
2. Modularize: convert your anonymous callbacks into named functions.
3. Use promises and async/await.

Let’s fix the callback hell from printFilesSize keeping our code shallow and modularizing it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

const fs = require('fs');

const dir = '/Users/adrian/Code';

function printFileSize(filePath) {
  fs.lstat(filePath, (err, stat) => {
    if (err) { console.error(err); }
    if (stat.isFile()) {
      console.log(filePath, stat.size.toLocaleString());
    }
  });
}

function printFilesSize(files, basePath) {
  files.forEach((filename) => {
    const filePath = `${basePath}/${filename}`;

    printFileSize(filePath);
  });
}

function printFilesSizeFromDirectory(basePath) {
  fs.readdir(basePath, (err, files) => {
    if (err) {
      console.log(`Error finding files: ${err}`);
    } else {
      printFilesSize(files, basePath);
    }
  });
}

printFilesSizeFromDirectory(dir);

The original implement had five levels of indentation, now that we modularized it is 1-2 levels.

Callbacks are not the only way to deal with asynchronous code. In the following post we are going to cover:

• Promises
• Async/Await
• Generators

Stay tuned!

Related Posts:

1. Async vs Sync in JavaScript
2. JavaScript Callbacks (this one)
3. JavaScript Promises

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 you are going to learn in 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.

Related Posts:

1. Async vs Sync in JavaScript (this one)
2. JavaScript Callbacks
3. JavaScript Promises

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

1
2
3
4
5
6
7
8

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:

1
2
3

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:

1
2
3
4
5
6
7
8
9
10

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?

1
2
3

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)

1
2
3
4
5
6
7
8
9
10
11
12
13

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

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:

Finished creating my own system to sell ebooks! https://t.co/9w0DHBU8T8 It was harder than I thought but it was fun. When payments are completed, a webhook is sent to my server, which grabs the ebook PDF from S3. A #Node process stamp the document and uses API to send it by email

— Adrian.js (@iAmAdrianMejia) May 13, 2019

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:

https://github.com/amejiarosario/dsa.js

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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.

1
2
3
4
5
6
7
8

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.

Before moving forward to checking out how we can apply atomic operations in MongoDB, we will be looking at some of the critical points that you need to keep in your mind in regards to MongoDB:

• MongoDB does not support atomicity for multi-document transactions. However, version 4.0 onwards will support multi-document transactions in several cases.
• It is only possible to use the atomicity feature of MongoDB in a single document (not in case of version 4.0). Suppose, there is a document that consists of 35 fields. In that document, there will either be updates in all 35 fields or none.
• The atomicity feature is only limited to the document level.

If you want to jump into the NoSQL database, you should consider MongoDB certification. It will give you a strong foundation and skills to use MongoDB to solve real-world problems. There is a considerable job demand for MongoDB professionals.

Introduction to Atomic Operations

The atomic operations in database terminology is a chained and sophisticated database operations series. In this series, either all aspects of the series will be affected, or nothing will be altered. In atomic operations, there is no such thing as a partial database change.

In atomic operations, there is only a room for complete database updates and changes. In case of any partial updates, the whole database will roll back.

We use atomic operations in a case where the partial update will create more harm in comparison to rolling back. There are some instances in the real world where we need to maintain our database in this manner. In the latter part of this article, we will discuss more in depth about it.

We can explain atomic operations in MongoDB clearly with the use of ACID, a.k.a. Atomicity, Consistency, Isolation, and Durability.

• Here is a simple rule of atomicity for every single operation, “either all or none.”
• The consistency property will play a crucial role in atomicity. It will ensure that each transaction will ultimately lead to a valid state of some kind.
• The isolation property of the database will play a part in guaranteeing the systematic process of the concurrent transaction, which means one by one.
• Finally, the durability property will come into play. This property ensures the permanency of the database after each database transaction regardless of errors, crashes, and power loss.

Modeling e-Commerce Products in MongoDB

We should maintain atomicity in MongoDB by compiling all the related information in a single document, which will update consistently. We can create such type of consistency via embedded documents. The embedded is for ensuring that every single update that takes place in the document is atomic.

Here is how the document looks like for representing item purchase information.

Creating a new product