The Last Algorithms Course You'll Need
Table of Contents
IntroductionThePrimeagen introduces the course by discussing some personal background with algorithms, types of algorithms that will be covered, and suggestions for retaining the information presented in this course. Reasons to learn algorithms, why this course uses TypeScript, and ThePrimeagen's social media links are also provided in this lesson.
Big O Time ComplexityThePrimeagen 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 StructureThePrimeagen 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.
Linear Search & Kata SetupThePrimeagen 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 AlgorithmThePrimeagen 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 SearchThePrimeagen walks through creating and implementing a pseudo-code version of a Binary search algorithm.
Implementing Binary SearchThePrimeagen 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 ProblemThePrimeagen 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 BallsThePrimeagen 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.
Bubble SortThePrimeagen 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 SortThePrimeagen 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 StructuresThePrimeagen 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 ComplexityThePrimeagen discusses the time and space complexity of linked lists. A student's question regarding the insertion of F is also covered in this segment.
QueueThePrimeagen 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 QueueThePrimeagen walks through implementing and testing the queue algorithm.
Queue Q&AThePrimeagen 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.
StackThePrimeagen 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 StackThePrimeagen walks through implementing and testing a stack, including push, pop, and peek.
Arrays vs Linked ListThePrimeagen 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.
ArrayListThePrimeagen demonstrates the ability to write list operations such as get, push, and pop on arrays using ArrayList.
ArrayBufferThePrimeagen discusses an ArrayBuffer object which is used to represent a generic, fixed-length raw binary data buffer.
Data Structures Q&AThePrimegen 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.
RecursionThePrimeagen 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 CaseThePrimeagen walks through an example of pathfinding using a base case by implementing and testing the MazeSolver example in the kata machine.
Path Finding: Recursive CaseThePrimeagen walks through the MazeSolver example of pathfinding using the recursive case.
Recursion Q&AThePrimeagen 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.
QuickSort AlgorithmThePrimeagen 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 QuickSortThePrimeagen 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, & appendThePrimeagen walks through implementing a doubly linked list, including prepend, insertAt, and append.
Linked List: remove, get, & removeAtThePrimeagen walks through implementing the second half of a doubly linked list, including remove, get, and removeAt.
Linked List Q&AThePrimeagen 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 ListThePrimeagen 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 OverviewThePrimeagen 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 TraversalsThePrimeagen discusses and demonstrates, via whiteboarding, visiting nodes using three types of traversals preorder, inorder, and postorder.
Implement Tree TraversalThePrimeagen 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.
Breadth-First SearchThePrimeagen discusses using a queue data structure to perform a breadth-first search and the running time.
Implement Breadth-First SearchThePrimeagen 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 PracticeThePrimeagen 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 ComparisonThePrimeagen 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: FindThePrimeagen 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: InsertThePrimeagen writes out pseudo-code to demonstrate insertion in a binary tree and demonstrates what to do in a null case.
Depth-First: DeleteThePrimeagen 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&AThePrimeagen 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 SearchThePrimeagen walks through implementing and testing a depth-first binary search.
HeapThePrimeagen 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.
TriesThePrimeagen 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 OverviewThePrimeagen 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 MatrixThePrimeagen 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 MatrixThePrimeagen 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 ListThePrimeagen 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 PathThePrimeagen 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 PathThePrimeagen walks through implementing and testing a version of Dijkstra's shortest path in the kata machine.
Dijkstra's Shortest Path Run TimeThePrimeagen 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
MapsThePrimeagen discusses an overview of map terminology, including load factor, key-value, and collision.
LRU CacheThePrimeagen 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 SetupThePrimeagen walks through setting up a pseudocode outline for the LRU cache data structure.
Implementing an LRU CacheThePrimeagen walks through implementing and testing an LRU cache in the kata machine.