A trie is a tree data structure that is useful for searching and retrieving data. Most often used with strings, where each character of the string is a single node in the tree, which will then have a child node that is the following character of the string. In this blog I will explain how to insert into a trie, and how to determine if a word is in the trie. …

In this blog I’m going to teach you one method for rotating a square matrix 90 degrees clockwise, in place. I came across this question on leetcode. I thought I would have trouble remembering the steps to solve this problem, so I wanted to write a blog about it. Hopefully in addition to helping me remember how to solve this problem, I can help others understand it as well.

Step by Step Example

Dijkstra’s Algorithm is an algorithm to find the shortest path between vertices in a graph. It was created by Edsger W. Dijkstra, a Dutch computer scientist. Given a source vertex, the algorithm will find the shortest path between that vertex and all other vertices in the graph (returning infinity if there is no path between the source vertex and a given vertex). This is known as the shortest-path tree. It can be modified to find the shortest distance between the source vertex and a target vertex, simply by stopping once the shortest path is found for the target vertex.

Step by Step Example

Dijkstra’s…

I recently came across an implementation of an undirected weighted graph using an adjacency matrix. Prior to this, I was used to seeing graphs represented using adjacency lists. To keep this blog focused, today I’ll only be writing about representing a weighted graph using an adjacency matrix, and will assume that the reader is already aware of how to represent a graph using an adjacency list. By the end of this blog, the goal will be that you will be able to build a Graph class which utilizes an adjacency matrix.

What is an Adjacency Matrix?

Square Matrix

An adjacency matrix, is a square matrix which is…

Last week I took a quick look at bit manipulation. I learned about bitwise operators, as well as how to represent positive base 10 numbers in binary (base 2). Today I want to dig a little deeper, and talk about negative numbers represented in binary, as well as a few clever bit manipulation tricks.

Negative Numbers

In my last blog I discussed how using the NOT (~) bitwise operator on a number in your code, would get you a different result than what I had shown. …

Recently, while doing leetcode problems I came across a problem in which the most optimal solution was the result of bit manipulation. I knew bits were the 0’s and 1’s in binary, but that was about it. I decided to dig a little deeper and share what I’ve found here.

What are Bits?

Bit is a portmanteau of binary digit. Binary meaning two. A single bit therefor has 2 states, most often true or false, this is generally represented as 1 or 0. Through a series of bits one may represent a piece of data such as a number. …

A hash table is a data structure which consists of key and value pairs. A good analogy is thinking of it like a dictionary (the book), the keys are the words and the values are the definitions. If you think that sounds familiar, you’re correct, JavaScript Objects are an example of a hash table. That being said, using JavaScript’s built in Object or Map, is going to be faster and more optimal than what I implement here. This blog is more about understanding the concepts behind a hash table.

Pros and Cons of a Hash Table

Pros

• Fast lookup
• Fast insertion
• Fast deletion

Cons

• Hash Collisions (particularly when there…

Last week I wrote about implementing a max heap in JavaScript, now we’re going to put that knowledge to the test and write a heap sort algorithm. Understanding the implementation, and time and space complexities of a max heap will make understanding the heap sort algorithm quite simple.

Step by Step Example

The Process

We know in a max heap, the largest element is stored at the root. So these will be the steps of heap sort:

• Move the element at index 0 to the end of the array
• Re-heapify the array, excluding the last element
• Continue this process of swapping and re-heapifying each time excluding…