DEV Community: Terrence Jung

Do you really know Git? (2)

Terrence Jung — Fri, 27 Sep 2024 23:13:28 +0000

Examples in this blog come from "Pro Git" by Scott Chacon, Ben Straub

Let's get into more interesting aspects about Git that may help your understanding of it on a deeper level.

1 - What happens behind the scenes when we stage and commit?

Suppose we have a directory containing 3 files and we stage them all and commit.

What happens during staging?

Compute checksum for each file using SHA-1 hashing
Stores the current version of the files in the Git repository as blobs, versioned snapshots of a files.
Record the checksum for each file in the staging area.

What happens during a commit?

Git checksums each subdirectory (usually the top level is the root project directory) and stores them as a tree object in the Git repository. This object records the structure of the project at that moment, including file names and their corresponding blobs (file contents).
Git creates a commit object that contains metadata + a pointer to the tree object. This allows Git to re-create the entire project snapshot when needed.

At this point, your Git repository contains 5 objects:

3 blobs
1 tree object (lists directory contents and maps file names to blobs)
1 commit object that points to the tree object and contains metadata

If we make more changes and commit again, the commit history would look like this:

2 - Using git switch instead of git checkout

You may already be familiar with using git checkout to switch between branches, and that method works totally fine.

However, if you want a more intuitive way to switch between and create branches, use git switch!

git switch branch-name - switch to an existing branch
git switch -c new-branch - create new branch and switch to it
git switch - - return to previously checked out branch

3 - What happens behind the scenes during a merge?

When we merge two branches, we can intuitively say that it just takes two histories and combines their work. But what does that really mean? Let's look at this example:

Let's say we're done with iss10 branch and want to merge it with master.

git switch master
git merge iss10

Since iss53 isn't a direct ancestor of master, we have some work to do when merging. The default merge performs a three-way merge among the two snapshots pointed to by master and iss53 and the common ancestor of them.

In the three-way merge, Git creates a new snapshot that results from it and automatically creates a new commit that points to the snapshot. This commit is called a merge commit. It's special since it has more than 1 parent.

At this point, everything is merged and you can delete the iss10 branch.

4 - Two Common Types of Branching Workflows

Long-Running Branches

In this workflow, you can have several branches that are always open that each represent different stages of your development cycle.

master/main - code that is entirely stable
develop/next - code that isn't necessarily stable (for testing stability)
topic-branch - current feature you are working on

You can also view this workflow as work silos, where sets of commits graduate to a more stable silo when they’re fully tested.

Topic Branches

This workflow is useful for projects of any size. A topic branch is a short-lived branch that you create and use for a single feature. This technique allows you to context switch quickly and completely, since your work is separated into silos where all changes in that branch have to do with that topic.

Let's follow this workflow:

Do some work on master
Branch off to iss91
Branch off to another branch iss91v2 and do some work
Go back to master and do some work
Branch off to dumbidea to test an idea

Here's what the commit history would look like:

Let’s say you like the work on iss91v2 and dumbidea turned out to be a genius idea. Let’s throw away iss91 (losing commits C5 and C6) and merge in the other two branches.

5 - What is Rebasing?

In Git, there are 2 ways to integrate changes from 1 branch into another: merge and rebase. We've already gone over merging. Let's go over a basic rebase.

Let's look at this example of a diverged history:

A merge would perform a 3-way merge and create a merge commit. In a rebase, we get the same result in a different way. Essentially, we'll take the changes in C4 and reapply it on top of C3's commit. In this case, you would checkout experiment and rebase it onto master.

What is actually happening here?

Rebasing goes to the common ancestor of the 2 branches
It gets the diff introduced by each commit of the branch you're on (experiment) and saves it to a temporarily file
It rests the current branch (experiment) to the same commit as the branch you're rebasing onto (master)
Finally, it applies each change (from the file with the diffs).

At this point, you can go back to master and do a fast-forward merge.

Here, the latest snapshot is the exact same as the one that would result from a default merge. The difference here is that rebasing produces a cleaner history.

One more thing. Let's discuss the cons of rebasing since it sounds too good to be true. In can be summed up in one line: do not rebase commits that exist outside your repository and that people may have based work on.

Why? Well, think about this workflow:

You push commits somewhere and others pull them down and base work off of them.
You rewrite these commits with git rebase and push them up again.

At this point, your collaborators would have to re-merge their work and it could get very messy when you try to pull their work back into yours.

6 - Which is better? Merge or Rebase?

Now for the age-old debate that has caused a divide among programmers. Is merge or rebase better? In reality, we can't say. It depends on the use case and the team/project.

Personally, I think there's a misconception that the two do the same thing and it just depends on personal preference. While that is true mostly, it's very important to know how each works and what scenarios each could possibly bring.

"Pro Git" mentions a good point about comparing the two. When we talk about a project's history, we should ask ourselves how it should be perceived.

One point of view states that your repository's commit history is a record of what actually happened. It's historical and shouldn't be tampered with.

The opposing point of view is that the commit history is the story of how your project was made. There will be drafts before the final, clean version.

You can probably tell that the first POV caters toward using merge while the second caters towards using rebase. Again, neither is better than the other and it depends on the project and team.

If you can't decide which to use, you could even get the best of both worlds:

Rebase local changes before pushing to clean up your work
Never rebase anything you’ve pushed somewhere

That's it! Hope you enjoyed this blog and learned more about Git and how you can use it in your own work!

Do you really know Git?

Terrence Jung — Tue, 24 Sep 2024 21:19:45 +0000

Examples in this blog come from "Pro Git" by Scott Chacon, Ben Straub

In this blog, you'll get to read about all kinds of neat facts about some of the every-day features within Git that you use in programming!

It's easy for developers to blindly use tools and not know how they work under the hood. While this abstractions is for the better, knowing how things work can sometimes be what makes the difference between a seasoned and amateur programmer.

Let's dive into some cool facts!

1 - Short Status

If you've used Git for quite a while, you should know about git status. However, did you know there's an option to get a more readable and minimal status output?

By using the short status flag, -s, you get a more compact format.

$ git status -s
 M README
MM Rakefile
A  lib/git.rb
M  lib/simplegit.rb
?? LICENSE.txt

You'll notice that there are 2 columns on the left section of the output. The left column represents the status of the staging area, while the right column represents the status of the working tree. The order of actions chronologically is represented from left to right as well.

Let's interpret the output above:

" M" - modified but not staged
"MM" - staged and then modified again. Thus, an additional stage is required for the next commit.
"A " - a new file was created and staged
"M " - staged
"??" - a new file was created but was not staged (untracked)

2 - Skipping the Staging Area

What if you want to stage your tracked files and commit all in one command?

You can do so by using git commit -a -m "message".

Note that untracked files (newly created files) will not be staged with this magical command unfortunately.

3 - View your Commit History

Use git log to list the commits made in your repository in reverse chronological order (most recent commits show up first).

There are various options that allow you to customize the output. Let's go over some useful ones:

