Algorithms and Data Structures

Written in Python, Golang, Node and Java

Vin Colgin (Summer/Fall 2019)

https://github.com/marvincolgin

https://linkedin.com/in/mcolgin

Table of Contents:

• Algorithms
  • Bubble Sort
  • Insertion Sort
  • Merge Sort
  • Quick Sort
• Data Structures
  • Arrays
    • Reverse Elements
    • Insert and Shift Array Elements
    • Binary Search
  • Singly Linked Lists
  • Stack (LIFO)
    • Balanced Brackets
  • Queue (FIFO)
    • Queue: Animal Shelter
  • Binary Tree (BT)
    • Breadth-first Traversal
    • Find the Maximum Value
    • FizzBuzzTree
    • Tree Intersection
  • Binary Search Tree (BST)
  • Hash Table
    • Repeated Words
    • Left Join
  • Graphs
    • Get Graph Edges
    • Depth-First Traversal

CI/CD

CircleCi for Tests:

Algorithms

Bubble Sort

Source Code:

Source: Github

def bubble_sort(arr):
    # BigO == n^2

---

Insertion Sort

Source Code:

Source: Github

def insertion_sort(arr):
    # BigO = O(2n)

---

Merge Sort

Source Code:

Source: Github

def merge_sort(arr):
    # BigO (n log n)
    # :: log n, as this is a divide algo
    # :: n, as we need to merge the halfs back

def merge_split(arr):
    # actual merge_sort function, without error handling
    # :: recursivily called

def merge_array(arr, left, right):
    # combine left and right sides

---

Quick Sort

Source Code:

Source: Github

def quick_sort(arr):
    # BigO (n log n)
    # :: log n, as this is a divide algo
    # :: n, as we need to merge the halfs back

Data Structures

Arrays

In Python, arrays are dynamic lists of pointers to memory addresses, Big O Time == 0(1)

Reverse Elements

Create a function, which reverses an array/linked-list, as passed via a parameter and pass the new array back as the return() for the function.

Approach & Efficiency My initial approach was to utilize the list.insert() and list.pop() to rebuild the list in reverse order. However, my white boarding partner showed me a more pythonic method utilizing slices with a -1 stride.

Solution Two solutions were used, one that utilizes a while() loop and is destructive on the inbound array. The second is "pythonic" and utilizes an index slice and a -1 stride.

Source Code:

Source: Github

def reverse_array(orig):
def reverse_array2(orig):

---

Insert and Shift Array Elements

Write a function which takes in an array and the value to be added. Without utilizing any of the built-in methods available to your language, return an array with the new value added at the middle index.

Solution Create an index into the array where the value will be inserted, utilize slice and .append/.extend to construct a return array

Source Code:

Source: Github

def insert_shift_array_sorted(arr, val):
def insert_shift_array(arr, val):

---

Binary Search

Write a function which takes in an array and the value to be searched. Return -1 if the value is not found, otherwise return the index (0 based). Incoming array is sorted.

Solution Divide and Conquer! Look at the middle element, is it the middle element? Return. If not, create a new middle from either the smaller side or larger side. Repeat.

Source Code:

Source: Github

def array_binary_search(arr, val):

---

Singly Linked Lists

Linked-Lists (singly) are dynamic data-structures which resembles a length of chain, where the entire length of chain is the list and the individual links of the chain are nodes. A singlarly linked list is only traversable in one direction, but utilizing a head element that points to the first node in the list, the second node in the list points to the next link in the chain, and finally the last element in the list points to "none"

Insert()

KthFromEnd(): Iterative Approach

KthFromEnd(): Recursive Approach

MergeList()

Source Code:

Source: Github

class LinkList()

    def __init__(self):
        # constructor

    def toJSON(self):
        # dump object to JSON and return as String

    def insert(self, value):
        # insert value at the head of the list

    def includes(self, value):
        # traverse list and determine if a value exists
        # return bool

    def count(self):
        # count the number of nodes and return count

    def append(value):
        # adds a new node with the given value to the end of the list
        # BigO == O(n)

    def insertBefore(value, newVal):
        # add a new node with the given newValue immediately before the first value node
        # BigO == O(n)

    def insertAfter(value, newVal):
        # add a new node with the given newValue immediately after the first value node
        # BigO == O(n)

class ListNode()
    def __init__(self, value, next=None, prev=None):
         # constructor

Source: Github

type LinkNode struct {
    value interface{}
	next  *LinkNode
	prev  *LinkNode
}
func (node *LinkNode) Init(value interface{}) {
    head *LinkNode
	// @TODO: comparison_func func
}

type LinkList struct {
	head *LinkNode
	// @TODO: comparison_func func
}
func (list *LinkList) Init() {}
func (list *LinkList) toJSON() string {}
func (list *LinkList) toStr() string {}
func (list *LinkList) Insert(value interface{}) bool {}
func (list *LinkList) Includes(value interface{}) bool {}
func (list *LinkList) Get(value interface{}) interface{} {}
func (list *LinkList) Count() int {}
func (list *LinkList) Append(value interface{}) bool {}
func (list *LinkList) Remove(value interface{}) bool {}
func (list *LinkList) Peek() (bool, interface{}) {}
func (list *LinkList) InsertBefore(targetVal, newVal interface{}, afterInstead bool) bool {}
func (list *LinkList) InsertAfter(targetVal, newVal interface{}) bool {}
func (list *LinkList) KthFromEnd(k int) (bool, interface{}) {}
func (list *LinkList) MergeList(listA, listB LinkList) LinkList {}

Source: Github

// LinkNode this is the internal object for individual link-nodes
class LinkNode {
	constructor(value) {
}

// LinkList is the internal data-structure
class LinkList {
	constructor() {}

   toStr() {}
   count() {}
   peek() {}
   append(value) {}
   insert(value) {}
   includes(value) {}
   remove(value) {}
   insertBefore(targetVal, newVal, afterInstead=false)  {}
   insertAfter(targetVal, newVal) {}
   kthFromEnd(k) {}
   mergeList(listA, listB) { }

Source: Github

public class LinkList {

   public class RetObj {}

   public Node head;

   private BiFunction<String, String, Boolean> comparisonFunc;
   public void setComparisonFunc(BiFunction f) {}

   public LinkList(BiFunction cf) {}

   class Node {}

   public void insert(String value) {}
   public int count() {}
   public Boolean includes(String value) {}
   public RetObj peek() {}
   public String toStr() {}
   public Boolean append(String value) {}
   public Boolean remove(String value) {}
   public String get(String value) {}
   private Boolean insertBeforeOrAfter(String targetVal, String newVal, Boolean afterInstead) {}
   public Boolean insertBefore(String targetVal, String newVal) {}
   public Boolean insertAfter(String targetVal, String newVal) {}
   public void traverse(Consumer actionFunc) {}
   public String kthFromEnd(int k) {}
   public LinkList mergeList(LinkList listA, LinkList listB) {}
}

---

Stack (LIFO)

Source Code:

Source: Github

class Stack():
    def push(val) -> bool:
    def pop() -> str:
    def peek() -> str:

Source: Github

type Stack struct {
	_data linklist.LinkList
}
func (stack *Stack) Init() {}
func (stack *Stack) Count() int {}
func (stack *Stack) Pop() (bool, interface{}) {}
func (stack *Stack) Push(val interface{}) bool {}
func (stack *Stack) Peek() (bool, interface{}) {}

</de