DEV Community: Sean Tansey

Algorithms: Breadth First Search

Sean Tansey — Mon, 03 Oct 2022 23:57:33 +0000

Tree and Graph traversal is a popular topic in coding interviews. There are many approaches to graph traversal but one of the most common and important to be familiar with is Breadth First Search (BFS). We'll explore the basic ideas of the algorithm and a few example implementations.

The Basics

Breadth First Search is an algorithm used to traverse graph data structures. It is the order in which the nodes will be visited. As the name implies the traversal is conducted in a breadth first manner, meaning that starting from a certain node we will traverse every node of the current level before exploring additional nodes at deeper levels.

Tree Order Traversal

Starting from the root node (6), each level is explored from left to right before moving to the next level.

Implementations

BFS algorithms are usually implemented iteratively using a queue data structure. We start by adding the root node to the queue. Then we iterate through the queue, removing the node and adding its children to the queue. This allows us to explore the graph level by level.

Problem

Given a binary tree, return an array of sub-arrays that represents its level by level traversal.

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

Solution

const bfs = (root) => {
 const result = []
 const queue = [ root ]

 while (queue.length) {
   const level = []
   const qLength = queue.length
   for (let x = 0; x < qLength; x++) {
      const node = queue.shift()
      level.push(node.val)
      if (node.left !== null) queue.push(node.left)
      if (node.right !== null) queue.push(node.right)
   }
  result.push(level)
 }
 return result
}

Algorithms: Depth First Search

Sean Tansey — Mon, 08 Aug 2022 14:59:00 +0000

Tree and Graph traversal is a popular topic in coding interviews. There are many approaches to graph traversal but one of the most common and important to be familiar with is Depth-First Search (DFS). We'll explore the basic ideas of the algorithm and a few example implementations.

The Basics

Depth-First Search is an algorithm used to traverse graph data structures. It is the order in which the nodes will be visited. As the name implies the traversal is conducted in a depth-first manner, meaning that starting from a certain node we will traverse as deeply into that node as possible before exploring additional nodes. Once a leaf node is found (a node with no children) backtracking will occur until a non-fully explored node is found and the searching will continue in a depth-first manner from there.

Tree Traversal Order

Starting from the root node (6), the left side of the tree is explored to maximum depth before exploring the right. Note that this logic continues from the child nodes as well. From node 8, the left side (8 -> 1 -> 3) is explored prior to the right (8 -> 7).

Non-Tree Traversal Order

DFS can be used with non-tree structures as well. The exploration order may change depending on the starting node and exploration logic, but the concept still holds true. All child nodes are explored to maximum depth before additional nodes are explored.

Implementations

DFS algorithms can be implemented recursively or iteratively using a stack data structure. A recursive implementation utilizes the call stack whereas an iterative solution uses a stack directly. Whilst traversing a graph, nodes are added to the stack and popped off as they are fully explored.

Note: recursive implementations tend to be more common for DFS as they are visually more elegant and straight forward to implement.

Problem

Write an algorithm to check if there are any root to leaf paths where the sum of the path's values equal a given value "k".

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

Solution - Recursive

const hasPath = (node, k) => {
  if (node === null) return false

  if (node.left === null && 
      node.right === null && 
      node.val === k) {
        return true
  }
  return hasPath(node.left, k - node.val) || 
         hasPath(node.right, k - node.val)
}

Solution - Iterative

const hasPath = (node, k) => {
  const stack = [ [node, k ] ]

  while (stack.length > 0) {
    const [ node, target ] = stack.pop()

    if (node.left === null && node.right === null && node.val === target) {
      return true
    }

    if (node.right) {
      stack.push([node.right, target - node.val])
    }

    if (node.left) {
      stack.push([node.left, target - node.val])
    }
  }
  return false
}

Data Structures: Stacks and Queues

Sean Tansey — Wed, 13 Jul 2022 00:33:00 +0000

Stacks and Queues are common data structures you may be questioned on during a job interview. Let's take a look at what Stack and Queues are from a high level.

Stack

A stack is a linear data structure that operates in a LIFO (Last In First Out) order. Think of a stack of plates. Each plate is stacked on top of an existing one, and the last plate stacked is the first one removed. Stack data structures operate the same way. Data is added to the end of the structure, and when acted upon is removed from the end of that same structure.

Queue

A queue is a linear data structure that operates in a FIFO (First In First Out) order. A common metaphor for a queue is a check out line at the store. Whoever is at the front of the line gets to check out first. A queue data structure operates in a similar fashion, data is added to the end of the stack and removed and acted upon from the front.

Implementations

Let's create some simple implementations of these data structures using JavaScript arrays and array methods.

Stack