-{number} limits the number of log entries displayed (e.g., git log -2 shows the last two entries)
--stat shows abbreviated stats like # of files or # of insertions/deletions for each commit
--pretty=oneline prints each commit on a single line
--graph adds an ASCII graph showing your branch and merge history

4 - Undoing Things using Git Restore

When you want to unstage a file, use git reset HEAD . When you want to unmodify a modified file, use git checkout -- {file}.

Now there's an easier way to do both! Git version 2.23.0 introduced git restore, which brings a 2-in-1 ability to both unstage and unmodify files.

git restore {file} - unmodify a modified file
git restore --staged {file} - unstage a staged file

5 - Git Fetch vs. Git Pull

Most likely, you've used git pull at least once as a programmer. Additionally, you've most likely heard about git fetch but never really had the need to use it. Well, let's talk about what it actually does and how it's different from git pull.

You can think of fetch as just the first step of what happens within a pull.

In a pull, we download all the data from the remote repository and transfer it onto the local repository. This is what a fetch does.

At this point, your local repository has the data but hasn't merged it with the working directory so that you can work on the latest changes. The next step within a pull is a merge with your branch so that the latest changes are then in your working directory.

Thus, a pull fetches and merges all at once, while a fetch only does the first step.

6 - Git Aliases

What if I told you there was a way to make your git commands customizable? Through the git config, you can!

You can set aliases for frequently used commands like so:

$ git config --global alias.co checkout
$ git config --global alias.br branch
$ git config --global alias.ci commit
$ git config --global alias.st status

Now, instead of typing git commit, you just need to type git ci.

This is especially useful for commands that help make a certain task more intuitive.

$ git config --global alias.unstage 'reset HEAD --'
# the double dash serves as an option separator. 
# It tells Git to treat anything after it as a filename

The command above makes the following commands equivalent:

git unstage fileA
git reset HEAD -- fileA

It's also common to add a last command to see your most recent commit:

$ git config --global alias.last 'log -1 HEAD'

That's all for this blog! I hope you learned a few neat tricks for your next project with Git that will improve the quality of your workflow. Thanks for reading!

What's so special about Git?

Terrence Jung — Fri, 20 Sep 2024 17:34:42 +0000

Images in this blog come from "Pro Git" by Scott Chacon, Ben Straub

Git is widely used among programmers to maintain projects on the server, but why is it so widely used and what actually is it? In this blog, we'll go over what a version control system is, its types, what Git is, and the basic structure of a Git project.

What is Version Control?

Simply put, it is a system that records changes to a file or set of files over time. Since you're tracking changes over time, you can recall specific versions at any point of your work.

Features of a VCS include:

revert project files to previous version
compare changes over time
see who last modified something that might be causing a problem

As you can tell, a VCS provides the basic necessities to track a project. Next, we'll discuss how VCS's evolved over time and how the way we maintain projects changed (for the better).

Types of Version Control Systems

There are 3 main types of VCSs: Local, Centralized, and Distributed.

Local

Before even local VCSs existed, people's version-control method of choice was to literally copy files into another directory to version their project files. It did its job and was simple, but it obviously can get very disorganized and cause you to lose track of your work.

Therefore, local VCSs came in to offer a more organized approach to this method. A local VCS uses a simple database (locally) to store changes to files under revision control.

A popular example of a local VCS, an early implementation of a VCS in fact, is RCS (Revision-Control System). It works by keeping patch sets (differences between files) in a special format on the local disk. It then recreates what any file looked like at any point in time by adding up all the patches.

Centralized

What if we want to work with others? The increase in need for collaboration brought about Centralized VCSs. These systems utilize a single server that contains all versioned files, and a number of clients that checkout files from that central place.

The downside is pretty straightforward. If the server goes down, no one can collaborate or save changes. If the disk the central database is on becomes corrupted, and backups weren't kept, then everything is lost. This goes for local VCSs as well.

Although CVCSs can easily be disadvantageous, it is the right step towards an even better VCS.

Distributed

Distributed VCSs solve the issues that CVCSs brought about. DVCSs allow clients to fully mirror the repository (server data), including its full history rather than just checking out the latest snapshot of files from the server. Since local clients can mirror the full history of a project, any one of them can restore a project in the case a server dies. You can think of each client as a cloned backup of all the data.

DVCSs also allow multiple remote repositories that can be worked with, meaning you can collaborate with different groups of people in different ways simultaneously. This gives way to various types of workflows for a project.

Git

What is Git? Git is a DVCS. It was created by creator of Linux, Linus Torvalds. Git was created in hopes of solving issues that other VCSs didn't. Git is especially known for its speed, simple design, and strong support for non-linear development (branches).

What is so special about Git and how does it compare to other VCSs? Well, Git does things a bit differently when it comes to storing information.

Snapshots

Most systems store information as a list of file-based changes. Git on the other hand thinks of its data more like a series of snapshots of a miniature filesystem.

Whenever you commit, Git basically "takes a picture" of what all your files look like at that moment and stores a reference to that snapshot.

If a file is unchanged, Git doesn't store that file again and simply links to the previous identical file that was already stored.

Snapshots are the reason why nearly every operation via Git seems instantaneous.

Checksums

How do we uniquely identify the changes being stored via Git? Luckily, Git checksums everything before it is stored. After data is stored, it is referred to by that checksum.

What is a checksum? A checksum refers to a unique identifier generated using SHA-1 hashing for each piece of data stored in the Git repository.

Through a checksum, you really can't lose information in transit or get file corruption without Git being able to detect. Git ensures that every piece of data is tracked not by file name but by the hash value of its contents.

The Three Main Sections of a Git Project

The last part of this blog will go over the general structure of a Git project locally. Let's first discuss the 3 states that any file can reside in: modified, staged, and committed.

Modified - you changed the file in its current version to go into your next commit snapshot
Staged - you marked a modified file in its current version to go into your next commit snapshot
Committed - the data is safely stored in your local database

A Git project has 3 main sections: working tree, staging area, git directory (repository). A file(s) are placed in one of three sections depending on their state.

Working Tree - a single checkout of one version of the project. These files are pulled out of the compressed database in the Git directory and placed on disk for you to use or modify.
Staging Area - a file that stores information about what will go into your next commit.
Git Directory - where Git stores the metadata and object database for your project. This is what is copied when you clone a repository from another computer.

Git is a powerful tool and provides a working environment that proves to be convenient and fast. I hope learning the history of VCSs helped with your understanding of how Git came to be and why it's so special! Like always, I appreciate any feedback or topics you would want to read about :)

Trees 101: Binary, Heaps, Tries

Terrence Jung — Mon, 16 Sep 2024 22:43:09 +0000

Assumes understanding of Big O notation. Examples are in JavaScript. Information references "Cracking the Coding Interview" by Gayle Laakmann McDowell

Today, we're going to learn all about trees, specifically binary search trees, heaps, and tries. We'll dive into how they work, and by the end of this blog you will be an expert on trees.

