Data Structures And Algo In JS

[weikee94]

Intro

Defining Pseudo Class

function Building(floors) {
  this.what = "building";
  this.floors = floors;
}

var myHouse = new Building(3);
console.log(myHouse);

function Food(type) {
  this.type = type;
}

Food.prototype.countTypes = function() {
  console.log(`There are ${this.type} in total`);
};

var myLunch = new Food(3);
console.log(myLunch.countTypes());

Class Methods for all instances

Building.prototype.countFloors = function() {
  console.log(`I have ${this.floors}`);
};

[weikee94]

Stack and Queues

Concept: Stacks (LIFO)

• The last item added into the stack (aka pushed onto)
• The first item taken out of the stack (aka popped off)

Interface: Stacks

1. Constructor Function
   Storage

2. Methods
   push(value) // add value to the stack and return size of stack
   pop() // removes value from stack, returns value
   size() // returns size of stack as an integer

var Stack = function() {
  this.storage = "";
};

Stack.prototype.push = function(val) {
  this.storage = this.storage.concat(val);
};

Stack.prototype.pop = function() {
  // slice off the last index
  var removeStr = this.storage.slice(-1);
  // updating the new stack without last item
  this.storage = this.storage.substring(0, this.storage.lastIndexOf(removeStr));
  return removeStr;
};

Stack.prototype.size = function() {
  return this.storage.length;
};

var myWeeklyMenu = new Stack();

myWeeklyMenu.push("RedBeans");

Concept: Queues (FIFO)

• The first item added into the queue (aka enqueued)
• The first item taken out of the queue (aka dequeued)

Interface: Queues

1. Constructor Function
   Storage

2. Methods
   enqueue(value) // add value to the back and return size
   dequeue() // removes value from front, returns value
   size() // returns size of queue as an integer

Exercise Sections (Stack)

1. LIFO - Last in, first out
   Collection of elements with push and pop operations.
   Note that there is a natural order. Elements are removed in the reverse order of their addition.
   DO NOT use an array and the native push/pop method in your implementation. That's too easy, yeah? =P
   Use an object as the underlying data structure.

2. Operations:
   myStack.push(value)
   => count of stack
   add value to collection
   myStack.pop()
   => most recent element added collection
   Remove item so that it is no longer in collection
   myStack.peek()
   => most recent element added collection
   Similiar to pop, but do not remove element from collection
   myStack.count()
   => number of elements in stack\

3. Exercises:
   Modify your stack to take a max capacity and return a string if you try to add an element when there's no more room:
   myStack.push(value)
   => "Max capacity already reached. Remove element before adding a new one."
   Create a contains method to check if a value is in the stack:
   myStack.contains('findme')
   => true/false
   What's the time complexity?
   Create an until method to get the number of pops until you get to a certain value:
   stack values - (first)2-5-7-3-6-9(last)
   myStack.until(7)
   => 4
   What's the time complexity?\

4. Test Case:
   var myStack = new Stack(3);
   console.log(myStack.push('a'), 'should be 1');
   console.log(myStack.push('b'), 'should be 2');
   console.log(myStack.push('c'), 'should be 3');
   console.log(myStack.push('d'), 'should be Max capacity reached');
   console.log(myStack.pop(), 'should be c');
   console.log(myStack.count(), 'should be 2');
   console.log(myStack.peek(), 'should be b');
   console.log(myStack.count(), 'should be 2');\

var Stack = function(numberOfSize) {
  this.collection = {};
  this.count = 0;
  this.numberOfSize = numberOfSize;
};

Stack.prototype.push = function(value) {
  if (this.count < this.numberOfSize) {
    this.collection[this.count++] = value;
    return this.count;
  }
  return "Max capacity already reached. Remove element before adding a new one.";
};

Stack.prototype.pop = function() {
  // my method
  // delete this.collection[Object.keys(this.collection).length];
  // answer
  var value = this.collection[--this.count];
  delete this.collection[this.count];
  return value;
};

Stack.prototype.peek = function() {
  return this.collection[this.count - 1];
};

Stack.prototype.total = function() {
  return this.count;
};

Stack.prototype.contains = function(val) {
  for (let i = 0; i < this.count; i++) {
    if (this.collection[i] === val) {
      return true;
    }
  }
  return false;
};

Stack.prototype.until = function(val) {
  for (let i = this.count, j = 0; i >= 0; i--) {
    if (this.collection[i] === val) {
      return j;
    }
    j++;
  }
  return false;
};

var myStack = new Stack(3);
console.log(myStack.push("a"), "should be 1");
console.log(myStack.push("b"), "should be 2");
console.log(myStack.push("c"), "should be 3");
console.log(myStack.push("d"), "should be Max capacity reached");
console.log(myStack.pop(), "should be c");
console.log(myStack.total(), "should be 2");
console.log(myStack.peek(), "should be b");
console.log(myStack.total(), "should be 2");
console.log(myStack.contains("a"));