We can create a simple stack class using a JavaScript array and the built in array methods push and pop. Push adds a new value to the end of the array. Pop removes and returns the last value in the array. This allows our data structure to operate in LIFO order.

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

    push(value) {
        this.stack.push(value)
    }

    pop() {
        return this.stack.pop()
    }
}

const stack = new Stack()

stack.push('a') // -> stack: [ 'a' ] 
stack.push('b') // -> stack: [ 'a', 'b' ]
stack.push('c') // -> stack: [ 'a', 'b', 'c' ]

stack.pop() // -> returns 'c', stack: [ 'a', 'b' ]

Queue

We can create a simple queue class using a JavaScript array and the built in array methods push and shift. Push adds a new value to the end of the array. Shift removes and returns the first value in the array. This allows our data structure to operate in FIFO order.

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

    push(value) {
        this.stack.push(value)
    }

    shift() {
        return this.stack.shift()
    }
}

const queue = new Queue()

queue.push('a') // -> queue: [ 'a' ] 
queue.push('b') // -> queue: [ 'a', 'b' ]
queue.push('c') // -> queue: [ 'a', 'b', 'c' ]

queue.shift() // -> returns 'a', queue: [ 'b', 'c' ]

Summary

Stacks and Queues are both linear data structures, stacks however operate in LIFO order while Queues operate in FIFO order. The different removal order of these structures allows them to be useful in different ways.

Data Structures: Linked Lists

Sean Tansey — Fri, 13 May 2022 23:31:00 +0000

Linked lists are a common data structure you may receive questions on during a job interview. Let's take a look at what a linked list is at a high level.

What is it?