Tree Basics

A tree is a hierarchical data structure composed of nodes. It starts with a root node and branches out to child nodes.

Key Components

Root Node: The topmost node of the tree.
Child Nodes: Nodes directly connected to another node when moving away from the root.
Leaf Nodes: Nodes with no children.

Important Characteristics

Trees cannot contain cycles.
Nodes can store any data type.
Parent links are optional.

Structure

The root node has 0 or more child nodes.
Each child node can have its own child nodes. This pattern continues, forming the tree structure.

Node/Tree Definition

Class-Based

class Node {
  constructor(name) {
    this.name = name;
    this.children = [];
  }
}

class Tree {
  constructor(rootName) {
    this.root = new Node(rootName);
  }
}

Functional/Prototype-Based

function Node(name) {
  this.name = name;
  this.children = [];
}

function Tree(rootName) {
  this.root = new Node(rootName);
}

Binary Trees

A binary tree is a tree in which each node has up to 2 children. A binary search tree on the other hand is a binary tree in which every node fits a specific ordering property: all left descendants ≤ n ≤ all right descendants. This is true for each node n.

Note: There are other BST definitions that don’t allow duplicate values.

Balanced vs. Unbalanced Trees

A balanced tree is a tree where the height of the left and right subtrees of every node differs by at most one. This property ensures that operations like insertion, deletion, and search have a time complexity of O(log n) in the average and worst cases.

Unbalanced trees, on the other hand, can degenerate into linear structures, potentially leading to O(n) time complexity for these operations.

Complete Binary Trees

Every level of the tree is filled, except for perhaps the last level. For the last level, it must be filled left to right.

Full Binary Trees

Every node has either 0 or 2 children. No nodes have only one child.

Perfect Binary Trees

One that is both full and complete. All leaf nodes will be at the same level, and this level has the maximum # of nodes. It has exactly $2^k - 1$ nodes.

Binary Tree Traversal

When working with binary trees, we often need to visit all the nodes in a specific order. This process is called traversal.

In-Order Traversal

In-order traversal is like reading a book from left to right. Here's how it works:

Visit the left subtree.
Visit the root node.
Visit the right subtree.

This process is applied recursively to each subtree. When performed on a binary search tree, it visits the nodes in ascending order.

function inOrderTraversal(node) {
  if (node !== null) {
    inOrderTraversal(node.left);
    visit(node);
    inOrderTraversal(node.right);
  }
}

Pre-Order Traversal

In pre-order traversal, we follow this sequence:

Visit the root node first.
Traverse the left subtree.
Traverse the right subtree.

This "root-first" approach can be particularly useful in scenarios where you need to explore a tree's structure from the top down.

function preOrderTraversal(node) {
  if (node !== null) {
    visit(node); // root is first node visited
    preOrderTraversal(node.left);
    preOrderTraversal(node.right);
  }
}

Post-Order Traversal

In post-order traversal, we follow this sequence:

Traverse the left subtree
Traverse the right subtree
Visit the root node

This "bottom-up" approach visits all the children before their parent nodes.

function postOrderTraversal(node) {
  if (node !== null) {
    postOrderTraversal(node.left);
    postOrderTraversal(node.right);
    visit(node); // root is last node visited
  }
}

Binary Heaps (Min-Heaps/Max-Heaps)

A min-heap is a complete binary tree where each node is smaller than its children. Thus, the root is the minimum element.

Key Operations

insert - start by inserting the element at the bottom. We insert at the rightmost spot so as to maintain the complete tree property. Then, we fix the tree by swapping the new element with its parent, until we find an appropriate spot for the element (bubbling up the minimum element). This takes $O (l o g n)$ time, where n is the number of nodes in the heap.

extract_min - finding the minimum element is easy. Removing it is tricky. First, remove the minimum element and swap it with the last element in the heap. Then, we bubble down this element, swapping it with one of its children (the smaller valued node) until the min-heap property is restored. This also takes $O (l o g n)$ time.

Max-heaps are essentially equivalent, but the elements are in descending order rather than ascending order.

Tries (Prefix Trees)

A trie is a variant of an n-ary tree in which characters are stored at each node. Each path down the tree may represent a word.

When building a trie for storing words, we need a way to mark the end of complete words. This is crucial for distinguishing between prefixes and actual words in the trie. There are two common approaches to implement this feature:

Special Terminating Node

Create a TerminatingTrieNode class that inherits from TrieNode. Use these special nodes to mark the end of a word

Example: In a trie containing "man" and "many", the path to "man" ends with a terminating node, while "many" continues with regular nodes

Boolean Flag in Parent Node

Add a terminates boolean flag to each TrieNode. Set this flag to true for nodes that represent the last character of a word

Example: For "man" and "many", the 'n' node would have terminates = true, while also having a child 'y' node

Both methods effectively distinguish between prefixes and complete words, allowing the trie to accurately store and retrieve words. The choice between these approaches often depends on specific implementation requirements and personal preference.

Use Case

A trie is typically used to store the entire English language for quick prefix lookups. While a HashMap can tell us whether a string is a valid word, it cannot tell us if a string is a prefix of any valid words. It takes $O (k)$ where k is length of string, to check if string is valid prefix.

Hope you enjoyed this blog :). Would love to hear feedback on other topics you would like to read about.

LIFO or FIFO? Guide to Stacks/Queues

Terrence Jung — Tue, 20 Aug 2024 02:45:30 +0000

Assumes understanding of Big O notation. Examples are in JavaScript. Information references "Cracking the Coding Interview" by Gayle Laakmann McDowell

Today, we're going to explore two essential data structures: stacks and queues. We'll dive into their concepts, use cases, and implement them in JavaScript using both classical and prototype-based approaches.

Stacks: Last In, First Out (LIFO)

Imagine a stack of pancakes – the last one you put on top is the first one you'll eat. That's exactly how a stack data structure works. It follows the Last In, First Out (LIFO) principle.

Key Operations

push(item): Add an item to the top of the stack
pop(): Remove the top item from the stack
peek(): Return the top item without removing it
isEmpty(): Check if the stack is empty

Use Cases

Stacks are particularly useful in scenarios involving:

Recursive algorithms
Undo mechanisms in text editors

JavaScript Implementation

Classical OOP

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

  push(element) {
    this.items.push(element);
  }

  pop() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.items.pop();
  }

  peek() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }

  clear() {
    this.items = [];
  }
}

Prototype-Based

function Stack() {
  this.items = [];
}

Stack.prototype.push = function(element) {
  this.items.push(element);
};

Stack.prototype.pop = function() {
  if (this.isEmpty()) {
    return "Stack is empty";
  }
  return this.items.pop();
};

Stack.prototype.peek = function() {
  if (this.isEmpty()) {
    return "Stack is empty";
  }
  return this.items[this.items.length - 1];
};

Stack.prototype.isEmpty = function() {
  return this.items.length === 0;
};