var myStack2 = new Stack(10);
console.log(myStack2.push(2));
console.log(myStack2.push(5));
console.log(myStack2.push(7));
console.log(myStack2.push(3));
console.log(myStack2.push(6));
console.log(myStack2.push(9));
console.log(myStack2.until(2));

5. Exercises (MinStack todo)
   Implement a MinStack that has a min method which will return the minimum value in the stack in constant time.

[weikee94]

Recursion

Recursion Recipe

• Identify base case(s)
• Identify recursive case(s)
• Return where appropriate
• Write procedures for each case that bring you closer to the base case(s)

var callMyself = function () {
    if() {
        // base case
        return;
    } else {
        // recursive case
        callMyself;
    }

    return;
}

Example

var loopNTimes = function(n) {
  console.log("n is: ", n);
  if (n <= 1) {
    return "hit 1";
  }
  return loopNTimes(n - 1);
};
loopNTimes(4);

Factorial

• 3! = 321

var factorialRecursion = function(n) {
  if (n === 1) {
    return 1;
  } else {
    return n * factorialRecursion(n - 1);
  }
};

factorialRecursion(3);

Common pattern

• wrapper function and passing memos/accumulators

Exercises

• 1. Write a function that loops through the numbers n down to 0. If you havent done so try using a while loop to do this.

var countToZero = function(n) {
  while (n > 0) {
    n--;
  }
};

• 2. Looping just like above except using recursion.

var countToZeroRecursion = function(n) {
  if (n === 0) {
    return "done";
  } else {
    console.log(n);
    return countToZeroRecursion(n - 1);
  }
};

• 3. Write a function 'exponent' that takes two arguments base, and expo, uses a while loop to return the exponenet value of the base.

var exponent = function(baseA, expoB) {
  var returnValue = 1;
  while (expoB >= 1) {
    returnValue = returnValue * baseA;
    expoB--;
  }
  return returnValue;
};
exponent(3, 2);

• 4. Write a function 'RecursiveExponent' that takes two arguments base, and expo, recursively returns exponent value of the base.

var recursiveExponent = function(baseA, expoB) {
  var result = 1;
  if (expoB >= 1) {
    result = baseA * recursiveExponent(baseA, expoB - 1);
  }
  return result;
};

• 5. Write a function 'recursiveMultiplier' that takes two arguments, 'arr and num', and multiplies each arr value by num and returns an array of the values.

var recursiveMultiplier = function(arr, num) {
  // [1,2,3], 3
  // multiplies 3
  // output is [3,6,9]
};

• 6. Write a function 'recursiveReverse' that takes an array and uses recursion to return its contents in reverse

var recursiveReverse = function(arr) {
  // [1,2,3]
  // output => [3,2,1]
};

[weikee94]

Sorting

Bubble

• Sorting Function
• bubbleSort(list) => a sorted list
• loops through list
• compares adjacent elements
• swaps higher item towards the end

Example (Bubble)

• Iterate over array, comparing adjacent items and swap if in incorrect order. Largest elements bubble to the end of the array.
• Implement bubble sort and identify time complexity

var bubbleSort = function(arr) {
  let newArr = [];
  for (let i = 0; i < arr.length; i++) {}
  return newArr;
};

bubbleSort([1, 8, 7, 2, 4, 5]);

Selection

• Selects the smallest element in an array, pushed it into a new array
• [1,5,2] => [1,2,5] (loop through the array and select, push)
• Selection Sort (in place), selects the largest element in an array, swaps it to the end of the array
• [1,5,2] => [1,2,5] (select biggest which is 5 and swap to the end of the array which is 2)

Insertion

• Selects the first element in array, pushed it into a new array. As each new element is added, insert the new element in the correct order.
• Insertion Sort(in place), selects the first element in an array, considers that our sorted list of size 1. As each new element is added, insert the new element in the correct order by swapping in place.

Divide and Conquer

• recursive calls to a subset of the problem
• steps for divide and conquer
• 0 recognize base case
• 1 divide: break down during each call
• 2 conquer: do work on each subset
• 3 combine solutions

Merge Sort

• concept: merge take two sorted lists and merges them into 1 sorted list

Merge Pseudocode

// 1
merge(L,R)
Rpr = 0
Lpr = 0

Output array = []
Loop until L.ln === Lpr and R.ln === Rpr
  if L[Lpr] is greater than R[Rpr]
    Push R[Rpr] to Output array
    increment Rpr
  else
    Push L[Lpr] to Output array
    increment Lpr

// 2
mergeSort(list)
  base case: if list.length < 2, return
  break the list into halves L & R
  Lsorted = mergeSort(L)
  Rsorted = mergeSort(R)
  return merge(Lsorted, Rsorted)