A linked list is a list of elements (which we'll refer to as nodes) that store some data, as well a pointer (or pointers) to other nodes in the list. This pointing is what creates the list. There are two major types of linked lists: singly and doubly linked lists.

In a singly linked list, each node only knows about the next node in the list. When we reach the last node it points to null. For doubly linked lists each node knows about the previous and next node in the list. This allows traversing of the list forwards and backward, whereas singly linked can only be traversed forwards.

Singly Linked List

Doubly Linked List

Why do this?

Why do we need a linked list when we already have array's built right into JavaScript? Great question, I wondered the same. The major difference between the two is how they are stored in memory. Let's take a look at the pros/cons of each.

Arrays

Arrays elements are stored in contiguous memory locations. Meaning that their elements are stored all in a row.

Linked Lists

Linked lists do not need to be stored in contiguous locations. Due to each node storing the location of the next node, they can be stored anywhere.

Arrays

Pros:

Random access: since arrays store elements contiguously, accessing an element at a given index is much quicker. (ex. array[3]). No need to traverse the elements, we already know its location.
Less memory per element: an element in an array does not need to store the location of the next element.

Cons:

Insertion/Deletion: is much slower because arrays use contiguous memory, adding a new element requires shifting the memory locations of other elements to make room.
Static Memory Allocation: memory for an array takes place at compile time. It can not be altered dynamically at runtime because that may result in overwriting data.

Linked Lists

Pros:

Insertion/Deletion: since linked lists use non contiguous memory, these operations are much faster. There's no need to shift anything around, just update where the nodes point.
Dynamic Memory Allocation: new nodes can be inserted at runtime as soon as they are created.

Cons:

Sequential Access: finding a given index of a linked list requires traversing the list up to that point, this is much slower than the random access of an array.
Increased storage: linked list nodes need to store the location of the next node. This increases the storage used per element.

TL;DR

A linked list is a data structure of elements we refer to as nodes. Each node stores the location of the next and this creates a list. While similar to an array it has the advantages of faster insertion/deletion, and can be modified dynamically at run time. The disadvantages in comparison are slower access and increased storage usage, due to each node storing the location of the next.

Postgres: Setup & Basics

Sean Tansey — Mon, 09 May 2022 02:49:00 +0000

I recently started working on a personal project that includes a database in the back end. As a primarily Frontend Engineer it had been years since I'd set up a database. Below are the basic steps to getting started with postgresql.

Installation

I'll be installing postgres using Homebrew, a package manager used for Mac/Linux. If you don't have homebrew installed here's a link. Now pop open a terminal window and lets get to work.

We'll start by updating homebrew to make sure we have the latest:

brew update

Next we'll install postgres:

brew install postgresql

Once installed lets start the service:

brew services start postgresql

Postgres is now installed and running. You can stop the service at anytime with:

brew services stop postgresql

Log into postgres and create a user

psql is a terminal based front-end for postgres. It will connect us to postgres and allow us to create databases, users, issue queries, etc..

First we have to log in to psql as the default root user:

psql postgres

We are now logged in as the root user. You should see this in the command prompt:

postgres=#

Here's a list of some common postgres commands you'll use now that we are logged in:

\q - quit/exit psql
\list - lists all databases
\du - lists all database roles
\dt - lists all database tables
\conninfo - lists info about current database connection
\c [dbname] - connect to a different database 
CREATE DATABASE [dbname]; - creates a new database
CREATE USER [username]; - creates a new user
ALTER ROLE [username] CREATEDB; - allows user to create databases
ALTER ROLE [username] CREATEROLE; - allows user to create roles
DROP DATABASE [dbname]; - deletes database
DROP USER [username]; - deletes a user

Currently we are logged in as our root user, its generally poor practice to use this user in postgres so lets create a new user that we'll use to perform our database actions and grant them some basic permissions:

postgres=# CREATE USER username WITH PASSWORD 'password';
postgres=# ALTER ROLE username CREATEDB CREATEROLE;

We've now created a new user called username with a password and given them permission to create databases and roles/users. You can check this by running \du and you should see your user listed.

Log out of the root user and log in as our new user:

postgres=# \q

psql -d postgres -U username

Note: -d indicates which database we are logging into (we are logging into the default postgres db), -U indicates what user we are logging in as.

You should now see:

postgres=>

Creating a Database and Tables

Lets create a new database:

postgres=> CREATE DATABASE dbName;

If you use the \list command you should see your new database listed. Congrats you've just created a database in postgres! From here you can add tables and data to your database directly in psql, however I'd recommend doing this in a tool like TablePlus or pgAdmin as its much easier to visual and doesnt require memorizing SQL commands. However heres a basic example in psql for a table of messages.

To create a table:

dbname=> CREATE TABLE messages (
   id SERIAL PRIMARY KEY,
   name VARCHAR(30),
   message TEXT
);

To add data to that table:

dbname=> INSERT INTO messages (name, message) VALUES ('Donald Duck', 'Qwack Qwack');

Then to check out our data:

dbname=> SELECT * FROM messages;

Result:

id |    name     |   message
----+-------------+-------------
  1 | Donald Duck | Qwack Qwack
(1 row)

ELI5: Dependency Injection

Sean Tansey — Wed, 04 May 2022 14:57:00 +0000

"Tell me about Dependency Injection"... this was the first technical question I was ever asked in a job interview. At the time, as a fresh coding bootcamp grad I honestly had no idea... I instantly felt like a fool, and had to admit I didn't know a thing about it. The interviewer was nice and explained it to me, but at that point I was barely listening, I already knew I wasn't going to get the job. Years later I understand the concept, and to be honest despite all the fancy computer science-y words people use when they talk about it, its really not that complex of an idea.

What is it?

Let's start with a dependency. A dependency is something that a piece of code depends on to function properly. Dependency Injection then, is simply when we pass (inject) that functionality in from the outside, rather than building it inside. It's a separation of responsibilities.

Example

Say we have a database with a table of users, and from our server we want to GET one of those users by their ID. Before dependency injection that code might look something like this:

// imports database functionality
import dbConnection from 'dbConnection'

// router code
router.get('/:id', (request) => {

  // connects to our database
  const mockDatabaseConnection = new dbConnection({
    user: 'mockUsername',
    host: 'mockHost',
    database: 'mockDatabase',
    password: 'mockPassword',
    port: 'mockPort'
})

  // grabs the id from our request
  const { id } = request.params

  // builds a query object
  const query = `SELECT * FROM users WHERE id = ${id}`

  // queries our database
  mockDatabaseConnection.query(query)
    .then((response) => {
      // handles response
    })
})

You can see there a quite a few things going on here. And with this architecture, if we wanted to make another route to a different table, we'd have to duplicate a lot of this code. So maybe theres a way we could split this code up and make it more modular? Looking at the code theres a few different groupings we could make:

Code that handles the request, and builds a query object from it
Code that handles anything related to the database (connection and query)
Code that handles what to do with the response or error thats returned

Lets try extracting the database code into another file so it can be shared across all of our requests:

DATABASE FILE

// imports database functionality
import dbConnection from 'dbConnection'

// connects to our database
const mockDatabaseConnection = new dbConnection({
    user: 'mockUsername',
    host: 'mockHost',
    database: 'mockDatabase',
    password: 'mockPassword',
    port: 'mockPort'
})

// a simple query function that we can export
const queryFunction = (query) => {
  return mockDatabaseConnection.query()
}

export default queryFunction

Now lets inject that code into our routing function rather than building it inside:

// imports database functionality
import queryFunction from 'DatabaseFile'

// GET user by id
router.get('/:id', (request) => {

  // grabs the id from our request
  const { id } = request.params

  // builds a query object
  const query = `SELECT * FROM users WHERE id = ${id}`

  // queries our database
  queryFunction(query)
    .then((response) => {
      //handles response
    })
})

Man thats a lot cleaner looking... and it's an example of dependency injection! We are injecting the database code into the route code, to which the route code is dependent. Beyond being cleaner visually, what are some of the benefits of this?

It's much modular and reusable. Now every time we want to write a new route we can simply inject the database into the route rather than rebuilding it each time.
It's much cleaner and easier to test. Our database code lives in one file and can be tested all at once. Before we'd have to test our database code in every route! (As someone who loathes writing unit tests this is huge)
It separate's the logic in a way that makes sense, each piece doing what it needs to independent of the other. Why should the router code be involved with our database connection? What if we wanted to change databases? Using dependency injection we can just update the database file and we're good to go. Before we'd have to change it in every single route... yikes.
The code is DRY (don't repeat yourself)

TL;DR

Dependency Injection occurs when we separate code into smaller reusable classes/objects and then inject that functionality into other objects, rather than rebuilding it each time. This makes our code more reusable, testable and maintainable.

JavaScript: The Event Loop

Sean Tansey — Sun, 01 May 2022 20:45:00 +0000

Many developers are aware that JavaScript is a single-threaded language. When executed in a runtime such as your web browser, JavaScript code runs synchronously, only ever able to do one thing at a time. But if thats the case then how are we writing all this fancy asynchronous code with callbacks, promises and async/await? The secret lies in the event loop.

The Basics

There are a few different components to understand that make up the event loop:

Stack

A stack is a data structure that operates in a LIFO (Last In, First Out) order. When we execute JavaScript functions they are added to the call stack and referred to as a frame.

For example lets say we had the following code:

const a = (num) => {
    return num + 5
}

const b = (num) => {
    return a(num)
}

b(15)

function a(): takes in a number as a parameter and returns that number plus 5
function b(): takes a number as a parameter and then calls function a() passing in that number as a parameter
we call function b() passing in 15 as the parameter

The order of operations of this code is as follows:

When calling b(), our first frame is created and added to the stack
When b() calls a(), a second fame is created and added on top of the stack
a() executes returning the value of 15 and is removed from the stack
b() returns the value it received from a() and is removed from the stack, leaving the stack empty

While LIFO is great and all, it does have some limitations, what happens if we have to make some data calls that take a considerable amount of time?

// takes 1 second to execute
const a = () => {
    return 'a'
}

// takes 60 seconds to execute
const b = () => {
    return 'b'
}

// takes 1 second execute
const c = () => {
    return 'c'
}

a()
b()
c()

a() is added to the stack as a new frame, executes in 1 second and is removed from the stack
b() is added to the stack as a new frame, executes in 60 second and is removed from the stack
c() is added to the stack as a new frame, executes in 1 second and is removed from the stack

We can see here some of the limitations of the call stack, while function b() is executing for a full minute, nothing else can be done. This is referred to as blocking, and to create smooth experiences on the web we try to minimize this as much as possible.

Heap

The heap is where memory allocation occurs, storing all of your variables in your program. The stack and heap combine to form your JavaScript runtime. For the purposes of this article we can mostly ignore the heap.

Web API's

There are a number of API's provided by our browsers, such as the HTML DOM (Document Object Model), setTimout(), or the fetch API. These exist outside of the JavaScript runtime and combined with the queue below is what allows us to execute functions asynchronously, without blocking the call stack.

Queue

A queue is a data structure like the stack, but unlike the stack it operates in a FIFO (First In, First Out) manner. When we perform asynchronous operations through web API's like fetching data, upon completion they are added to the queue and are referred to as a message.

Event Loop

Ahh.. now we're finally getting somewhere! The event loop is where all of this asynchronous magic comes together. The event loop is the process by which messages are removed from the queue, and their callback functions are added to the stack as a new frame.

Putting it all together

// takes 1 second to execute
const a = () => {
    return 'a'
}

// takes 60 seconds to execute
const b = () => {
    return fetch('http://mockURL.com/example')
        .then((response) => {
            return response.json()
        })
}

// takes 1 second execute
const c = () => {
    return 'c'
}

a()
b()
c()

Steps:

Function a() is added to the call stack as a new frame, the code executes and is removed from the stack
Function b() is added to the stack and the fetch api is called
Handling the call is done within the fetch api itself, so function b() can now be removed from the stack. The fetch api continues to handle the request behind the scenes
Function c() is added to the stack, executes and is removed
Upon completion of the fetch request the data returned from the api, as well as the callback function (in our case return response.json()) is added to the queue as a message
Since the stack is now empty once again the event loop runs, moving function b()'s callback with the api response data into the call stack
The call stack executes function b()'s callback and removes it from the stack