Stack.prototype.size = function() {
  return this.items.length;
};

Stack.prototype.clear = function() {
  this.items = [];
};

Queues: First In, First Out (FIFO)

Now, let's shift our focus to queues. Unlike stacks, queues follow the First In, First Out (FIFO) principle. Think of a line at a concert venue – the first person to arrive is the first one to enter.

Key Operations

enqueue(item): Add an item to the end of the queue
dequeue(): Remove the first item from the queue
peek(): Return the first item without removing it
isEmpty(): Check if the queue is empty

Use Cases

Queues are commonly used in:

Breadth-first search algorithms
Task scheduling

JavaScript Implementation

Classical OOP

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

class Queue {
  constructor() {
    this.start = null;
    this.end = null;
    this.size = 0;
  }

  enqueue(element) {
    const newNode = new Node(element);
    if (this.isEmpty()) {
      this.start = newNode;
      this.end = newNode;
    } else {
      this.end.next = newNode;
      this.end = newNode;
    }
    this.size++;
  }

  dequeue() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    const removedData = this.start.data;
    this.start = this.start.next;
    this.size--;
    if (this.isEmpty()) {
      this.end = null;
    }
    return removedData;
  }

  peek() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    return this.start.data;
  }

  isEmpty() {
    return this.size === 0;
  }

  getSize() {
    return this.size;
  }

  clear() {
    this.start = null;
    this.end = null;
    this.size = 0;
  }
}

Prototype-Based

function Node(data) {
  this.data = data;
  this.next = null;
}

function Queue() {
  this.start = null;
  this.end = null;
  this.size = 0;
}

Queue.prototype.enqueue = function(element) {
  const newNode = new Node(element);
  if (this.isEmpty()) {
    this.start = newNode;
    this.end = newNode;
  } else {
    this.end.next = newNode;
    this.end = newNode;
  }
  this.size++;
};

Queue.prototype.dequeue = function() {
  if (this.isEmpty()) {
    return "Queue is empty";
  }
  const removedData = this.start.data;
  this.start = this.start.next;
  this.size--;
  if (this.isEmpty()) {
    this.end = null;
  }
  return removedData;
};

Queue.prototype.peek = function() {
  if (this.isEmpty()) {
    return "Queue is empty";
  }
  return this.start.data;
};

Queue.prototype.isEmpty = function() {
  return this.size === 0;
};

Queue.prototype.getSize = function() {
  return this.size;
};

Queue.prototype.clear = function() {
  this.start = null;
  this.end = null;
  this.size = 0;
};

Performance Analysis

Both stacks and queues offer $O (1)$ time complexity for their core operations (push/pop for stacks, enqueue/dequeue for queues) when implemented efficiently. This makes them highly performant for their specific use cases.

They both provide elegant solutions to many common programming problems and form the basis for more complex data structures and algorithms. By understanding and implementing these structures in JavaScript, you're well-equipped to tackle a wide range of Leetcode/Algorithm problems 😎.

Hash Tables 101: Collisions, Resizing, Hashing

Terrence Jung — Fri, 16 Aug 2024 23:47:32 +0000

Assumes understanding of Big O notation. Examples are in JavaScript. Information references "Cracking the Coding Interview" by Gayle Laakmann McDowell

Understanding Hash Tables

Whether you've heard about dictionaries, or hash maps, or hash tables, they are all essentially the same. In this blog, we'll reference this data structure as a hash table for simplicity's sake.

Let's start with defining what a hash table is. A hash table is a data structure that maps keys to values in the form of key-value pairs for highly efficient lookup. There are multiple ways to implement it.

Key Components of a Hash Table

Using an array of linked lists and a hashing function we can implement a hash table. Let's dive deeper into what a hashing function is.

What is a Hashing Function?

A hashing function is a crucial component of a hash table. It's an algorithm, typically in the form of a function, that takes an input (or 'key') and returns a fixed-size string of bytes, typically in the form of an integer. The output is called a hash code or simply a hash.

The main purpose of a hashing function in the context of hash tables is to map a hash code to a valid index of an array of buckets/slots, from which the desired value can be found. These buckets/slots would be linked lists in our case.

Characteristics of a Good Hashing Function:

Deterministic: For a given input, it should always produce the same hash output.
Uniform Distribution: It should map the expected inputs as evenly as possible over its output range.
Efficient: It should be quick to compute.
Avalanche Effect: A small change in the input should result in a significantly different hash output.

Why Use an Array of Linked Lists?

The use of an array of linked lists in hash table implementation is a common technique known as chaining. This approach offers several advantages:

Collision Handling: The primary reason for using an array of linked lists is to handle collisions efficiently. When two keys hash and map to the same index, we can simply add the new key-value pair to the linked list at that index.
Space Efficiency: It allows the hash table to store more items than the size of the underlying array. Each array slot can hold multiple items through its linked list.

Array:  [0] -> (key1, value1) -> (key2, value2)
        [1] -> (key3, value3)
        [2] -> (key4, value4) -> (key5, value5) -> (key6, value6)
        [3] -> Empty
        [4] -> (key7, value7)

In this example, keys 1 and 2 hash to index 0, while keys 4, 5, and 6 all hash to index 2.

Inserting Key-Value Pairs

Now that we have a good understanding of hash functions and why we use chaining, let's go through the flow of inserting key-value pairs into a hash table:

When inserting the key (any value), we first compute the key’s hash code (usually an int or long). It’s possible that two different keys could have the same hash code since there may be an infinite # of keys and finite # of ints.
Map the hash code to an index in the array. A common method for mapping a hash code to an array is using the modulus operator. (e.g., hash(key) % array.length)). It's possible that two different hash codes could map to the same index with this method.
At an index, there is a linked lists of keys and values. Store the key-value pair at this index. Collisions occur when keys have the same hash codes or hash codes map to the same indices.

Accessing Key-Value Pairs

Accessing key-value pairs is highly efficient in a hash table implementation. Simply compute the hash code from the key, then compute the index from the hash code, and finally search through the linked list for the value with this key.

Assuming a good implementation, accessing key-value pairs (insertion and deletion too), takes $O (1)$ .

What Makes a Hash Table Implementation "Good"?

A well-implemented hash table should balance efficiency, space utilization, and collision handling. Here are the key factors that contribute to a good hash table implementation:

A Good Hash Function

The heart of any hash table is its hash function. A good hash function should:

Be quick to compute
Minimize collisions

Optimal Load Factor

The load factor is the ratio of filled slots to total slots in the hash table. Maintaining an appropriate load factor is crucial:

A typical sweet spot is between 0.6 and 0.75

Too low (< 0.5): Wastes space
Too high (> 0.8): Increases collision risk

Collision Resolution Techniques

Two primary methods for handling collisions are:

Chaining: Each table position stores a linked list of collided items. Simple to implement but can lead to slower lookups if chains become long.
Open Addressing: If a collision occurs, look for the next available slot. Keeps all data in the table but requires careful implementation to avoid clustering of stored data.

