zhorton34 / data-structures-algorithms-101 Goto Github PK

Arrays, Hash Tables, Linked Lists, Binary Trees, Graphs, Quick Sort, Merge Sort, Bubble Sort, Insertion Sort, Selection Sort, Priority Queues, Binary Heaps, Breadth First Search, Depth First Search

JavaScript 100.00%

data-structures-algorithms-101's Introduction

Hi! My name's Zak & I'm a dev who's worked on startups, fast-growth series D, Fortune 500, and FAANG (Amazon dev) codebases.

Develops software across industries, teams, & has experience at just about every scale in which the software life cycle is utilized
Self-taught college dropout with a love for sharing the knowledge
All-in on Web 3

Sr. Dev at Anaconda Inc.building out the world's most popular data science platform alongside a thriving open source community that empowers students, professionals, & enterprises alike to innovate in groundbreaking real-world business impacting ways thru the power of emerging Web 3 technologies like that of Machine Learning/Artificial Intelligence solutions.

Clean Code Studio

☕️ Code Tips
☕️ Career Advice
☕️ Developer Memes

Self-Taught Dev Looking to make it a full-time career? Feel free to reach out!

I'm always down to hop on a call with any #codenewbies out there looking for some advice from a fellow self-taught engineer who's been through that journey and made it to some upper levels of tech without a degree. As a 28-day college dropout I can relate to how the information overload can knock you off course on your journey and make it feel like a daunting task to become a full-time dev - but I assure you, No degree is needed to become a full-time dev 😉

If I'm able to help others to better define that path towards becoming a full-time software dev, then I'd love to do so - feel free to reach out via anyone of my socials. I'm always down to hop on a call with #codenewbie's looking to break into the dev career as well as those experienced #webdev's looking to break into the #bigtech dev career. Can't make it an easy journey, but hopefully - if you give me the time - I can at the very least help to simplify the path so you're re-assured that your'e headed in the right direction within your career path.

data-structures-algorithms-101's People

Contributors

Stargazers

Watchers

Forkers

clean-code-studio rickymelida

data-structures-algorithms-101's Issues

Priority Queue DataStructure

DoublyLinkedList

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

  setNextNode(node) {
    if (node instanceof Node || node === null) {
      this.next = node;
    } else {
      throw new Error('Next node must be a member of the Node class')
    }
  }

  setPreviousNode(node) {
    if (node instanceof Node || node === null) {
      this.previous = node;
    } else {
      throw new Error('Previous node must be a member of the Node class')
    }
  }

  getNextNode() {
    return this.next;
  }

  getPreviousNode() {
    return this.previous;
  }
}

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

  addToHead(data) {
    const newHead = new Node(data);
    const currentHead = this.head;
    if (currentHead) {
      currentHead.setPreviousNode(newHead);
      newHead.setNextNode(currentHead);
    }
    this.head = newHead;
    if (!this.tail) {
      this.tail = newHead;
    }
  }

  addToTail(data) {
    const newTail = new Node(data);
    const currentTail = this.tail;
    if (currentTail) {
      currentTail.setNextNode(newTail);
      newTail.setPreviousNode(currentTail);
    }
    this.tail = newTail;
    if (!this.head) {
      this.head = newTail;
    }
  }

  removeHead() {
    const removedHead = this.head;
    if (!removedHead) {
      return;
    }
    this.head = removedHead.getNextNode();
    if (this.head) {
      this.head.setPreviousNode(null);
    }
    if (removedHead === this.tail) {
      this.removeTail();
    }
    return removedHead.data;
  }

  removeTail() {
    const removedTail = this.tail;
    if (!removedTail) {
      return;
    }
    this.tail = removedTail.getPreviousNode();
    if (this.tail) {
      this.tail.setNextNode(null);
    }
    if (removedTail === this.head) {
      this.removeHead();
    }
    return removedTail.data;
  }

  removeByData(data) {
    let nodeToRemove;
    let currentNode = this.head;
    while (currentNode !== null) {
      if (currentNode.data === data) {
        nodeToRemove = currentNode;
        break;
      }
      currentNode = currentNode.getNextNode();
    }
    if (!nodeToRemove) {
      return null;
    }
    if (nodeToRemove === this.head) {
      this.removeHead();
    } else if (nodeToRemove === this.tail) {
      this.removeTail();
    } else {
      const nextNode = nodeToRemove.getNextNode();
      const previousNode = nodeToRemove.getPreviousNode();
      nextNode.setPreviousNode(previousNode);
      previousNode.setNextNode(nextNode);
    }
    return nodeToRemove;
  }

  printList() {
    let currentNode = this.head;
    let output = '<head> ';
    while (currentNode !== null) {
      output += currentNode.data + ' ';
      currentNode = currentNode.getNextNode();
    }
    output += '<tail>';
    console.log(output);
  }
}

HashMap

