One of the many steps you need to learn and master in software development, is understanding algorithms, doing so will take your craft to the next level. Stuck in tutorial hell, probably getting a grasp of theory is what you need to move past muscle memory.
On that note, if you find these topics interesting, I would HIGHLY recommend, polishing up your math skills. Remove the ego and just observe the functions and methods in Algebra, Arithmetic, Calculus. For me I had to restart at fractions, re-learning basic im/proper fractions and conversions are just basic methods we can compare with writing an API. If you break it down input > output, your brain begins to recognize the rules of algebra, calculus, any system with own mechanics .
Another note is always learn from different perspectives, Traversy Media, Colt Steele are among some who I spent hours watching and taking notes. For books I highly recommend Think like a programmer to start, or Grokking Algorithms is another great choice for starters. If you’re more on the intermediate to advance then Algorithms 4/3 Edition by Robert Sedgewick Kevin Wayne is a great reference.
These don’t make sense, write it down on paper. Still lost? Break it down till you understand the fundamentals. Remember confusion is your brain learning.
Basic Data Structures
Singly linked list
Singly linked lists are like a conga line at a party, everybody's got a person in front of 'em, but they're all alone in the back. Each element points to the next, but never looks back. They're perfect for situations where you want to efficiently insert or delete elements, but keep in mind that searching takes O(n) time, so it's like asking each person in the conga line for their name one by one. Real smooth.
SinglyLinkedList.tscode block is ts
class ListNode {
value: number;
next: ListNode | null;
constructor(value: number) {
this.value = value;
this.next = null;
}
}
class SinglyLinkedList {
head: ListNode | null;
constructor() {
this.head = null;
}
append(value: number): void {
const newNode = new ListNode(value);
if (!this.head) {
this.head = newNode;
return;
}
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
}
}
export { ListNode, SinglyLinkedList };
Doubly linked list
Doubly linked lists are like two people dancing tango, they always know who's in front and who's behind. In this case, each element has a pointer to both the next and previous elements. Use them when you need to traverse in both directions, but remember you're now dealing with twice as many pointers. Searching still takes O(n) time, so it's not much better than the conga line.
DoublyLinkedList.tscode block is ts
class DoublyListNode {
value: number;
next: DoublyListNode | null;
prev: DoublyListNode | null;
constructor(value: number) {
this.value = value;
this.next = null;
this.prev = null;
}
}
class DoublyLinkedList {
head: DoublyListNode | null;
constructor() {
this.head = null;
}
append(value: number): void {
const newNode = new DoublyListNode(value);
if (!this.head) {
this.head = newNode;
return;
}
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
newNode.prev = current;
}
}
export { DoublyListNode, DoublyLinkedList };
Stacks / Queues
Stacks are like a stack of pancakes, you always eat the one on top and then work your way down. These LIFO (Last In, First Out) structures are great for managing tasks that depend on previous tasks, like navigating back in your web browser. Adding and removing elements takes O(1) time, which is so quick you'll feel like you just slammed a shot of espresso.
Stacks.tscode block is ts
class Stack {
private storage: number[];
constructor() {
this.storage = [];
}
push(value: number): void {
this.storage.push(value);
}
pop(): number | undefined {
return this.storage.pop();
}
peek(): number | undefined {
return this.storage[this.storage.length - 1];
}
isEmpty(): boolean {
return this.storage.length === 0;
}
}
export { Stack };
Queues are like waiting in line for a roller coaster, the first one in is the first one out (FIFO). They're perfect for managing tasks that need to be processed in order, like tasks in a printer queue. Adding and removing elements takes O(1) time, so you can get on with your life instead of waiting in line like a chump.
Queue.tscode block is ts
class Queue {
private storage: number[];
constructor() {
this.storage = [];
}
enqueue(value: number): void {
this.storage.push(value);
}
dequeue(): number | undefined {
return this.storage.shift();
}
peek(): number | undefined {
return this.storage[0];
}
isEmpty(): boolean {
return this.storage.length === 0;
}
}
export { Queue };
Graph
Graphs are like a spiderweb of connections where each node represents a person at a party, and the edges are the gossip they share. With no index, just pointers and weights, graphs are great for representing complex relationships between data points. But watch out, because searching can take anywhere from O(1) to O(n) time, depending on how juicy the gossip is.
Graph.tscode block is ts
class GraphNode {
value: number;
neighbors: GraphNode[];
constructor(value: number) {
this.value = value;
this.neighbors = [];
}
}
class Graph {
nodes: GraphNode[];
constructor() {
this.nodes = [];
}
addNode(value: number): void {
this.nodes.push(new GraphNode(value));
}
addEdge(value1: number, value2: number): void {
const node1 = this.nodes.find(node => node.value === value1);
const node2 = this.nodes.find(node => node.value === value2);
if (node1 && node2) {
node1.neighbors.push(node2);
node2.neighbors.push(node1);
}
}
}
export { GraphNode, Graph };
Binary Search Tree
Binary search trees (BSTs) are like well-organized family trees where each person knows their parent and children. Each node has a value, and all nodes to the left have lower values, while all nodes to the right have higher values. BSTs are great for searching, inserting, and deleting in O(log n) time, making them the efficient choice for a balanced life, unlike your cousin Jerry.
BinarySearchTree.tscode block is ts
class BSTNode {
value: number;
left: BSTNode | null;
right: BSTNode | null;
constructor(value: number) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
root: BSTNode | null;
constructor() {
this.root = null;
}
insert(value: number): void {
const newNode = new BSTNode(value);
if (!this.root) {
this.root = newNode;
return;
}
let current = this.root;
while (true) {
if (value < current.value) {
if (!current.left) {
current.left = newNode;
break;
}
current = current.left;
} else {
if (!current.right) {
current.right = newNode;
break;
}
current = current.right;
}
}
}
}
export { BSTNode, BinarySearchTree };
Hash Tables
Hash tables are like a magical filing cabinet that instantly knows where to store and retrieve data. Using a unique key, it hashes the data to store and access values in constant O(1) time. But, like a cluttered drawer, collisions can happen, and resolving them might slow things down a bit.
HashTable.tscode block is ts
class HashTable {
private storage: { [key: string]: number };
constructor() {
this.storage = {};
}
hash(key: string): number {
return key.split('').reduce((acc, char) => acc + char.charCodeAt(0), 0);
}
set(key: string, value: number): void {
const hashedKey = this.hash(key).toString();
this.storage[hashedKey] = value;
}
get(key: string): number | undefined {
const hashedKey = this.hash(key).toString();
return this.storage[hashedKey];
}
}
export { HashTable };
Basic Algorithms
Sorted
Merge sort
Merge sort is like sorting a deck of cards by dividing them into smaller piles, then merging the piles back together in the right order. With a time complexity of O(n log n), it's fast and efficient, but it's got a memory usage that makes your over-protective mother look like an amateur.
MergeSort.tscode block is ts
function merge(arr1: number[], arr2: number[]): number[] {
const result: number[] = [];
let i = 0;
let j = 0;
while (i < arr1.length && j < arr2.length) {
if (arr1[i] < arr2[j]) {
result.push(arr1[i]);
i++;
} else {
result.push(arr2[j]);
j++;
}
}
while (i < arr1.length) {
result.push(arr1[i]);
i++;
}
while (j < arr2.length) {
result.push(arr2[j]);
j++;
}
return result;
}
function mergeSort(arr: number[]): number[] {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
export { mergeSort };
Quick Sort
Quick sort is like throwing a bunch of numbers into a hat, picking a random number as the pivot, and then tossing the smaller numbers to the left and larger numbers to the right. It's a fast sorting algorithm with an average time complexity of O(n log n), but in the worst case, it could take O(n^2) time, which is as unpredictable as your drunk uncle at a family reunion.
QuickSort.tscode block is ts
function partition(arr: number[], left: number, right: number): number {
const pivot = arr[Math.floor((left + right) / 2)];
let i = left;
let j = right;
while (i <= j) {
while (arr[i] < pivot) i++;
while (arr[j] > pivot) j--;
if (i <= j) {
[arr[i],arr[j]] = [arr[j], arr[i]];
i++;
j--;
}
}
return i;
}
function quickSort(arr: number[], left: number = 0, right: number = arr.length - 1): number[] {
if (arr.length > 1) {
const index = partition(arr, left, right);
if (left < index - 1) {
quickSort(arr, left, index - 1);
}
if (index < right) {
quickSort(arr, index, right);
}
}
return arr;
}
export { quickSort };
Priority queues
Priority queues are like VIP lines at a club, where the most important person always gets in first. These fancy queues assign a priority to each element, and higher priority elements are served before lower priority ones. Adding elements takes O(log n) time, but removing the highest priority element takes O(1) time, making you feel like a rockstar walking past the bouncer.
PriorityQueue.tscode block is ts
class PriorityQueue {
private storage: number[];
constructor() {
this.storage = [];
}
enqueue(value: number): void {
if (this.isEmpty()) {
this.storage.push(value);
} else {
let added = false;
for (let i = 0; i < this.storage.length; i++) {
if (value < this.storage[i]) {
this.storage.splice(i, 0, value);
added = true;
break;
}
}
if (!added) {
this.storage.push(value);
}
}
}
dequeue(): number | undefined {
return this.storage.shift();
}
peek(): number | undefined {
return this.storage[0];
}
isEmpty(): boolean {
return this.storage.length === 0;
}
}
export { PriorityQueue };
Radix sort
Radix sort is like organizing a library of books by sorting them digit by digit, starting from the least significant digit. It's a non-comparative sorting algorithm that takes O(nk) time, where n is the number of elements and k is the number of digits. It's super fast for sorting integers and strings, but don't try it on floating-point numbers unless you want to dive into a never-ending rabbit hole.
RadixSort.tscode block is ts
function getDigit(num: number, place: number): number {
return Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
}
function digitCount(num: number): number {
if (num === 0) return 1;
return Math.floor(Math.log10(Math.abs(num))) + 1;
}
function maxDigits(arr: number[]): number {
let max = 0;
for (const num of arr) {
max = Math.max(max, digitCount(num));
}
return max;
}
function radixSort(arr: number[]): number[] {
const max = maxDigits(arr);
for (let k = 0; k < max; k++) {
const buckets: number[][] = Array.from({ length: 10 }, () => []);
for (const num of arr) {
const digit = getDigit(num, k);
buckets[digit].push(num);
}
arr = ([] as number[]).concat(...buckets);
}
return arr;
}
export { radixSort };
Searching
Binary Search
Binary search is like playing a "higher or lower" guessing game. It works on a sorted array and keeps dividing the search interval in half until it finds the target value. With a time complexity of O(log n), it's a real quick way to find what you're looking for, unless, of course, you're looking for your misplaced keys – then you're on your own.
BinarySearch.tscode block is ts
function binarySearch(arr: number[], target: number): number {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
const midValue = arr[mid];
if (midValue === target) {
return mid;
} else if (midValue < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
export { binarySearch };
Remember, each data structure and algorithm has its strengths and weaknesses, and it's crucial to pick the right one for your specific use case. Otherwise, you might end up like that guy who brings a spoon to a knife fight – completely unprepared and wondering why everything is taking so long.