Photo by Brett Jordan on Unsplash

Last week I wrote part one of this series of blogs. We learned how to insert a word into a trie, as well as determine whether or not the trie contains a given word. In this blog I’m going to look at removing a word from a trie, as well as getting a list of words from a trie that begin with a given prefix.

Steps

Words With Prefix


Photo by Amador Loureiro on Unsplash

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. …


Photo by Possessed Photography on Unsplash

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


Photo by Zoran Borojevic on Unsplash

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…


Photo by Omar Flores on Unsplash

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…


Image by Gerd Altmann from Pixabay

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. …


Photo by Alexander Sinn on Unsplash

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. …


Photo by Pisit Heng on Unsplash

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…


Photo by Volodymyr Hryshchenko on Unsplash

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…


Photo by Tyler Milligan on Unsplash

Last week I wrote about implementing quicksort in JavaScript, the next sorting algorithm I would like to cover is heap sort. However, in order to do so, we need to understand the heap data structure. A heap is a tree based structure. Specifically we will be looking at a max heap, which is a form of binary heap that satisfies the heap property. The heap property states that every child node will be less than (or greater than, in the case of a min heap) its parent node. This means that the root node will always be the maximum element…

Regina Furness

Aspiring Software Engineer

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store