// 3
mergeSort(list)
  initialize n to the length of the list
  base case if n < 2, just return
  initialize mid to n/2
  left = left slice of array to mid - 1
  right = right slice of array mid to n - 1
  mergeSort(left)
  mergeSort(right)

  merge(left, right)

Concept: Merge Sort

• step 1: divide input array into 'n' single element subarrays
• step 2: repeatedly merge subarrays and sort on each merge

Time Complexity for Merge Sort

• mergeSort(left) n/2
• mergeSort(right) n/2
• merge(left, right) n
• time complexity = n + 2(n/2) = O(n*logn)

Qucik Sort

• Select pivot and rearrange all the elements that are greater than, to the right and all the elements that less than or equal to on the left.
• Uses divide conquer and choose a pivot point in a collection of elements. It partitions the collection around the pivot, so that element smaller than the pivot are moved before it, and element larger than the pivot are moved after it.
• Step 1: pick an element to act as pivot point in the array
• Step 2: Partition the array by reorganizing elements
• Step 3: Recursively apply steps 1 and 2 to subarrays on either side of the pivot
• Partition: pivot location which is the pointer that keeps track of where the list is less than on the left and greater than our pivot point on the right.

Pseudocode Quick Sort

partition(arr, first, last)
  pivotLoc = first
  pivot = arr[last]
  loop from first to last
    compare pivot to arr[pivotLoc]
    if(pivot > arr[pivotLoc])
      increment pivotLoc
    else
      swap arr[pivotLoc] with pivot
      swap pivot with arr[arr.ln-2] // maybe we need to tack this somewhere

[weikee94]

Trees

Trees

• Methods: insert, search, min/max, remove
• insert(key): this inserts a new key in the tree
• search(key): this searches for the key in the tree and returns true if exists and returns false if the node doesn't
• min/max: this returns the min or max value/key in the tree
• remove(key): this removes the key from the tree

Linked List

• A linked list is a tree structure with only one child per node.
• Each node in the list contains
  • stored data (a node value)
  • stored reference (a link to the next item in the list)
• Methods: addToTail(val) //adds node to tail, remove(node) // removes node from list and returns it

Pseudocode: Linked List

Pseudocode: Tree

[weikee94]

Binary Trees

Binary Tree

• Each node can have a max of 2 children
• Each node is comparable
• Each node's Left subtree < parent value
• Right subtree > parent value

Pseudocode Binary Tree

// constructor
    // value
    // left
    // right

// methods
    // insert
        // if value < current
            // if(left) go left
            // else insert
        // else (value > current)
            // if(right) go right
            // else insert
============
bst = BST(11);
bst.insert(15);
bst.insert(7);
bst.insert(5);
bst.insert(17);

    // contains (value) => true/false
        // if(current value === value)
            // return true;
        // else if (value < current)
            // go left (contains)
        // else if (value > current)
            // go right (contains)
        // else
            // return false;

In-order, Pre-order, Post-order

// In Order Traversal
    // first go all the way to the left
    // then parent
    // then right
    // then parent parent

// Pre Order Traversal (Self, Left, Right)
    // first go all the way to the left
    // then right
    // when u are left leaf (finish then go right)

// Post Order Traversal (Left, Right, Self)
    // first go all the way to the left
============

Delete Min Max

//go left until the left is null
    // if (left)
        // traverse left
    // delte the node by setting parent's left to null

[weikee94]

Graph

Common Operations

• Adding an edge
• Deleting an edge
• Detecting an edge
• Finding the neighbors of a vertex
• Finding a path between two vertices

Types of Graph

• Directed Graph
• Undirected Graph
• Weighted Directed Graph

Pseudocode

• create matrix for graph

[weikee94]

Hashtables

Hash Table Concept

• javascript objects are hash tables
• represented as key/value pairs
• a hashing function maps the key to an index
• a hashing function takes an input of any size and returns a hash code identifier of a fixed size

Pseudocode

• write a function that takes an input and always returns the same output
• ascii value of each character
• added or multiplied them together
• then returned it as hex instead of decimal

myObj = {};
myObj.itemOne = 'Hey';
myObj.itemTwo = 'Hello';

{ itemOne: 'Hey', itemTwo: 'Hello' }

myHash(itemOne) => 123
myHash(itemTwo) => 666

memory[___, ___, '123', ___, '666']

[weikee94]

DFS BFS

Depth first search

• graph traversing (find paths, cycles and connectivity)
• explored(black), visited(gray), undiscovered(white)
• once there are no more unexplored nodes, return
• each node needs to be visited and be marked as explored
• base case: if has been explored no where to go (empty)
• for i, loop through arr of edges, traverse(this._nodes[value][i])

Breath first search

• create a queue Q
• mark v as discovered (grey) and enqueue v into Q
• while Q is not empty, perform following steps:
  • dequeue u from Q
  • mark u as discovered (grey)
  • enqueue all unvisited (white) neighbors w of u
  • mark u as explored (black)