Note that chaining and open-addressing cannot coexist easily. Logically, it would not make sense to look for the next available slot but store collided items at a specific index.

Dynamic Resizing

As the number of elements grows, the hash table should resize to maintain performance:

Typically, the table size is doubled when the load factor exceeds a threshold. All elements need to be rehashed into the new, larger table.

This operation is expensive but infrequent, keeping the amortized time complexity at O(1).

JavaScript Implementation

This implementation will utilize resizing and chaining for collision resolution. We will assume that our keys are integers.

For the hash function + mapping, we will keep it very simple and simply perform the following given a key:

\hspace{0.2cm} \% \hspace{0.2cm} array \hspace{0.1cm} capacity

Classical OOP

class HashNode {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.next = null;
    }
}

class HashTable {
    constructor(capacity = 16) {
        this.capacity = capacity;
        this.size = 0;
        this.buckets = new Array(this.capacity).fill(null);
        this.threshold = 0.75;
    }

    hash(key) {
        return key % this.capacity;
    }

    insert(key, value) {
        const index = this.hash(key);
        if (!this.buckets[index]) {
            this.buckets[index] = new HashNode(key, value);
            this.size++;
        } else {
            let currentNode = this.buckets[index];
            while (currentNode.next) {
                if (currentNode.key === key) {
                    currentNode.value = value;
                    return;
                }
                currentNode = currentNode.next;
            }
            if (currentNode.key === key) {
                currentNode.value = value;
            } else {
                currentNode.next = new HashNode(key, value);
                this.size++;
            }
        }

        if (this.size / this.capacity >= this.threshold) {
            this.resize();
        }
    }

    get(key) {
        const index = this.hash(key);
        let currentNode = this.buckets[index];
        while (currentNode) {
            if (currentNode.key === key) {
                return currentNode.value;
            }
            currentNode = currentNode.next;
        }
        return undefined;
    }

    remove(key) {
        const index = this.hash(key);
        if (!this.buckets[index]) {
            return false;
        }
        if (this.buckets[index].key === key) {
            this.buckets[index] = this.buckets[index].next;
            this.size--;
            return true;
        }
        let currentNode = this.buckets[index];
        while (currentNode.next) {
            if (currentNode.next.key === key) {
                currentNode.next = currentNode.next.next;
                this.size--;
                return true;
            }
            currentNode = currentNode.next;
        }
        return false;
    }

    resize() {
        const newCapacity = this.capacity * 2;
        const newBuckets = new Array(newCapacity).fill(null);
        this.buckets.forEach(head => {
            while (head) {
                const newIndex = head.key % newCapacity;
                const next = head.next;
                head.next = newBuckets[newIndex];
                newBuckets[newIndex] = head;
                head = next;
            }
        });
        this.buckets = newBuckets;
        this.capacity = newCapacity;
    }

    getSize() {
        return this.size;
    }

    getCapacity() {
        return this.capacity;
    }
}

Functional OOP

function createHashTable(initialCapacity = 16) {
    let capacity = initialCapacity;
    let size = 0;
    let buckets = new Array(capacity).fill(null);
    const threshold = 0.75;

    function hash(key) {
        return key % capacity;
    }

    function resize() {
        const newCapacity = capacity * 2;
        const newBuckets = new Array(newCapacity).fill(null);
        buckets.forEach(function(head) {
            while (head) {
                const newIndex = head.key % newCapacity;
                const next = head.next;
                head.next = newBuckets[newIndex];
                newBuckets[newIndex] = head;
                head = next;
            }
        });
        buckets = newBuckets;
        capacity = newCapacity;
    }

    return {
        insert: function(key, value) {
            const index = hash(key);
            const newNode = { key, value, next: null };

            if (!buckets[index]) {
                buckets[index] = newNode;
                size++;
            } else {
                let currentNode = buckets[index];
                while (currentNode.next) {
                    if (currentNode.key === key) {
                        currentNode.value = value;
                        return;
                    }
                    currentNode = currentNode.next;
                }
                if (currentNode.key === key) {
                    currentNode.value = value;
                } else {
                    currentNode.next = newNode;
                    size++;
                }
            }

            if (size / capacity >= threshold) {
                resize();
            }
        },

        get: function(key) {
            const index = hash(key);
            let currentNode = buckets[index];
            while (currentNode) {
                if (currentNode.key === key) {
                    return currentNode.value;
                }
                currentNode = currentNode.next;
            }
            return undefined;
        },

        remove: function(key) {
            const index = hash(key);
            if (!buckets[index]) {
                return false;
            }
            if (buckets[index].key === key) {
                buckets[index] = buckets[index].next;
                size--;
                return true;
            }
            let currentNode = buckets[index];
            while (currentNode.next) {
                if (currentNode.next.key === key) {
                    currentNode.next = currentNode.next.next;
                    size--;
                    return true;
                }
                currentNode = currentNode.next;
            }
            return false;
        },

        getSize: function() {
            return size;
        },

        getCapacity: function() {
            return capacity;
        }
    };
}

Implementing a Doubly Linked List

Terrence Jung — Wed, 14 Aug 2024 21:40:36 +0000

Assumes understanding of Big O notation. Examples are in JavaScript. Information references "Cracking the Coding Interview" by Gayle Laakmann McDowell

Understanding Doubly Linked Lists

A doubly linked list is very similar to a singly linked list, except for the node’s structure and the way we add/remove nodes.

Node Structure

A node in a doubly linked list contains a prev pointer, next pointer, and value. The prev pointer points to the previous node and the next pointer points to the next node. By nature, this list goes both ways at each node.

Adding a Node

To insert a new node (newNode) at a specific index:

Store the node currently at the insertion index in a temporary variable nextNode.
Update the connections for the previous node and the new node:
- Set the previous node's next pointer to newNode.
- Set newNode's prev pointer to the previous node.
Connect the new node to the next node:
- Set newNode's next pointer to nextNode.
- Set nextNode's prev pointer to newNode.

Removing a Node

To remove a node at a specific index:

Update the previous node's next pointer:
- Set it to point to the node after the one being removed.
Update the next node's prev pointer:
- Set it to point to the node before the one being removed.

This effectively "bridges" the gap created by removing the node, maintaining the list's integrity.

Time Complexity Analysis

Adding/Removing inside the doubly linked list → $O (n)$
Adding/Removing at the head or tail of doubly linked list → $O (1)$

JavaScript Implementation

Classical OOP