class HashMap {
  constructor(size = 0) {
    this.hashmap = new Array(size)
      .fill(null)
      .map(() => new LinkedList());
  }

  hash(key) {
    let hashCode = 0;
    for (let i = 0; i < key.length; i++) {
      hashCode += hashCode + key.charCodeAt(i);
    }
    return hashCode % this.hashmap.length;
  }

  assign(key, value) {
    const arrayIndex = this.hash(key);
    const linkedList = this.hashmap[arrayIndex];
    console.log(`Storing ${value} at index ${arrayIndex}`);
    if (linkedList.head === null) {
      linkedList.addToHead({ key, value });
      return;
    }
    let current = linkedList.head;
    while (current) {
      if (current.data.key === key) {
        current.data = { key, value };
      }
      if (!current.next) {
        current.next = new Node({ key, value });
        break;
      }
      current = current.next;
    }
  }

  retrieve(key) {
    const arrayIndex = this.hash(key);
    let current = this.hashmap[arrayIndex].head;
    while (current) {
      if (current.data.key === key) {
        console.log(`\nRetrieving ${current.data.value} from index ${arrayIndex}`);
        return current.data.value;
      }
      current = current.next;
    }
    return null;
  }
}

module.exports = HashMap;

Binary Search Tree

class BinarySearchTree
{
   constructor (value, depth = 1) 
   {
      this.value= value
      this.depth = depth      
      this.left = null
      this.right = null
  }

  insert (value) 
  {
     const side = value < this.value? 'left' : 'right'
      
     if (this[side]) this[side].insert(value)
     if (!this[side]) this[side] = new BinaryTree(value, this.depth + 1)
  }

  getNodeByValue (value)
  {
     if (value === this.value) return this

     const side = value < this.value ? 'left' : 'right'

     return this[side] ? this[side].getNodeByValue(value) : null
  }

  /* inOrder Depth First Traversal */
  depthFirstTraversal() 
  {
     if (this.left) this.left.depthFirstTraversal()
     
     console.log(`Depth=${this.depth}, Value=${this.value}`)

     if (this.right) this.right.depthFirstTraversal()    
  }
}

Fix Webpack (Laravel Mix) Alias Paths On Project Build

webpack.mix.js defines aliases for webpack

mix.wbpackConfig({ 
  resolve: { alias: {} }
 })

Aliases aren't being converted to their full path when project is built for distribution (built to the dist/index.js')

Example Case:

LinkedListNode in LinkedList.append method
@see Build file at dist/structures/LinkedList.js line 60 - 62
@see Project file at `src/structures/LinkedList.js' line 47 - 48

MinHeap

class MinHeap 
{
  constructor() 
{
    this.heap = [ null ]
    this.size = 0
  }

  popMin() 
 {
    if (this.size === 0) {
      return null
    }
    console.log(`\n.. Swap ${this.heap[1]} with last element ${this.heap[this.size]}`);
    this.swap(1, this.size);
    const min = this.heap.pop();
    this.size--;
    console.log(`.. Removed ${min} from heap`);
    console.log('..',this.heap);
    this.heapify();
    return min;
  }

  add(value) {
    console.log(`.. adding ${value}`)
    this.heap.push(value)
    this.size++
    this.bubbleUp()
    console.log(`added ${value} to heap`, this.heap)
  }

  bubbleUp() 
  {
    let current = this.size
    while (current > 1 && this.heap[getParent(current)] > this.heap[current]) {
      console.log(`.. swap ${this.heap[current]} with parent ${this.heap[getParent(current)]}`)
      this.swap(current, getParent(current))
      console.log('..', this.heap)
      current = getParent(current)
    }
  }

  heapify() 
 {
    let current = 1
    let leftChild = getLeft(current)
    let rightChild = getRight(current)

    while (this.canSwap(current, leftChild, rightChild)) {
      while (this.canSwap(current, leftChild, rightChild)) {
      if (this.exists(leftChild) && this.exists(rightChild)) {
        if (this.heap[leftChild] < this.heap[rightChild]) {
          this.swap(current, leftChild)
          current = leftChild
        } else {
          this.swap(current, rightChild)
          current = rightChild
        }        
      } else {
        this.swap(current, leftChild)
        current = leftChild
      }
      leftChild = getLeft(current)
      rightChild = getRight(current)
    }
      leftChild = getLeft(current)
      rightChild = getRight(current)
    }
  }

  exists(index) 
 {
    return index <= this.size
  }

  canSwap(current, leftChild, rightChild) 
 {
    // Check that one of the possible swap conditions exists
    return (
      this.exists(leftChild) && this.heap[current] > this.heap[leftChild]
      || this.exists(rightChild) && this.heap[current] > this.heap[rightChild]
    );
  }

  swap(a, b) 
 {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]]
  }
}

Queue

const LinkedList = require("./LinkedList");

class Queue {
  constructor(maxSize = Infinity) {
    this.queue = new LinkedList();
    this.maxSize = maxSize;
    this.size = 0;
  }

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

  hasRoom() {
    return this.size < this.maxSize;
  }

  enqueue(data) {
    if (this.hasRoom()) {
      this.queue.addToTail(data);
      this.size++;
    } else {
      throw new Error("Queue is full!");
    }
  }

  dequeue() {
    if (!this.isEmpty()) {
      const data = this.queue.removeHead();
      this.size--;
      return data;
    } else {
      throw new Error("Queue is empty!");
    }
  }
}

module.exports = Queue;

Stack

class Stack {
  constructor(maxSize = Infinity) {
    this.stack = new LinkedList();
    this.maxSize = maxSize;
    this.size = 0;
  }

  hasRoom() {
    return (this.size < this.maxSize);  
  }
  
  isEmpty() {
    return (this.size === 0);  
  }
  
  push(value) {
    if (this.hasRoom()) {
      this.stack.addToHead(value);
      this.size++;      
    } else {
      throw new Error('Stack is full');
    }
  }

  pop() {
    if (!this.isEmpty()) {
      const value = this.stack.removeHead();
      this.size--;
      return value;
    } else {
      throw new Error('Stack is empty!');
    }
  }

  peek() {
    if (!this.isEmpty()) {
      return this.stack.head.data;
    } else {
      return null;
    }
  }
}

module.exports = Stack;

Graphs

class Edge {
  constructor(start, end, weight = null) {
    this.start = start;
    this.end = end;
    this.weight = weight;
  }
}

class Vertex {
  constructor(data) {
    this.data = data;
    this.edges = [];
  }

  addEdge(vertex, weight) {
    if (vertex instanceof Vertex) {
      this.edges.push(new Edge(this, vertex, weight));
    } else {
      throw new Error('Edge start and end must both be Vertex');
    }
  }

  removeEdge(vertex) {
    this.edges = this.edges.filter(edge => edge.end !== vertex);
  }

  print() {
    const edgeList = this.edges.map(edge =>
        edge.weight !== undefined ? `${edge.end.data} (${edge.weight})` : edge.end.data) || [];

    const output = `${this.data} --> ${edgeList.join(', ')}`;
    console.log(output);
  }
}

class Graph {
  constructor(isWeighted = false, isDirected = false) {
    this.vertices = [];
    this.isWeighted = isWeighted;
    this.isDirected = isDirected;
  }

  addVertex(data) {
    const newVertex = new Vertex(data);
    this.vertices.push(newVertex);

    return newVertex;
  }

  removeVertex(vertex) {
    this.vertices = this.vertices.filter(v => v !== vertex);
  }

  addEdge(vertexOne, vertexTwo, weight) {
    const edgeWeight = this.isWeighted ? weight : null;

    if (vertexOne instanceof Vertex && vertexTwo instanceof Vertex) {
      if (this.isDirected === false) {
        vertexOne.addEdge(vertexTwo, edgeWeight);
      
        vertexTwo.addEdge(vertexOne, edgeWeight);
      } else {
        vertexOne.addEdge(vertexTwo, edgeWeight);
      }
    } else {
      throw new Error('Expected Vertex arguments.');
    }
  }

  removeEdge(vertexOne, vertexTwo) {
    if (vertexOne instanceof Vertex && vertexTwo instanceof Vertex) {
      if (this.isDirected === false) {
        vertexOne.removeEdge(vertexTwo);
      
        vertexTwo.removeEdge(vertexOne);
      } else {
        vertexOne.removeEdge(vertexTwo);
      }

    } else {
      throw new Error('Expected Vertex arguments.');
    }
  }

  print() {
    this.vertices.forEach(vertex => vertex.print());
  }
}

Recursion vs. Iteration (Factorial)

const recursiveFibonacci n => {
  if (n <= 1) return 1
  
  return recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2)
}

const recursiveSum = n => {
  if (n === 1) return 1
  
  if (n > 0) return recursiveSum(n - 1) + 1
}

const recursiveFactorial = n => {
  if (n === 0) return 1
  
  return n * recursiveFactorial(n - 1)
}

/* Would go in a class */
const recursiveNodeFnider = (data, currentNode = this.head) => {
    if (currentNode === null) {
      return null;
    } else if (currentNode.data === data) {
      return currentNode;
    } else {
      return this.findNodeRecursively(data, currentNode.next);
    }
  
}

module.exports = {
  recursiveFibonacci,
  recursiveFactorial,
  recursiveSum,
}

zhorton34 / data-structures-algorithms-101 Goto Github PK

data-structures-algorithms-101's Introduction

data-structures-algorithms-101's People

Contributors

Stargazers

Watchers

Forkers

data-structures-algorithms-101's Issues

Priority Queue DataStructure

DoublyLinkedList

HashMap

Binary Search Tree

Fix Webpack (Laravel Mix) Alias Paths On Project Build

MinHeap

Queue

Stack

Graphs

Recursion vs. Iteration (Factorial)

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent