Algorithems

Binary Search Tree (BST)

// through iteration - my initial attempt
class Tree {
  constructor() {
    this.root = null;
  }
  
  add(value) {
    const newNode = new Node(value);
    if (!this.root) this.root = newNode;
    else{
      let currentNode = this.root;
      let loop = true;
      while (loop) {
        if (value <= currentNode.value) {
          if (currentNode.left) currentNode = currentNode.left;
          else { 
            currentNode.left = newNode;
            loop = false;
          }
        } else {
          if (currentNode.right) currentNode = currentNode.right;
          else { 
            currentNode.right = newNode;
            loop = false;
          }
        }
        
      }    
    }
    
  }
  toObject() {
    return this.root;
  }
}

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
 
}

// better version

class Tree {
  constructor() {
    this.root = null;
  }
  
  add(value) {
    const newNode = new Node(value);
    if (!this.root) this.root = newNode;
    else{
      let currentNode = this.root;
      while (true) {
        if (value <= currentNode.value) {
          if (currentNode.left) currentNode = currentNode.left;
          else { 
            currentNode.left = newNode;
            break;
          }
        } else {
          if (currentNode.right) currentNode = currentNode.right;
          else { 
            currentNode.right = newNode;
            break;
          }
        }
        
      }    
    }
    
  }
  toObject() {
    return this.root;
  }
}

class Node {
  constructor(value, left=null, right=null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
 
}

Bubble sort

const bubbleSort = nums => {
  do {
     var swapped = false;
     for (let i = 0, l = nums.length; i < l; i++) {
       if (nums[i] >= nums[i+1]) {
         const temp = nums[i];
         nums[i] = nums[i+1];
         nums[i+1] = temp;
         swapped = true;
       }
     }
    
  } while(swapped);
  console.log(nums);
}

bubbleSort([5, 7,6,4, 20, 1, 2])

Factorial_recurse

const factorial = num => {
  if (num < 2) return 1;
  return num * factorial(num - 1);
}

factorial(5);

Fibonacchi_recurse

const fib = num => {
  if (num <= 2) return 1;
  return fib(num - 1) + fib(num - 2);
}

fib(7);

Find_median_number_in_two_sorted_arrays

function merge(arr1, arr2) {
  const results = [];
  const totalMedian = Math.round ( (arr1.length + arr2.length)/2 ); 
  console.log('totalMedian', totalMedian);
  while (results.length < totalMedian) {
    if (arr1[0] <= arr2[0]) results.push( arr1.shift() ); 
    else results.push( arr2.shift() );
  }
  console.log('results', results);
  return results[totalMedian-1];
}

merge( [1, 7, 8],  [2, 5, 6, 9] );

insertion-sort

const insertSort = nums => {
  for(let i = 1, l = nums.length; i < l; i++) {
    for(let j = 0, l = nums.length; j < l; j++) {
      if (nums[i] <= nums[j]) {
        const spliced = nums.splice(i, 1);
        nums.splice(j, 0, spliced[0]);
      }
    }
  }
  return nums;
}; 

insertSort([4,1,0, 10, 7, 2, 1])

Linked List

// not very elegant solution

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  
  push(value) {
    const newNode = new Node(value);
    if (this.length < 1) { 
      this.head = newNode;
      this.tail = newNode;
    }
    else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
  }
  
  pop() {
    let i = 0, pTail, deleted = this.tail;
    pTail = this.head;
    while (i <= this.length - 3) {
      pTail = pTail.next; 
      i++;
    }
    pTail.next = null;
    this.length--;
    this.tail = pTail;
    return deleted.value;
  }
  get(index) {
    let i = 0, pTail;
    pTail = this.head;
    while (i < index) {
      pTail = pTail.next;
      i++;
    }
    return pTail.value;
  }
  delete(index) {
    let i = 0, pTail, previous, deleted;
    pTail = this.head;
    if (index === 0) { 
      deleted = pTail;
      this.head = pTail.next;
    } else if (index === 1) {
      previous = this.head;
      pTail = previous.next;
      deleted = pTail;
      previous.next = pTail.next;
    } else {
      while (i < index - 1) {
        pTail = pTail.next;
        i++;
      }
      previous = pTail;
      deleted = pTail.next;
      previous.next = deleted.next;
      
    }
     
      this.length --;
      return deleted;
  }
}

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

// sophisticated version

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  
  push(value) {
    const newNode = new Node(value);
    if (!this.head) { 
      this.head = newNode;
      this.tail = newNode;
    }
    else this.tail.next = newNode;
    this.tail = newNode;
    this.length++;
  }
  
  pop() {
    return this.delete(this.length-1);
  }
  get(index) {
    const node = this._find(index, this._testIndex);
    if (!node) return null;
    return node.value;
  }
  delete(index) {
    if (index === 0) {
      const head = this.head;
      if (head) this.head = head.next;
      else this.tail = this.head = null;
      this.length --;
      return head.value;
    }
    const node = this._find(index-1, this._testIndex);
    if (!node.next) return null;
    const deleted = node.next;
    node.next = deleted.next;
    if(!node.next) this.tail = node;
    if (node.next && !node.next.next) this.tail = node.next; // handles tail if deleted is the last one
    this.length --;
    return deleted.value;
  }
  _find(value, test=this._test) {
    let current = this.head,
        i = 0;
    while(current) {
      if (test(value, current.value, i, current)) {
        return current;
      }
      current = current.next;
      i++;
    }
    return null // signify not finding the value in this list
  }
  _test(a, b) {
    return a === b;
  }
  _testIndex(search, __, i) {
    return search === i;
  }
}

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

Merge sort

const mergeSort = nums => {
  if (nums.length < 2) {
    return nums;
  }
  const length = nums.length;
  const middle = Math.floor(length / 2);
  const left = nums.slice(0, middle);
  const right = nums.slice(middle, length);
  
  return merge(mergeSort(left), mergeSort(right));
};

const merge = (left, right) => {
  
  const results = [];
  
  while (left.length && right.length) {
    if (left[0] <= right[0]) results.push(left.shift());
    else results.push(right.shift()); 
    
  }
  
  return [...results, ...left, ...right];
};

QuickSort

const quickSort = arr => {
  const lessArr = [];
  const greaterArr = [];
  let pivot = arr[arr.length - 1];
  
  // base case
  if (arr.length <= 1) return arr;
  
  for (let i = 0, l = arr.length-1; i < l; i++) {
    if (arr[i] < pivot) lessArr.push( arr[i] );
    else greaterArr.push( arr[i] );
  }
  return [...quickSort(lessArr), pivot, ...quickSort(greaterArr)]
  
}