class ListNode {
  constructor(value, prev = null, next = null) {
    this.value = value;
    this.prev = prev;
    this.next = next;
  }
}

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  // add a node to the head of the list
  addHead(value) {
    const newNode = new ListNode(value, null, this.head);
    if (this.head) {
      this.head.prev = newNode;
    } else {
      this.tail = newNode; // If list was empty, new node is also the tail
    }
    this.head = newNode;
    this.size++;
  }

  // Add a node to the tail of the list
  addTail(value) {
    const newNode = new ListNode(value, this.tail, null);
    if (this.tail) {
      this.tail.next = newNode;
    } else {
      this.head = newNode; // If list was empty, new node is also the head
    }
    this.tail = newNode;
    this.size++;
  }

  // Remove a node from the head of the list
  removeHead() {
    if (!this.head) return null; // List is empty
    const removedValue = this.head.value;
    this.head = this.head.next;
    if (this.head) {
      this.head.prev = null;
    } else {
      this.tail = null; // List became empty
    }
    this.size--;
    return removedValue;
  }

  // Remove a node from the tail of the list
  removeTail() {
    if (!this.tail) return null; // List is empty
    const removedValue = this.tail.value;
    this.tail = this.tail.prev;
    if (this.tail) {
      this.tail.next = null;
    } else {
      this.head = null; // List became empty
    }
    this.size--;
    return removedValue;
  }

  // Remove a node at a specific index
  removeAt(index) {
    if (index < 0 || index >= this.size) return null;
    let current;
    if (index < this.size / 2) {
      current = this.head;
      for (let i = 0; i < index; i++) {
        current = current.next;
      }
    } else {
      current = this.tail;
      for (let i = this.size - 1; i > index; i--) {
        current = current.prev;
      }
    }
    if (current.prev) current.prev.next = current.next;
    if (current.next) current.next.prev = current.prev;
    if (index === 0) this.head = current.next;
    if (index === this.size - 1) this.tail = current.prev;
    this.size--;
    return current.value;
  }

  // Get the size of the list
  getSize() {
    return this.size;
  }

  // Get the values in the list
  getValues() {
    const values = [];
    let current = this.head;
    while (current) {
      values.push(current.value);
      current = current.next;
    }
    return values;
  }
}

Prototype-based OOP

function ListNode(value, prev = null, next = null) {
  this.value = value;
  this.prev = prev;
  this.next = next;
}

function DoublyLinkedList() {
  this.head = null;
  this.tail = null;
  this.size = 0;
}

// Add a node to the head of the list
DoublyLinkedList.prototype.addHead = function(value) {
  const newNode = new ListNode(value, null, this.head);
  if (this.head) {
    this.head.prev = newNode;
  } else {
    this.tail = newNode;
  }
  this.head = newNode;
  this.size++;
};

// Add a node to the tail of the list
DoublyLinkedList.prototype.addTail = function(value) {
  const newNode = new ListNode(value, this.tail, null);
  if (this.tail) {
    this.tail.next = newNode;
  } else {
    this.head = newNode;
  }
  this.tail = newNode;
  this.size++;
};

// Remove a node from the head of the list
DoublyLinkedList.prototype.removeHead = function() {
  if (!this.head) return null;
  const removedValue = this.head.value;
  this.head = this.head.next;
  if (this.head) {
    this.head.prev = null;
  } else {
    this.tail = null;
  }
  this.size--;
  return removedValue;
};

// Remove a node from the tail of the list
DoublyLinkedList.prototype.removeTail = function() {
  if (!this.tail) return null;
  const removedValue = this.tail.value;
  this.tail = this.tail.prev;
  if (this.tail) {
    this.tail.next = null;
  } else {
    this.head = null;
  }
  this.size--;
  return removedValue;
};

// Remove a node at a specific index
DoublyLinkedList.prototype.removeAt = function(index) {
  if (index < 0 || index >= this.size) return null;
  let current;
  if (index < this.size / 2) {
    current = this.head;
    for (let i = 0; i < index; i++) {
      current = current.next;
    }
  } else {
    current = this.tail;
    for (let i = this.size - 1; i > index; i--) {
      current = current.prev;
    }
  }
  if (current.prev) current.prev.next = current.next;
  if (current.next) current.next.prev = current.prev;
  if (index === 0) this.head = current.next;
  if (index === this.size - 1) this.tail = current.prev;
  this.size--;
  return current.value;
};

// Get the size of the list
DoublyLinkedList.prototype.getSize = function() {
  return this.size;
};

// Get the values in the list
DoublyLinkedList.prototype.getValues = function() {
  const values = [];
  let current = this.head;
  while (current) {
    values.push(current.value);
    current = current.next;
  }
  return values;
};

Implementing a Singly Linked List

Terrence Jung — Wed, 14 Aug 2024 00:31:24 +0000

Assumes understanding of Big O notation. Examples are in JavaScript. Information references "Cracking the Coding Interview" by Gayle Laakmann McDowell

Understanding Singly Linked Lists

A linked list is a data structure that represents a sequence of nodes. In a singly linked list, each node points to the next node.

In memory, these nodes do not need to be sorted contiguously (adjacent to one another) since we are not relying on indexing. When we iterate through a linked list, we pass through each reference of a node until we hit a null pointer.

Structure of a Node

In a singly linked list, each node typically contains two fields:

data: the value or information contained in the node
next: the reference (pointer) to the next node in the list

Head and Tail Pointers

The head is a reference to the first node in the list. It is essential because it allows access to the linked list’s start. It sometimes acts as a sentinel node (placed before the actual head node) for easier operations like inserting at the head. The tail is a reference to the last node in the list. It’s next pointer is null indicating the end of the list.

Memory Efficiency of Insertions/Deletions

Compared to arrays, linked lists are more memory efficient in terms of insertion/deletion since these operations do not require “shifting” of elements. The operation of adding or removing an element from anywhere in a linked list takes $O (1)$ time. However, it takes $O (n)$ time in the worst case to traverse through the linked list to then add/remove an element (does not apply for adding/removing first element).

It's worth pointing out that linked lists have extra memory overhead due to the storage of pointers along with data in each node.

Time Complexity Analysis

Insertion:

at beginning or end (with head/tail pointers) → $O (1)$
at specific position (due to traversal) → $O (n)$

Deletion:

at beginning → $O (1)$
at end → $O (n)$
at specific position → $O (n)$

Traversal/Search: $O (n)$

JavaScript Implementation

Classical OOP

class ListNode {
    constructor(val, nextNode = null) {
        this.val = val;
        this.next = nextNode;
    }
}

class LinkedList {
    constructor() {
        // sentinel node for easy operations on head
        this.head = new ListNode(-1);
        this.tail = this.head;
    }

    // get the value at the specified index.
    get(index) {
        let curr = this.head.next;
        let i = 0;
        while (curr !== null) {
            if (i === index) return curr.val;
            curr = curr.next;
            i++;
        }
        return -1;
    }

    // insert a new value at the head of the list.
    insertHead(val) {
        const newNode = new ListNode(val);
        newNode.next = this.head.next;
        this.head.next = newNode;
        if (newNode.next === null) {
            this.tail = newNode;
        }
    }

    // insert a new value at the tail of the list.
    insertTail(val) {
        const newNode = new ListNode(val);
        this.tail.next = newNode;
        this.tail = newNode;
    }

