# The Last Algorithms Course You'll Need

Learning Paths:

Table of Contents

## Introduction

## Basics

### Big O Time Complexity

ThePrimeagen discusses an overview of Big O, including, what it is, why it's used, and some essential concepts. A walkthrough of a Big O code example is also provided in this segment.### Arrays Data Structure

ThePrimeagen demonstrates interpreting arrays as a fixed size, contiguous memory chunk by walking through array positions in an array buffer. Operations that can be performed on an array are also demonstrated in this segment.### Arrays Q&A

ThePrimeagen answers student questions about whether there is no insert, push, or pop in an array and if an array's size and memory allocation must be specified at initialization. Questions regarding whether something that has an array is being created when creating an array in JavaScript and how big the array is that is instantiated are also covered in this segment.

## Search

### Linear Search & Kata Setup

ThePrimeagen discusses searching through an array with a linear search algorithm. Setting up the TypeScript library Kata and a walkthrough of implementing the linear search algorithm are also covered in this segment.### Binary Search Algorithm

ThePrimeagen demonstrates a search algorithm that jumps forward by ten percent, discusses possible pitfalls of that search, and demonstrates how the binary search algorithm differs. Binary search is an efficient algorithm for finding an item from a sorted list of items.### Pseudo Code Binary Search

ThePrimeagen walks through creating and implementing a pseudo-code version of a Binary search algorithm.### Implementing Binary Search

ThePrimeagen demonstrates implementing the binary search algorithm in TypeScript and uses the kata machine to test that the algorithm is correct. The binary search algorithm repeatedly halves the portion of a sorted list that could contain the target item until the possible locations have been narrowed down to one.### Two Crystal Balls Problem

ThePrimeagen discusses options for solving this previous interview problem: When given two crystal balls that will break if dropped from a high enough distance, determine the exact spot in which it will break in the most optimized way. This segment demonstrates breaking down a search problem without using a linear search.### Implementing Two Crystal Balls

ThePrimeagen walks through implementing the solution for the two crystal balls problem. Student questions regarding traveling using the cube root of N are also covered in this segment.

## Sort

### Bubble Sort

ThePrimeagen demonstrates what happens under the hood when bubble sorting. Bubble sort repeatedly steps through the input list, swapping their values if needed until no swaps have to be performed during a pass, meaning that the list has become fully sorted.### Implementing Bubble Sort

ThePrimeagen walks through implementing and testing the bubble sort algorithm. Student questions regarding how the formula was produced and for sorting algorithm suggestions for immutable arrays are also covered in this segment.### Linked List Data Structures

ThePrimeagen discusses an overview of linked list data structures, including implementing deletion and insertion. A student's question regarding if there is no index in the linked list is also covered in this segment.### Linked List Complexity

ThePrimeagen discusses the time and space complexity of linked lists. A student's question regarding the insertion of F is also covered in this segment.### Queue

ThePrimeagen discusses the function of a queue, a linear data structure that follows the First in, First Out Principle (FIFO). Queue supports operations such as peek, enqueue, dequeue and print().### Implementing a Queue

ThePrimeagen walks through implementing and testing the queue algorithm.### Queue Q&A

ThePrimeagen answers student questions regarding if having no tail means there is no node, clarification on the peek method, and why this.tail.next is being set to the new node.### Stack

ThePrimeagen demonstrates a linear data structure that follows the principle of Last In First Out, the opposite of a queue, a stack. In a stack, the last element inserted inside the stack is removed first.### Implementing a Stack

ThePrimeagen walks through implementing and testing a stack, including push, pop, and peek.

## Arrays

### Arrays vs Linked List

ThePrimeagen discusses similarities and differences between arrays and linked lists. Linked lists use less memory, but must be stepped through to find the target item. A demonstration of traversing a linked list is also provided in this segment.### ArrayList

ThePrimeagen demonstrates the ability to write list operations such as get, push, and pop on arrays using ArrayList.### ArrayBuffer

ThePrimeagen discusses an ArrayBuffer object which is used to represent a generic, fixed-length raw binary data buffer.### Data Structures Q&A

ThePrimegen walks through an empirical test for what data structure is being used under the hood with `const a = []`. Student questions regarding if unshift and shift are exponential, what type of operation is slice, and where would this be used in practical code are also covered in this segment.

## Recursion

### Recursion

ThePrimeagen discusses recursion as a function that calls itself until it reaches the base case and the problem is solved. Recursion can be broken into three steps: pre, recurse, and post.### Path Finding: Base Case

ThePrimeagen walks through an example of pathfinding using a base case by implementing and testing the MazeSolver example in the kata machine.### Path Finding: Recursive Case

ThePrimeagen walks through the MazeSolver example of pathfinding using the recursive case.### Recursion Q&A

ThePrimeagen answers student questions regarding what happens when the recursive function can no longer move forward, how the end path of the MazeSolver was found, and if there are any scenarios in which changing the recursion direction would improve performance.

## Quick Sort

### QuickSort Algorithm

ThePrimeagen discusses the QuickSort algorithm as an algorithm that uses a divide and conquer technique. The algorithm picks a pivot element and rearranges the array so elements smaller than the pivot element move to the left side of the pivot, and elements greater move to the right side. The algorithm then recursively sorts the subarrays on the left and right of the pivot element.### Implementing QuickSort

ThePrimeagen walks through implementing and testing the QuickSort algorithm in the kata machine. Both a Quicksort function and a partition function are implemented in this segment.

## Doubly Linked List

### Linked List: prepend, insertAt, & append

ThePrimeagen walks through implementing a doubly linked list, including prepend, insertAt, and append.### Linked List: remove, get, & removeAt

ThePrimeagen walks through implementing the second half of a doubly linked list, including remove, get, and removeAt.### Linked List Q&A

ThePrimeagen answers student questions regarding using VIM, if setting remove undefined would break, where the methods are taken from, and the reason for using the Java methods.### Debugging Linked List

ThePrimeagen walks through debugging the remove portion of the doubly linked list. A student's question regarding an example of keeping track of removed nodes is also covered in this segment.

## Trees

### Trees Overview

ThePrimeagen discusses an overview of more advanced data structures known as trees and walks through some terminology with a whiteboard example. A tree can be empty with no nodes, or a tree can be a structure consisting of one node called the root and zero or one or more subtrees.### Tree Traversals

ThePrimeagen discusses and demonstrates, via whiteboarding, visiting nodes using three types of traversals preorder, inorder, and postorder.### Implement Tree Traversal

ThePrimeagen live codes the three types of tree traversals. Inorder traversal traverses one subtree of a node, visits the node, and then traverses its other subtree. Preorder traversal visits a node and then traverses both of its subtrees. Postorder traversal traverses both subtrees of a node, then visits the node.

## Tree Search

### Breadth-First Search

ThePrimeagen discusses using a queue data structure to perform a breadth-first search and the running time.### Implement Breadth-First Search

ThePrimeagen walks through implementing a breadth-first search on a binary tree by pushing into a queue instead of recursing. A brief discussion regarding student preferences between breadth-first and depth-first searches is also covered in this segment.### Search Practice

ThePrimeagen walks through an interview question example of comparing the contents and shape. Depth-first search preserves tree shape, while breadth-first search does not.### Implement Binary Tree Comparison

ThePrimeagen walks through implementing breadth-first and depth-first searching to compare two binary trees and testing the resulting functions using the kata machine.### Depth-First: Find

ThePrimeagen discusses quick finding using a binary search tree. Students' questions regarding possible use cases and if the right side can be greater than the initial node or if it has to be equal are also covered in this segment.### Depth-First: Insert

ThePrimeagen writes out pseudo-code to demonstrate insertion in a binary tree and demonstrates what to do in a null case.### Depth-First: Delete

ThePrimeagen discusses deletion cases in a depth-first binary tree, including, no child and one child while smallest on the large side and largest on the small side can be reduced to no child and one child deletion.### Binary Search Tree Q&A

ThePrimeagen answers student questions regarding if the tree will be balanced after insertion, AVL compared to red black, if removing the same node can result in different trees, and if there are other ways to make trees.### Implement Depth-First Search

ThePrimeagen walks through implementing and testing a depth-first binary search.

## Heap

### Heap

ThePrimeagen discusses the heap data structure as a binary tree where every child and grandchild is smaller (MinHeap) or larger than (MaxHeap) the current node. Student questions regarding if this is considered a doubly linked list and if this is implemented in an array are also covered in this segment.### Implementing Heap

ThePrimeagen walks through implementing and testing a MinHeap data structure using a JavaScript array in the kata machine. The insert and delete methods are implemented in this segment.### Tries

ThePrimeagen discusses visualizing tries as autocomplete, demonstrates the structure of a trie tree with pseudo code, and implements a trie tree in the kata machine. Insertion and deletion in a trie tree are also covered in this segment.

## Graphs

### Graphs Overview

ThePrimeagen discusses an overview of graphs as a series of nodes with connections and terminology related to graphs. Vocabulary covered in this segment includes cycle, acyclic, connected, directed, undirected, weighted, dag, node, and edge.### Searching an Adjacency Matrix

ThePrimeagen demonstrates representing graphs in an adjacency matrix. Breadth-first and depth-first searches still exist on a graph, and are virtually the same as on a tree.### Implementing BFS on Adjacency Matrix

ThePrimeagen walks through implementing and testing a breadth-first search on an adjacency matrix using the kata machine. An adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph.### Implement DFS on Adjacency List

ThePrimeagen walks through implementing and testing a depth-first search on an adjacency list using the kata machine. An Adjacency list is an array consisting of the address of all the linked lists.### Dijkstra's Shortest Path

ThePrimeagen discusses Dijkstra's shortest path, what it is, where it's used, and demonstrates some variations of it. Dijkstra's shortest path is an algorithm that finds the shortest paths between nodes in a graph.### Implement Dijkstra's Shortest Path

ThePrimeagen walks through implementing and testing a version of Dijkstra's shortest path in the kata machine.### Dijkstra's Shortest Path Run Time

ThePrimeagen discusses the running time of Dijkstra's shortest path by walking through what happens behind the scenes in pseudo-code. A student's question regarding if there are a lot of graph questions in interviews is also covered in this segment.

## Maps & LRU

### Maps

ThePrimeagen discusses an overview of map terminology, including load factor, key-value, and collision.### LRU Cache

ThePrimeagen discusses a least recently used cache data structure that evicts the least recently used item. An LRU cache is a combination of map and linked list data structures.### LRU Cache Setup

ThePrimeagen walks through setting up a pseudocode outline for the LRU cache data structure.### Implementing an LRU Cache

ThePrimeagen walks through implementing and testing an LRU cache in the kata machine.