CheatSheet.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "ANpNp_orBx7L"
   },
   "source": [
    "BigO cheat sheet is [here](https://www.bigocheatsheet.com/).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "5CXB-ho7urw6"
   },
   "source": [
    "# **1. Sorting Algorithms**\n",
    "* Bubble sort - end of array is sorted (O(N^2)).\n",
    "* Selection sort - beginning of the array is sorted (O(N^2))."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "_VBpI20cvCiX"
   },
   "source": [
    "### **Merge sort**\n",
    "* Time complexity - O(NlogN)\n",
    "* Space complexity - O(N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "AU_WIxq8ug7l",
    "outputId": "f6af0981-63c6-418c-df07-0fd068621f33"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6]\n"
     ]
    }
   ],
   "source": [
    "arr = [3, 2, 4, 5, 1, 6]\n",
    "\n",
    "def mergeSortMain(arr):\n",
    "  mergeSort(arr)\n",
    "  return arr\n",
    "\n",
    "def mergeSort(arr):\n",
    "\n",
    "  # 0 and 1 are base cases (we should not change them, use them directly)\n",
    "\n",
    "  if len(arr) > 1:\n",
    "\n",
    "    mid = (len(arr)) // 2\n",
    "\n",
    "    left, right = arr[:mid], arr[mid:]\n",
    "\n",
    "    mergeSort(left)\n",
    "    mergeSort(right)\n",
    "\n",
    "    l, r, a = 0, 0, 0\n",
    "\n",
    "    while l < len(left) and r < len(right):\n",
    "      if left[l] < right[r]:\n",
    "        arr[a] = left[l]\n",
    "        l += 1\n",
    "      else:\n",
    "        arr[a] = right[r]\n",
    "        r += 1\n",
    "      \n",
    "      a += 1\n",
    "\n",
    "    while l < len(left):\n",
    "      arr[a] = left[l]\n",
    "      a += 1\n",
    "      l += 1\n",
    "\n",
    "    while r < len(right):\n",
    "      arr[a] = right[r]\n",
    "      a += 1\n",
    "      r += 1\n",
    "\n",
    "arr = [3, 2, 4, 5, 1, 6]\n",
    "print(mergeSortMain(arr))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "zq-35tbQ04x7"
   },
   "source": [
    "**Space complexity**\n",
    "![alt text](https://drive.google.com/uc?id=16j7WOIL1U_5eA_KqKICtqT8X7NJxuYk0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "miLEOYNC0cXH"
   },
   "source": [
    "### **Quick Sort**\n",
    "* Time complexity - O(NlogN) (average) / O(N^2) (worst)\n",
    "* Space complexity - O(logN) (average)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "bSWv9a5G0_7h",
    "outputId": "4ca1e195-1b63-4a96-9c01-c12979a10d70"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6]"
      ]
     },
     "execution_count": 7,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def quickSortMain(arr):\n",
    "  quickSort(arr, 0, len(arr)-1)\n",
    "  return arr\n",
    "\n",
    "def quickSort(arr, start, end):\n",
    "  \n",
    "  # base cases - when invested array has 0 or 1 length\n",
    "  if start < end:\n",
    "    idx = partition(arr, start, end)\n",
    "    quickSort(arr, start, idx-1)\n",
    "    quickSort(arr, idx+1, end)\n",
    "\n",
    "def partition(arr, start, end):\n",
    "\n",
    "  i = start+1\n",
    "\n",
    "  pivot = arr[start] \n",
    "\n",
    "  for j in range(start+1, end+1):\n",
    "    if arr[j] < pivot:\n",
    "      arr[i], arr[j] = arr[j], arr[i]\n",
    "      i += 1\n",
    "    \n",
    "  arr[start], arr[i-1] = arr[i-1], arr[start]\n",
    "\n",
    "  return i-1\n",
    "\n",
    "\n",
    "arr = [3, 2, 4, 5, 1, 6]\n",
    "quickSortMain(arr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "ToRFnBPG4IbH"
   },
   "source": [
    "# **2. Binary Search**\n",
    "* Time complexiy - O(logN)\n",
    "* Space complexity - O(1)\n",
    "\n",
    "**NOTE:** If the target does not exist in the array, \n",
    "* **start:** is the index that we know left element is smaller than the target element\n",
    "* **end:** is the index that we know right elemet is bigger than the target element"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "Rv4g5l0v0f_G",
    "outputId": "dbe99c6d-7ca6-4147-f31b-14350d3473ba"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 2,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def binary_search(arr, target):\n",
    "  \n",
    "  start, end = 0, len(arr)-1\n",
    "\n",
    "  while start <= end:\n",
    "    mid = (start + end) // 2\n",
    "\n",
    "    if arr[mid] == target:\n",
    "      return mid\n",
    "    elif arr[mid] < target:\n",
    "      start = mid+1\n",
    "    else:\n",
    "      end = mid-1\n",
    "  \n",
    "  return start, end\n",
    "\n",
    "arr = [1, 2, 4, 8, 9, 12]\n",
    "binary_search(arr, 9)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "VOIarjBm6DjQ"
   },
   "source": [
    "# **3. Data Structures**\n",
    "\n",
    "Python time complexities in [python wiki](https://wiki.python.org/moin/TimeComplexity)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "C5qmAgNL6JTq"
   },
   "source": [
    "### **Hash Map**\n",
    "The code is take from [leetcode question](https://leetcode.com/problems/design-hashmap/solution/).\n",
    "\n",
    "* Python **dict** is a **hashmap**\n",
    "* Two most important aspects:\n",
    "  * **Hash function design:** Hash function maps a key to an address. Good hash function distributes the keys evenly.\n",
    "  * **Collision handling:** Collision is the situation when two keys point to the same address.\n",
    "\n",
    "**Implementation**\n",
    "* **Hash function:** Modulo\n",
    "  * Prime number is used to prevent collision. (Ex: 2069)\n",
    "* **Storage:** List with size of modulo (2069 in our case)\n",
    "  * The modulo result of the key addresses to one of the indexes of array.\n",
    "* **Collision:** List bucket\n",
    "  * Each index holds a list bucket to store elements addressed to the same index\n",
    "\n",
    "![alt text](https://drive.google.com/uc?id=1DpGjBZo1vvbUKlHk6Ah-m7TmbMjdYXo6)\n",
    "\n",
    "**Main Functions**\n",
    "* get(key)\n",
    "* put(key, value)\n",
    "* remove(key)\n",
    "\n",
    "**Complexity Analysis**\n",
    "* Time complexity - O(N/K) for each function.\n",
    "  * N - all possible numbers\n",
    "  * K - number of buckets (hash_space). 2069 in our case.\n",
    "  * With decent hash function we assume these complexities have O(1) time. In worst case, all cases are in one bucket and each operation takes O(N) time\n",
    "\n",
    "* Space complexity - O(K+M)\n",
    "  * K - number of buckets (key space)\n",
    "  * M - # of unique keys inserted in hashmap\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 85
    },
    "colab_type": "code",
    "id": "ho06Y9Jl6Iyi",
    "outputId": "0dd8e1ef-3450-49f9-babe-ccc35af82c3f"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "-1\n",
      "1\n",
      "-1\n"
     ]
    }
   ],
   "source": [
    "class Bucket:\n",
    "  \n",
    "  def __init__(self):\n",
    "    self.bucket = []\n",
    "\n",
    "  def get(self, key):\n",
    "    for k, v in self.bucket:\n",
    "      if k == key:\n",
    "        return v\n",
    "    return -1\n",
    "\n",
    "  # either add new one or change existing one\n",
    "  def update(self, key, value):\n",
    "    found = False\n",
    "\n",
    "    for idx, kv in enumerate(self.bucket):\n",
    "      if key == kv[0]:\n",
    "        self.bucket[idx] = (key, value)\n",
    "        found = True\n",
    "        break \n",
    "      \n",
    "    if not found:\n",
    "      self.bucket.append((key, value))\n",
    "\n",
    "  def remove(self, key):\n",
    "    for idx, kv in enumerate(self.bucket):\n",
    "      if key == kv[0]:\n",
    "        del self.bucket[idx]\n",
    "        break\n",
    "\n",
    "class HashMap:\n",
    "  \n",
    "  def __init__(self):\n",
    "\n",
    "    # holds the size of hash_table\n",
    "    self.key_space = 2069\n",
    "    self.hash_table = [Bucket() for i in range(self.key_space)]\n",
    "\n",
    "  def put(self, key, value):\n",
    "    hash_key = key % self.key_space\n",
    "    self.hash_table[hash_key].update(key, value)\n",
    "\n",
    "  def get(self, key):\n",
    "    hash_key = key % self.key_space\n",
    "    return self.hash_table[hash_key].get(key)\n",
    "\n",
    "  def remove(self, key):\n",
    "    hash_key = key % self.key_space\n",
    "    self.hash_table[hash_key].remove(key)\n",
    "\n",
    "'''\n",
    "[\"MyHashMap\",\"put\",\"put\",\"get\",\"get\",\"put\",\"get\", \"remove\", \"get\"]\n",
    "[[],[1,1],[2,2],[1],[3],[2,1],[2],[2],[2]]\n",
    "'''\n",
    "\n",
    "hm = HashMap()\n",
    "hm.put(1,1)\n",
    "hm.put(2,2)\n",
    "print(hm.get(1))\n",
    "print(hm.get(3))\n",
    "hm.put(2,1)\n",
    "print(hm.get(2))\n",
    "hm.remove(2)\n",
    "print(hm.get(2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "REqCOlidCEOO"
   },
   "source": [
    "### **Linked List**\n",
    "\n",
    "The code is taken from [leetcode question](https://leetcode.com/problems/design-linked-list/).\n",
    "\n",
    "* Python **list** is a **doubly linked list**.\n",
    "* LinkedListNode has two attributes\n",
    "  * value\n",
    "  * linked nodes\n",
    "* Singly linked list addAtHead is O(1) and addAtTail is O(N). Doubly linked list both is O(1)\n",
    "* Sentinental nodes are used to ease adding and removing. The do not hold any data.\n",
    "\n",
    "**Main Functions**\n",
    "* get(index)\n",
    "* addAtHead(val)\n",
    "* addAtTail(val)\n",
    "* addAtIndex(index, val)\n",
    "* deleteAtIndex(index)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "fckcZ50ASMPW"
   },
   "source": [
    "**Singly Linked List**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 85
    },
    "colab_type": "code",
    "id": "CncjfSlpCHC5",
    "outputId": "ab8ab857-8b47-43c6-f517-3b48b69673e3"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "1\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "'''\n",
    "Time complexities\n",
    "\n",
    "get(index) - O(k)\n",
    "addAtHead(val) - O(1)\n",
    "addAtTail(val) - O(N)\n",
    "addAtIndex(index, val) - O(k)\n",
    "deleteAtIndex(index) - O(k)\n",
    "\n",
    "Space complexity\n",
    "O(1)\n",
    "\n",
    "'''\n",
    "\n",
    "class ListNode:\n",
    "\n",
    "  def __init__(self, data):\n",
    "    self.data = data\n",
    "    self.nextNode = None\n",
    "\n",
    "class SinglyLinkedList:\n",
    "\n",
    "  def __init__(self):\n",
    "\n",
    "    self.size = 0\n",
    "    # sentinentel node as pseudo head\n",
    "    self.head = ListNode(0)\n",
    "\n",
    "  def get(self, index):\n",
    "\n",
    "    # invalid index check\n",
    "    if index < 0 or index >= self.size:\n",
    "      return -1\n",
    "\n",
    "    node = self.head\n",
    "    while index >= 0:\n",
    "      node = node.nextNode\n",
    "      index -= 1\n",
    "\n",
    "    return node\n",
    "\n",
    "  def addAtIndex(self, index, val):\n",
    "\n",
    "    # invalid index check\n",
    "    # 0 - start\n",
    "    # size - end\n",
    "    if index < 0 or index > self.size:\n",
    "      return -1\n",
    "\n",
    "    pred = self.head\n",
    "    while index > 0:\n",
    "      pred = pred.nextNode\n",
    "      index -= 1\n",
    "\n",
    "    to_add = ListNode(val)\n",
    "    to_add.nextNode = pred.nextNode\n",
    "    pred.nextNode = to_add\n",
    "\n",
    "    self.size += 1\n",
    "\n",
    "  def addAtHead(self, val):\n",
    "    self.addAtIndex(0, val)\n",
    "\n",
    "  def addAtTail(self, val):\n",
    "    self.addAtIndex(self.size, val)\n",
    "\n",
    "  def deleteAtIndex(self, index):\n",
    "    \n",
    "    # invalid index check\n",
    "    if index < 0 or index >= self.size:\n",
    "      return -1 \n",
    "\n",
    "    pred = self.head\n",
    "    while index > 0:\n",
    "      pred = pred.nextNode\n",
    "    \n",
    "    pred.nextNode = pred.nextNode.nextNode\n",
    "    self.size -= 1\n",
    "\n",
    "\n",
    "ll = SinglyLinkedList()\n",
    "ll.addAtTail(1)\n",
    "print(ll.get(0).data)\n",
    "ll.addAtIndex(0, 2)\n",
    "print(ll.get(0).data)\n",
    "print(ll.get(1).data)\n",
    "ll.deleteAtIndex(0)\n",
    "print(ll.get(0).data)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "WtQTIijMSPrF"
   },
   "source": [
    "**Doubly Linked List**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "BnD3z2XGSK4V"
   },
   "outputs": [],
   "source": [
    "class ListNode:\n",
    "\n",
    "  def __init__(self, data):\n",
    "    self.data = data\n",
    "    self.nextNode = None\n",
    "    self.prevNode = None\n",
    "\n",
    "\n",
    "class DoublyLinkedList:\n",
    "\n",
    "  def __init__(self):\n",
    "    self.size = 0\n",
    "    self.head, self.tail = ListNode(0), ListNode(0)\n",
    "    self.head.nextNode = self.tail\n",
    "    self.tail.prevNoe = self.head\n",
    "\n",
    "  def get(self, index):\n",
    "\n",
    "    # invalid\n",
    "    if index < 0 and index >= self.size:\n",
    "      return -1\n",
    "\n",
    "    # read from tail\n",
    "    if index >= self.size // 2:\n",
    "      node = self.tail \n",
    "      for _ in range(self.size-index):\n",
    "        node = node.prevNode\n",
    "\n",
    "      return node\n",
    "    \n",
    "    # read from head\n",
    "    else:\n",
    "\n",
    "      node = self.head\n",
    "      for _ in range(index+1):\n",
    "        node = node.nextNode\n",
    "\n",
    "      return node\n",
    "\n",
    "  def addAtIndex(self, index, val):\n",
    "\n",
    "    # invalid\n",
    "    if 0 < index and index > self.size:\n",
    "      return -1\n",
    "\n",
    "    pred = self.get(index-1)\n",
    "    succ = pred.nextNode\n",
    "\n",
    "    to_add = ListNode(val)\n",
    "    to_add.prevNode = pred\n",
    "    to_add.nextNode = succ\n",
    "\n",
    "    pred.nextNode = to_add\n",
    "    succ.prevNode = to_add\n",
    "\n",
    "    self.size += 1\n",
    "  \n",
    "  def addAtHead(self, val):\n",
    "    self.addAtIndex(0, val)\n",
    "\n",
    "  def addAtTail(self, val):\n",
    "    self.addAtIndex(self.size, val)\n",
    "\n",
    "  def deleteAtIndex(self, index):\n",
    "\n",
    "    # invalid\n",
    "    if index < 0 and index >= self.size:\n",
    "      return -1\n",
    "\n",
    "    pred = self.get(index-1)\n",
    "    succ = pred.nextNode.nextNode\n",
    "\n",
    "    pred.nextNode = succ\n",
    "    succ.prevNode = pred\n",
    "\n",
    "    self.size -= 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "eBA43dZkgPis"
   },
   "source": [
    "### **Stack**\n",
    "* Python uses **list** as stack\n",
    "\n",
    "**Methods**\n",
    "* pop() - pop()\n",
    "* push() - append()\n",
    "* peek() - stack[-1]\n",
    "* isEmpty() - len(stack) == 0\n",
    "\n",
    "**NOTE:** In stack questions, try to generate the index of item based on the result length, so you do not need to traverse twice or keep an extra index."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 119
    },
    "colab_type": "code",
    "id": "LF0CXyuygScP",
    "outputId": "3d7c2023-65b4-498f-def6-4fe1b996f0ac"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "5\n",
      "4\n",
      "3\n",
      "3\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "class StackNode:\n",
    "  def __init__(self, data):\n",
    "    self.data = data\n",
    "    self.nextNode = None\n",
    "\n",
    "class Stack:\n",
    "\n",
    "  def __init__(self):\n",
    "    self.top = None\n",
    "\n",
    "  def pop(self):\n",
    "    if self.top == None:\n",
    "      return None\n",
    "\n",
    "    node = self.top\n",
    "    self.top = self.top.nextNode\n",
    "    node.nextNode = None\n",
    "\n",
    "    return node\n",
    "\n",
    "  def push(self, node):\n",
    "    if self.top == None:\n",
    "      self.top = node\n",
    "    else:\n",
    "      node.nextNode = self.top\n",
    "      self.top = node\n",
    "\n",
    "  def peek(self):\n",
    "    if self.top == None:\n",
    "      return -1\n",
    "\n",
    "    return self.top\n",
    "\n",
    "  def isEmpty(self):\n",
    "    return self.top == None\n",
    "\n",
    "stack = Stack()\n",
    "stack.push(StackNode(3))\n",
    "print(stack.isEmpty())\n",
    "stack.push(StackNode(4))\n",
    "stack.push(StackNode(5))\n",
    "print(stack.pop().data)\n",
    "print(stack.pop().data)\n",
    "print(stack.peek().data)\n",
    "print(stack.pop().data)\n",
    "print(stack.isEmpty())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "_-ChI7bihtA8"
   },
   "source": [
    "### **Queue**\n",
    "\n",
    "* from collections import deque\n",
    "\n",
    "**Methods**\n",
    "* add(item) - append()\n",
    "* remove() - popleft()\n",
    "* peek() - queue[0]\n",
    "* isEmpty() - len(queue) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 119
    },
    "colab_type": "code",
    "id": "M8Y72vd2h2Ra",
    "outputId": "341aadb0-931b-4fdb-c4a8-bc63fd42a084"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "3\n",
      "4\n",
      "5\n",
      "5\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "class QueueNode:\n",
    "  def __init__(self, data):\n",
    "    self.data = data\n",
    "    self.nextNode = None\n",
    "\n",
    "class Queue:\n",
    "  def __init__(self):\n",
    "    self.first, self.last = None, None\n",
    "\n",
    "  def add(self, node):\n",
    "    \n",
    "    if self.first == None:\n",
    "      self.first, self.last = node, node\n",
    "    else:  \n",
    "      self.last.nextNode = node\n",
    "      self.last = node\n",
    "\n",
    "  def remove(self):\n",
    "    if self.first == None:\n",
    "      return -1\n",
    "\n",
    "    node = self.first\n",
    "    self.first = self.first.nextNode\n",
    "    node.nextNode = None\n",
    "\n",
    "    if self.first == None:\n",
    "      self.last = None\n",
    "    \n",
    "    return node\n",
    "  \n",
    "  def peek(self):\n",
    "    if self.first == None:\n",
    "      return -1\n",
    "\n",
    "    return self.first\n",
    "\n",
    "  def isEmpty(self):\n",
    "    return self.first == None\n",
    "\n",
    "queue = Queue()\n",
    "queue.add(QueueNode(3))\n",
    "print(queue.isEmpty())\n",
    "queue.add(QueueNode(4))\n",
    "queue.add(QueueNode(5))\n",
    "print(queue.remove().data)\n",
    "print(queue.remove().data)\n",
    "print(queue.peek().data)\n",
    "print(queue.remove().data)\n",
    "print(queue.isEmpty())\n",
    "  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "dzu21suep-II"
   },
   "source": [
    "### **Trie**\n",
    "The code is taken from [leetcode](https://leetcode.com/problems/implement-trie-prefix-tree/)\n",
    "\n",
    "\n",
    "**Trie Node**\n",
    "\n",
    "Features:\n",
    "* **links (list)** - The connections to next letter\n",
    "* **isEnd (bool)** - Indicates if the current node is an end\n",
    "* **K (int):** - number of letters\n",
    "\n",
    "Functions:\n",
    "* **containsKey(key) (bool)** - Check if current node has connection to given key \n",
    "* **get(key) (TrieNode)** - Returns the TrieNode of given key\n",
    "* **put(key, node)** - Creates the link connection to given key\n",
    "\n",
    "**Trie**\n",
    "* **insert(word)** - Puts the word to current Trie\n",
    "* **getPrefix(prefix) (TreeNode)** - Returns the node of the end if prefix exist, otherwise None \n",
    "* **search(word) (bool)** - Returns if the given word is in the Trie\n",
    "* **startsWith(prefix) (bool)** - Returns if there is word starting with given prefix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "6ryLaIaKqMZG"
   },
   "outputs": [],
   "source": [
    "class Trie:\n",
    "    \n",
    "    '''\n",
    "    word length - m \n",
    "    number of sequences - n\n",
    "    '''\n",
    "\n",
    "  def __init__(self):\n",
    "    self.root = TrieNode()\n",
    "\n",
    "  # Time complexity - O(m)\n",
    "  # Space complexity - O(m)\n",
    "  def insert(self, word):\n",
    "\n",
    "    # TODO check if the word already exists\n",
    "\n",
    "    node = self.root\n",
    "    for letter in word:\n",
    "      if not node.containsKey(letter):\n",
    "        node.put(letter, TrieNode())\n",
    "\n",
    "      node = node.get(letter)\n",
    "\n",
    "    node.isEnd = True\n",
    "\n",
    "  def getPrefix(self, prefix):\n",
    "\n",
    "    node = self.root\n",
    "    for letter in prefix:\n",
    "      if not node.containsKey(letter):\n",
    "        return None\n",
    "\n",
    "      node = node.get(letter)\n",
    "\n",
    "    return node\n",
    "\n",
    "  # Time complexity - O(m)\n",
    "  # Space complexity - O(1)\n",
    "  def search(self, word):\n",
    "    node = self.getPrefix(word)\n",
    "    return node is not None and node.isEnd\n",
    "\n",
    "  # Time complexity - O(m)\n",
    "  # Space complexity - O(1)\n",
    "  def startsWith(self, prefix):\n",
    "    return self.getPrefix(prefix) is not None         \n",
    "\n",
    "class TrieNode:\n",
    "    '''\n",
    "    TrieNode does not hold the ata itself. It just creates a link \n",
    "    to the next node\n",
    "    '''\n",
    "    # isEnd indicates the current letter is the end of word\n",
    "    links, R, isEnd = [], 26, False\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.links = [None for i in range(self.R)]\n",
    "        \n",
    "    def containsKey(self, c):\n",
    "        return self.links[ord(c)-ord('a')] != None\n",
    "    \n",
    "    def get(self, c):\n",
    "        return self.links[ord(c) - ord('a')]\n",
    "    \n",
    "    def put(self, c, node):\n",
    "        self.links[ord(c) - ord('a')] = node\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 82
    },
    "colab_type": "code",
    "id": "nt_TisSPTJg0",
    "outputId": "b6d7cad6-6f97-4df8-8897-2e2d46065c82"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n",
      "True\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "trie = Trie()\n",
    "\n",
    "trie.insert(\"apple\")\n",
    "print(trie.search(\"apple\"))   # True\n",
    "print(trie.search(\"app\"))     # False\n",
    "print(trie.startsWith(\"app\")) # True\n",
    "trie.insert(\"app\")   \n",
    "print(trie.search(\"app\"))     # True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Xj4WfrPKrEc7"
   },
   "source": [
    "### **Heap**\n",
    "\n",
    "The code is taken from [this link](https://runestone.academy/runestone/books/published/pythonds/Trees/BinaryHeapImplementation.html).\n",
    "\n",
    "* The elements are kept in **Complete binary tree**\n",
    "* Complete binary tree can be represented with a list\n",
    "  * parent: p\n",
    "  * left child: 2p\n",
    "  * right child: 2p+1\n",
    "  * Any parent node can be found with python integer division. (2p//2=p & (2p+1)//2=p)\n",
    "* Heap order property:\n",
    "  * **Max heap:** The value of parent is alway greater or equal to the value of child node. (biggest node at the root)\n",
    "  * **Min heap:** less than or equal\n",
    "  * We will work on min heap here.\n",
    "\n",
    "![alt text](https://drive.google.com/uc?id=1sxVAyD3yRZWuPEW-gUlUILAfPMjRBPi3)\n",
    "\n",
    "**Methods**\n",
    "* insert(val) - O(logN)\n",
    "  * Append to the end of the list\n",
    "  * Swap with the parent if it does not preserve heap property.\n",
    "\n",
    "* delMin() - O(logN)\n",
    "  * Pop the last element and append to the head\n",
    "  * Swap it with smallest child until it is not swappable anymore\n",
    "* buildHeap(alist) - O(N)\n",
    "  * Starting from one level up of the leaf to the top node, we percDown nodes one by one."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "uvH7ezZwtBSr"
   },
   "outputs": [],
   "source": [
    "class MinHeap:\n",
    "  \n",
    "  def __init__(self):\n",
    "    self.heapList = [0]\n",
    "    self.currentSize = 0\n",
    "\n",
    "  def percUp(self, i):\n",
    "\n",
    "    # i // 2 gives the parent index\n",
    "    while i // 2 > 0 and self.heapList[i] < self.heapList[i//2]:\n",
    "      self.heapList[i], self.heapList[i//2] = self.heapList[i//2], self.heapList[i]\n",
    "      i = i//2\n",
    "\n",
    "  def minChild(self, i):\n",
    "    left = self.heapList[i*2]\n",
    "\n",
    "    right = float('inf')\n",
    "    if i*2+1 <= self.currentSize:\n",
    "      right = self.heapList[i*2+1]\n",
    "    \n",
    "    if right < left:\n",
    "      return 2*i+1\n",
    "    else:\n",
    "      return 2*i\n",
    "\n",
    "  def percDown(self, i):\n",
    "    \n",
    "    # left child will be there\n",
    "    while i*2 <= self.currentSize:\n",
    "      mc = self.minChild(i)\n",
    "\n",
    "      if self.heapList[i] > self.heapList[mc]:\n",
    "        self.heapList[i], self.heapList[mc] = self.heapList[mc], self.heapList[i]\n",
    "        i = mc\n",
    "      else:\n",
    "        break\n",
    "\n",
    "  def insert(self, k):\n",
    "    self.heapList.append(k)\n",
    "    self.currentSize += 1\n",
    "\n",
    "    # current size is the index of newly added item\n",
    "    self.percUp(self.currentSize)\n",
    "\n",
    "  def delMin(self):\n",
    "    self.heapList[1], self.heapList[self.currentSize] = self.heapList[self.currentSize], self.heapList[1]\n",
    "    minItem = self.heapList.pop()\n",
    "    self.currentSize -= 1\n",
    "\n",
    "    self.percDown(1)\n",
    "    return minItem\n",
    "\n",
    "  def buildHeap(self, alist):\n",
    "    self.heapList = [0] + alist[:]\n",
    "    self.currentSize = len(alist)\n",
    "\n",
    "    # the last item before leaf\n",
    "    i = self.currentSize // 2\n",
    "\n",
    "    while i > 0:\n",
    "      self.percDown(i)\n",
    "      i -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 68
    },
    "colab_type": "code",
    "id": "YjGai9SI9mhf",
    "outputId": "174b2d0c-58cf-45da-ffb0-ba11292249b0"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 2, 3, 5, 6, 9]\n",
      "[0, 5, 7, 11, 14, 9, 19, 21, 33, 17, 27, 18]\n",
      "[0, 9, 14, 11, 17, 18, 19, 21, 33, 27]\n"
     ]
    }
   ],
   "source": [
    "# buildHeap\n",
    "mh = MinHeap()\n",
    "mh.buildHeap([9, 6, 5, 2, 3])\n",
    "print(mh.heapList)\n",
    "\n",
    "mh2 = MinHeap()\n",
    "\n",
    "# insert\n",
    "mh2.buildHeap([5, 9, 11, 14, 18, 19, 21, 33, 17, 27])\n",
    "mh2.insert(7)\n",
    "print(mh2.heapList)\n",
    "\n",
    "# delMin\n",
    "mh2.buildHeap([5, 9, 11, 14, 18, 19, 21, 33, 17, 27])\n",
    "mh2.delMin()\n",
    "print(mh2.heapList)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "_Xn-KBM9_xJX"
   },
   "source": [
    "**Python Implementation**\n",
    "\n",
    "heapq is min queue as default. If max queue is required, then negative version should be appended and popped from the heap."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 68
    },
    "colab_type": "code",
    "id": "HVymvjQh_zkv",
    "outputId": "7f53736f-967b-4bf5-8d6d-e0ff327e0515"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3, 6, 9, 5]\n",
      "2\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "from heapq import heapify, heappush, heappop \n",
    "\n",
    "# Creating empty heap \n",
    "heap = [] \n",
    "heapify(heap) \n",
    "  \n",
    "# Adding items to the heap using heappush function \n",
    "heappush(heap, 9) \n",
    "heappush(heap, 6) \n",
    "heappush(heap, 5) \n",
    "heappush(heap, 2)\n",
    "heappush(heap, 3)\n",
    "print(heap)\n",
    "\n",
    "element = heappop(heap)\n",
    "print(element)\n",
    "element = heappop(heap)\n",
    "print(element)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "b6lUxED-Poib"
   },
   "source": [
    "### **Binary Search Tree**\n",
    "\n",
    "For each node in binary search tree:\n",
    "* **Nodes in left subtree:** smaller or equal\n",
    "* **Nodes in right subtree:** bigger"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "6CgkxPSaKd9Q"
   },
   "outputs": [],
   "source": [
    "class TreeNode:\n",
    "  def __init__(self, data):\n",
    "    self.left, self.right = None, None\n",
    "    self.data = data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "MdOumaRBKL3C"
   },
   "outputs": [],
   "source": [
    "class BST:\n",
    "\n",
    "  def __init__(self):\n",
    "    self.root = None\n",
    "\n",
    "  def insert(self, data):\n",
    "\n",
    "    if self.root is None:\n",
    "      self.root = TreeNode(data)\n",
    "    else:    \n",
    "      node, parent = self.root, None\n",
    "\n",
    "      while node is not None:\n",
    "        parent = node\n",
    "        if data <= node.data:\n",
    "          node = node.left\n",
    "        else:\n",
    "          node = node.right\n",
    "\n",
    "      if data <= parent.data:\n",
    "        parent.left = TreeNode(data)\n",
    "      else:\n",
    "        parent.right = TreeNode(data)\n",
    "\n",
    "  def get(self, data):\n",
    "\n",
    "    node = self.root\n",
    "\n",
    "    while node is not None:\n",
    "      if node.data == data:\n",
    "        return data\n",
    "      elif data <= node.data:\n",
    "        node = node.left\n",
    "      else:\n",
    "        node = node.right\n",
    "    \n",
    "    # node is not found\n",
    "    return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 173
    },
    "colab_type": "code",
    "id": "YTFxSQN4Mb92",
    "outputId": "11a72b0f-96c4-45f7-9a71-3d7d71b4c56f"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "3\n",
      "4\n",
      "4\n",
      "5\n",
      "5\n",
      "7\n",
      "9\n",
      "13\n"
     ]
    }
   ],
   "source": [
    "bst = BST()\n",
    "bst.insert(5)\n",
    "bst.insert(1)\n",
    "bst.insert(4)\n",
    "bst.insert(4)\n",
    "bst.insert(5)\n",
    "bst.insert(9)\n",
    "bst.insert(7)\n",
    "bst.insert(13)\n",
    "bst.insert(3)\n",
    "\n",
    "root = bst.root\n",
    "in_order(root)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "tSj5BBqkP8BE"
   },
   "source": [
    "# **4. Traversal Algorithms**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "YirdIco5P_lu"
   },
   "source": [
    "### **BFS**\n",
    "* Implemented with **queue** (not recursive)\n",
    "* Level-wise implementation\n",
    "* In general:\n",
    "  * Time complexity - O(V+E)\n",
    "  * Space complexity - O(V)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "X9KWJwL8yG5l"
   },
   "source": [
    "#### **BFS-Tree**\n",
    "* Time complexity - O(N)\n",
    "* Space complexity - O(N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "fnAl5Z4sQC1K"
   },
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "\n",
    "class TreeNode:\n",
    "  def __init__(self, data):\n",
    "    self.left, self.right = None, None\n",
    "    self.data = data\n",
    "\n",
    "def bfsTree(root):\n",
    "  queue = deque()\n",
    "\n",
    "  queue.append(root)\n",
    "\n",
    "  while queue:\n",
    "    curr = queue.popleft()\n",
    "    print(curr.data)\n",
    "\n",
    "    if curr.left:\n",
    "      queue.append(curr.left)\n",
    "    if curr.right:\n",
    "      queue.append(curr.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 136
    },
    "colab_type": "code",
    "id": "zSKqEbxERH3x",
    "outputId": "88ccee72-3f36-41e2-dece-36b9466bb8f5"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n"
     ]
    }
   ],
   "source": [
    "'''\n",
    "     1\n",
    "   2   3\n",
    " 4  5 6 7\n",
    "'''\n",
    "\n",
    "t = TreeNode(1)\n",
    "t.left = TreeNode(2)\n",
    "t.right = TreeNode(3)\n",
    "t.left.left = TreeNode(4)\n",
    "t.left.right = TreeNode(5)\n",
    "t.right.left = TreeNode(6)\n",
    "t.right.right = TreeNode(7)\n",
    "\n",
    "bfsTree(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "1Wj0dN2ayKiE"
   },
   "source": [
    "#### **BFS-Tree (Levels)**\n",
    "* Time complexity - O(N)\n",
    "* Space complexity - O(N)  except the result array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "g2yW6ZaByQZY"
   },
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "\n",
    "class TreeNode:\n",
    "  def __init__(self, data):\n",
    "    self.left, self.right = None, None\n",
    "    self.data = data\n",
    "\n",
    "def bfs_level(root):\n",
    "  queue = deque()\n",
    "  queue.append((root, 0))\n",
    "\n",
    "  result = []\n",
    "\n",
    "  while len(queue) != 0:\n",
    "      curr, level = queue.popleft()\n",
    "      if len(result) == level:\n",
    "          l = []\n",
    "          l.append(curr.data)\n",
    "          result.append(l)\n",
    "      else:\n",
    "          result[level].append(curr.data)\n",
    "      \n",
    "      if curr.left != None:\n",
    "          queue.append((curr.left, level+1))\n",
    "          \n",
    "      if curr.right != None:\n",
    "          queue.append((curr.right, level+1))\n",
    "          \n",
    "  return result   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "MXlCxOB50tDC",
    "outputId": "429700c5-a0da-4f55-8b85-ddfef99634e2"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1], [2, 3], [4, 5, 6, 7]]\n"
     ]
    }
   ],
   "source": [
    "'''\n",
    "     1\n",
    "   2   3\n",
    " 4  5 6 7\n",
    "'''\n",
    "\n",
    "t = TreeNode(1)\n",
    "t.left = TreeNode(2)\n",
    "t.right = TreeNode(3)\n",
    "t.left.left = TreeNode(4)\n",
    "t.left.right = TreeNode(5)\n",
    "t.right.left = TreeNode(6)\n",
    "t.right.right = TreeNode(7)\n",
    "\n",
    "print(bfs_level(t))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "S_Q4Xu4QRrdX"
   },
   "source": [
    "#### **BFS-Graph**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "lg72cICuRv_1"
   },
   "outputs": [],
   "source": [
    "class Node:\n",
    "  def __init__(self, data):\n",
    "    self.data = data\n",
    "    self.adjList = []\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "def bfsGraph(node):\n",
    "  queue = deque()\n",
    "\n",
    "  queue.append(node)\n",
    "  visited = set()\n",
    "  visited.add(node)\n",
    "\n",
    "  while queue:\n",
    "    curr = queue.popleft()\n",
    "    print(curr.data)\n",
    "\n",
    "    for adj in curr.adjList:\n",
    "      if adj not in visited:\n",
    "        visited.add(adj)\n",
    "        queue.append(adj) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 119
    },
    "colab_type": "code",
    "id": "NeEt5tJwTNA7",
    "outputId": "4975a89c-06eb-4795-de00-0d6380e2cb87"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "6\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "class Node:\n",
    "  def __init__(self, data):\n",
    "    self.data = data\n",
    "    self.adjList = []\n",
    "'''\n",
    "    5\n",
    "    |\n",
    "    4\n",
    "  / | \\\n",
    "2 - 1 - 3 - 6\n",
    "\n",
    "'''\n",
    "\n",
    "one, two, three, four, five, six = Node(1), Node(2), Node(3), Node(4), Node(5), Node(6)\n",
    "one.adjList = [two, three, four]\n",
    "two.adjList = [one, four]\n",
    "three.adjList = [one, four, six]\n",
    "four.adjList = [one, two, three, five]\n",
    "\n",
    "bfsGraph(one)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "wrW0AoZkUfrR"
   },
   "source": [
    "### **DFS**\n",
    "\n",
    "* Implemented with **stack** or **recursively**.\n",
    "* Deep-wise implementation\n",
    "* In general:\n",
    "  * Time complexity - O(V+E)\n",
    "  * Space complexity - O(V)\n",
    "* Tree DFS has 3 types\n",
    "  * pre-order (C-L-R)\n",
    "  * in-order (L-C-R)\n",
    "  * post-order (L-R-C)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "J5dujGYLVIIT"
   },
   "source": [
    "#### **DFS-Tree**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "JEYo3pYyVJ_X"
   },
   "outputs": [],
   "source": [
    "class TreeNode:\n",
    "  def __init__(self, data):\n",
    "    self.left, self.right = None, None\n",
    "    self.data = data\n",
    "\n",
    "'''\n",
    "     1\n",
    "   2   3\n",
    " 4  5 6 7\n",
    "'''\n",
    "\n",
    "t = TreeNode(1)\n",
    "t.left = TreeNode(2)\n",
    "t.right = TreeNode(3)\n",
    "t.left.left = TreeNode(4)\n",
    "t.left.right = TreeNode(5)\n",
    "t.right.left = TreeNode(6)\n",
    "t.right.right = TreeNode(7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "68sbhiNqWwH2"
   },
   "source": [
    "**Pre-Order (CLR)**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 136
    },
    "colab_type": "code",
    "id": "giLLJTYDWyG4",
    "outputId": "acec58c0-de61-4fd3-93b2-ba9af7da23ec"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "4\n",
      "5\n",
      "3\n",
      "6\n",
      "7\n"
     ]
    }
   ],
   "source": [
    "# recursive\n",
    "def pre_order(node):\n",
    "  if node:\n",
    "    print(node.data)\n",
    "    pre_order(node.left)\n",
    "    pre_order(node.right)\n",
    "\n",
    "pre_order(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 136
    },
    "colab_type": "code",
    "id": "p8VCkZVdYR05",
    "outputId": "c2066eaa-ae7c-4dcd-923f-288c2546ccf7"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "4\n",
      "5\n",
      "3\n",
      "6\n",
      "7\n"
     ]
    }
   ],
   "source": [
    "# iterative\n",
    "def pre_order_itr(node):\n",
    "  stack = []\n",
    "  stack.append(node)\n",
    "\n",
    "  while stack:\n",
    "    curr = stack.pop()\n",
    "    print(curr.data)\n",
    "\n",
    "    # left will be read first\n",
    "    if curr.right:\n",
    "      stack.append(curr.right)\n",
    "    if curr.left:\n",
    "      stack.append(curr.left)\n",
    "\n",
    "\n",
    "pre_order_itr(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "JdePydclXbla"
   },
   "source": [
    "**In-Order (LCR)**\n",
    "\n",
    "Prints in sorted order in binary search trees."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "CjnrebUkXr7D"
   },
   "outputs": [],
   "source": [
    "def in_order(node):\n",
    "  if node:\n",
    "    in_order(node.left)\n",
    "    print(node.data)\n",
    "    in_order(node.right)\n",
    "\n",
    "# in_order(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 136
    },
    "colab_type": "code",
    "id": "1czkV9U_bbrc",
    "outputId": "fd13e802-ab3e-4aed-ff8e-a13c6809d7c3"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "2\n",
      "5\n",
      "1\n",
      "6\n",
      "3\n",
      "7\n"
     ]
    }
   ],
   "source": [
    "def in_order_itr(node):\n",
    "  stack = []\n",
    "\n",
    "  while node or stack:\n",
    "    \n",
    "    while node:\n",
    "      stack.append(node)\n",
    "      node = node.left\n",
    "    \n",
    "    node = stack.pop()\n",
    "    print(node.data)\n",
    "\n",
    "    # think it like new root\n",
    "    node = node.right\n",
    "  \n",
    "in_order(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "v-2WMvLKX6jv"
   },
   "source": [
    "**Post-Order (LRC)**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 136
    },
    "colab_type": "code",
    "id": "2fTMFnvjX_WG",
    "outputId": "e5d2964e-14d5-47e6-cfc4-1bc6b4a2c17e"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "5\n",
      "2\n",
      "6\n",
      "7\n",
      "3\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "def post_order(node):\n",
    "  if node:\n",
    "    post_order(node.left)\n",
    "    post_order(node.right)\n",
    "    print(node.data)\n",
    "\n",
    "post_order(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 136
    },
    "colab_type": "code",
    "id": "q6RHtBhAcF6x",
    "outputId": "0066530d-e24a-4830-a5b8-d43e35702784"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "5\n",
      "2\n",
      "6\n",
      "7\n",
      "3\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "def post_order_itr(node):\n",
    "  stack, outStack = [], []\n",
    "  stack.append(node)\n",
    "\n",
    "  while stack:\n",
    "    node = stack.pop()\n",
    "\n",
    "    outStack.append(node)\n",
    "\n",
    "    # put first to stack to read first in outStack\n",
    "    if node.left:\n",
    "      stack.append(node.left)\n",
    "    if node.right:\n",
    "      stack.append(node.right)\n",
    "\n",
    "  while outStack:\n",
    "    node = outStack.pop()\n",
    "    print(node.data)\n",
    "\n",
    "post_order_itr(t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "xby2wNCs1Xxj"
   },
   "source": [
    "#### **DFS-Tree (Levels)**\n",
    "* Time complexity - O(N)\n",
    "* Space complexity - O(logN)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "sMBwEkjb1cQ0"
   },
   "outputs": [],
   "source": [
    "def dfs_level_main(root):\n",
    "  result = []\n",
    "  dfs_level(root, 0, result)\n",
    "  return result\n",
    "\n",
    "def dfs_level(root, level, result):\n",
    "  if root:\n",
    "    if level == len(result):\n",
    "      result.append([root.data])\n",
    "    else:\n",
    "      result[level].append(root.data)\n",
    "\n",
    "    dfs_level(root.left, level+1, result)\n",
    "    dfs_level(root.right, level+1, result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "-4ipH2Ya2SQE",
    "outputId": "01486a0c-5130-4757-afab-1fdd0636960b"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1], [2, 3], [4, 5, 6, 7]]"
      ]
     },
     "execution_count": 14,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dfs_level_main(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "h6NFq15Wgvco"
   },
   "source": [
    "#### **DFS-Graph**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "Qmkctb0ng0mr"
   },
   "outputs": [],
   "source": [
    "def dfs_graph_itr(node):\n",
    "  stack, visited = [], set()\n",
    "  stack.append(node)\n",
    "  visited.add(node)\n",
    "\n",
    "  while stack:\n",
    "    curr = stack.pop()\n",
    "    print(curr.data)\n",
    "\n",
    "    for adj in curr.adjList:\n",
    "      if adj not in visited:\n",
    "        visited.add(adj)\n",
    "        stack.append(adj)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 119
    },
    "colab_type": "code",
    "id": "Y837pi49hcsq",
    "outputId": "b8c574b5-85f3-46ff-e835-e736ff74da83"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "4\n",
      "5\n",
      "3\n",
      "6\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "class Node:\n",
    "  def __init__(self, data):\n",
    "    self.data = data\n",
    "    self.adjList = []\n",
    "'''\n",
    "    5\n",
    "    |\n",
    "    4\n",
    "  / | \\\n",
    "2 - 1 - 3 - 6\n",
    "\n",
    "'''\n",
    "\n",
    "one, two, three, four, five, six = Node(1), Node(2), Node(3), Node(4), Node(5), Node(6)\n",
    "one.adjList = [two, three, four]\n",
    "two.adjList = [one, four]\n",
    "three.adjList = [one, four, six]\n",
    "four.adjList = [one, two, three, five]\n",
    "\n",
    "dfs_graph_dir(one)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "ajSApHX5iYow"
   },
   "outputs": [],
   "source": [
    "def dfs_rec_main(node):\n",
    "  visited = set()\n",
    "  visited.add(node)\n",
    "  dfs_graph_rec(node, visited)\n",
    "\n",
    "def dfs_graph_rec(node, visited):\n",
    "  print(node.data)\n",
    "  # the iteration is reversed to obtain the same result above\n",
    "  for adj in reversed(node.adjList):\n",
    "    if adj not in visited:\n",
    "      visited.add(adj)\n",
    "      dfs_graph_rec(adj, visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 119
    },
    "colab_type": "code",
    "id": "FJ-MNu6ejDb-",
    "outputId": "1aa15d51-13fa-4571-ea73-5b098766eba2"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "4\n",
      "5\n",
      "3\n",
      "6\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "dfs_rec_main(one)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "BU9FezB-Fc8G"
   },
   "source": [
    "#### **DFS Find Cycle (Directed)**\n",
    "\n",
    "In the following codes \n",
    "* **explore():** return True if there is cycle\n",
    "* **dfs functions:** finds the nodes do not have cycle on their path.\n",
    "* Taken from the [leetcode question](https://leetcode.com/problems/find-eventual-safe-states/)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "T-DahW1JG8PM"
   },
   "source": [
    "##### **Coloring**\n",
    "* **White (0):** The vertices that are not explore yet.\n",
    "* **Gray (1):** The verticies in process.\n",
    "* **Black (2):** The vertices which DFS completed\n",
    "* **Cycle Detection:** Encountering with a gray vertex (already in progress) means that there is a cycle.\n",
    "* Time complexity - O(V+E)\n",
    "* Space complexity - O(V) (maximum depth / also visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "4NChFR33IENK"
   },
   "outputs": [],
   "source": [
    "def dfs_cycle_coloring(graph):\n",
    "  def explore(node):\n",
    "\n",
    "    # started exploring\n",
    "    colors[node] = 1\n",
    "\n",
    "    for adj in graph[node]:\n",
    "      # first part: already explored node\n",
    "      # second part: not explored yet, but it has cycle \n",
    "      if colors[adj] == 1 or (colors[adj] == 0 and explore(adj)):\n",
    "        return True\n",
    "    \n",
    "    # the node achieve to complete dfs (no cycle)\n",
    "    colors[node] = 2\n",
    "    result.append(node)\n",
    "    return False\n",
    "\n",
    "  length = len(graph)\n",
    "  colors = [0 for _ in range(length)]\n",
    "  result = []\n",
    "  \n",
    "  for i in range(length):  \n",
    "    # not explored node\n",
    "    if colors[i] == 0:\n",
    "      explore(i)\n",
    "  # returns the nodes do not lead to a cycle\n",
    "  return sorted(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 33
    },
    "colab_type": "code",
    "id": "7nqV-V-9Nk6c",
    "outputId": "abfecd08-0d46-4ead-8275-9c64c9d6d58d"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 4, 5, 6]"
      ]
     },
     "execution_count": 70,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph = [[1,2],[2,3],[5],[0],[5],[],[]]\n",
    "\n",
    "dfs_cycle_coloring(graph)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "0nFMmWQe7VOc"
   },
   "source": [
    "#### **DFS Print Cycles (Undirected)**\n",
    "\n",
    "* Color each vertex based on cycle coloring\n",
    "  * 0 - not explored\n",
    "  * 1 - exploring\n",
    "  * 2 - completed\n",
    "* If a cycle is found\n",
    "  * increase cycle number\n",
    "  * add all parents to the cycle number\n",
    "* If no cycle\n",
    "  * assign parent and continue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "em-dzVN17fLN"
   },
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "# global cycle variable\n",
    "\n",
    "def print_cycles(graph):\n",
    "\n",
    "  def explore(node, parent):\n",
    "    nonlocal cyc_num\n",
    "    # already completed\n",
    "    if colors[node] == 2:\n",
    "      return \n",
    "\n",
    "    # cycle detected\n",
    "    elif colors[node] == 1:\n",
    "      cyc_num += 1\n",
    "      current = parent\n",
    "      result[cyc_num].append(current)\n",
    "\n",
    "      # mark the nodes\n",
    "      while current != node:\n",
    "        current = parents[current]\n",
    "        result[cyc_num].append(current)\n",
    "\n",
    "    else:\n",
    "      parents[node] = parent\n",
    "      colors[node] = 1\n",
    "\n",
    "      for adj in graph[node]:\n",
    "        \n",
    "        # do not go to parent as it is an undirected graph we need to \n",
    "        # check this\n",
    "        if adj != parents[node]:\n",
    "          explore(adj, node)\n",
    "\n",
    "      colors[node] = 2\n",
    "\n",
    "  \n",
    "  # main part\n",
    "  N = len(graph)\n",
    "  colors = [0 for _ in range(N)]\n",
    "  parents = [-1 for _ in range(N)]\n",
    "  result = defaultdict(list)[[1], [0, 2], [1, 3, 4], [2, 5, 6], [2, 5, 8], [3, 4, 9], [3, 7], [6], [4], [5, 10], [9, 11, 12], [10, 12], [10, 11], [14], [15], [16], [13]]\n",
    "\n",
    "  cyc_num = 0\n",
    "\n",
    "  # this can be explored many times for disconnected graph\n",
    "  for n in range(N):\n",
    "    if colors[n] == 0:\n",
    "      #print(n)\n",
    "      explore(1, 0)\n",
    "  print(result)\n",
    "  #print(mark)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 33
    },
    "colab_type": "code",
    "id": "SWzaiC0v9k3c",
    "outputId": "0a7db10c-b652-4f22-fe85-c0f38751d247"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "defaultdict(<class 'list'>, {1: [4, 5, 3, 2], 2: [12, 11, 10], 3: [13, 16, 15, 14]})\n"
     ]
    }
   ],
   "source": [
    "graph = [[1], [0, 2], [1, 3, 4], [2, 5, 6], [2, 5, 8], [3, 4, 9], [3, 7], [6], [4], [5, 10], [9, 11, 12], [10, 12], [10, 11,14], [14], [15], [16], [13]]\n",
    "print_cycles(graph)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "hTsZntlsXSO0"
   },
   "source": [
    "#### **Articulation Points(Cut Vertices) and Edges(Bridges)**\n",
    "\n",
    "Articulation point is the point when it is removed, the # of connected components increase in the graph. \n",
    "\n",
    "**Algorithm**\n",
    "* Rank all the nodes along dfs traversal\n",
    "* During the traversal the following two condition indicates articulation point\n",
    "  * root node (start of traversal) with at least 2 children\n",
    "  * any node(u) whose child (v) cannot go any upper ancestor than the parent\n",
    "    \n",
    "    `low[v] >= rank[u]`\n",
    "* Time complexity - O(V+E)\n",
    "* Space complexity - O(V)\n",
    "* Source code is from [geeksforgeek](https://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/)\n",
    "\n",
    "![alt text](https://drive.google.com/uc?id=1sPDtLPqqUp5161yJGMc-N538uQrxtXug)\n",
    "![alt text](https://drive.google.com/uc?id=1GSjwi9ozvVgePVky4VydVXRPCGnrTTcl)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "tnwQSBI4XWwh"
   },
   "outputs": [],
   "source": [
    "def articulation(graph):\n",
    "    \n",
    "  def explore(u):  \n",
    "    nonlocal time\n",
    "\n",
    "    visited[u] = True\n",
    "    rank[u] = time\n",
    "    time += 1\n",
    "\n",
    "    children = 0\n",
    "    for v in graph[u]:\n",
    "      if not visited[v]:\n",
    "        parent[v] = u\n",
    "        children += 1\n",
    "\n",
    "        # find the articulation recursively\n",
    "        explore(v)\n",
    "\n",
    "        # update low in case a lower found\n",
    "        low[u] = min(low[u], low[v])\n",
    "\n",
    "        # art node\n",
    "        # (1) root has at least 2 children\n",
    "        if parent[u] == -1 and children > 1:\n",
    "          art_nodes.append(u)\n",
    "\n",
    "        # (2) if child cannot go lower rank than parent, then parent is articulation\n",
    "        if parent[u] != -1 and low[v] >= rank[u]:\n",
    "          art_nodes.append(u)\n",
    "\n",
    "        # art edge\n",
    "        if low[v] > rank[u]:\n",
    "          art_edges.append((u,v ))\n",
    "      \n",
    "      # cycle found       \n",
    "      else:\n",
    "\n",
    "          # not immediate parent\n",
    "          if v != parent[u]:\n",
    "            low[u] = min(low[u], rank[v])\n",
    "            \n",
    "  N = len(graph)\n",
    "  rank = [float('inf') for _ in range(N)]\n",
    "  low = [float('inf') for _ in range(N)]\n",
    "  parent = [-1 for _ in range(N)]\n",
    "  visited = [False for _ in range(N)]\n",
    "  time = 0\n",
    "\n",
    "  art_nodes, art_edges = [], []\n",
    "\n",
    "  for i in range(N):\n",
    "    if not visited[i]:\n",
    "      explore(i)\n",
    "  \n",
    "  if art_nodes:\n",
    "    print('Art Nodes', art_nodes)\n",
    "  \n",
    "  if art_edges:\n",
    "    print('Art Edges', art_edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 50
    },
    "colab_type": "code",
    "id": "m93gv45b9tQM",
    "outputId": "061381e3-d771-47df-e07c-a93ce3e5f683"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Art Nodes [6, 2]\n",
      "Art Edges [(2, 6)]\n"
     ]
    }
   ],
   "source": [
    "graph_node = [[1, 3], [0, 2], [1, 3, 4, 5], [0, 2], [2, 5], [2, 4]]\n",
    "graph_edge = [[1, 3], [0, 2], [1, 3, 6], [0, 2], [5, 6], [4, 6], [2, 4, 5]]\n",
    "\n",
    "articulation(graph_edge)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "qm7WxqVvsV6a"
   },
   "source": [
    "### **Dijkstra**\n",
    "Finds the shortest path from a source node to all other nodes. Algorithm is defined as follows:\n",
    "* Create a distance dictionary showing the distance of all nodes to the source.\n",
    "* At the beginning all values are initialized as infinity, whereas source is initialized as 0.\n",
    "* Apply the following two until there is no node left to be investigated:\n",
    "  * Choose the node with shortest distance in unvisited nodes.\n",
    "  * Improve adjacent nodes' distances.\n",
    "\n",
    "The code is created based on [LC743 - Network Delay Time](https://leetcode.com/problems/network-delay-time/).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "IYuuu4G3lbhH"
   },
   "source": [
    "#### **Dictionary**\n",
    "* Time complexity - O(V^2)\n",
    "\n",
    "**Method**\n",
    "* A distance dictionary is initialized to show each node's distance to the source node. (all values are inf at the beginning)\n",
    "* The distance of source node to itself is set as 0.\n",
    "* Afterwards the following is done iteratively:\n",
    "  * Choose the unvisited node with smallest distance to the source.\n",
    "  * Update all distances of the neighbors if they are improved.\n",
    "* Continue this until there is no node left to investigate."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "TqPsQRDBIIve"
   },
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "def dijkstra(graph, num, source):\n",
    "\n",
    "  adj_list = {n: [] for n in range(1, num+1)}\n",
    "  distance = {n: float('inf') for n in range(1, num+1)}\n",
    "  visited = {n: False for n in range(1, num+1)}\n",
    "\n",
    "  for s, d, w in graph:\n",
    "    adj_list[s].append((d, w))\n",
    "\n",
    "  distance[source] = 0\n",
    "  \n",
    "  while True:\n",
    "    cnum, cval = -1, float('inf')\n",
    "\n",
    "    # find the min unvisited value\n",
    "    for n in range(1, num+1):\n",
    "      if not visited[n]:\n",
    "        if cval > distance[n]:\n",
    "          cval = distance[n]\n",
    "          cnum = n\n",
    "\n",
    "    # nothing left to be improved\n",
    "    if cnum == -1:\n",
    "      break\n",
    "\n",
    "    visited[cnum] = True\n",
    "\n",
    "    # improve the distace\n",
    "    for adj, dist in adj_list[cnum]:\n",
    "      distance[adj] = min(distance[adj], distance[cnum] + dist)\n",
    "\n",
    "  # furthest point to the source\n",
    "  furthest = max(distance.values())\n",
    "  return -1 if furthest == float('inf') else furthest\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 33
    },
    "colab_type": "code",
    "id": "1-AwzHL4mgnO",
    "outputId": "a60a4a50-af62-4cac-f7a4-4ecc36f67800"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 14,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph = [[1, 2, 1], [1, 2, 2], [1,2,3], [2, 3, 4], [2, 3, 1], [2, 3, 2]]\n",
    "\n",
    "dijkstra(graph, 3, 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "ODTfFL265E_T"
   },
   "source": [
    "#### **Priority Queue**\n",
    "* Time complexity -  O(ElogV+V).\n",
    "  - O(V) - each node is visited once\n",
    "  - O(ElogV) - pop from and push to the queue\n",
    "  - Explanation on the [link](https://cs.stackexchange.com/questions/104566/dijkstra-complexity-analysis-using-adjacency-list-and-priority-queue#:~:text=Dijkstra's%20algorithm%20visits%20every%20node,in%20O(logV).).\n",
    "\n",
    "\n",
    "* The code is inspired from [this link](https://codereview.stackexchange.com/questions/79025/dijkstras-algorithm-in-python).\n",
    "\n",
    "**Method**\n",
    "* A distance dictionary is initialized to show each node's distance to the source node. (all values are inf at the beginning)\n",
    "* A heap is created to choose next shortest distance and it keeps node and distance to the corresponding node.\n",
    "* While heap becomes empty:\n",
    "  * Pop the element from heap\n",
    "  * If the distance of the current element is inf, it means that current element is not visited. We update its distance to current distance.\n",
    "  * Push the unvisited nodes (dist=inf) to the heap.\n",
    "  * Also the [following link](https://leetcode.com/problems/network-delay-time/discuss/187713/Python-concise-queue-and-heap-solutions) provides good intuation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "Rpr0vogT52Ev"
   },
   "outputs": [],
   "source": [
    "from heapq import *\n",
    "from collections import defaultdict\n",
    "\n",
    "def dijkstra_pq(graph, num, source):\n",
    "\n",
    "        \n",
    "  # create adjList\n",
    "  adjList = defaultdict(list)\n",
    "  for s, d, l in graph:\n",
    "      adjList[s].append((d, l))\n",
    "\n",
    "  # create dist array\n",
    "  dist = {n:float('inf') for n in range(1, num+1)}\n",
    "\n",
    "  heap = []\n",
    "  heappush(heap, (0, source))\n",
    "\n",
    "  while heap:\n",
    "      path_len, node = heappop(heap)\n",
    "\n",
    "      if dist[node] == float('inf'):\n",
    "          dist[node] = path_len\n",
    "\n",
    "          for adj, adj_len in adjList[node]:\n",
    "\n",
    "              # push to the heap but we are not sure if it is the min yet\n",
    "              if dist[adj] == float('inf'):\n",
    "                  heappush(heap, (path_len+adj_len, adj))\n",
    "\n",
    "  # print(dist)\n",
    "\n",
    "  furthest = max(dist.values())\n",
    "\n",
    "  return furthest if furthest < float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "R3XAH0T5oZbn",
    "outputId": "b627c595-a9d2-4308-9b84-54bcd4143f74"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 18,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph = [[1, 2, 1], [1, 2, 2], [1,2,3], [2, 3, 4], [2, 3, 1], [2, 3, 2]]\n",
    "\n",
    "dijkstra_pq(graph, 3, 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Qc_NIptfUPjp"
   },
   "source": [
    "**Example Question:** There are N network nodes, labelled 1 to N.\n",
    "\n",
    "Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.\n",
    "\n",
    "Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 33
    },
    "colab_type": "code",
    "id": "rn54Uic7IaJj",
    "outputId": "5122cc60-2ea7-40a4-9061-cef56767a218"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 3,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "arr = [[2,1,1],[2,3,1],[3,4,1]]\n",
    "N = 4\n",
    "K = 2\n",
    "\n",
    "dijkstra(arr, 4, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "0RKyKN9orzF4"
   },
   "source": [
    "### **Topological Sort**\n",
    "* Create one list, one dict\n",
    " * list - holds # of incoming edges\n",
    " * hashmap - holds adjacent nodes\n",
    " * count each edge\n",
    "* Collect the nodes with 0 incoming edges in stack.\n",
    "* Pop nodes with 0 incoming edges\n",
    "* Update the nodes with connections\n",
    "* Append new nodes with 0 incoming edges\n",
    "* Count removed edges. If it is equal to the whole edges, then there is no cycle\n",
    "\n",
    "**Complexities**\n",
    "* Time complexity - O(V+E)\n",
    "* Space complexity - O(V)\n",
    "\n",
    "**NOTE:** If you append the popped items from the stack to a list you will obtain **TOPOLOGICAL SORT**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "snTMbLKnr3MJ"
   },
   "outputs": [],
   "source": [
    "def isDAG(graph):\n",
    "\n",
    "    N, edges = len(graph), 0\n",
    "    \n",
    "    # in-coming edges\n",
    "    incoming = [0 for i in range(N)]\n",
    "        \n",
    "    # fill incoming edges\n",
    "    for s, adjs in enumerate(graph):\n",
    "        for d in adjs:\n",
    "          incoming[d] += 1\n",
    "          edges += 1\n",
    "\n",
    "    # select nodes with no incoming edges\n",
    "    noincoming = [node for node in range(N) if incoming[node] == 0]\n",
    "            \n",
    "    # while incoming edges are not empty\n",
    "    while noincoming:\n",
    "        curr = noincoming.pop()\n",
    "        \n",
    "        for adj in graph[curr]:\n",
    "            incoming[adj] -= 1\n",
    "            edges -= 1\n",
    "            \n",
    "            if incoming[adj] == 0:\n",
    "                noincoming.append(adj)\n",
    "                \n",
    "    return edges == 0          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 33
    },
    "colab_type": "code",
    "id": "0AbtxM_EsoEa",
    "outputId": "b8ebf34a-f4a9-4f53-8b97-4d5026fe0aa7"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 25,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph = [[1, 2, 3], [2], [], [], [1, 3]]\n",
    "isDAG(graph)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "PGuQkdnWXXm6"
   },
   "source": [
    "### **Notes about Graph Traversal**\n",
    "* If the shortest path is asked, use BFS\n",
    "* For DFS memoization, make sure to use correct variables in your memo array. Even if the same variables could have different effect as variable causes different changes in the graph.\n",
    "* For BFS also check carefully which elements should be in visited set/matrix or queue.\n",
    "* For DP as well, choose the variables correctly, do not forget changing state of the matrix etc."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "QMBuCMA8s1-M"
   },
   "source": [
    "# **5. Collections, List and Iteratives**\n",
    "\n",
    "The complexities can be found in [python wiki](https://wiki.python.org/moin/TimeComplexity)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "4XQ8z0b2tdiq"
   },
   "source": [
    "### **a) collections**\n",
    "\n",
    "collection library provides alternative for built-in containers such as dict, list, set and tuple. Check the [doc](https://docs.python.org/3/library/collections.html) for more info."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "1hxmBp-At2Pk"
   },
   "source": [
    "#### **defaultdict:** \n",
    "Creates dict where default list is created when first item added"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "bTI0ZV7BuDSw",
    "outputId": "40d383de-e35b-4c61-db4c-ff05392cd3b1"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defaultdict(list, {'trala': [1]})"
      ]
     },
     "execution_count": 95,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "d = defaultdict(list)\n",
    "d['trala'].append(1)\n",
    "d"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "6FXJ61_JuNYs"
   },
   "source": [
    "#### **Counter:** \n",
    "Creates a dictionary where key is the list elements and the value is number of these elements in the list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "tnCyq_7puZG2",
    "outputId": "f121bd73-9f22-494b-95fe-71acb76543d1"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({1: 3, 2: 1, 3: 1, 4: 1})"
      ]
     },
     "execution_count": 96,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import Counter\n",
    "\n",
    "l = [1, 2, 1, 3, 4, 1]\n",
    "d = Counter(l)\n",
    "\n",
    "d"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "PjCKf7LRsZw9"
   },
   "source": [
    "#### **deque**\n",
    "\n",
    "Works as a queue."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "0-TGOnmfsquK",
    "outputId": "74396567-3948-46ee-df8e-39d66c796da9"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 2,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import deque\n",
    "\n",
    "queue = deque()\n",
    "queue.append(1)\n",
    "queue.append(2)\n",
    "queue.popleft()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "yodYj7IrxAN2"
   },
   "source": [
    "### **b) queue**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "wiCYeYzexGk6"
   },
   "source": [
    "#### **PriorityQueue**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 68
    },
    "colab_type": "code",
    "id": "7yffRncMxK50",
    "outputId": "da05ae27-732c-4527-cd15-87ab4d6814bc"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "3\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "from queue import PriorityQueue\n",
    "\n",
    "pq = PriorityQueue()\n",
    "\n",
    "pq.put(3)\n",
    "pq.put(5)\n",
    "pq.put(1)\n",
    "\n",
    "print(pq.get())\n",
    "print(pq.get())\n",
    "print(pq.get())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "-1eA_oLdxWJq"
   },
   "source": [
    "### **c) heapq**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 121
    },
    "colab_type": "code",
    "id": "-MYDXCVyxZgx",
    "outputId": "435b185a-837b-4df8-a022-d220964fac50"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "original heap [2, 3, 6, 9, 5]\n",
      "min popped 2 [3, 5, 6, 9]\n",
      "min popped 3 [5, 9, 6]\n",
      "new heap [1, 5, 3, 10, 9, 6, 4]\n",
      "5 removed [1, 3, 10, 9, 6, 4]\n",
      "heapified [1, 3, 4, 9, 6, 10]\n"
     ]
    }
   ],
   "source": [
    "from heapq import heapify, heappush, heappop \n",
    "\n",
    "# Creating empty heap \n",
    "heap = [] \n",
    "heapify(heap) \n",
    "  \n",
    "# Adding items to the heap using heappush function \n",
    "heappush(heap, 9) \n",
    "heappush(heap, 6) \n",
    "heappush(heap, 5) \n",
    "heappush(heap, 2)\n",
    "heappush(heap, 3)\n",
    "print('original heap', heap)\n",
    "\n",
    "element = heappop(heap)\n",
    "print('min popped', element, heap)\n",
    "element = heappop(heap)\n",
    "print('min popped', element, heap)\n",
    "\n",
    "heappush(heap, 10)\n",
    "heappush(heap, 1)\n",
    "heappush(heap, 4)\n",
    "heappush(heap, 3)\n",
    "print('new heap', heap)\n",
    "\n",
    "heap.remove(5)\n",
    "print('5 removed', heap)\n",
    "heapify(heap)\n",
    "print('heapified', heap)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "CkoyTcAuSD96"
   },
   "source": [
    "**Largest Element in a Heap**\n",
    "\n",
    "**nlargest(k, iterable, key = fun):** This function is used to return the k largest elements from the iterable specified and satisfying the key if mentioned."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 82
    },
    "colab_type": "code",
    "id": "pk22WCumxgCG",
    "outputId": "b4429bdc-8daa-4d37-eff1-defa9b467359"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "biggest 2 items [6, 6]\n",
      "Counter({6: 4, 5: 3, 3: 2, 2: 2, 1: 1, 4: 1})\n",
      "4\n",
      "[6, 5]\n"
     ]
    }
   ],
   "source": [
    "import heapq\n",
    "from collections import Counter\n",
    "\n",
    "nums, k = [3,2,3,1,2,4,5,5,5, 6, 6, 6, 6], 2\n",
    "\n",
    "print('biggest ' + str(k) + ' items', heapq.nlargest(k, nums))\n",
    "\n",
    "counts = Counter(nums)\n",
    "print(counts)\n",
    "print(counts.get(6))\n",
    "# return keys, orders based on the values\n",
    "print(heapq.nlargest(k, counts.keys(), key=counts.get))\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "o9bBa3re0YfF"
   },
   "source": [
    "**nsmallest(k, iterable, key=fun)** Return k smallest element of the iterable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "dxQY9Ylj0jRe",
    "outputId": "febe590d-e965-412c-a308-2026a33d38ac"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['i', 'love']"
      ]
     },
     "execution_count": 4,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import Counter\n",
    "import heapq\n",
    "function\n",
    "# get the most frequent words in increasing alphabetical order in case of same frequency\n",
    "words = [\"i\", \"love\", \"leetcode\", \"i\", \"love\", \"coding\"]\n",
    "k = 2\n",
    "\n",
    "Freqs = Counter(words)\n",
    "heapq.nsmallest(k, Freqs,\n",
    "    key=lambda word:(~Freqs[word], word)\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "SfcncBI7OXc2"
   },
   "source": [
    "### **d)bisect**\n",
    "Maintaining a list in sorted order without having to sort the list after each insertion.\n",
    "* **insort(list, x):** Finds the correct place for the num to be added and keeps the array sorted. It works in O(N) complexity.\n",
    "* **bisect(list, x):** Returns the index where x should be. The index is the index after the biggest smaller element."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 52
    },
    "colab_type": "code",
    "id": "H1GiFOoqQLyo",
    "outputId": "a6fb79c1-ce68-4424-ce75-3ccd21d79f40"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 5, 6, 7, 8]\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "from bisect import *\n",
    "\n",
    "nums = [2, 5, 7, 8]\n",
    "insort(nums, 6)\n",
    "print(nums)\n",
    "\n",
    "print(bisect(nums, 4))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "u8nRwKfVutF8"
   },
   "source": [
    "### **e) More Info**\n",
    "\n",
    "These includes useful information and structures to ease the solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "80NF3soYu3jW"
   },
   "source": [
    "#### **min/max values**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "QkDdo_BwwrWp",
    "outputId": "6925054b-8cd8-4137-b288-05fab760432e"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "inf"
      ]
     },
     "execution_count": 97,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# min\n",
    "float('-inf')\n",
    "\n",
    "# max\n",
    "float('inf')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "P8DNMNocSeH-",
    "outputId": "6807dacf-b7b1-49d6-e0a7-7a4894cb0630"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "inf"
      ]
     },
     "execution_count": 1,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "float('inf')+1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "412CXl7NwzRQ"
   },
   "source": [
    "#### **Assign a default value to key**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "wnfzs9nvw4nL",
    "outputId": "e02cf494-3d1f-4ee8-e199-0d81d8a78cbf"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': 1}"
      ]
     },
     "execution_count": 98,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d = {}\n",
    "\n",
    "d['a'] = d.get('a', 0) + 1 \n",
    "d"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "_0eEuu-hxoOF"
   },
   "source": [
    "#### **reversed/sorted vs reverse/sort**\n",
    "\n",
    "* sort() and reverse()\n",
    "  * list \n",
    "  * in-place\n",
    "* sorted() and reversed()\n",
    "  * list & string\n",
    "  * returns the result as **list**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 51
    },
    "colab_type": "code",
    "id": "ZLJnZoLhxtQo",
    "outputId": "dfe0f71c-b7c6-486d-c5a4-fa4b276abd16"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4]\n",
      "[4, 3, 2, 1]\n"
     ]
    }
   ],
   "source": [
    "# sort() and reverse() functions can be only used for the lists, not the strings. They apply the operations IN-PLACE\n",
    "\n",
    "l = [1, 4, 2, 3]\n",
    "l.sort()\n",
    "print(l)\n",
    "\n",
    "l.reverse()\n",
    "print(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 85
    },
    "colab_type": "code",
    "id": "bRzYl1nCxwkM",
    "outputId": "7140b4f7-d96d-4d85-da95-da10677247f6"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4]\n",
      "['1', '2', '3', '4']\n",
      "[3, 2, 4, 1]\n",
      "['3', '2', '4', '1']\n"
     ]
    }
   ],
   "source": [
    "# sorted() and reversed() functions can be applied on both lists and strings. They return back the list of resulting operation. They do not cause IN-PLACE changes\n",
    "\n",
    "l = [1, 4, 2, 3]\n",
    "s = '1423'\n",
    "\n",
    "print(sorted(l))\n",
    "print(sorted(s))\n",
    "\n",
    "print(list(reversed(l)))\n",
    "print(list(reversed(s)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "F90Fcw8ASmF5"
   },
   "source": [
    "#### **Check if a stack or queue empty**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 82
    },
    "colab_type": "code",
    "id": "IKc9VVLoSscP",
    "outputId": "f77df30a-4a51-4e16-b8e7-d732b197411f"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "empty stack\n",
      "not empty stack\n",
      "empty queue\n",
      "non empty queue\n"
     ]
    }
   ],
   "source": [
    "from collections import deque\n",
    "stack, queue = [], deque()\n",
    "\n",
    "if not stack:\n",
    "  print('empty stack')\n",
    "\n",
    "stack.append('z')\n",
    "if stack:\n",
    "  print('not empty stack')\n",
    "\n",
    "if not queue:\n",
    "  print('empty queue')\n",
    "  \n",
    "queue.append('ray')\n",
    "\n",
    "if queue:\n",
    "  print('non empty queue')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "JJi5IVV2NUMw"
   },
   "source": [
    "#### **Check digit and character**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "ZtJskoPyNYN0",
    "outputId": "0a7df87a-cc22-45bd-d906-374c8505a922"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 1,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "digit = '12'\n",
    "digit.isdigit()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "uKxkKqXoNnO4",
    "outputId": "03213957-d218-4704-905a-bf6a7098a8e3"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 2,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "character = 'a'\n",
    "character.isalpha()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "KF7uVLLHNtti",
    "outputId": "4054503b-cec4-4c3e-fee6-1650c5e8baa7"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 3,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "digit.isalpha()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "IIiMGqsCQh1K"
   },
   "source": [
    "#### **Random Number**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "J0rOCrp3QkXM",
    "outputId": "fb634f2a-2a23-4fc5-f1d0-c1d82bfc245c"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 7,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from random import randint\n",
    "\n",
    "# a number btw 1 and 5 both are included\n",
    "num = randint(1, 5)\n",
    "num"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "ltPokKKScGEJ"
   },
   "source": [
    "#### **bin(num)**\n",
    "\n",
    "bin(num) returns the binary representation of the number with 0b at the beginning."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 52
    },
    "colab_type": "code",
    "id": "li3X6iw0cO9A",
    "outputId": "3567fef6-32c9-4466-d587-bdff42c96fcd"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0b11\n",
      "0b100\n"
     ]
    }
   ],
   "source": [
    "# 3 - 11\n",
    "print(bin(3))\n",
    "\n",
    "# 4 - 100\n",
    "print(bin(4))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "1kJwObIncka9"
   },
   "source": [
    "#### **all(boolean list)**\n",
    "\n",
    "Similar to sum, abs, max or min. It returns true if all items in the list are True."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 52
    },
    "colab_type": "code",
    "id": "i78sfo0wcwLE",
    "outputId": "e12f1614-4c3c-4a8f-cd06-4920ddeb2edf"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "all true, True\n",
      "not all true, False\n"
     ]
    }
   ],
   "source": [
    "all_true = [True, True, True]\n",
    "print('all true,', all(all_true))\n",
    "\n",
    "not_all_true = [True, False, True]\n",
    "print('not all true,', all(not_all_true))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "vZFweHWy9aUY"
   },
   "source": [
    "### **e) Iterables, Generators, Yield**\n",
    "\n",
    "The following explanation is taken from [this link](https://pythontips.com/2013/09/29/the-python-yield-keyword-explained/)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "f5S-wZDwhCkb"
   },
   "source": [
    "#### **Iterables**\n",
    "* Everything can be used with **for..in..** form is iterable.\n",
    "* Iterables can be read more than once\n",
    "* Examples: lists, strings, files\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 102
    },
    "colab_type": "code",
    "id": "-uTyjWcb9iwE",
    "outputId": "1f30a6f1-0e78-4aa9-fe0b-3dbff63129cd"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "4\n",
      "9\n",
      "16\n"
     ]
    }
   ],
   "source": [
    "iterable = [x*x for x in range(5)]\n",
    "for num in iterable:\n",
    "  print(num)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "3zNNjR9Yic30"
   },
   "source": [
    "#### **Generators**\n",
    "* Generators are iterators.\n",
    "* The calues are not stored on the memory and generated on the fly. For this reason, it is iteratable once."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 102
    },
    "colab_type": "code",
    "id": "gba8oQRjjUTl",
    "outputId": "32e91f59-a290-4554-ccab-58f3e3ee15ac"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "4\n",
      "9\n",
      "16\n"
     ]
    }
   ],
   "source": [
    "generator = (x*x for x in range(5))\n",
    "for num in generator:\n",
    "  print(num)\n",
    "\n",
    "for z in generator:\n",
    "  print('ray', z)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "_bvXe9yujwU0"
   },
   "source": [
    "#### **Yield**\n",
    "* It is used like return\n",
    "* Different from return, yield returns a generator"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 102
    },
    "colab_type": "code",
    "id": "lwQ8Gj7pkF-y",
    "outputId": "d5df1f3f-4b60-488f-be50-84e5e9b81fc6"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "4\n",
      "9\n",
      "16\n"
     ]
    }
   ],
   "source": [
    "def createGenerator():\n",
    "  nums = range(5)\n",
    "  for i in nums:\n",
    "    yield i*i\n",
    "\n",
    "generator = createGenerator()\n",
    "for i in generator:\n",
    "  print(i)\n",
    "\n",
    "for z in generator:\n",
    "  print(z)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "nI3wkwaEyVbH"
   },
   "source": [
    "# **6. Recursion, Backtracking and Dynamic Programming**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "W5RLkxW03mTZ"
   },
   "source": [
    "### **a) Recursion**\n",
    "\n",
    "**1. Bottom-Up Approach**\n",
    "\n",
    "* The most intuitive.\n",
    "* Find the straightforward solution for the **simple case** such as 1 element.\n",
    "* Find the way to **build the solution from previous case**.\n",
    "* Backtracking problems (the key idea is the structure of date should not change after execution for different values.)\n",
    "\n",
    "\n",
    "**2. Top-Down Approach**\n",
    "* More complex, less concrete.\n",
    "* Find the way to divide the problem to **N subproblems**.\n",
    "\n",
    "**3. Half-and-Half Approach**\n",
    "* Binary search and merge sort is an example.\n",
    "* Recursively work on halves by choosing (binary search) or together (merge sort).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "3KRMKcas4y35",
    "outputId": "2d72b200-b362-49fe-99c9-f83fccd5ac55"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "13"
      ]
     },
     "execution_count": 106,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def fibRec(n):\n",
    "  if n == 0:\n",
    "    return 0\n",
    "  elif n ==1:\n",
    "    return 1\n",
    "  else:\n",
    "    return fibRec(n-1) + fibRec(n-2)\n",
    "\n",
    "fibRec(7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "2paTVsTspw2x"
   },
   "source": [
    "### **b) Backtracking**\n",
    "\n",
    "Finding all or some solutions to some computatinal problems by incrementally building solutions from candidates. (compute all and generate all questions)\n",
    "\n",
    "**Properties**\n",
    "1. **No repetition and missing elements in result:** Backtrack for complete solution.\n",
    "2. **Search pruning:** Evaluate on the way if the current candidate will not lead a valid solution\n",
    "\n",
    "**NOTE:** Recursion complexity is mostly $O(branches^{depth})$.\n",
    "\n",
    "![GENERAL FPRMULA](https://drive.google.com/uc?id=1cGL8uoaEtlPCEtheU0anNwSVn2FHUl2L)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "DbXgzLPj431f"
   },
   "source": [
    "### **c) Dynamic Programming**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "AUQEl4Gl480_"
   },
   "source": [
    "#### **Top-Down (Memoization)**\n",
    "* Applied on the recursion problems for repetative parts (improves the complexity).\n",
    "* Memoization is done based on the variables that determine base cases. **It is i in this case.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 52
    },
    "colab_type": "code",
    "id": "pK2qIhCT5kk-",
    "outputId": "1f80ce0a-7300-4ea0-ab09-29de76aa3ebb"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 1, 2, 3, 5, 8, 13]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "13"
      ]
     },
     "execution_count": 5,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def fib_top_down_main(n):\n",
    "  memo = [None for i in range(n+1)]\n",
    "  res = fib_top_down(n, memo)\n",
    "  print(memo)\n",
    "  return res\n",
    "\n",
    "def fib_top_down(i, memo):\n",
    "\n",
    "  # base cases\n",
    "  if i == 0:\n",
    "    return 0\n",
    "  elif i ==1:\n",
    "    return 1\n",
    "\n",
    "  # memoization\n",
    "  elif memo[i] is not None:\n",
    "    return memo[i]\n",
    "    \n",
    "  # recursion\n",
    "  else:\n",
    "    memo[i] = fib_top_down(i-1, memo) + fib_top_down(i-2, memo)\n",
    "    return memo[i]\n",
    "\n",
    "\n",
    "# 0-1-1-2-3-5-8-13-21\n",
    "# 0 1 2 3 4 5 6  7 \n",
    "\n",
    "fib_top_down_main(7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "FCJxGEB35mWC"
   },
   "source": [
    "#### **Bottom-Up**\n",
    "Bottom-up approach fills the memo array from zero till the end."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "7CuySAL68EFb",
    "outputId": "4745f0a3-48b7-47f0-c0a6-08ff8ffa4fca"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "13"
      ]
     },
     "execution_count": 6,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def fib_bottom_up(n):\n",
    "  dp = [None for i in range(n+1)]\n",
    "\n",
    "  # base cases\n",
    "  dp[0], dp[1] = 0, 1\n",
    "\n",
    "  for i in range(2, n+1):\n",
    "    dp[i] = dp[i-1] + dp[i-2]\n",
    "\n",
    "  return dp[n]\n",
    "\n",
    "fib_bottom_up(7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "SzSeyjNc-DAj"
   },
   "source": [
    "**General Botom-Up Approach**\n",
    "1. Describe the auxilary dynamic programming array to compute what is asked in the question.\n",
    "2. Find the recurrence of this array\n",
    "  * Base case\n",
    "  * Recurrence (the function should be applied for all elements from bottom to the top)\n",
    "3. Implement the algorithm\n",
    "4. Return the optimal/requested solution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "NZ0Hqq-B2YLA"
   },
   "source": [
    "#### **Examples**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "XYCTVGzZ-nG_"
   },
   "source": [
    "**Longest Increasing Subsequence**\n",
    "\n",
    "Find the size of the longest increasing subsequence. Subsequence does not need to be consecutive, but it needs to be like subset.\n",
    "\n",
    "1. Describe the array\n",
    "  * Array `dp[i]` stores the length of longest increasing subsequenec until ith index.\n",
    "  * Initialize the elements as 1.\n",
    "  * Size: `len(arr)`\n",
    "2. Give recurrence\n",
    "  * **Base case**\n",
    "    * `A[i] = 1`  for all indexes at the beginning.\n",
    "  * **Recurrence:** The current item is compared with previous items. The max length obtained from previous items or current value of the current item is kept\n",
    "\n",
    "\n",
    "  ```\n",
    "      j = 1..i-1 if C[j] < C[i] and A[j] + 1 > A[i] : A[i] = A[j] + 1\n",
    "\n",
    "  ```\n",
    "\n",
    "\n",
    "3. Implement the algorithm from step 2\n",
    "4. Return the max value calculated in A array.\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "rgrTeAaGAjqZ",
    "outputId": "1e61b77b-d7cb-47e0-83e7-57bf9f68f9b4"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 52,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Time complexity - O(N²)\n",
    "# Space complexity - O(N)\n",
    "\n",
    "def longest_inc(arr):\n",
    "  length = len(arr)\n",
    "\n",
    "  # base case\n",
    "  longest = [1 for i in range(length)]\n",
    "\n",
    "  for i in range(1, length):\n",
    "    for j in range(i):\n",
    "      if arr[j] < arr[i]:\n",
    "        longest[i] = max(longest[i], longest[j]+1)\n",
    "  \n",
    "  return max(longest)\n",
    "\n",
    "a = [7, 3, 8, 4, 2, 6]\n",
    "longest_inc(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "ZBaRcRbf4IQI"
   },
   "source": [
    "**Change Making**\n",
    "\n",
    "Find the **minimum number of coins** to make 40 cents. `coins = [100, 25, 20, 1]`\n",
    "\n",
    "1. Describe the array\n",
    "  * Array `dp[i]` stores minimum coins to make i cents.\n",
    "  * All elements are initlialized as `float('inf')` at the beginning.\n",
    "  * Size: `target+1'\n",
    "2. Give recurrence\n",
    "  * **Base case**\n",
    "    * `dp[coins[i]] = 1`  if `coins[i] < len(dp)`\n",
    "  * **Recurrence:** \n",
    "    * Fill the money from 0 to target\n",
    "    * For each coin decide if you will use the corresponding coin or not (Same idea in knapsack.)\n",
    "\n",
    "  ```\n",
    "  dp[money] = min(dp[money], dp[money-cent]+1)   \n",
    "  ```\n",
    "\n",
    "\n",
    "3. Implement the algorithm from step 2\n",
    "4. Return the dp[-1]\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "wZ4pNhKQ2XRB",
    "outputId": "b309c052-36e4-4a2d-bdac-27589fe57bc7"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 53,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Time complexity - O(target*len(coin))\n",
    "# Space complexity - O(len(coin))\n",
    "def makeChange(coins, target):\n",
    "\n",
    "  # dp - min amount of money to obtain each target index\n",
    "  dp = [float('inf') for i in range(target+1)]\n",
    "\n",
    "  # base case:\n",
    "  for coin in coins:\n",
    "    if coin < len(dp):\n",
    "      dp[coin] = 1\n",
    "\n",
    "  for money in range(1, target+1):\n",
    "    for cent in coins:\n",
    "      if money-cent >= 0:\n",
    "        # with and without current money\n",
    "        dp[money] = min(dp[money], dp[money-cent]+1)\n",
    "\n",
    "  return dp[target]\n",
    "\n",
    "makeChange([1, 20, 25, 100], 40)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "NZ1N-ACU86ch"
   },
   "source": [
    "**Knapsack**\n",
    "* Fit the maximum value to given weight capacity.\n",
    "\n",
    "  * V = [10, 40, 30, 50]\n",
    "  * W = [5, 4, 6, 3]\n",
    "  * Weight capacity: 10\n",
    "\n",
    "We are checking if I take this coin to reach max value of current money.\n",
    "\n",
    "1. Describe the array\n",
    "  * Array `dp[i][w]` stores maximum value that can be obtained with w weight at ith item.\n",
    "  * All elements are initlialized as `float('inf')` at the beginning.\n",
    "  * Size: `target+1'\n",
    "2. Give recurrence\n",
    "  * **Base case**\n",
    "    * `dp[coins[i]] = 1`  if `coins[i] < len(dp)`\n",
    "  * **Recurrence:** \n",
    "    * Fill the money from 0 to target\n",
    "    * For each coin decide if you will use the corresponding coin or not (Same idea in knapsack.)\n",
    "\n",
    "  ```\n",
    "  dp[money] = min(dp[money], dp[money-cent]+1)   \n",
    "  ```\n",
    "\n",
    "\n",
    "3. Implement the algorithm from step 2\n",
    "4. Return the dp[-1]\n",
    "\n",
    "**Idea:** dp[i][w] whose size is n+1 x W+1\n",
    "  * **row** - set of all items from 1 to i\n",
    "  * **col** - current weight capacity\n",
    "  * ith row and jth col represents the max value that can be obtained by using items from 1 to i items with j weight capacity.\n",
    "\n",
    "* This is about picking or not picking the current element for the required target."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "TZeV11jYt4Lv",
    "outputId": "f55a2345-282c-4cd5-e169-4a57755f97e3"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "90"
      ]
     },
     "execution_count": 14,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def knapsack(values, weights, target):\n",
    "  v, w = len(values), len(weights)\n",
    "  dp = [[0 for i in range(target+1)] for j in range(v+1)]\n",
    "\n",
    "  # row 0 - no items are picked\n",
    "  for c in range(len(weights)+1):\n",
    "    dp[0][c] = 0\n",
    "\n",
    "  # col 0 - 0 weight\n",
    "  for r in range(v+1):\n",
    "    dp[r][0] = 0\n",
    "\n",
    "  for item in range(1, v+1):\n",
    "    for capacity in range(1, target+1):\n",
    "        withoutCurr = dp[item-1][capacity]\n",
    "\n",
    "        withCurr = 0\n",
    "        if capacity-weights[item-1] >= 0:\n",
    "          withCurr = dp[item-1][capacity-weights[item-1]]+values[item-1]\n",
    "\n",
    "        dp[item][capacity] = max(withoutCurr, withCurr)\n",
    "\n",
    "  # item x weight\n",
    "  maxVal = float('-inf')\n",
    "  for i in range(len(dp)):\n",
    "    maxVal = max(maxVal, dp[i][target])\n",
    "\n",
    "  return maxVal\n",
    "\n",
    "V = [10, 40, 30, 50]\n",
    "W = [5, 4, 6, 3]\n",
    "knapsack(V, W, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "MuoXsp5rBery"
   },
   "source": [
    "# **7. BigO**\n",
    "\n",
    "### **General Complexity of Recursive Calls**\n",
    "\n",
    "* **Time Complexity=** O($branches^{depth}$)\n",
    "* **Space Complexity=** O($depth$)\n",
    "\n",
    "This general formula does not work in case of 1 branch.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "iIubIatxEeSB"
   },
   "source": [
    "**Example of general approach**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "6sQliVyHEiOW",
    "outputId": "3929dbe4-3ece-4c74-8255-eee381cfd7fd"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "16"
      ]
     },
     "execution_count": 114,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# finds the n-1 power of 2\n",
    "def f(n):\n",
    "  if n <=1:\n",
    "    return 1\n",
    "  return f(n-1)+f(n-1)\n",
    "\n",
    "f(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "lM-W7UAGEcK9"
   },
   "source": [
    "Draw the function call tree to understand the run time.\n",
    "\n",
    "![picture](https://drive.google.com/uc?id=15Cf9oW83gPv-rblQ69EUKnhy6ARH513Z)\n",
    "\n",
    "**Time Complexity**\n",
    "\n",
    "As a result function is called:\n",
    "\n",
    "$2^{0}+2^{1}+..+2^{N} = 2^{N+1}-1$ \n",
    "\n",
    "which corresponds to **O($2^{N}$)** time complexity. Number of times that the **f** function is called.\n",
    "\n",
    "**Space Complexity**\n",
    "\n",
    "Until the function reach the base case, it holds N functions. After every calculation, one function is realsed. For this reason, space complexity is **O(N)**.\n",
    "\n",
    "4 - 3 - 3 \\\\\n",
    "4 - 2 - 2 - 3 \\\\\n",
    "4 - 1 - 1 - 2 - 3 \\\\\n",
    "4 - 2 - 1 - 1 - 3 \\\\\n",
    "4 - 2 - 2 - 3 \\\\\n",
    "4 - 3 - 3 \\\\\n",
    "continues same for the right\n",
    "\n",
    "**NOTE:** The base of exponential function is not constant and it does matter. ($2^{3n} = 2^{n}*2^{2n}$. So there is a big difference between $2^{n}$ and $2^{3n}$)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "LWby-iZ7Mk9T"
   },
   "source": [
    "### **Some BigO Examples**\n",
    "\n",
    "* **Sorting a string list.(Ex 8)** First sort strings, then the list.(a-list size, s-string size)\n",
    "  * O(a*s(loga+logs))\n",
    "\n",
    "* **Permutation of String (Ex 12)**\n",
    "![alt text](https://drive.google.com/uc?id=1ZOM93dkkE6KCs592mFK23Ns7QJnIOGZ2)\n",
    "\n",
    "  * $O(N^{2}N!)$\n",
    "\n",
    "* **Recursive Fibonacci (Ex 13)**\n",
    "  * $O(2^{N})$ which is calculated with $O(braches^{depth}$)\n",
    "\n",
    "* **Memorized Fibonacci (Ex 15)**\n",
    "  * O(N)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "HRDEpy1fuLXa"
   },
   "source": [
    "# **8. General Ideas**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "M4ccIUE94Oxo"
   },
   "source": [
    "## **[Next permutation](https://leetcode.com/problems/next-permutation/)**\n",
    "* Find the first number that is smaller than its right (starting from the end).\n",
    "* Find the furthest number just larger than the element found at the right of the element.\n",
    "* Swap these two\n",
    "* Reverse the remaining\n",
    "\n",
    "**Example** \n",
    "\n",
    "1432\n",
    "\n",
    "* Check for the last number greater than the number of its right\n",
    "  * idx = 0, val = 1\n",
    "* Find the just larger element.\n",
    "  * idx = 3, val = 2\n",
    "* Swap these two elements\n",
    "  * 2431\n",
    "* Reverse the remaining element of first found element\n",
    "  * 2134\n",
    "\n",
    "```\n",
    "1234\n",
    "1243\n",
    "1324\n",
    "1342\n",
    "1423\n",
    "1432\n",
    "2134\n",
    "```\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 33
    },
    "colab_type": "code",
    "id": "I4NebPxM8wu9",
    "outputId": "7e44a384-7ac2-4fd4-e39e-8a551bb8f85a"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 1, 3, 4]"
      ]
     },
     "execution_count": 30,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def next_permutation(nums):\n",
    "\n",
    "  N = len(nums)\n",
    "  \n",
    "  # edge case - no next in this case\n",
    "  if N == 1:\n",
    "    return\n",
    "\n",
    "  # find the element smaller than the left\n",
    "  idx = N-2\n",
    "  while nums[idx] >= nums[idx+1]:\n",
    "    idx -= 1\n",
    "\n",
    "    # the last element (smallest element is the next)\n",
    "    if idx == -1:\n",
    "      nums.sort()\n",
    "      return nums\n",
    "\n",
    "  # find the next just bigger element\n",
    "  sidx, sval = -1, float('inf')\n",
    "\n",
    "  for i in range(idx+1, N):\n",
    "    if nums[i] > nums[idx] and nums[i] <= sval:\n",
    "      sval = nums[i]\n",
    "      sidx = i\n",
    "\n",
    "  # swap the elements\n",
    "  nums[sidx], nums[idx] = nums[idx], nums[sidx]\n",
    "\n",
    "  # reverse the remaining\n",
    "  s, e = idx+1, N-1\n",
    "  while s < e:\n",
    "    nums[s], nums[e] = nums[e], nums[s]\n",
    "    s += 1\n",
    "    e -= 1\n",
    "  \n",
    "  return nums\n",
    "\n",
    "next_permutation([1, 4, 3, 2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "R9ec1QbGEihz"
   },
   "source": [
    "## **[Meeting Rooms 2](https://leetcode.com/problems/meeting-rooms-ii/)**\n",
    "\n",
    "1st Idea\n",
    "* Create startTime & endtime dicts to hold the start end end times and their occurunces\n",
    "* Create times set() to hold all times\n",
    "* For each time if there is start increase room if there is end, decrease room\n",
    "* Find the max\n",
    "\n",
    "\n",
    "2nd Idea\n",
    "* Create two lists for start and end times\n",
    "* Create two pointers for start and end\n",
    "* Increase the start while there is item in start times.\n",
    "* Change the room number:\n",
    "  * start < end: new room open, increase\n",
    "  * start >= end: a room is closed , decrease\n",
    "* return the used rooms \n",
    "\n",
    "* Time complexity - O(nlogn)\n",
    "* Space complexity - O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "BFLblt85SMeK"
   },
   "outputs": [],
   "source": [
    "def meeting(intervals):\n",
    "  \n",
    "  startTimes, endTimes, times = {}, {}, set()\n",
    "\n",
    "  for start, end in intervals:\n",
    "    startTimes[start] = startTimes.get(start, 0) + 1\n",
    "    endTimes[end] = endTimes.get(end, 0) + 1\n",
    "\n",
    "    times.add(start)\n",
    "    times.add(end)\n",
    "\n",
    "  times = sorted(list(times))\n",
    "  rooms, minRoom = 0, 0\n",
    "\n",
    "  for time in times:\n",
    "    if time in startTimes:\n",
    "      rooms += startTimes[time]\n",
    "    \n",
    "    if time in endTimes:\n",
    "      rooms -= endTimes[time]\n",
    "\n",
    "    minRoom = max(minRoom, rooms)\n",
    "\n",
    "  return minRoom\n",
    "  \n",
    "arr = [[7, 10], [2, 4]]\n",
    "meeting(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "cKKS0JFmSPQC"
   },
   "outputs": [],
   "source": [
    "def meetingTime(intervals):\n",
    "  start = [time[0] for time in intervals]\n",
    "  end = [time[1] for time in intervals]\n",
    "\n",
    "  start.sort()\n",
    "  end.sort()\n",
    "  rooms = 0\n",
    "  sidx, eidx = 0,0\n",
    "\n",
    "  # consider the time according to the start\n",
    "  while sidx < len(intervals):\n",
    "\n",
    "    if start[sidx] > end[eidx]:\n",
    "      rooms -= 1\n",
    "      eidx += 1\n",
    "\n",
    "    rooms += 1\n",
    "    sidx += 1\n",
    "  \n",
    "  return rooms\n",
    "\n",
    "arr = [[7, 10], [2, 4]]\n",
    "meetingTime(arr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "zzZIjvrWWaCq"
   },
   "source": [
    "## **[124. Binary Tree Maximum Path Sum](https://leetcode.com/problems/binary-tree-maximum-path-sum/)**\n",
    "* **IDEA:** For the current node, there are two types of paths. \n",
    "  * Path from left to right. Sum max of left, current, max of right\n",
    "  * Path from max of left or right pass throught current.\n",
    "* As the first type is completed, we check if it is improve the result\n",
    "* The second one we return to be investigated at upper nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "jtM8O2uyW2PJ"
   },
   "outputs": [],
   "source": [
    "def maxPathSum(self, root):\n",
    "    \"\"\"\n",
    "    :type root: TreeNode\n",
    "    :rtype: int\n",
    "    \"\"\"\n",
    "    self.maxVal = float('-inf')\n",
    "    \n",
    "    def maxPath(node):\n",
    "        if node == None:\n",
    "            return 0\n",
    "\n",
    "        # only take if it improves the result\n",
    "        left = max(maxPath(node.left), 0)\n",
    "        right = max(maxPath(node.right), 0)\n",
    "\n",
    "        # the node is in between left and right\n",
    "        self.maxVal = max(self.maxVal, left + right + node.val)\n",
    "\n",
    "        # node is on the path coming from the maximum of left & right\n",
    "        return node.val + max(left, right)\n",
    "    \n",
    "    maxPath(root)\n",
    "    return self.maxVal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "JBHZsTd3ruOG"
   },
   "source": [
    "## **[5. Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring/)**\n",
    "\n",
    "* Define the array:\n",
    "  * 2D array which returns true if the substring is btw given indices is palindrome, False otherwise\n",
    "  * Base cases \n",
    "  ```\n",
    "  dp[i][i] =True & dp[i][i+1] = s[i] == s[i-1]\n",
    "  ```\n",
    "  * Recurrence \n",
    "  ```\n",
    "  dp[i][j] = dp[i+1][j-1] and (s[i] == s[j])\n",
    "  ```\n",
    "* Time complexity - $O(N^{2})$\n",
    "* Space complexity - $O(N^{2})$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "Enl83lSer4XT"
   },
   "outputs": [],
   "source": [
    "def pal(s):\n",
    "\n",
    "  length = len(s)\n",
    "  dp = [[False for c in range(length)] for r in range(length)]\n",
    "\n",
    "  f, l = 0, 0  \n",
    "\n",
    "  for i in range(length):\n",
    "    dp[i][i] = True\n",
    "\n",
    "  for i in range(length-1):\n",
    "    dp[i][i+1] = s[i] == s[i+1]\n",
    "    if dp[i][i+1]:\n",
    "      f, l = i, i+1\n",
    "\n",
    "\n",
    "  for start in range(length):\n",
    "    for end in range(start+2, length):\n",
    "      dp[start][end] = dp[start+1][end-1] + (s[start] == s[end])\n",
    "      if dp[start][end] and end-start > l-f:\n",
    "        f, l = start, end\n",
    "  \n",
    "  return s[f:l+1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "9AtU5xJiKFOI"
   },
   "source": [
    "## **[939. Minimum Area Rectangle](https://leetcode.com/problems/minimum-area-rectangle/)**\n",
    "* Pass through all points and put them to the seen set\n",
    "* Check if you see the corners before\n",
    "* If so, calculate the min area\n",
    "* Time complexity - $O(N^{2})$\n",
    "* Space complexity - O(N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "POPW5zoCKHxr"
   },
   "outputs": [],
   "source": [
    "def minRectangle(points):\n",
    "\n",
    "  minArea = float('inf')\n",
    "  seen = set()\n",
    "  \n",
    "  for x1, y1 in points:\n",
    "    for x2, y2 in seen:\n",
    "      if (x1, y2) in seen and (x2, y1) in seen:\n",
    "          minArea = min(minArea, (x1-x2)*abs(y1-y2))\n",
    "\n",
    "    seen.add((x1, y1))\n",
    "\n",
    "  return minArea"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "JvkkuJ1Yqb5a"
   },
   "source": [
    "## **[105. Construct Binary Tree from Preorder and Inorder Traversal](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "P9aecjg_qiVY"
   },
   "outputs": [],
   "source": [
    "\n",
    "def buildTree(preorder, inorder):\n",
    "  def construct(preorder, inorder, idxMap, start, end):\n",
    "    nonlocal preIdx\n",
    "    if start <= end:\n",
    "\n",
    "      rootVal = preorder[preIdx]\n",
    "      root = TreeNode(rootVal)\n",
    "      rootIdx = idxMap[rootVal]\n",
    "\n",
    "      leftEnd, rightStart = rootIdx-1, rootIdx+1\n",
    "      preIdx += 1\n",
    "\n",
    "      root.left = construct(preorder, inorder, idxMap, start, leftEnd)\n",
    "      root.right = construct(preorder, inorder, idxMap, rightStart, end)\n",
    "\n",
    "      return root\n",
    "\n",
    "  \n",
    "  preIdx = 0\n",
    "  indexMap = {val:idx for idx, val in enumerate(inorder)}\n",
    "\n",
    "  return construct(preorder, inorder, indexMap, 0, len(preorder)-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "V0EUJWOI3Cst"
   },
   "source": [
    "## **Boyre Moore Majority Voting Algorithm**\n",
    "\n",
    "This is the majority finding element. The algorithm has 2 main variables:\n",
    "\n",
    "* **candidate:** Majority candidate.\n",
    "* **count:** The count of current candidate\n",
    "\n",
    "The algorithm works as follows:\n",
    "* Traverse each number in the given array\n",
    "* If the count of prev candidate is 0, the current num becomes candidate as previous number is canceled out.\n",
    "* Whenever we see the same number as the current candidate, we increase the count of current candidate.\n",
    "* Whenever we see a different number with current candidate, we decrease the count of current candidate.\n",
    "\n",
    "Here is the [article](https://gregable.com/2013/10/majority-vote-algorithm-find-majority.html) for more information."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "Aeb4U5t-4UhT"
   },
   "outputs": [],
   "source": [
    "def voting(arr):\n",
    "  count, candidate = 0, 0\n",
    "\n",
    "  for num in arr:\n",
    "    if count == 0:\n",
    "      candidate = num \n",
    "      count = 1\n",
    "    elif candidate == num:\n",
    "      count += 1\n",
    "    else:\n",
    "      count -= 1\n",
    "  \n",
    "  return candidate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "IXPpRnwn6Yy_",
    "outputId": "7568587e-3185-411f-cc89-daa39f06ff6d"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 5,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [1, 1, 2, 3, 3, 2, 1]\n",
    "voting(arr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "zCOE1V7KkTnY"
   },
   "source": [
    "# **9. String Concatenation**\n",
    "\n",
    "\n",
    "Let's say we have a list (str_list) with length N whose each element is a letter.\n",
    "\n",
    "### **Concatenation**\n",
    "```\n",
    "result = ''\n",
    "for letter in str_list:\n",
    "  result += letter\n",
    "```\n",
    "\n",
    "Everytime we add a letter to the result, a new copy is created. Thus, the length of result is:\n",
    "\n",
    "1 + 2 + ... + N = N(N+1) / 2\n",
    "\n",
    "As a result, complexity is **O($N^{2}$)**\n",
    "\n",
    "**NOTE:** If each element has length M, the complexity is O($N^2M$)\n",
    "\n",
    "M + 2M + 3M + ... + NM = $N^{2}M$\n",
    "\n",
    "### **Join**\n",
    "\n",
    "\n",
    "```\n",
    "word_list = []\n",
    "\n",
    "for letter in str_list:\n",
    "  word_list.append(letter)\n",
    "\n",
    "result = ''.join(word_list)\n",
    "```\n",
    "\n",
    "As a result, complexity is **O(N)**\n",
    "\n",
    "**NOTE:** If each element has length M, the complexity is O(NM)\n",
    "\n",
    "**RESULT:** ''.join() is a good alternative for efficient string concatenation.\n",
    "\n",
    "Time complexity of string concatenation is take from [this website](https://stackoverflow.com/questions/37133547/time-complexity-of-string-concatenation-in-python).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Oi_iHnjauAzD"
   },
   "source": [
    "# **10. List Concatenation**\n",
    "\n",
    "The following explanation is obtained from [stackoverflow](https://stackoverflow.com/questions/33191470/difference-in-complexity-of-append-and-concatenate-for-this-list-code).\n",
    "\n",
    "### **Concatenation**\n",
    "\n",
    "\n",
    "```\n",
    "l = l + [i]\n",
    "```\n",
    "\n",
    "\n",
    "* Creates a new list\n",
    "* Complexity is O(N)\n",
    "\n",
    "### **Augmented Concatenation**\n",
    "\n",
    "\n",
    "```\n",
    "l += [i]\n",
    "```\n",
    "\n",
    "* Same as extend\n",
    "* Does not create a new list\n",
    "* O(k) complexity, where k is the number of elements in the added list.\n",
    "\n",
    "### **append(), extend() functions**\n",
    "\n",
    "\n",
    "```\n",
    "l.append(i) - O(1)\n",
    "l.extend([1, .. , k]) - O(k)\n",
    "```\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "I4xZlHO5PjX2"
   },
   "source": [
    "# **11. Sorting/Searching Big Files**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "WYAcGwSXqDl6"
   },
   "source": [
    "### **General Info**\n",
    "* $2^{30}$ byte =  $2^{20}$ kbyte = $2^{10}$ mbyte = 1 gbyte\n",
    "* $2^{10}$ ~ $10^3$\n",
    "* $10^9$ byte ~ $10^6$ kbyte ~ $10^3$ mbyte ~ 1 gbyte\n",
    "* 1 byte = 8 bits\n",
    "* 1 integer 4 byte (assumption)\n",
    "* Integer.maxval = $2^{31}$ - 1\n",
    "* Integer.minval = -$2^{31}$\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "vZF2pnlObBBF"
   },
   "source": [
    "### **External Memory**\n",
    "\n",
    "\n",
    "[<img src=\"https://drive.google.com/uc?id=13MCGIf1j9B2WwSFo8cnRrNisg2ibiec2\" width=\"400\">](https://drive.google.com/uc?id=13MCGIf1j9B2WwSFo8cnRrNisg2ibiec2)\n",
    "\n",
    "* **M** - Memory (cache/RAM/internal memory) size\n",
    "* **B** - Block size\n",
    "* **N** - Disk (external memory) size\n",
    "\n",
    "* One memory transfer operation consists of moving a block of size B.\n",
    "* **Run time** - Number of memory transfer operations (from external to internal)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "bb-gxkkXbFNy"
   },
   "source": [
    "#### **External Merge Sort**\n",
    "N = 900MB, M = 100MB\n",
    "\n",
    "1. Sort 100 MB blocks\n",
    "2. Write the sorted blocks to disk\n",
    "3. Repeat 1 and 2 until all blocks are sorted (9 in total)\n",
    "4. Store 10 MB blocks from each sorted block to RAM (10MB x 9 = 90MB). Remaining 10MB is used as **output buffer**\n",
    "5. Perform **9-way merge**.\n",
    "  * If the **output buffer fills**, write the sorted file to the disk.\n",
    "  * If **one of the chunks is empty**, bring 10MB from the corresponding chunk to the hard drive.\n",
    "  * Continue until no chunk left.\n",
    "\n",
    "**Time complexity:** $O(\\frac{N}{B}\\log_{\\frac{M}{B}}\\frac{N}{B})$\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "8gmaCmoSbIeQ"
   },
   "source": [
    "### **Missing Int**\n",
    "Find the integer that is not in the file.\n",
    "\n",
    "* N = 4.000.000.000 (number of integers)\n",
    "* M = 1GB\n",
    "\n",
    "1. Size of data\n",
    "  * 4.000.000.000 x 8 byte (1 int) = 32.000.000.000 byte = 32.000.000 KB = 32.000 MB = 32 GB (does not fit to the memory)\n",
    "2. Bit vector:\n",
    "  * $2^{31}$ (number of non-negative integers) = $2^{31}$ bits = $2*(2^{10})^{3}$ bits = $2*(2^{10})^{3}$ / $2^{3}$ byte = 0.25 GB\n",
    "\n",
    "3. Put the bit vector to the memory\n",
    "  * bit vector - 0.25 GB\n",
    "  * remaining - 0.75 GB\n",
    "\n",
    "4. Pass number\n",
    "  * 32 GB / 0.75 GB = 42 pass\n",
    "\n",
    "5. Fill the bit vector in each pass\n",
    "6. Check which number is missing\n",
    "\n",
    "**FOLLOWUP:** If bit vector does not fit to the memory as well, check numbers for certain ranges. If the range has missing int, return it immediately. Otherwise, continue searching.\n",
    "\n",
    "For example search ranges in order 0..999, 1000..1999, 2000..2999 ...\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "V9KyCmpFQKFI"
   },
   "outputs": [],
   "source": [
    "class BitArray:\n",
    "  arr = [] # in array\n",
    "\n",
    "  def __init__(self, num):\n",
    "    \n",
    "    # As each element of the array is an integer, we find the integer position of the number by dividing by 32\n",
    "    self.arr = [0] * (num // 32) # each int is 4 byte, 32 bit\n",
    "\n",
    "  def get(self, pos):\n",
    "\n",
    "    # find the integer index\n",
    "    idx = pos//32\n",
    "\n",
    "    # find the bit position in the corresponding integer\n",
    "    bitIdx = pos%32\n",
    "    return self.arr[idx] & (1<<bitIdx) != 0\n",
    "\n",
    "  def set(self, pos):\n",
    "    self.arr[pos//32] |= (1 << (pos%32))\n",
    "\n",
    "def findMissing(arr):\n",
    "\n",
    "  # we need 2.000.000.000 bits to represent all non-negative numbers\n",
    "  bitArr = BitArray(2000000000)\n",
    "\n",
    "  for num in arr:\n",
    "    bitArr.set(num)\n",
    "\n",
    "  for i in range(2000000000):\n",
    "    if not bitArr.get(i):\n",
    "      print(i)\n",
    "      break\n",
    "\n",
    "nums = [0,1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12,13, 15]\n",
    "findMissing(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "p7SdKFCobLTV"
   },
   "source": [
    "### **Find Duplicates**\n",
    "Print all duplicates in given integer range.\n",
    "\n",
    "* Integers 1...N (at most 32.000)\n",
    "* M = 4KB\n",
    "\n",
    "1. Size of data\n",
    "\n",
    "  * 32.000 x 8 byte = 256.000 byte = 256 KB (does not fit to the memory)\n",
    "\n",
    "2. Bit vector\n",
    "  * 32.000 bits = 4.000 byte = 4 KB\n",
    "\n",
    "3. Memory size:\n",
    "  * $8*4*2^{10}$ bits > 32000 (bit vector can fit memory and also some integer)\n",
    "\n",
    "4. Use bitarray to find dups."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "rfFalG_1f7n7"
   },
   "source": [
    "# **12. Advanced Algorithms**\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Vv_WHlAia1TA"
   },
   "source": [
    "### **Greedy Problems**\n",
    "\n",
    "Greedy problems has 2 main properties:\n",
    "\n",
    "1. **Greedy-choice property:** Global optimal solution can be arrived at by making a local optimal (greedy) choice.\n",
    "\n",
    "  * The choice in greedy algorithm does not depend on any subproblem or feature choice rather depends on choices so far.\n",
    "  * Preprocessing the input yields effective algorithm.\n",
    "\n",
    "    **Ex:** order based on finish time in activity-selection problem, using data structure (mostly priority queue)\n",
    "\n",
    "2- **Optimal substructure:** Optimal solution to the problem contains optimal solution to subproblems.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "4GmfW2uea4Dd"
   },
   "source": [
    "### **A* Algorithm**\n",
    "\n",
    "Starting from a specific node of a graph, it aims to find a shortest path to the given goal node.\n",
    "\n",
    "* g(n) - the cost of the path from the start to n.\n",
    "* h(n) - heuristic function that estimates the cheapest path from n to the goal (heuristic should be underestimated).\n",
    "* f(n) - the estimated cost from the start node to the goal node.\n",
    "\n",
    "  `f(n) = g(n) + h(n)`\n",
    "\n",
    "The following code is implemented based on the explanation in [wikipedia](https://en.wikipedia.org/wiki/A*_search_algorithm)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "DUYOenviW-wf"
   },
   "outputs": [],
   "source": [
    "from heapq import *\n",
    "from collections import deque\n",
    "\n",
    "# TODO think about this\n",
    "def reconstruct_path(came_from, current):\n",
    "  print(current)\n",
    "  path = deque([current])\n",
    "\n",
    "  while current in came_from:\n",
    "    current = came_from[current]\n",
    "    path.appendleft(current)\n",
    "\n",
    "  return path\n",
    "\n",
    "def h_score(source, dest):\n",
    "  sr, sc = source\n",
    "  dr, dc = dest\n",
    "\n",
    "  return (sr-dr)**2 + (sc-dc)**2\n",
    "\n",
    "def astar(matrix, start, goal):\n",
    "\n",
    "  # neighbors in maze shape\n",
    "  neighbors = [(0,1),(0,-1),(1,0),(-1,0),(1,1),(1,-1),(-1,1),(-1,-1)]\n",
    "  \n",
    "  # height and width\n",
    "  height, width = len(matrix), len(matrix[0])\n",
    "\n",
    "  # set of discovered nodes. ordered based on f_score of the node\n",
    "  openSet = []\n",
    "\n",
    "  # estimated cost from start to node \n",
    "  g_score = {}\n",
    "  g_score[start] = 0\n",
    "\n",
    "  # estimated cost from start to nodes\n",
    "  f_score = {}\n",
    "  f_score[start] = h_score(start, goal) + g_score[start]\n",
    "\n",
    "  # holds the previous element on the path\n",
    "  came_from = {}\n",
    "\n",
    "  # initially only start node is in the heap\n",
    "  heappush(openSet, (f_score[start], start))\n",
    "\n",
    "  while openSet:\n",
    "\n",
    "    current = heappop(openSet)[1]\n",
    "\n",
    "    if current == goal:\n",
    "      return reconstruct_path(came_from, current)\n",
    "    \n",
    "    else:\n",
    "      for r, c in neighbors:\n",
    "        cr, cc = current[0]+r, current[1]+c\n",
    "\n",
    "        # inside the borders and not obstacles\n",
    "        if 0 <= cr < height and 0 <= cc < width and matrix[cr][cc] != 1:\n",
    "\n",
    "          neighbor = (cr, cc)\n",
    "\n",
    "          # 1 - distance from current to neighbor\n",
    "          tentative_g_score = g_score[current] + 1\n",
    "\n",
    "          if tentative_g_score < g_score.get(neighbor, float('inf')):\n",
    "            came_from[neighbor] = current\n",
    "            g_score[neighbor] = tentative_g_score\n",
    "            f_score[neighbor] = g_score[neighbor] + h_score(neighbor, goal)\n",
    "\n",
    "            # We are sure if it is in openSet, result will not be improved as weights are positive\n",
    "            if neighbor not in [item[1] for item in openSet]:\n",
    "              heappush(openSet, (f_score[neighbor], neighbor))\n",
    "  return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 277
    },
    "colab_type": "code",
    "id": "MueHlY7Dluh3",
    "outputId": "6ab27daa-a4a6-4545-be84-a4b4eb525969"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(2, 0)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "deque([(4, 13),\n",
       "       (3, 12),\n",
       "       (2, 11),\n",
       "       (2, 10),\n",
       "       (2, 9),\n",
       "       (2, 8),\n",
       "       (2, 7),\n",
       "       (2, 6),\n",
       "       (2, 5),\n",
       "       (2, 4),\n",
       "       (2, 3),\n",
       "       (2, 2),\n",
       "       (2, 1),\n",
       "       (2, 0)])"
      ]
     },
     "execution_count": 26,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "maze = [\n",
    "    [0,0,0,0,0,0,0,0,0,0,0,0,0,0],\n",
    "    [1,1,1,1,1,1,1,1,1,1,1,1,0,1],\n",
    "    [0,0,0,0,0,0,0,0,0,0,0,0,0,0],\n",
    "    [1,0,1,1,1,1,1,1,1,1,0,1,0,1],\n",
    "    [0,0,0,0,0,0,0,0,0,0,0,0,0,0],\n",
    "    [1,1,1,1,1,1,1,1,1,1,1,1,0,1],\n",
    "    [0,0,0,0,0,0,0,0,0,0,0,0,0,0],\n",
    "    [1,0,1,1,1,1,1,1,1,1,1,1,1,1],\n",
    "    [0,0,0,0,0,0,0,0,0,0,0,0,0,0],\n",
    "    [1,1,1,1,1,1,1,1,1,1,1,1,0,1],\n",
    "    [0,0,0,0,0,0,0,0,0,0,0,0,0,0]]\n",
    "\n",
    "astar(maze, (4,13), (2,0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "GM8l6K6nlt-d"
   },
   "source": [
    "### **Red-Black Tree**\n",
    "\n",
    "* Self-balancing binary search tree\n",
    "* Red-black tree is slightly slower than AVL tree.\n",
    "* Guarantees O(logN) search time\n",
    "\n",
    "**Properties of Red-Black Tree**\n",
    "1. Each node is either red or black (red=1, black=0).\n",
    "2. The root is always black.\n",
    "3. All leaves are None and black\n",
    "4. If a node is red, then its parent is black\n",
    "5. Any path from a given node to leaves contains same amount of black nodes (black depth). This does not count the starting node.\n",
    "\n",
    "![picture](https://drive.google.com/uc?id=12RgY-qQq2m06cgM531diZhIK7PO5-Qsf)\n",
    "\n",
    "When a new node inserted, its color is red. The following cases need to be fixed in insertion:\n",
    "\n",
    "**Case 1:** The parent and uncle are red\n",
    "\n",
    "**Solution:** \n",
    "\n",
    "* Switch the color of grandparent and the parents. \n",
    "* Continue to this until the root of the tree.\n",
    "\n",
    "![picture](https://drive.google.com/uc?id=1KUCaACKeIW1u0YbR-3yUD4z6NlVIbFgm)\n",
    "\n",
    "**Case 2:** Parent is red, parent's sibling is black and current node is the right child of parent (value of the node is in between parent and grandparent). \n",
    "\n",
    "**Solution**\n",
    "* Rotate left around the parent\n",
    "* Go to case 3.\n",
    "\n",
    "![picture](https://drive.google.com/uc?id=1AzIL88YqgB8borKJg0ZfHal_FzeeGniT)\n",
    "\n",
    "**Case 3:** Parent is red, parent's sibling is black and current node is the left child of the parent\n",
    "\n",
    "**Solution**\n",
    "* Rotate right around the grandparent\n",
    "\n",
    "\n",
    "![picture](https://drive.google.com/uc?id=1sMt9ir5MIKCowaef0FS2rrHLMWmk-7DF)\n",
    "\n",
    "The code is taken from the [following link](https://brilliant.org/wiki/red-black-tree/).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "Gc46pdTM2VT6"
   },
   "outputs": [],
   "source": [
    "class Node:\n",
    "\n",
    "  def __init__(self, data):\n",
    "    self.data = data\n",
    "    self.red = True\n",
    "    self.left, self.right, self.parent = None, None, None\n",
    "\n",
    "\n",
    "class RBTree:\n",
    "\n",
    "  def __init__(self):\n",
    "    self.root = None\n",
    "\n",
    "  def search(self, data):\n",
    "\n",
    "    currentNode = self.root\n",
    "\n",
    "    while currentNode is not None and currentNode.data != data:\n",
    "      if data < currentNode.data:\n",
    "        currentNode = currentNode.left\n",
    "\n",
    "      else:\n",
    "        currentNode = currentNode.right\n",
    "\n",
    "    return currentNode\n",
    "\n",
    "  def insert(self, data):\n",
    "    node = Node(data)\n",
    "\n",
    "    # empty tree\n",
    "    if self.root is None:\n",
    "      node.red = False\n",
    "      self.root = node\n",
    "    \n",
    "    else:\n",
    "\n",
    "      # search the correct place of the node\n",
    "      currentNode = self.root\n",
    "      while currentNode is not None:\n",
    "        potentailParent = currentNode\n",
    "\n",
    "        if node.data < currentNode.data:\n",
    "          currentNode = currentNode.left\n",
    "        else:\n",
    "          currentNode = currentNode.right\n",
    "\n",
    "      # assign parent to the new node\n",
    "      node.parent = potentailParent\n",
    "      if node.data <= node.parant.data:\n",
    "        node.parent.left = node\n",
    "      else:\n",
    "        node.parent.right = node\n",
    "\n",
    "      self.fixTree(node)\n",
    "\n",
    "  def fixTree(self, node):\n",
    "\n",
    "    # as inserted node is red, parent should be black\n",
    "    while node != self.root and node.parent.red == True:\n",
    "\n",
    "      # the current is left child of grandparent\n",
    "      if node.parent == node.parent.parent.left:\n",
    "        parent = node.parent\n",
    "        uncle = node.parent.parent.right\n",
    "        grandparent = node.parent.parent.parent\n",
    "        \n",
    "        # case 1 - parent & uncle are red\n",
    "        if uncle.red:\n",
    "\n",
    "          parent.red = False\n",
    "          uncle.red = False\n",
    "          grandparent.red = True\n",
    "          node = grandparent\n",
    "        \n",
    "        # uncle is black\n",
    "        else:\n",
    "\n",
    "          # case 2 - current node data is in between parent and grandparent\n",
    "          if node == node.parent.right:\n",
    "              node = node.parent\n",
    "\n",
    "              # rotate cc around parent\n",
    "              self.left_rotate(node)\n",
    "\n",
    "          # case 3 - rotate around grandparent\n",
    "          node.parent.red = False\n",
    "          node.parent.parent.red = True\n",
    "          self.right_rotate(node.parent.parent)\n",
    "      else:\n",
    "        parent = node.parent\n",
    "        uncle = node.parent.parent.left\n",
    "        grandparent = node.parent.parent.parent\n",
    "\n",
    "        if uncle.red:\n",
    "          parent.red = False\n",
    "          uncle.red = False\n",
    "          grandparent.red = True\n",
    "          node = grandparent\n",
    "        else:\n",
    "\n",
    "          # case 2 - current node data is in between parent and grandparent\n",
    "          if node == node.parent.left:\n",
    "              node = node.parent\n",
    "\n",
    "              # rotate cc around parent\n",
    "              self.right_rotate(node)\n",
    "\n",
    "          # case 3 - rotate around grandparent\n",
    "          node.parent.red = False\n",
    "          node.parent.parent.red = True\n",
    "          self.left_rotate(node.parent.parent)\n",
    "    \n",
    "    self.root.red = False\n",
    "\n",
    "def left_rotate(self, node):\n",
    "  sibling = node.right\n",
    "  node.right = sibling.left\n",
    "\n",
    "  if sibling.left is not None:\n",
    "    sibling.left.parent = node\n",
    "\n",
    "  sibling.parent = node.parent\n",
    "\n",
    "  if node.parent is None:\n",
    "    self.root = sibling\n",
    "  else:\n",
    "    if node == node.parent.left:\n",
    "      node.parent.left = sibling\n",
    "    else:\n",
    "      node.parent.right = sibling\n",
    "  \n",
    "  sibling.left = node\n",
    "  node.parent = sibling\n",
    "\n",
    "def right_rotate(self, node):\n",
    "  sibling = node.left\n",
    "  node.left = sibling.right\n",
    "\n",
    "  if sibling.right is not None:\n",
    "    sibling.right.parent = node\n",
    "\n",
    "  sibling.parent = node.parent\n",
    "\n",
    "  if node.parent is None:\n",
    "    self.root = sibling\n",
    "  else:\n",
    "    if node == node.parent.right:\n",
    "      node.parent.right = sibling\n",
    "    else:\n",
    "      node.parent.left = sibling\n",
    "  \n",
    "  sibling.right = node\n",
    "  node.parent = sibling"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "sM55bzJIR7Sw"
   },
   "source": [
    "### **AVL Tree**\n",
    "* Self-balancing binary search tree\n",
    "* Guarantees O(logN) search time\n",
    "* Each node of AVL tree keeps the following property\n",
    "\n",
    "  $|h_{l}-h_{r}| \\leq 1$\n",
    "\n",
    "* **Balance Factor(bf):** Balance factor of a node is the height difference between left and right subtree of the node.\n",
    "\n",
    "The following shape is not an AVL tree, but indicates the balance factor:\n",
    "\n",
    "![](https://drive.google.com/uc?id=1axhJpAitvWWGE0ueKW6B77KDzBJNIIUe)\n",
    "\n",
    "**Balancing AVL Tree**\n",
    "When bf of a node is less than -1 or greater than 1, we perform tree rotations on the node.There are 4 kinds of rotations\n",
    "\n",
    "**1. Left Rotation**\n",
    "* a is right heavy\n",
    "* a's right child is not left heavy\n",
    "\n",
    "\n",
    "![picture](https://drive.google.com/uc?id=1WwpvIQ-6aoMVMW21c3uOSStPGDtRUE7N)\n",
    "\n",
    "**2. Right Rotation**\n",
    "* a is left heavy\n",
    "* a's left child is not right heavy\n",
    "\n",
    "![picture](https://drive.google.com/uc?id=1_FsLrXoXnZrSRexSvWsR76VYdU01mxL8)\n",
    "\n",
    "\n",
    "**3. Left-Right Rotation**\n",
    "* a is right heavy\n",
    "* a's right child is left heavy\n",
    "\n",
    "![picture](https://drive.google.com/uc?id=11TLWEEgxwwdHUn7N3npjBt1v4BMRh1ON)\n",
    "\n",
    "\n",
    "**4. Right-Left Rotation**\n",
    "* a is left heavy\n",
    "* a's left child is right heavy\n",
    "\n",
    "\n",
    "![picture](https://drive.google.com/uc?id=18Q61eBroLPt_tP-e6-xXkDE4jsQIO7yv)\n",
    "\n",
    "Implementation is taken from the [following website](https://algorithmtutor.com/Data-Structures/Tree/AVL-Trees/).\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "F9H387rOTlJU"
   },
   "outputs": [],
   "source": [
    "class Node:\n",
    "  \n",
    "  def __init__(self, data):\n",
    "    self.data = data\n",
    "    self.left, self.right, self.parent = None, None, None\n",
    "    self.bf = 0\n",
    "\n",
    "class AVLTree:\n",
    "\n",
    "  def __init__(self):\n",
    "    self.root = None\n",
    "\n",
    "  def insert(self, data):\n",
    "\n",
    "    node = Node(data)\n",
    "\n",
    "    # empty tree\n",
    "    if self.root is None:\n",
    "      self.root = node\n",
    "    \n",
    "    else:\n",
    "\n",
    "      # search the correct place of the node\n",
    "      currentNode = self.root\n",
    "      while currentNode is not None:\n",
    "        potentailParent = currentNode\n",
    "\n",
    "        if node.data < currentNode.data:\n",
    "          currentNode = currentNode.left\n",
    "        else:\n",
    "          currentNode = currentNode.right\n",
    "\n",
    "      node.parent = potentailParent\n",
    "      if node.data <= node.parant.data:\n",
    "        node.parent.left = node\n",
    "      else:\n",
    "        node.parent.right = node\n",
    "\n",
    "      self.updateBalance(node)\n",
    "\n",
    "  def updateBalance(self, node):\n",
    "    if node.bf < -1 or node.bf > 1:\n",
    "      self.rebalance(node)\n",
    "    else:\n",
    "\n",
    "      if node.parent is not None:\n",
    "        if node is node.parent.left:\n",
    "          node.parent.bf -= 1\n",
    "\n",
    "        if node is node.parent.right:\n",
    "          node.parent.bf += 1\n",
    "\n",
    "        # work on parent only if it becomes a heavy on one of the sides\n",
    "        if node.parent.bf != 0:\n",
    "          self.updateBalance(node.parent)\n",
    "\n",
    "  def rebalance(self, node):\n",
    "    if node.bf > 0:\n",
    "      if node.right.bf < 0:\n",
    "        self.rightRotate(node.right)\n",
    "        self.leftRotate(node)\n",
    "      else:\n",
    "        self.leftRotate(node)\n",
    "\n",
    "    if node.bf < 0:ent;\n",
    "    if x.parent == None:\n",
    "      self.root = y\n",
    "    elif x == x.parent.left:\n",
    "      x.parent.left = y\n",
    "    else:\n",
    "      x.parent.right = y\n",
    "    y.left = x\n",
    "    x.parent = y\n",
    "\n",
    "      if node.left.bf > 0:\n",
    "        self.leftRotate(node.left)\n",
    "        self.rightRotate(node)\n",
    "      else:\n",
    "        self.rightRotate(node)\n",
    "\n",
    "\n",
    "  # rotate left at node x\n",
    "  def leftRotate(self, x):\n",
    "    y = x.right\n",
    "    x.right = y.left\n",
    "    \n",
    "    if y.left != None:\n",
    "      y.left.parent = x\n",
    "\n",
    "    y.parent = x.par\n",
    "    # update the balance factor\n",
    "    x.bf = x.bf - 1 - max(0, y.bf)\n",
    "    y.bf = y.bf - 1 + min(0, x.bf)\n",
    "\n",
    "  # rotate right at node x\n",
    "  def rightRotate(self, x):\n",
    "    y = x.left\n",
    "    x.left = y.right;\n",
    "    \n",
    "    if y.right != None:\n",
    "      y.right.parent = x\n",
    "    \n",
    "    y.parent = x.parent;\n",
    "    if x.parent == None:\n",
    "      self.root = y\n",
    "    elif x == x.parent.right:\n",
    "      x.parent.right = y\n",
    "    else:\n",
    "      x.parent.left = y\n",
    "    \n",
    "    y.right = x\n",
    "    x.parent = y\n",
    "\n",
    "    # update the balance factor\n",
    "    x.bf = x.bf + 1 - min(0, y.bf)\n",
    "    y.bf = y.bf + 1 + max(0, x.bf)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "lrqFChRZdQh2"
   },
   "source": [
    "### **Minimum Spanning Tree**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "kYMldwo1wiVB"
   },
   "source": [
    "#### **Prim's Algorithm**\n",
    "* **heap** is used to select the edge `[source, dest]` such that\n",
    "  * source - node in the tree\n",
    "  * dest - candidate node for the tree\n",
    "1. Firstly only start node is visited\n",
    "2. Push all edges starting from the start node to the heap\n",
    "3. Pop the edge with smallest weight\n",
    "4. If the destination of the popped edge is not visited (did not become start node before), then push all edges created with unvisited neighbors to heap\n",
    "5. Go back to step 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "7LfjLaEhGVqN"
   },
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "def create_adjlist(graph):\n",
    "  adj_list = defaultdict(list)\n",
    "\n",
    "  v = len(graph)\n",
    "  for s in range(v):\n",
    "    for d in range(s+1, v):\n",
    "      if graph[s][d] != 0:\n",
    "        adj_list[s].append((d, graph[s][d]))\n",
    "        adj_list[d].append((s, graph[s][d]))\n",
    "\n",
    "  return adj_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "loHlGurS1-7w"
   },
   "outputs": [],
   "source": [
    "from heapq import *\n",
    "\n",
    "def MST_prim(graph):\n",
    "\n",
    "  heap, result , visited = [], [], set()\n",
    "  adj_list = create_adjlist(graph)\n",
    "\n",
    "  start = 0\n",
    "  visited.add(start)\n",
    "  \n",
    "  for dest, weight in adj_list[start]:\n",
    "    heappush(heap, (weight, start, dest))\n",
    "  \n",
    "  while heap:\n",
    "    weight, source, dest = heappop(heap)\n",
    "    if dest not in visited:    \n",
    "      result.append((source, dest, weight))\n",
    "      visited.add(dest)\n",
    "\n",
    "      for d, w in adj_list[dest]:\n",
    "        if d not in visited:\n",
    "          heappush(heap, (w, dest, d))\n",
    "  \n",
    "  return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 33
    },
    "colab_type": "code",
    "id": "gDJMzPda1Xnu",
    "outputId": "73325366-296a-4947-b1a5-af1fb728acbd"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, 3, 2), (3, 1, 4), (1, 2, 3), (1, 4, 5)]"
      ]
     },
     "execution_count": 70,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph = [ [0, 5, 0, 2, 0], \n",
    "          [5, 0, 3, 4, 5], \n",
    "          [0, 3, 0, 0, 7], \n",
    "          [2, 4, 0, 0, 9], \n",
    "          [0, 5, 7, 9, 0]] \n",
    "\n",
    "MST_prim(graph)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "aLpUUY_DEze0"
   },
   "source": [
    "#### **Kruskal's Algorithm**\n",
    "* **heap** is used to store edges\n",
    "* This algorithm based on union find structure\n",
    "* O(ElogE)\n",
    "\n",
    "**Algorithm**\n",
    "1. Generate sets from each vertex in DSU\n",
    "2. Push all edges to the heap\n",
    "3. Pop the smallest one\n",
    "4. If the roots of smallest edge's vertices different, union them and add this edge to the result."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "hoXXUuhcFmQ4"
   },
   "outputs": [],
   "source": [
    "from heapq import *\n",
    "\n",
    "class DSU:\n",
    "  def __init__(self):\n",
    "    self.rank = {}\n",
    "    self.parent = {}\n",
    "\n",
    "  def make_set(self, x):\n",
    "    if x not in self.parent:\n",
    "      self.parent[x] = x\n",
    "      self.rank[x] = 0\n",
    "\n",
    "  def find(self, x):\n",
    "    if self.parent[x] != x:\n",
    "      self.parent[x] = self.find(self.parent[x])\n",
    "    return self.parent[x]\n",
    "\n",
    "  def union(self, x1, x2):\n",
    "    r1, r2 = self.find(x1), self.find(x2)\n",
    "\n",
    "    if self.rank[r1] < self.rank[r2]:\n",
    "      self.parent[r1] = r2\n",
    "    elif self.rank[r1] > self.rank[r2]:\n",
    "      self.parent[r2] = r1\n",
    "    else:\n",
    "      self.parent[r1] = r2\n",
    "      self.rank[r2] += 1\n",
    "\n",
    "def MST_kruskal(graph):\n",
    "\n",
    "  heap, result = [], []\n",
    "  adj_list = create_adjlist(graph)\n",
    "  N = len(adj_list)\n",
    "\n",
    "  dsu = DSU()\n",
    "  for v in range(N):\n",
    "    dsu.make_set(v)\n",
    "\n",
    "  # push all the edges to the heap\n",
    "  for s in adj_list:\n",
    "    for d, w in adj_list[s]:\n",
    "      heappush(heap, (w, s, d))\n",
    "\n",
    "  while heap:\n",
    "    weight, source, dest = heappop(heap)    \n",
    "\n",
    "    root_s = dsu.find(source)\n",
    "    root_d = dsu.find(dest) \n",
    "\n",
    "    if root_s != root_d:\n",
    "      result.append((source, dest, weight))\n",
    "      dsu.union(source, dest)\n",
    "\n",
    "  return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 33
    },
    "colab_type": "code",
    "id": "hD3tFDatI_q_",
    "outputId": "186e4768-207c-4463-b011-bb863a05a037"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, 3, 2), (1, 2, 3), (1, 3, 4), (1, 4, 5)]"
      ]
     },
     "execution_count": 79,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph = [ [0, 5, 0, 2, 0], \n",
    "          [5, 0, 3, 4, 5], \n",
    "          [0, 3, 0, 0, 7], \n",
    "          [2, 4, 0, 0, 9], \n",
    "          [0, 5, 7, 9, 0]] \n",
    "\n",
    "MST_kruskal(graph)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "1a5JeLxKDLdp"
   },
   "source": [
    "### **Union-Find**\n",
    "\n",
    "The shapes are taken from [link](https://algorithms.tutorialhorizon.com/disjoint-set-union-find-algorithm-union-by-rank-and-path-compression/).\n",
    "\n",
    "#### **Union by rank:** attaches shorter tree to the root of taller tree.\n",
    "\n",
    "  * Time complexity:\n",
    "    * find(x) - O(logN)\n",
    "    * union(x) - O(logN)\n",
    "\n",
    "\n",
    "![](https://drive.google.com/uc?id=1A55hvpPAN6Xt-vN31mFt0UpleHLHn1CK)\n",
    "\n",
    "#### **Path compression:** Flattens the structure whenever find is called.\n",
    "\n",
    "* Time complexity is smaller than O(logN)\n",
    "\n",
    "![](https://drive.google.com/uc?id=1FkkMY-OThPIGzqhk4lNe1fPXypz7JgdR)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "2V6QUFR2DOIP"
   },
   "outputs": [],
   "source": [
    "class DSU:\n",
    "  def __init__(self):\n",
    "    self.parents, self.ranks = {}, {}\n",
    "    \n",
    "  def union(self, x, y):\n",
    "    parent_x, parent_y = self.find(x), self.find(y)\n",
    "\n",
    "    if self.ranks[parent_x] > self.ranks[parent_y]:\n",
    "      self.parents[parent_y] = parent_x\n",
    "\n",
    "    elif self.ranks[parent_y] > self.ranks[parent_x]:\n",
    "      self.parents[parent_x] = parent_y\n",
    "\n",
    "    else:\n",
    "      self.parents[parent_x] = parent_y\n",
    "      self.ranks[parent_y] += 1\n",
    "\n",
    "  def make_set(self, x):\n",
    "    if x not in self.parents:\n",
    "      self.parents[x] = x\n",
    "      self.ranks[x] = 0\n",
    "    return x\n",
    "\n",
    "  def find(self, x):\n",
    "    while x != self.parents[x]:\n",
    "      x = self.parents[x]\n",
    "    return x\n",
    "    \n",
    "    \n",
    "  def find_compressed(self, x):\n",
    "    if self.parents[x] != x:\n",
    "      self.parents[x] = self.find_compressed(self.parents[x])\n",
    "    return self.parents[x]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 52
    },
    "colab_type": "code",
    "id": "rQtAA6Rk3tTO",
    "outputId": "1ed8708b-f4c5-4156-d35b-26faf2cf4847"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "union(0, 1) {0: 1, 1: 1, 2: 2}\n",
      "union(1, 2) {0: 1, 1: 1, 2: 1}\n"
     ]
    }
   ],
   "source": [
    "dsu = DSU()\n",
    "\n",
    "dsu.make_set(0)\n",
    "dsu.make_set(1)\n",
    "dsu.make_set(2)\n",
    "\n",
    "dsu.union(0, 1)\n",
    "print('union(0, 1)', dsu.parents)\n",
    "dsu.union(1, 2)\n",
    "print('union(1, 2)', dsu.parents)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "RzcDz1G61ecP"
   },
   "source": [
    "### **Graph Coloring**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "M_1cfVAg3wK_"
   },
   "source": [
    "#### **Minimum number of colors required to color a graph**\n",
    "\n",
    "The main idea is that assigning colors to the edges with most dependencies first.\n",
    "\n",
    "1. Count the edges of each vertex\n",
    "2. Choose the one with most outgoing edges\n",
    "3. Color it with next available color\n",
    "4. Go to the next vertex with most outgoing edges\n",
    "* Time complexity - O(V^2+E)\n",
    "\n",
    "![](https://drive.google.com/uc?id=1UbV1OVHUl7F_rCmv3ACZpX3KBHlUvrzc)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "4izT0cc932Ih",
    "outputId": "115fd3a6-26c8-4c2d-980d-95d0f8ca2de1"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'c': 0, 'a': 1, 'd': 2, 'e': 1, 'b': 2, 'f': 2}\n"
     ]
    }
   ],
   "source": [
    "def min_coloring(graph):\n",
    "  color_map = {}\n",
    "\n",
    "  # O(VlogV)\n",
    "  sorted_vertices = sorted([v for v in graph], key=lambda x:len(graph[x]), reverse=True)\n",
    "\n",
    "  # O(V)\n",
    "  for n in sorted_vertices:\n",
    "    \n",
    "    # O(E) - in total (2E)\n",
    "    # find the not-available colors\n",
    "    neighbor_colors = set()\n",
    "    for adj in graph[n]:\n",
    "      if adj in color_map:\n",
    "        neighbor_colors.add(color_map[adj])\n",
    "\n",
    "    # O(V)\n",
    "    # find the next available color\n",
    "    for color in range(len(graph)):\n",
    "      if color not in neighbor_colors:\n",
    "        color_map[n] = color \n",
    "        break\n",
    "  return color_map\n",
    "\n",
    "if __name__ == '__main__':\n",
    "  graph = {\n",
    "    'a': list('bcd'),\n",
    "    'b': list('ac'),\n",
    "    'c': list('abdef'),\n",
    "    'd': list('ace'),\n",
    "    'e': list('cdf'),\n",
    "    'f': list('ce')\n",
    "  }\n",
    "  print(min_coloring(graph))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "4POlzBVN32oE"
   },
   "source": [
    "#### **2-colorability**\n",
    "1. For each node if it is not assigned to a color, start applying bfs/dfs\n",
    "2. If adj has same color with current node, return False\n",
    "3. Else if adj not colored, color it and put to the stack or queue\n",
    "\n",
    "**NOTE:** Same can be done recursively as well.\n",
    "\n",
    "* Time complexity - O(V+E)\n",
    "* Space complexity - O(V+E)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "vpY_0vIzK9BP"
   },
   "outputs": [],
   "source": [
    "def bfs_2_color(graph):\n",
    "  color_map = {}\n",
    "  N = len(graph)\n",
    "\n",
    "  # O(N)\n",
    "  for node in range(N):\n",
    "      \n",
    "      if node not in color_map:\n",
    "          queue = deque()\n",
    "\n",
    "          queue.append(node)\n",
    "          color_map[node] = 0\n",
    "\n",
    "          # BFS\n",
    "          # O(E)\n",
    "          while queue:\n",
    "              current = queue.popleft()\n",
    "\n",
    "              for adj in graph[current]:\n",
    "                  if adj in color_map and color_map[adj] == color_map[current]:\n",
    "                      return False\n",
    "\n",
    "                  if adj not in color_map:\n",
    "                      color_map[adj] = 1 - color_map[current]\n",
    "                      queue.append(adj)\n",
    "                  \n",
    "  return True\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "3eB_CAHCPAgK"
   },
   "outputs": [],
   "source": [
    " def dfs_2_color(graph):\n",
    "  color_map = {}\n",
    "  N = len(graph)\n",
    "\n",
    "\n",
    "  for node in range(N):\n",
    "      \n",
    "      if node not in color_map:\n",
    "          stack = []\n",
    "\n",
    "          stack.append(node)\n",
    "          color_map[node] = 0\n",
    "\n",
    "          # DFS\n",
    "          while stack:\n",
    "              current = stack.pop()\n",
    "\n",
    "              for adj in graph[current]:\n",
    "                  if adj in color_map and color_map[adj] == color_map[current]:\n",
    "                      return False\n",
    "\n",
    "                  if adj not in color_map:\n",
    "                      color_map[adj] = 1 - color_map[current]\n",
    "                      stack.append(adj)\n",
    "                  \n",
    "  return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "MRJSMXgLPhsY",
    "outputId": "55abf69a-8ff0-4d33-bc97-2a6d6e72b22a"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 11,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph_true = [[1,3], [0,2], [1,3], [0,2]]\n",
    "graph_false = [[1,2,3], [0,2], [0,1,3], [0,2]]\n",
    "\n",
    "dfs_2_color(graph_false)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "5akGQYis4EWa"
   },
   "source": [
    "#### **m-colorability**\n",
    "* Time complexity - O(m^V)\n",
    "* Space complexity - O(V)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "lblqIlrFVWj9"
   },
   "outputs": [],
   "source": [
    "def graph_coloring_m(graph, m):\n",
    "  def safe(node, color):\n",
    "    for adj in graph[node]:\n",
    "      if adj in color_map and color_map[adj] == color:\n",
    "        return False\n",
    "    \n",
    "    return True\n",
    "\n",
    "  # detects the current graph is m colorable\n",
    "  def color_graph(node):\n",
    "\n",
    "    # base case (reached to the end)\n",
    "    if node == N:\n",
    "      return True\n",
    "    \n",
    "    else:\n",
    "      for color in range(1, m+1):\n",
    "        if safe(node, color):\n",
    "          color_map[node] = color\n",
    "\n",
    "          if color_graph(node+1):\n",
    "            return True\n",
    "          \n",
    "          del color_map[node]\n",
    "\n",
    "      return False\n",
    "\n",
    "  N = len(graph)\n",
    "\n",
    "  if m > N:\n",
    "    print('Graph is not ' + str(m) + ' colorable :(')\n",
    "  else:\n",
    "    color_map = {}\n",
    "\n",
    "    if color_graph(0):\n",
    "      print('Graph is ' + str(m) + ' colorable!')\n",
    "    else:\n",
    "      print('Graph is not ' + str(m) + ' colorable :(')\n",
    "\n",
    "  #  print(color_map)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "ozvz-o0sZsp_",
    "outputId": "d2ef124e-0c15-41a4-b536-2d9f5753bd9d"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Graph is not 5 colorable :(\n"
     ]
    }
   ],
   "source": [
    "graph = [[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]]\n",
    "graph_coloring_m(graph, 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "ispwmFx7K_My"
   },
   "source": [
    "## **Floyd Warschall (All pairs Shortest Path)**\n",
    "Given a directed, weighted graph, we wish to find, for every pair of vertices u and v, the cost of a cheapest path from u to v. This should be called the “all pairs cheapest path problem”, and that is how we will refer to it from now on, but traditionally it has been called the **“all pairs shortest path problem”**. We will give the Floyd-Warshall dynamic programming algorithm for this problem.\n",
    "\n",
    "**Representation:** \n",
    "* Vertices: V = {1, · · · n}\n",
    "* Cost matrix nxn dim: costs c(i, j) \n",
    "  * c(i, i) = 0\n",
    "  * c(i, j) = ∞ no edge btw i and j\n",
    "* D(i, j) is the distance matrix which represents cost of a cheapest path from i to j. (**auxilary array**)\n",
    "\n",
    "**Goal:** Compute all values in distance matrix D."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "MHKQ_8QDLPLf"
   },
   "source": [
    "### **Solution**\n",
    "1. Describe the array to compute\n",
    "   * A distance array will be created as D with nxn dimension, holding shortest distance from i to j\n",
    "\n",
    "2. Give the recurrence\n",
    "   * **Simplest case**     \n",
    "      * `D[i, i] = 0`\n",
    "      * `D[i, j] = C[i, j]` for each edge in the graph\n",
    "      * The rest is equal it infinity.\n",
    "\n",
    "  * **Recurrence**\n",
    "\n",
    "      `D[i, j] = min{ D[i, j], D[i, k] + D[k, i]}` with/without the kth verices. For every vertex k, we calculate the best path from i to j with/without k. For this reason, the for loop order should start with k. If not, the correct result is not given. Check the image below.\n",
    "\n",
    "3. Create high level programming (Implement the solution from step 2. Next cell).\n",
    "\n",
    "4. Create the program the calculate the optiomal solution. Show the actual path with smallest cost.\n",
    "\n",
    "**Time Complexity** $O(N^{3})$ \\\\\n",
    "**Space Complexity** $O(N^{2})$\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "B6SqA1ESLk4x"
   },
   "outputs": [],
   "source": [
    "# Step 3\n",
    "import sys\n",
    "\n",
    "def get_dist_arr(adj_list, cost_arr):\n",
    "  n = len(cost_arr)\n",
    "  dist = [[float('inf') for i in range(n)] for j in range(n)]\n",
    "  last_node = [[-1 for i in range(n)] for j in range(n)]\n",
    "\n",
    "  # simplest cases:\n",
    "  \n",
    "  # distance to itself\n",
    "  for i in range(n):\n",
    "    dist[i][i] = 0\n",
    "\n",
    "  # direct distance\n",
    "  for i in adj_list.keys():\n",
    "    for j in adj_list[i]:\n",
    "      dist[i][j] = cost_arr[i][j]\n",
    "    \n",
    "  for k in range(n):\n",
    "    for i in range(n):\n",
    "      for j in range(n):\n",
    "        if dist[i][k] + dist[k][j] < dist[i][j]:\n",
    "          dist[i][j] = dist[i][k] + dist[k][j]\n",
    "          last_node[i][j] = k\n",
    "  \n",
    "  return dist, last_node\n",
    "  \n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "tWicux26Lorq"
   },
   "outputs": [],
   "source": [
    "# Step 4 \n",
    "# Compute the least cost path from i to j\n",
    "\n",
    "def print_optimal_path(i, j, last_node):\n",
    "  k = last_node[i][j]\n",
    "\n",
    "  if k == -1:\n",
    "    print(i, j)\n",
    "  else:\n",
    "    print_optimal_path(i, k, last_node)\n",
    "    print_optimal_path(k, j, last_node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 121
    },
    "colab_type": "code",
    "id": "qiVZP-ozMFv1",
    "outputId": "524a1d86-5094-4161-c3ec-c19f7f4ba5e4"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 2\n",
      "2 1\n",
      "---------\n",
      "0 2\n",
      "2 3\n",
      "3 5\n"
     ]
    }
   ],
   "source": [
    "adjList = {0:[1, 2], 1:[3], 2:[1, 3, 4], 3:[5], 4:[3,5], 5:[]}\n",
    "cost_arr = [[0 for i in range(6)] for i in range(6)]\n",
    "cost_arr[0][1] = 4\n",
    "cost_arr[0][2] = 1\n",
    "cost_arr[1][3] = 3\n",
    "cost_arr[2][1] = 2\n",
    "cost_arr[2][3] = 2\n",
    "cost_arr[2][4] = 1\n",
    "cost_arr[3][5] = 3\n",
    "cost_arr[4][3] = 2\n",
    "cost_arr[4][5] = 5\n",
    "\n",
    "dist, last_node = get_dist_arr(adjList, cost_arr)\n",
    "print_optimal_path(0,1, last_node)\n",
    "print('---------')\n",
    "print_optimal_path(0, 5, last_node)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "15xuTEy0Kw4i"
   },
   "source": [
    "# **13. Mindful Tricks**\n",
    "* The diagonals of the array has same (row+col) value.\n",
    "* To find the largest value of 1s in an array same with another array, check the ones with same distances."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "YTGA3gFLoXuo"
   },
   "source": [
    "# **Math Functions**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "8bFn9F4ooaem"
   },
   "source": [
    "### **Gratest Common Divisor (gcd)**\n",
    "* Time complexity - O(log(min(a, b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "iNqAMJDFod_7",
    "outputId": "8b64a1c5-8476-434f-b5e5-2c8375c68349"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 1,
     "metadata": {
      "tags": []
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def gcd(a, b):\n",
    "    while b > 0: \n",
    "        a, b = b, a % b\n",
    "    return a\n",
    "\n",
    "gcd(8, 12)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Z7g1DKOCs0-z"
   },
   "source": [
    "### **Least Common Multiplier (lcm)**\n",
    "* `gcd * lcm = a * b`\n",
    "\n",
    "![](https://drive.google.com/uc?id=1DR2HtBnXESZoWab2DORw6JZBSRI-joao)\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "CheatSheet",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}