    // remove the node at the specified index.
    remove(index) {
        let curr = this.head;
        let i = 0;
        while (i < index && curr.next !== null) {
            i++;
            curr = curr.next;
        }

        if (curr !== null && curr.next !== null) {
            if (curr.next === this.tail) this.tail = curr;
            curr.next = curr.next.next;
            return true;
        }
        return false;
    }

    // get all values in the list as an array.
    getValues() {
        const values = [];
        let curr = this.head.next;
        while (curr !== null) {
            values.push(curr.val);
            curr = curr.next;
        }
        return values;
    }

    // get the length of the list.
    length() {
        let length = 0;
        let curr = this.head.next;
        while (curr !== null) {
            length++;
            curr = curr.next;
        }
        return length;
    }
}

Prototype-Based OOP

function ListNode(val, nextNode = null) {
    this.val = val;
    this.next = nextNode;
}

function LinkedList() {
    this.head = new ListNode(-1); // Sentinel node
    this.tail = this.head;
}

// get the value at the specified index
LinkedList.prototype.get = function(index) {
    let curr = this.head.next;
    let i = 0;
    while (curr !== null) {
        if (i === index) return curr.val;
        curr = curr.next;
        i++;
    }
    return -1;
};

// insert a new value at the head of the list
LinkedList.prototype.insertHead = function(val) {
    const newNode = new ListNode(val);
    newNode.next = this.head.next;
    this.head.next = newNode;
    if (newNode.next === null) {
        this.tail = newNode;
    }
};

// insert a new value at the tail of the list
LinkedList.prototype.insertTail = function(val) {
    const newNode = new ListNode(val);
    this.tail.next = newNode;
    this.tail = newNode;
};

// remove the node at the specified index
LinkedList.prototype.remove = function(index) {
    let curr = this.head;
    let i = 0;
    while (i < index && curr.next !== null) {
        i++;
        curr = curr.next;
    }

    if (curr !== null && curr.next !== null) {
        if (curr.next === this.tail) this.tail = curr;
        curr.next = curr.next.next;
        return true;
    }
    return false;
};

// get all values in the list as an array
LinkedList.prototype.getValues = function() {
    const values = [];
    let curr = this.head.next;
    while (curr !== null) {
        values.push(curr.val);
        curr = curr.next;
    }
    return values;
};

// get the length of the list
LinkedList.prototype.length = function() {
    let length = 0;
    let curr = this.head.next;
    while (curr !== null) {
        length++;
        curr = curr.next;
    }
    return length;
};

Optimizing String Concatenation with StringBuilder

Terrence Jung — Tue, 30 Jul 2024 00:05:20 +0000

Assumes understanding of Big O notation. Examples are in JavaScript. Information references "Cracking the Coding Interview" by Gayle Laakmann McDowell

Imagine you want to concatenate a large number of strings together. Assuming the strings are all the same length x and there are n strings, it takes $O (x + 2 x + ... + n x)$ time. On each concatenation, we create a copy of the previous string and copy over the new string. Thus, the first iteration would require copying x characters. The next iteration would require copying 2x characters, and so on.

We can actually simplify the previously stated runtime further:

x(\frac{n(n-1)}{2}) = xn^2

Therefore, concatenating strings in this matter takes $O(xn^2)$ time to complete. Pretty long if you ask me. Here's the algorithm:

function joinWords(words) {
    let sentence = "";
    for (let w of words) {
        sentence = sentence + w;
    }
    return sentence;
}

StringBuilder Class

A StringBuilder class can help you avoid this long runtime. Simply, this class creates a resizable array of all the strings and copies them back to a string only when necessary.

In JavaScript, we can simply use the join method on a resizable array to copy the list of strings into a string.

function joinWords(words) {
    let sentence = [];
    for (let w of words) {
        sentence.push(w);
    }

    return sentence.join("");
}

Now, appending a string to the array takes $O (1)$ time per operation. The final step of copying the array to a single string takes $O (n)$ time, where n is the number of strings in the array.

Implementing Dynamic Arrays

Terrence Jung — Thu, 25 Jul 2024 04:03:30 +0000

Assumes understanding of Big O notation. Examples are in JavaScript. Information references "Cracking the Coding Interview" by Gayle Laakmann McDowell

Introduction

In some languages like JavaScript or Python, arrays are automatically resizable, meaning it will grow as you append items. In other languages like Java, arrays are fixed lengths, meaning the size is defined when you initialize the array. These arrays that grow automatically are called dynamic arrays.

Understanding Dynamic Arrays

In Java, an ArrayList is an array-like data structure that offers dynamic resizing while still providing $O (1)$ access. When the array is full, the array doubles in size. Each doubling takes $O (n)$ time, but happens so rarely that its amortized insertion time is still $O (1)$ .

Among different programming languages, the name of this data structure as well as its resizing factor (which is 2 in Java) varies. The resizing factor determines how much larger an array will be resized.

Why is Amortized Insertion Time $O (1)$ ?

When resizing, assuming the resizing factor is 2, we can observe that we increase to an array of size N by doubling the previous array (which is half of N). Furthermore, we also need to copy $N /2$ elements to this new array.

If we sum the number of elements we copy from the final capacity increase to the first capacity increase: $n2+n4+n8+n16+...+2+1\frac{n}{2} + \frac{n}{4} + \frac{n}{8} + \frac{n}{16} + ...+2 + 1$ which sums to just less than N. Therefore, inserting N elements takes about $O (n)$ work in total. Each insertion is $O (1)$ on average, even though some insertions take $O (n)$ time in the worst case.

Core Concepts and Big O Complexity

Dynamic arrays in JavaScript typically have several core methods, each with different time complexities:

get(i): This method retrieves the element at index i.

Complexity: $O (1)$

set(i, n): This method sets the element at index i to n.

Complexity: $O (1)$

pushback(n): This method adds the element n to the end of the array.

Complexity: $O (1)$ amortized, but $O (n)$ when resizing occurs

popback(): This method removes the last element of the array.

Complexity: $O (1)$

resize(): This method doubles the capacity of the array and copies all elements to the new array.

Complexity: $O (n)$

getSize(): This method returns the number of elements in the array.

Complexity: $O (1)$
Note: we are able to achieve this complexity by using a size variable to track the number of filled slots in the array.

getCapacity(): This method returns the current capacity of the array.

Complexity: $O (1)$

Implementation in JavaScript

class DynamicArray {
    // size is # of filled slots while capacity is total slots in array
    constructor(capacity) {
        this.capacity = capacity;
        this.arr = new Array(this.capacity);
        this.size = 0;
    }

    // O(1)
    get(i) {
        if (i < 0 || i >= this.size) return undefined;
        return this.arr[i];
    }

    // O(1)
    set(i, n) {
        if (i < 0 || i >= this.size) return undefined;
        this.arr[i] = n;
    }

    // O(1) amortized 
    pushback(n) {
        if (this.size === this.capacity) {
            this.resize();
        }
        this.arr[this.size] = n;
        this.size++;
    }

    // O(1) 
    popback() {
        if (this.size === 0) return undefined;
        this.size--;
        let temp = this.arr[this.size];
        this.arr[this.size] = undefined;
        return temp;

    }

    // O(n)
    resize() {
        this.capacity *= 2;
        let newArr = new Array(this.capacity);
        for (let i = 0; i < this.size; i++) {
            newArr[i] = this.arr[i];
        }
        this.arr = newArr;
    }

    // O(1)
    getSize() {
        return this.size;
    }

    // O(1) 
    getCapacity() {
        return this.capacity;
    }
}

Conclusion

Dynamic arrays are a powerful data structure that combines the flexibility of resizable storage with the efficiency of constant-time access. Hope this helps!

Complexity Uncomplicated: Your Guide to Big O and Algorithm Analysis

Terrence Jung — Tue, 23 Jul 2024 00:42:12 +0000

This blog assumes prior knowledge of fundamental data structures/algorithms. Examples are in JavaScript. Information references "Cracking the Coding Interview" by Gayle Laakmann McDowell

Introduction

Mastering technical interviews demands a diverse skill set, but two abilities stand out as crucial: understanding Big O notation and analyzing algorithm efficiency. These skills are the keys to unlocking your potential in algorithm complexity discussions.

What is Big O? It is the language and metric we use to describe the efficiency of algorithms.

In this blog, we'll review time/space complexity, how to measure them, amortized time, and logarithmic/recursive runtimes.

Time Complexity

Time complexity is our way of describing how an algorithm's runtime changes as the input size grows.

Best Case: the minimum time an algorithm needs to run.
Worst Case: the maximum time an algorithm might take.
Expected Case: the average time an algorithm usually takes.

While it's tempting to focus on the best case, it's often misleading. Any algorithm can perform well with a perfectly crafted input. That's why we typically focus on the worst and expected cases - they give us a more realistic picture of our algorithm's performance.

Interestingly, for many algorithms, the worst and expected cases are identical. But sometimes, they can differ (explained later).

Space Complexity

Space complexity is a parallel concept to time complexity, measuring the memory (space) required by an algorithm.

For instance, if we create an array of size $n$ , we're looking at $O (n)$ space complexity. It grows linearly with our input size.

But here's a twist: space isn't just about data structures. Every time we make a recursive call, we're adding to the call stack. Take this simple recursive sum function:

function sum(n) {
    if (n <= 0) {
        return 0;
    }
    return n + sum(n - 1);
}

this would take O(n) time and O(n) space because sum(4), sum(3), sum(2), sum(1), sum(0) all exist in the call stack simultaneously.

Measuring Complexity

When it comes to measuring the complexity of algorithms, we're not after pinpoint accuracy. Instead, we're looking for a big-picture view that helps us understand how our algorithm scales. Let's dive into some key "rules" that will help you with this.

Multi-Part Algorithms: Add vs. Multiply

For an algorithm that has 2 steps, when do you multiply the runtimes and when do you add them?

if your algorithm is in the form “do this. when done, do that” then you add the runtimes
if your algorithm is in the form “do this for each time you do that” then you multiply the runtimes. Take a look at the examples below:

// O(A + B) - "Do this, then do that"
arrA.forEach(a => console.log(a));
arrB.forEach(b => console.log(b));

// O(A * B) - "Do this for each time you do that"
arrA.forEach(a => {
    arrB.forEach(b => {
        console.log(`${a},${b}`);
    });
});

In the first example, we're doing two separate things sequentially. In the second, we're doing something for each combination of A and B.

Drop the Constants

In the world of Big O, we're more interested in the overall rate of growth than absolute speed. That's why we drop constants. Whether your algorithm runs in $O (2 N)$ or $O (N)$ time, we simplify it to $O (N)$ . As $N$ grows larger, the constant factor becomes less significant. Consider the two code snippets:

// Version 1
let min = Number.MAX_VALUE;
let max = Number.MIN_VALUE;
array.forEach(x => {
    if (x < min) min = x;
    if (x > max) max = x;
});

// Version 2
min = Number.MAX_VALUE;
max = Number.MIN_VALUE;
array.forEach(x => {
    if (x < min) min = x;
});
array.forEach(x => {
    if (x > max) max = x;
});

Both have the same O(N) time complexity, despite Version 2 having two separate loops.

Drop the Non-Dominant Terms: Focus on the Heavyweight

When you have multiple terms in your Big O expression, focus on the most significant one.

$O (N ² + N)$ becomes $O (N ²)$
$O (N + l o g N)$ simplifies to $O (N)$
$O (5 * 2ᴺ + 1000 N ¹⁰⁰)$ boils down to $O (2ᴺ)$

However, be cautious. If you have O(B² + A), and A and B are independent variables, you can't simplify further. Each represents different parts of the algorithm’s complexity

Amortized Time: The Secret Behind Efficient Operations

Amortized time is a fascinating concept in time complexity analysis that shines when there's a stark difference between the worst-case and average-case scenarios.

Take Java's ArrayList, for example—a dynamically resizing array. When you add an element to an ArrayList that still has space, the operation takes $O (1)$ time. When the array is full, the ArrayList has to create a new, larger array (typically double the size) and copy over all the existing elements, which takes $O (N)$ time. This $O (N)$ operation is a rare occurrence. Most of the time, adding an element is a quick $O (1)$ operation. When you look at the average time per operation over a long sequence of insertions, the amortized time remains a highly efficient $O (1)$ . This clever balance is what makes data structures like ArrayList incredibly efficient in practice.

Logarithmic Runtimes

What does $O(log⁡(N))O(\log(N))$ runtime really mean? An $O(log⁡(N))O(\log(N))$ runtime typically means that the algorithm divides the problem in half each time, such as with binary search. This logarithmic complexity grows much slower (as input grows) compared to linear or quadratic time complexities, making it very efficient for large inputs.

In the example below, we are performing binary search. Every time we make a "guess", we halve the input space in half each time. This means that we've reduced the space in which we search for "target" by one half! In the worst case, it would take $l o g (N)$ iterations to find "target".

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);

        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1; // target not found
}

Recursive Runtimes

The code below may at first seem like it runs in $O(N^2)$ time. It actually runs in $O(2^N)$ time because for each call, we call again twice. You can visualize the recursive calls as a tree. The tree would have a depth (height) of $N$ where each node has two children. At each level, we have twice as many nodes as the previous level. For a recursive algorithm that makes multiple calls, the runtime will often look like $O(branches^{depth})$ where branches is the number of times each recursive call branches.

function f(n) {
    if (n <= 1) {
        return 1;
    }
    return f(n - 1) + f(n - 1);
}

The space complexity is $O (N)$ . Although we have $O(2^N)$ nodes in the tree, only $O (N)$ exist at any given time.

Ending

Hope this helps with your technical interviews or your understanding of algorithm analysis. Good luck and look out for more blogs on Big O analysis, focusing on important examples.