Data-Structures-Algorithms.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Common Data Structures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Stack(object):\n",
    "    '''Implements stack usin a python list\n",
    "    '''\n",
    "    def __init__(self):\n",
    "        self.items = list()\n",
    "    def push(self,item):\n",
    "        return self.items.append(item)\n",
    "    def pop(self, item):\n",
    "        return self.items.pop(item)\n",
    "    def peek(self):\n",
    "        return len(self.items) - 1\n",
    "    def isEmpty(self):\n",
    "        return len(self.items) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "new_stack = Stack()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "new_stack.isEmpty()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## LinkedList"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Element(object):\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.next = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [],
   "source": [
    "      class LinkedList(object):\n",
    "    def __init__(self, head=None):\n",
    "        self.head = head\n",
    "        \n",
    "    def append(self, new_element):\n",
    "        current = self.head\n",
    "        if self.head:\n",
    "            while current.next:\n",
    "                current = current.next\n",
    "            current.next = new_element\n",
    "        else:\n",
    "            self.head = new_element\n",
    "            \n",
    "    def get_position(self, position):\n",
    "        \"\"\"Get an element from a particular position.\n",
    "        Assume the first position is \"1\".\n",
    "        Return \"None\" if position is not in the list.\"\"\"\n",
    "        current_pos = self.head\n",
    "        count = 1\n",
    "        while count < position:\n",
    "            if current_pos.next:\n",
    "                current_pos = current_pos.next\n",
    "            else:\n",
    "                return None\n",
    "            count += 1\n",
    "        return current_pos\n",
    "    \n",
    "    def insert(self, new_element, position):\n",
    "        \"\"\"Insert a new node at the given position.\n",
    "        Assume the first position is \"1\".\n",
    "        Inserting at position 3 means between\n",
    "        the 2nd and 3rd elements.\"\"\"\n",
    "        current_pos = self.head\n",
    "        count = 1\n",
    "        while count < position-1:\n",
    "            if current_pos.next:\n",
    "                current_pos = current_pos.next\n",
    "            else:\n",
    "                return None\n",
    "            count += 1\n",
    "        new_element.next = current_pos.next\n",
    "        current_pos.next = new_element\n",
    "    \n",
    "    \n",
    "    def delete(self, value):\n",
    "        \"\"\"Delete the first node with a given value.\"\"\"\n",
    "        prev_pos = None\n",
    "        curr_pos = self.head\n",
    "        \n",
    "        while curr_pos.value != value:\n",
    "            if curr_pos.next:\n",
    "                prev_pos = curr_pos\n",
    "                curr_pos = curr_pos.next\n",
    "            else: raise ValueError\n",
    "        if not prev_pos:\n",
    "            if curr_pos.next:\n",
    "                curr_pos = curr_pos.next\n",
    "                self.head = curr_pos\n",
    "        else:\n",
    "            prev_pos.next = curr_pos.next\n",
    "            curr_pos = curr_pos.next  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test cases\n",
    "# Set up some Elements\n",
    "e1 = Element(1)\n",
    "e2 = Element(2)\n",
    "e3 = Element(3)\n",
    "e4 = Element(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Start setting up a LinkedList\n",
    "ll = LinkedList(e1)\n",
    "ll.append(e2)\n",
    "ll.append(e3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "# Test get_position\n",
    "# Should print 3\n",
    "print(ll.head.next.next.value)\n",
    "# Should also print 3\n",
    "print(ll.get_position(3).value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "2\n",
      "4\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "# Test insert\n",
    "ll.insert(e4,3)\n",
    "# Should print 4 now\n",
    "print(ll.get_position(3).value)\n",
    "\n",
    "# Test delete\n",
    "ll.delete(1)\n",
    "# Should print 2 now\n",
    "print(ll.get_position(1).value)\n",
    "# Should print 4 now\n",
    "print (ll.get_position(2).value)\n",
    "# Should print 3 now\n",
    "print (ll.get_position(3).value)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stack using LinkedList object"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"Add a couple methods to our LinkedList class,\n",
    "and use that to implement a Stack.\n",
    "You have 4 functions below to fill in:\n",
    "insert_first, delete_first, push, and pop.\n",
    "Think about this while you're implementing:\n",
    "why is it easier to add an \"insert_first\"\n",
    "function than just use \"append\"?\"\"\"\n",
    "\n",
    "class Element(object):\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.next = None\n",
    "        \n",
    "class LinkedList(object):\n",
    "    def __init__(self, head=None):\n",
    "        self.head = head\n",
    "        \n",
    "    def append(self, new_element):\n",
    "        current = self.head\n",
    "        if self.head:\n",
    "            while current.next:\n",
    "                current = current.next\n",
    "            current.next = new_element\n",
    "        else:\n",
    "            self.head = new_element\n",
    "\n",
    "    def insert_first(self, new_element):\n",
    "        \"Insert new element as the head of the LinkedList\"\n",
    "        new_element.next = self.head\n",
    "        self.head = new_element\n",
    "\n",
    "    def delete_first(self):\n",
    "        \"Delete the first (head) element in the LinkedList as return it\"\n",
    "        if self.head:\n",
    "            curr_head = self.head\n",
    "            self.head = self.head.next\n",
    "        else: return None\n",
    "        return curr_head\n",
    "            \n",
    "\n",
    "class Stack(object):\n",
    "    def __init__(self,top=None):\n",
    "        self.ll = LinkedList(top)\n",
    "\n",
    "    def push(self, new_element):\n",
    "        \"Push (add) a new element onto the top of the stack\"\n",
    "        self.ll.insert_first(new_element)\n",
    "\n",
    "    def pop(self):\n",
    "        \"Pop (remove) the first element off the top of the stack and return it\"\n",
    "        return self.ll.delete_first()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test cases\n",
    "# Set up some Elements\n",
    "e1 = Element(1)\n",
    "e2 = Element(2)\n",
    "e3 = Element(3)\n",
    "e4 = Element(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "2\n",
      "1\n",
      "None\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "# Start setting up a Stack\n",
    "stack = Stack(e1)\n",
    "\n",
    "# Test stack functionality\n",
    "stack.push(e2)\n",
    "stack.push(e3)\n",
    "print (stack.pop().value)\n",
    "print (stack.pop().value)\n",
    "print (stack.pop().value)\n",
    "print (stack.pop())\n",
    "stack.push(e4)\n",
    "print (stack.pop().value)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Queue:\n",
    "    def __init__(self, head=None):\n",
    "        self.storage = [head]\n",
    "\n",
    "    def enqueue(self, new_element):\n",
    "        if None in self.storage:\n",
    "            self.storage = [new_element]\n",
    "        else:\n",
    "            self.storage = self.storage + [new_element]\n",
    "\n",
    "    def peek(self):\n",
    "        return self.storage[0] \n",
    "\n",
    "    def dequeue(self):\n",
    "        temp = self.storage[0]\n",
    "        return self.storage[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "# Setup\n",
    "q = Queue(1)\n",
    "q.enqueue(2)\n",
    "q.enqueue(3)\n",
    "\n",
    "# Test peek\n",
    "# Should be 1\n",
    "print (q.peek())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "invalid syntax (<ipython-input-103-163512fd996c>, line 3)",
     "output_type": "error",
     "traceback": [
      "\u001b[0;36m  File \u001b[0;32m\"<ipython-input-103-163512fd996c>\"\u001b[0;36m, line \u001b[0;32m3\u001b[0m\n\u001b[0;31m    print q.dequeue()\u001b[0m\n\u001b[0m          ^\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\u001b[0;31m:\u001b[0m invalid syntax\n"
     ]
    }
   ],
   "source": [
    "# Test dequeue\n",
    "# Should be 1\n",
    "print q.dequeue()\n",
    "\n",
    "# Test enqueue\n",
    "q.enqueue(4)\n",
    "# Should be 2\n",
    "print q.dequeue()\n",
    "# Should be 3\n",
    "print q.dequeue()\n",
    "# Should be 4\n",
    "print q.dequeue()\n",
    "q.enqueue(5)\n",
    "# Should be 5\n",
    "print(q.peek())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Quick Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "metadata": {},
   "outputs": [],
   "source": [
    "def quickSort(arr):\n",
    "    low = 0\n",
    "    high = len(arr) - 1\n",
    "    \n",
    "    def partition(arr):\n",
    "        # pivot (Element to be placed at right position)\n",
    "        pivot = arr[high]\n",
    "\n",
    "        i = low - 1\n",
    "\n",
    "        for j in range(len(arr)-1):\n",
    "            if arr[j] < pivot:\n",
    "                i += 1\n",
    "                arr[j], arr[i] = arr[i], arr[j]\n",
    "        arr[i+1], arr[high] = arr[high], arr[i+1]\n",
    "        \n",
    "        return arr, i+1\n",
    "    \n",
    "    if low < high:\n",
    "        arr, pi = partition(arr)\n",
    "        arr[0:pi] = quickSort(arr[0:pi])\n",
    "        arr[pi+1:] = quickSort(arr[pi+1:])\n",
    "    \n",
    "    return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 144,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 2, 40, 50, 70, 80, 90]"
      ]
     },
     "execution_count": 144,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [2, 80, 2, 90, 40, 50, 70]\n",
    "\n",
    "quickSort(arr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Multidimensional Arrays"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 174,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Matrix Multiplication\n",
    "A = [[1, 2, 3],\n",
    "     [3, 2, 1],\n",
    "     [1, 3, 5],\n",
    "     [4, 2, 1]]\n",
    "\n",
    "B = [[1, 2],\n",
    "     [3, 2],\n",
    "     [1, 3]]\n",
    "\n",
    "C = [[0, 0],\n",
    "    [0, 0],\n",
    "    [0, 0],\n",
    "    [0, 0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 179,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[10, 15],\n",
       "       [10, 13],\n",
       "       [15, 23],\n",
       "       [11, 15]])"
      ]
     },
     "execution_count": 179,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D_test = np.array(A)@np.array(B)\n",
    "D_test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 178,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[10, 15], [10, 13], [15, 23], [11, 15]]\n"
     ]
    }
   ],
   "source": [
    "for i in range(len(A)):\n",
    "    for j in range(len(B[0])):\n",
    "        C[i][j] = 0\n",
    "        for k in range(len(B)):\n",
    "            C[i][j] += A[i][k]*B[k][j]\n",
    "print(C)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 180,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 180,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.allclose(D_test, np.array(C))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Given nums = [2, 7, 11, 15], target = 9,\n",
    "\n",
    "Because nums[0] + nums[1] = 2 + 7 = 9,\n",
    "return [0, 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        idx_arr = []\n",
    "        for idx, val in enumerate(nums):\n",
    "            for idx_comp, val_comp in enumerate(nums[idx:])\n",
    "                if (val + val_comp == 5):\n",
    "                    idx_arr += [idx, ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 222,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        arr_len = len(nums)\n",
    "        for idx in range(arr_len):\n",
    "            for idx_comp in range(idx+1, arr_len):\n",
    "                if (nums[idx] + nums[idx_comp] == target):\n",
    "                    return [idx, idx_comp]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 223,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The slowest run took 22.64 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "1000000 loops, best of 5: 806 ns per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit Solution().twoSum(nums = [3, 2, 4], target = 6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 236,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        temp_dict = {}\n",
    "        for idx in range(len(nums)):\n",
    "            num = nums[idx]\n",
    "            rem = target - num\n",
    "            if rem in temp_dict:\n",
    "                return [temp_dict[rem], idx]\n",
    "            else:\n",
    "                temp_dict[num] = idx\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 238,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The slowest run took 15.74 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "1000000 loops, best of 5: 578 ns per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit Solution().twoSum(nums = [3, 2, 4], target = 6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 237,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2]"
      ]
     },
     "execution_count": 237,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Solution().twoSum(nums = [3, 2, 4], target = 6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 244,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Recursive Fibonacci with Memoization\n",
    "dict_arr = {}\n",
    "def fib(n):\n",
    "    if n in dict_arr: \n",
    "        return dict_arr[n]\n",
    "    if n<=1:\n",
    "        dict_arr[n] = n\n",
    "        return n\n",
    "    f = fib(n-1) + fib(n-2)\n",
    "    dict_arr[n] = f\n",
    "    return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 247,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The slowest run took 34.32 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 5: 79 ns per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit fib(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 248,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The slowest run took 21.13 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "10000000 loops, best of 5: 80 ns per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit fib(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 243,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1: 1, 0: 0, 2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55}"
      ]
     },
     "execution_count": 243,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dict_arr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Hash Tables"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 277,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"Write a HashTable class that stores strings\n",
    "in a hash table, where keys are calculated\n",
    "using the first two letters of the string.\"\"\"\n",
    "\n",
    "class HashTable(object):\n",
    "    def __init__(self):\n",
    "        self.table = [None]*10000\n",
    "\n",
    "    def store(self, string):\n",
    "        \"\"\"Input a string that's stored in \n",
    "        the table.\"\"\"\n",
    "        idx = self.calculate_hash_value(string)\n",
    "        self.table[idx] = [string]\n",
    "        return idx\n",
    "\n",
    "    def lookup(self, string):\n",
    "        \"\"\"Return the hash value if the\n",
    "        string is already in the table.\n",
    "        Return -1 otherwise.\"\"\"\n",
    "        idx = self.calculate_hash_value(string)\n",
    "        val = self.table[idx]\n",
    "        if val is None:\n",
    "            return -1\n",
    "        return idx\n",
    "\n",
    "    def calculate_hash_value(self, string):\n",
    "        \"\"\"Helper function to calulate a\n",
    "        hash value from a string.\"\"\"\n",
    "        return ord(string[0])*100 + ord(string[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 278,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 278,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# ord('C')\n",
    "# chr(67)\n",
    "[None]*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 279,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Setup\n",
    "hash_table = HashTable()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 280,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8568\n",
      "-1\n",
      "8568\n",
      "8568\n"
     ]
    }
   ],
   "source": [
    "# Test calculate_hash_value\n",
    "# Should be 8568\n",
    "print (hash_table.calculate_hash_value('UDACITY'))\n",
    "\n",
    "# Test lookup edge case\n",
    "# Should be -1\n",
    "print (hash_table.lookup('UDACITY'))\n",
    "\n",
    "# Test store\n",
    "hash_table.store('UDACITY')\n",
    "# Should be 8568\n",
    "print (hash_table.lookup('UDACITY'))\n",
    "\n",
    "# Test store edge case\n",
    "hash_table.store('UDACIOUS')\n",
    "# Should be 8568\n",
    "print (hash_table.lookup('UDACIOUS'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Binary Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 386,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class BinaryTree(object):\n",
    "    def __init__(self, root):\n",
    "        self.root = Node(root)\n",
    "\n",
    "    def search(self, find_val):\n",
    "        \"\"\"Return True if the value\n",
    "        is in the tree, return\n",
    "        False otherwise.\"\"\"\n",
    "        if self.preorder_search(self.root, find_val):\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "    def print_tree(self):\n",
    "        \"\"\"Print out all tree nodes\n",
    "        as they are visited in\n",
    "        a pre-order traversal.\"\"\"\n",
    "        traversal = ''\n",
    "        traversal = self.preorder_print(self.root, '')\n",
    "        return traversal[:-1]\n",
    "\n",
    "    def preorder_search(self, start, find_val):\n",
    "        \"\"\"Helper method - use this to create a \n",
    "        recursive search solution.\"\"\"\n",
    "        bool = False\n",
    "        if start.value == find_val:\n",
    "            bool = True\n",
    "        else:\n",
    "            if not bool:\n",
    "                if start.left:\n",
    "                    bool = self.preorder_search(start.left, find_val)\n",
    "            if not bool:\n",
    "                if start.right:\n",
    "                    bool = self.preorder_search(start.right, find_val)\n",
    "        return bool\n",
    "\n",
    "    def preorder_print(self, start, traversal):\n",
    "        \"\"\"Helper method - use this to create a \n",
    "        recursive print solution.\"\"\"\n",
    "        traversal = traversal + str(start.value) + '-'\n",
    "        print(traversal)\n",
    "        if start.left:\n",
    "            traversal = self.preorder_print(start.left, traversal)\n",
    "        if start.right: \n",
    "            traversal = self.preorder_print(start.right, traversal)\n",
    "        return traversal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 387,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Set up tree\n",
    "tree = BinaryTree(1)\n",
    "tree.root.left = Node(2)\n",
    "tree.root.right = Node(3)\n",
    "tree.root.left.left = Node(4)\n",
    "tree.root.left.right = Node(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 388,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n",
      "1-\n",
      "1-2-\n",
      "1-2-4-\n",
      "1-2-4-5-\n",
      "1-2-4-5-3-\n",
      "1-2-4-5-3\n"
     ]
    }
   ],
   "source": [
    "# Test search\n",
    "# Should be True\n",
    "print (tree.search(4))\n",
    "# Should be False\n",
    "print (tree.search(6))\n",
    "\n",
    "# Test print_tree\n",
    "# Should be 1-2-4-5-3\n",
    "print (tree.print_tree())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### BST"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 416,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class BST(object):\n",
    "    def __init__(self, root):\n",
    "        self.root = Node(root)\n",
    "    \n",
    "    def add_node(self, current_node, new_val):\n",
    "        if new_val <= current_node.value:\n",
    "            if current_node.left:\n",
    "                self.add_node(current_node.left, new_val)\n",
    "            else:\n",
    "                current_node.left = Node(new_val)\n",
    "        if new_val > current_node.value:\n",
    "            if current_node.right:\n",
    "                self.add_node(current_node.right, new_val)\n",
    "            else:\n",
    "                current_node.right = Node(new_val)           \n",
    "    \n",
    "    def search_preorder(self, current_node, find_val):\n",
    "        bool = False\n",
    "        if current_node.value == find_val:\n",
    "            return True\n",
    "        else:\n",
    "            if find_val <= current_node.value:\n",
    "                if current_node.left:\n",
    "                    return self.search_preorder(current_node.left, find_val)\n",
    "            else:\n",
    "                if current_node.right:\n",
    "                    return self.search_preorder(current_node.right, find_val)\n",
    "        return False\n",
    "    \n",
    "    def insert(self, new_val):\n",
    "        self.add_node(self.root, new_val)\n",
    "    \n",
    "    def search(self, find_val):\n",
    "        return self.search_preorder(self.root, find_val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 417,
   "metadata": {},
   "outputs": [],
   "source": [
    "    def insert(self, data):\n",
    "\n",
    "        if self.data:\n",
    "            if data < self.data:\n",
    "                if self.left is None:\n",
    "                    self.left = Node(data)\n",
    "                else:\n",
    "                    self.left.insert(data)\n",
    "            elif data > self.data:\n",
    "                if self.right is None:\n",
    "                    self.right = Node(data)\n",
    "                else:\n",
    "                    self.right.insert(data)\n",
    "        else:\n",
    "            self.data = data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 418,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "# Set up tree\n",
    "tree = BST(4)\n",
    "\n",
    "# Insert elements\n",
    "tree.insert(2)\n",
    "tree.insert(1)\n",
    "tree.insert(3)\n",
    "tree.insert(5)\n",
    "\n",
    "# Check search\n",
    "# Should be True\n",
    "print (tree.search(4))\n",
    "# Should be False\n",
    "print (tree.search(6))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Graphs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 474,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.edges = []\n",
    "\n",
    "class Edge(object):\n",
    "    def __init__(self, value, node_from, node_to):\n",
    "        self.value = value\n",
    "        self.node_from = node_from\n",
    "        self.node_to = node_to\n",
    "\n",
    "class Graph(object):\n",
    "    def __init__(self, nodes=[], edges=[]):\n",
    "        self.nodes = nodes\n",
    "        self.edges = edges\n",
    "\n",
    "    def insert_node(self, new_node_val):\n",
    "        new_node = Node(new_node_val)\n",
    "        self.nodes.append(new_node)\n",
    "        \n",
    "    def insert_edge(self, new_edge_val, node_from_val, node_to_val):\n",
    "        from_found = None\n",
    "        to_found = None\n",
    "        for node in self.nodes:\n",
    "            if node_from_val == node.value:\n",
    "                from_found = node\n",
    "            if node_to_val == node.value:\n",
    "                to_found = node\n",
    "        if from_found == None:\n",
    "            from_found = Node(node_from_val)\n",
    "            self.nodes.append(from_found)\n",
    "        if to_found == None:\n",
    "            to_found = Node(node_to_val)\n",
    "            self.nodes.append(to_found)\n",
    "        new_edge = Edge(new_edge_val, from_found, to_found)\n",
    "        from_found.edges.append(new_edge)\n",
    "        to_found.edges.append(new_edge)\n",
    "        self.edges.append(new_edge)\n",
    "\n",
    "    def get_edge_list(self):\n",
    "        \"\"\"Don't return a list of edge objects!\n",
    "        Return a list of triples that looks like this:\n",
    "        (Edge Value, From Node Value, To Node Value)\"\"\"\n",
    "        edge_list = []\n",
    "        for edge in self.edges:\n",
    "            edge_list.append((edge.value, edge.node_from.value, edge.node_to.value))\n",
    "        return edge_list\n",
    "    \n",
    "    def find_max_node_val(self):\n",
    "        max_val = -1\n",
    "        for node in self.nodes:\n",
    "            if node.value > max_val:\n",
    "                max_val = node.value\n",
    "        return max_val+1\n",
    "    \n",
    "    def get_adjacency_list(self):\n",
    "        \"\"\"Don't return any Node or Edge objects!\n",
    "        You'll return a list of lists.\n",
    "        The indecies of the outer list represent\n",
    "        \"from\" nodes.\n",
    "        Each section in the list will store a list\n",
    "        of tuples that looks like this:\n",
    "        (To Node, Edge Value)\"\"\"\n",
    "        size = self.find_max_node_val()\n",
    "        adjancency_list = [None for _ in range(size)]\n",
    "        for edge in self.edges:\n",
    "            idx = edge.node_from.value\n",
    "            if type(adjancency_list[idx]) is list:\n",
    "                adjancency_list[idx].append((edge.node_to.value, edge.value))\n",
    "            else:\n",
    "                adjancency_list[idx] = [(edge.node_to.value, edge.value)]\n",
    "        return adjancency_list\n",
    "    \n",
    "    def get_adjacency_matrix(self):\n",
    "        \"\"\"Return a matrix, or 2D list.\n",
    "        Row numbers represent from nodes,\n",
    "        column numbers represent to nodes.\n",
    "        Store the edge values in each spot,\n",
    "        and a 0 if no edge exists.\"\"\"\n",
    "        arr_size = self.find_max_node_val()\n",
    "        adj_mat = [[0 for _ in range(arr_size)] for _ in range(arr_size)]\n",
    "        for edge in self.edges:\n",
    "            adj_mat[edge.node_from.value][edge.node_to.value] = edge.value\n",
    "        return adj_mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 475,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[0, 0, 0, 0, 0],\n",
       " [0, 0, 0, 0, 0],\n",
       " [0, 0, 0, 0, 0],\n",
       " [0, 0, 0, 0, 0],\n",
       " [0, 0, 0, 0, 0]]"
      ]
     },
     "execution_count": 475,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr1 = [[0]*5]*5\n",
    "arr1[1][1] = 0 \n",
    "arr1\n",
    "[[0 for b in range(5)] for a in range(5)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 477,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(100, 1, 2), (101, 1, 3), (102, 1, 4), (103, 3, 4), (100, 1, 2), (101, 1, 3), (102, 1, 4), (103, 3, 4)]\n",
      "[None, [(2, 100), (3, 101), (4, 102), (2, 100), (3, 101), (4, 102)], None, [(4, 103), (4, 103)], None]\n",
      "[[0, 0, 0, 0, 0], [0, 0, 100, 101, 102], [0, 0, 0, 0, 0], [0, 0, 0, 0, 103], [0, 0, 0, 0, 0]]\n"
     ]
    }
   ],
   "source": [
    "graph = Graph()\n",
    "graph.insert_edge(100, 1, 2)\n",
    "graph.insert_edge(101, 1, 3)\n",
    "graph.insert_edge(102, 1, 4)\n",
    "graph.insert_edge(103, 3, 4)\n",
    "# Should be [(100, 1, 2), (101, 1, 3), (102, 1, 4), (103, 3, 4)]\n",
    "print (graph.get_edge_list())\n",
    "# Should be [None, [(2, 100), (3, 101), (4, 102)], None, [(4, 103)], None]\n",
    "print (graph.get_adjacency_list())\n",
    "# Should be [[0, 0, 0, 0, 0], [0, 0, 100, 101, 102], [0, 0, 0, 0, 0], [0, 0, 0, 0, 103], [0, 0, 0, 0, 0]]\n",
    "print (graph.get_adjacency_matrix())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Graph Traversal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 552,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.edges = []\n",
    "        self.visited = False\n",
    "\n",
    "class Edge(object):\n",
    "    def __init__(self, value, node_from, node_to):\n",
    "        self.value = value\n",
    "        self.node_from = node_from\n",
    "        self.node_to = node_to\n",
    "\n",
    "# You only need to change code with docs strings that have TODO.\n",
    "# Specifically: Graph.dfs_helper and Graph.bfs\n",
    "# New methods have been added to associate node numbers with names\n",
    "# Specifically: Graph.set_node_names\n",
    "# and the methods ending in \"_names\" which will print names instead\n",
    "# of node numbers\n",
    "\n",
    "class Graph(object):\n",
    "    def __init__(self, nodes=None, edges=None):\n",
    "        self.nodes = nodes or []\n",
    "        self.edges = edges or []\n",
    "        self.node_names = []\n",
    "        self._node_map = {}\n",
    "\n",
    "    def set_node_names(self, names):\n",
    "        \"\"\"The Nth name in names should correspond to node number N.\n",
    "        Node numbers are 0 based (starting at 0).\n",
    "        \"\"\"\n",
    "        self.node_names = list(names)\n",
    "\n",
    "    def insert_node(self, new_node_val):\n",
    "        \"Insert a new node with value new_node_val\"\n",
    "        new_node = Node(new_node_val)\n",
    "        self.nodes.append(new_node)\n",
    "        self._node_map[new_node_val] = new_node\n",
    "        return new_node\n",
    "\n",
    "    def insert_edge(self, new_edge_val, node_from_val, node_to_val):\n",
    "        \"Insert a new edge, creating new nodes if necessary\"\n",
    "        nodes = {node_from_val: None, node_to_val: None}\n",
    "        for node in self.nodes:\n",
    "            if node.value in nodes:\n",
    "                nodes[node.value] = node\n",
    "                if all(nodes.values()):\n",
    "                    break\n",
    "        for node_val in nodes:\n",
    "            nodes[node_val] = nodes[node_val] or self.insert_node(node_val)\n",
    "        node_from = nodes[node_from_val]\n",
    "        node_to = nodes[node_to_val]\n",
    "        new_edge = Edge(new_edge_val, node_from, node_to)\n",
    "        node_from.edges.append(new_edge)\n",
    "        node_to.edges.append(new_edge)\n",
    "        self.edges.append(new_edge)\n",
    "\n",
    "    def get_edge_list(self):\n",
    "        \"\"\"Return a list of triples that looks like this:\n",
    "        (Edge Value, From Node, To Node)\"\"\"\n",
    "        return [(e.value, e.node_from.value, e.node_to.value)\n",
    "                for e in self.edges]\n",
    "\n",
    "    def get_edge_list_names(self):\n",
    "        \"\"\"Return a list of triples that looks like this:\n",
    "        (Edge Value, From Node Name, To Node Name)\"\"\"\n",
    "        return [(edge.value,\n",
    "                 self.node_names[edge.node_from.value],\n",
    "                 self.node_names[edge.node_to.value])\n",
    "                for edge in self.edges]\n",
    "\n",
    "    def get_adjacency_list(self):\n",
    "        \"\"\"Return a list of lists.\n",
    "        The indecies of the outer list represent \"from\" nodes.\n",
    "        Each section in the list will store a list\n",
    "        of tuples that looks like this:\n",
    "        (To Node, Edge Value)\"\"\"\n",
    "        max_index = self.find_max_index()\n",
    "        adjacency_list = [[] for _ in range(max_index)]\n",
    "        for edg in self.edges:\n",
    "            from_value, to_value = edg.node_from.value, edg.node_to.value\n",
    "            adjacency_list[from_value].append((to_value, edg.value))\n",
    "        return [a or None for a in adjacency_list] # replace []'s with None\n",
    "\n",
    "    def get_adjacency_list_names(self):\n",
    "        \"\"\"Each section in the list will store a list\n",
    "        of tuples that looks like this:\n",
    "        (To Node Name, Edge Value).\n",
    "        Node names should come from the names set\n",
    "        with set_node_names.\"\"\"\n",
    "        adjacency_list = self.get_adjacency_list()\n",
    "        def convert_to_names(pair, graph=self):\n",
    "            node_number, value = pair\n",
    "            return (graph.node_names[node_number], value)\n",
    "        def map_conversion(adjacency_list_for_node):\n",
    "            if adjacency_list_for_node is None:\n",
    "                return None\n",
    "            return map(convert_to_names, adjacency_list_for_node)\n",
    "        return [map_conversion(adjacency_list_for_node)\n",
    "                for adjacency_list_for_node in adjacency_list]\n",
    "\n",
    "    def get_adjacency_matrix(self):\n",
    "        \"\"\"Return a matrix, or 2D list.\n",
    "        Row numbers represent from nodes,\n",
    "        column numbers represent to nodes.\n",
    "        Store the edge values in each spot,\n",
    "        and a 0 if no edge exists.\"\"\"\n",
    "        max_index = self.find_max_index()\n",
    "        adjacency_matrix = [[0] * (max_index) for _ in range(max_index)]\n",
    "        for edg in self.edges:\n",
    "            from_index, to_index = edg.node_from.value, edg.node_to.value\n",
    "            adjacency_matrix[from_index][to_index] = edg.value\n",
    "        return adjacency_matrix\n",
    "\n",
    "    def find_max_index(self):\n",
    "        \"\"\"Return the highest found node number\n",
    "        Or the length of the node names if set with set_node_names().\"\"\"\n",
    "        if len(self.node_names) > 0:\n",
    "            return len(self.node_names)\n",
    "        max_index = -1\n",
    "        if len(self.nodes):\n",
    "            for node in self.nodes:\n",
    "                if node.value > max_index:\n",
    "                    max_index = node.value\n",
    "        return max_index\n",
    "\n",
    "    def find_node(self, node_number):\n",
    "        \"Return the node with value node_number or None\"\n",
    "        return self._node_map.get(node_number)\n",
    "    \n",
    "    def _clear_visited(self):\n",
    "        for node in self.nodes:\n",
    "            node.visited = False\n",
    "    \n",
    "    def dfs_helper(self, start_node):\n",
    "        \"\"\"TODO: Write the helper function for a recursive implementation\n",
    "        of Depth First Search iterating through a node's edges. The\n",
    "        output should be a list of numbers corresponding to the\n",
    "        values of the traversed nodes.\n",
    "        ARGUMENTS: start_node is the starting Node\n",
    "        MODIFIES: the value of the visited property of nodes in self.nodes \n",
    "        RETURN: a list of the traversed node values (integers).\n",
    "        \"\"\"\n",
    "        ret_list = [start_node.value]\n",
    "        start_node.visited = True\n",
    "        if start_node.edges:\n",
    "            for edge in start_node.edges:\n",
    "                if not edge.node_to.visited:\n",
    "                    ret_list += self.dfs_helper(edge.node_to)\n",
    "        return ret_list\n",
    "\n",
    "    def dfs(self, start_node_num):\n",
    "        \"\"\"Outputs a list of numbers corresponding to the traversed nodes\n",
    "        in a Depth First Search.\n",
    "        ARGUMENTS: start_node_num is the starting node number (integer)\n",
    "        MODIFIES: the value of the visited property of nodes in self.nodes\n",
    "        RETURN: a list of the node values (integers).\"\"\"\n",
    "        self._clear_visited()\n",
    "        start_node = self.find_node(start_node_num)\n",
    "        return self.dfs_helper(start_node)\n",
    "\n",
    "    def dfs_names(self, start_node_num):\n",
    "        \"\"\"Return the results of dfs with numbers converted to names.\"\"\"\n",
    "        return [self.node_names[num] for num in self.dfs(start_node_num)]\n",
    "\n",
    "    def bfs(self, start_node_num):\n",
    "        \"\"\"TODO: Create an iterative implementation of Breadth First Search\n",
    "        iterating through a node's edges. The output should be a list of\n",
    "        numbers corresponding to the traversed nodes.\n",
    "        ARGUMENTS: start_node_num is the node number (integer)\n",
    "        MODIFIES: the value of the visited property of nodes in self.nodes\n",
    "        RETURN: a list of the node values (integers).\"\"\"\n",
    "        node = self.find_node(start_node_num)\n",
    "        self._clear_visited()\n",
    "        \n",
    "        ret_list = [node.value]\n",
    "        node.visited = True\n",
    "        node_queue = [node]\n",
    "        \n",
    "        if node.edges:\n",
    "            for node_tr in node_queue:\n",
    "                for edge in node_tr.edges:\n",
    "                    if edge.node_from == node_tr and not edge.node_to.visited:\n",
    "                        edge.node_to.visited = True\n",
    "                        ret_list.append(edge.node_to.value)\n",
    "                        node_queue.append(edge.node_to)                \n",
    "        return ret_list\n",
    "\n",
    "    def bfs_names(self, start_node_num):\n",
    "        \"\"\"Return the results of bfs with numbers converted to names.\"\"\"\n",
    "        return [self.node_names[num] for num in self.bfs(start_node_num)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 554,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph = Graph()\n",
    "\n",
    "# You do not need to change anything below this line.\n",
    "# You only need to implement Graph.dfs_helper and Graph.bfs\n",
    "\n",
    "graph.set_node_names(('Mountain View',   # 0\n",
    "                      'San Francisco',   # 1\n",
    "                      'London',          # 2\n",
    "                      'Shanghai',        # 3\n",
    "                      'Berlin',          # 4\n",
    "                      'Sao Paolo',       # 5\n",
    "                      'Bangalore'))      # 6 \n",
    "\n",
    "graph.insert_edge(51, 0, 1)     # MV <-> SF\n",
    "graph.insert_edge(51, 1, 0)     # SF <-> MV\n",
    "graph.insert_edge(9950, 0, 3)   # MV <-> Shanghai\n",
    "graph.insert_edge(9950, 3, 0)   # Shanghai <-> MV\n",
    "graph.insert_edge(10375, 0, 5)  # MV <-> Sao Paolo\n",
    "graph.insert_edge(10375, 5, 0)  # Sao Paolo <-> MV\n",
    "graph.insert_edge(9900, 1, 3)   # SF <-> Shanghai\n",
    "graph.insert_edge(9900, 3, 1)   # Shanghai <-> SF\n",
    "graph.insert_edge(9130, 1, 4)   # SF <-> Berlin\n",
    "graph.insert_edge(9130, 4, 1)   # Berlin <-> SF\n",
    "graph.insert_edge(9217, 2, 3)   # London <-> Shanghai\n",
    "graph.insert_edge(9217, 3, 2)   # Shanghai <-> London\n",
    "graph.insert_edge(932, 2, 4)    # London <-> Berlin\n",
    "graph.insert_edge(932, 4, 2)    # Berlin <-> London\n",
    "graph.insert_edge(9471, 2, 5)   # London <-> Sao Paolo\n",
    "graph.insert_edge(9471, 5, 2)   # Sao Paolo <-> London\n",
    "# (6) 'Bangalore' is intentionally disconnected (no edges)\n",
    "# for this problem and should produce None in the\n",
    "# Adjacency List, etc."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 555,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Edge List\n",
      "[ (51, 'Mountain View', 'San Francisco'),\n",
      "  (51, 'San Francisco', 'Mountain View'),\n",
      "  (9950, 'Mountain View', 'Shanghai'),\n",
      "  (9950, 'Shanghai', 'Mountain View'),\n",
      "  (10375, 'Mountain View', 'Sao Paolo'),\n",
      "  (10375, 'Sao Paolo', 'Mountain View'),\n",
      "  (9900, 'San Francisco', 'Shanghai'),\n",
      "  (9900, 'Shanghai', 'San Francisco'),\n",
      "  (9130, 'San Francisco', 'Berlin'),\n",
      "  (9130, 'Berlin', 'San Francisco'),\n",
      "  (9217, 'London', 'Shanghai'),\n",
      "  (9217, 'Shanghai', 'London'),\n",
      "  (932, 'London', 'Berlin'),\n",
      "  (932, 'Berlin', 'London'),\n",
      "  (9471, 'London', 'Sao Paolo'),\n",
      "  (9471, 'Sao Paolo', 'London')]\n",
      "\n",
      "Adjacency List\n",
      "[ <map object at 0x7f323cdfcf60>,\n",
      "  <map object at 0x7f323cdfc518>,\n",
      "  <map object at 0x7f323cdfc390>,\n",
      "  <map object at 0x7f323cb3b198>,\n",
      "  <map object at 0x7f323cb3b5f8>,\n",
      "  <map object at 0x7f323cb3b860>,\n",
      "  None]\n",
      "\n",
      "Adjacency Matrix\n",
      "[ [0, 51, 0, 9950, 0, 10375, 0],\n",
      "  [51, 0, 0, 9900, 9130, 0, 0],\n",
      "  [0, 0, 0, 9217, 932, 9471, 0],\n",
      "  [9950, 9900, 9217, 0, 0, 0, 0],\n",
      "  [0, 9130, 932, 0, 0, 0, 0],\n",
      "  [10375, 0, 9471, 0, 0, 0, 0],\n",
      "  [0, 0, 0, 0, 0, 0, 0]]\n",
      "\n",
      "Depth First Search\n",
      "['London', 'Shanghai', 'Mountain View', 'San Francisco', 'Berlin', 'Sao Paolo']\n",
      "\n",
      "Breadth First Search\n",
      "['London', 'Shanghai', 'Berlin', 'Sao Paolo', 'Mountain View', 'San Francisco']\n"
     ]
    }
   ],
   "source": [
    "import pprint\n",
    "pp = pprint.PrettyPrinter(indent=2)\n",
    "\n",
    "print (\"Edge List\")\n",
    "pp.pprint(graph.get_edge_list_names())\n",
    "\n",
    "print (\"\\nAdjacency List\")\n",
    "pp.pprint(graph.get_adjacency_list_names())\n",
    "\n",
    "print (\"\\nAdjacency Matrix\")\n",
    "pp.pprint(graph.get_adjacency_matrix())\n",
    "\n",
    "print (\"\\nDepth First Search\")\n",
    "pp.pprint(graph.dfs_names(2))\n",
    "\n",
    "# Should print:\n",
    "# Depth First Search\n",
    "# ['London', 'Shanghai', 'Mountain View', 'San Francisco', 'Berlin', 'Sao Paolo']\n",
    "\n",
    "print (\"\\nBreadth First Search\")\n",
    "pp.pprint(graph.bfs_names(2))\n",
    "# test error reporting\n",
    "# pp.pprint(['Sao Paolo', 'Mountain View', 'San Francisco', 'London', 'Shanghai', 'Berlin'])\n",
    "\n",
    "# Should print:\n",
    "# Breadth First Search\n",
    "# ['London', 'Shanghai', 'Berlin', 'Sao Paolo', 'Mountain View', 'San Francisco']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "d = deque()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "d.append([1, 2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "d.append(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "deque([[1, 2], 4])"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Input: nums = [1,2,3,4]\n",
    "Output: [2,4,4,4]\n",
    "Explanation: The first pair [1,2] means we have freq = 1 and val = 2 so we generate the array [2].\n",
    "The second pair [3,4] means we have freq = 3 and val = 4 so we generate [4,4,4].\n",
    "At the end the concatenation [2] + [4,4,4,4] is [2,4,4,4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "\n",
    "def decompressRLElist(self, nums: List[int]) -> List[int]:\n",
    "    length = len(nums)\n",
    "    arr = []\n",
    "    if not (length%2 == 0):\n",
    "        return\n",
    "    for i in range(0, length, 2):\n",
    "        arr += [nums[i+1]]*nums[i]\n",
    "    return arr               "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The slowest run took 10.89 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "1000000 loops, best of 5: 1.12 µs per loop\n"
     ]
    }
   ],
   "source": [
    "arr = [1,2,3,4]\n",
    "\n",
    "s = Solution()\n",
    "%timeit s.decompressRLElist(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The slowest run took 9.04 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "1000000 loops, best of 5: 514 ns per loop\n"
     ]
    }
   ],
   "source": [
    "arr = [1,2,3,4]\n",
    "\n",
    "s = Solution1()\n",
    "%timeit s.decompressRLElist(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "arr += [2]*4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 2, 2, 2, 2]"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [],
   "source": [
    "def oddCells(n: int, m: int, indices) -> int:\n",
    "    arr = [[0]*m for _ in range(n)]\n",
    "    total = 0\n",
    "    for indx in indices:\n",
    "        a = indx[0]\n",
    "        b = indx[1]\n",
    "        for i in range(m):\n",
    "            arr[a][i] += 1\n",
    "        for i in range(n):\n",
    "            arr[i][b] += 1\n",
    "            \n",
    "    for row in arr:\n",
    "        for col in row:\n",
    "            if col%2 != 0:\n",
    "                total += 1\n",
    "    return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 111,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "oddCells(2, 3, [[0,1],[1,1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 139,
   "metadata": {},
   "outputs": [],
   "source": [
    "def replaceElements(arr: List[int]) -> List[int]:\n",
    "    for i in range(len(arr)-1):\n",
    "        arr[i] = max(arr[i+1:])\n",
    "    arr[-1] = -1\n",
    "    return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 157,
   "metadata": {},
   "outputs": [],
   "source": [
    "def replaceElements(arr: List[int]) -> List[int]:\n",
    "    arra = [max(arr[i+1:]) for i in range(len(arr)-1)]\n",
    "    return arra+[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "arr = [17,18,5,4,6,1, 17,18,5,4,6,1, 17,18,5,4,6,1, 17,18,5,4,6,1, 17,18,5,4,6,1]\n",
    "#[18,6,6,6,1,-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 159,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[18, 6, 6, 6, 1, -1]"
      ]
     },
     "execution_count": 159,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "replaceElements(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 162,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-4, -1, 0, 3, 10]"
      ]
     },
     "execution_count": 162,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [-4,-1,0,3,10]\n",
    "# Output: [0,1,9,16,100]\n",
    "sorted(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 167,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sortedSquares(A: List[int]) -> List[int]:\n",
    "    return [a*a for a in A].sort()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 168,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The slowest run took 35.47 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "1000000 loops, best of 5: 345 ns per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit sortedSquares(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sortArrayByParity(A: List[int]) -> List[int]:\n",
    "    even = []\n",
    "    odd = []\n",
    "    for val in A:\n",
    "        if val%2 == 0:\n",
    "            even += [val]\n",
    "        else:\n",
    "            odd += [val]\n",
    "    return even + odd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100000 loops, best of 5: 2.09 µs per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit sortArrayByParity(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sortArrayByParity1(A: List[int]) -> List[int]:\n",
    "    length = len(A)\n",
    "    pt1 = 0\n",
    "    pt2 = length - 1\n",
    "    if length <= 1:\n",
    "        return A\n",
    "    while pt1 < pt2:\n",
    "        a = A[pt1]\n",
    "        b = A[pt2]\n",
    "        if a%2 == 0:\n",
    "            pt1 += 1\n",
    "        else: # a is odd \n",
    "            if b%2 == 0:\n",
    "                A[pt1], A[pt2] = A[pt2], A[pt1]\n",
    "                pt1 += 1\n",
    "                pt2 -= 1\n",
    "            else: #b is odd\n",
    "                pt2 -= 1\n",
    "    return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100000 loops, best of 5: 2.56 µs per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit sortArrayByParity1(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sortArrayByParity1(A: List[int]) -> List[int]:\n",
    "    length = len(A)\n",
    "    pt1 = 0\n",
    "    pt2 = length - 1\n",
    "    if length <= 1:\n",
    "        return A\n",
    "    while pt1 < pt2:\n",
    "        a = A[pt1]\n",
    "        b = A[pt2]\n",
    "        if a%2 == 0:\n",
    "            pt1 += 1\n",
    "        else: # a is odd \n",
    "            if b%2 == 0:\n",
    "                A[pt1], A[pt2] = A[pt2], A[pt1]\n",
    "                pt1 += 1\n",
    "                pt2 -= 1\n",
    "            else: #b is odd\n",
    "                pt2 -= 1\n",
    "    return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 368,
   "metadata": {},
   "outputs": [],
   "source": [
    "arr = [1, 2, 3, 4] # 8\n",
    "arr1 = [11, 11, 11, 11] #2\n",
    "arr2 = [1, 2, 3, 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 406,
   "metadata": {},
   "outputs": [],
   "source": [
    "def evenSubarray(arr, n):\n",
    "    length = len(arr)\n",
    "    arr_ret = []\n",
    "    \n",
    "    def get_subarr(arr, arr_ret, n):\n",
    "               \n",
    "        for j in range(len(arr)):\n",
    "            arr1 = arr[0: len(arr)-j]\n",
    "            if check_odd_subarr(arr1, n):\n",
    "                if arr1 not in arr_ret:\n",
    "                    arr_ret.append(sorted(arr1))\n",
    "        return arr_ret\n",
    "                \n",
    "    \n",
    "    def check_odd_subarr(arr: list, n: int):\n",
    "        odd = 0\n",
    "        even = 0\n",
    "        for val in arr:\n",
    "            if val%2 != 0:\n",
    "                odd += 1\n",
    "        if odd <= n:\n",
    "            return True\n",
    "        return False\n",
    "    \n",
    "    if arr == []:\n",
    "        return 0\n",
    "    \n",
    "    for i in range(length):\n",
    "        get_subarr(arr[i:], arr_ret, n)\n",
    "        \n",
    "    return arr_ret, len(arr_ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 384,
   "metadata": {},
   "outputs": [],
   "source": [
    "def evenSubarray(numbers, k):\n",
    "    length = len(numbers)\n",
    "    arr_ret = []\n",
    "    \n",
    "    def get_subarr(arr, arr_ret, k):       \n",
    "        for j in range(len(arr)):\n",
    "            arr1 = arr[0: len(arr)-j]\n",
    "            if check_odd_subarr(arr1, k):\n",
    "                if arr1 not in arr_ret:\n",
    "                    arr_ret.append(sorted(arr1))\n",
    "        return arr_ret        \n",
    "    \n",
    "    def check_odd_subarr(arr: list, k: int):\n",
    "        odd = 0\n",
    "        even = 0\n",
    "        for val in arr:\n",
    "            if val%2 != 0:\n",
    "                odd += 1\n",
    "        if odd <= k:\n",
    "            return True\n",
    "        return False\n",
    "    \n",
    "    if length <= 1:\n",
    "        return length\n",
    "    \n",
    "    for i in range(length):\n",
    "        get_subarr(numbers[i:], arr_ret, k)\n",
    "    \n",
    "    arr_r = set([tuple(a) for a in arr_ret])\n",
    "    return arr_r, len(arr_r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 425,
   "metadata": {},
   "outputs": [],
   "source": [
    "def evenSubarray(numbers, k):\n",
    "    length = len(numbers)\n",
    "    arr_ret = []\n",
    "    \n",
    "    def check_odd_subarr(arr, k):\n",
    "        odd_count = 0\n",
    "        for val in arr:\n",
    "            if val%2 != 0:\n",
    "                odd_count += 1\n",
    "        if odd_count <= k:\n",
    "            return True\n",
    "        return False\n",
    "    \n",
    "    def get_subarray(arr, arr_ret, k):\n",
    "        len_arr = len(arr)\n",
    "        for j in range(len_arr):\n",
    "            arr_temp = arr[0: len_arr-j]\n",
    "            if check_odd_subarr(arr_temp, k):\n",
    "                if arr_temp not in arr_ret:\n",
    "                    arr_ret.append(arr_temp)\n",
    "        return arr_ret\n",
    "     \n",
    "    if length <= 1:\n",
    "        return length\n",
    "    \n",
    "    for i in range(length):\n",
    "        get_subarray(numbers[i:], arr_ret, k)\n",
    "        \n",
    "    arr_r = set([tuple(a) for a in arr_ret])\n",
    "    return len(arr_r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def evenSubarray(numbers, k):\n",
    "    length = len(numbers)\n",
    "    arr_ret = []\n",
    "    \n",
    "    def check_odd_subarr(arr, k):\n",
    "        odd_count = 0\n",
    "        for val in arr:\n",
    "            if val%2 != 0:\n",
    "                odd_count += 1\n",
    "        if odd_count <= k:\n",
    "            return True\n",
    "        return False\n",
    "    \n",
    "    def get_subarray(arr, arr_ret, k):\n",
    "        len_arr = len(arr)\n",
    "        for j in range(len_arr):\n",
    "            arr_temp = arr[0: len_arr-j]\n",
    "            if check_odd_subarr(arr_temp, k):\n",
    "                if arr_temp not in arr_ret:\n",
    "                    arr_ret.append(arr_temp)\n",
    "        return arr_ret\n",
    "    \n",
    "    \n",
    "    if length <= 1:\n",
    "        return length\n",
    "    \n",
    "    for i in range(length):\n",
    "        get_subarray(numbers[i:], arr_ret, k)\n",
    "        \n",
    "    return len(arr_ret)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 426,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "({(4,),\n",
       "  (4, 10),\n",
       "  (4, 10, 14),\n",
       "  (10,),\n",
       "  (10, 14),\n",
       "  (11,),\n",
       "  (11, 12),\n",
       "  (11, 12, 14),\n",
       "  (11, 12, 14, 4),\n",
       "  (11, 12, 14, 4, 10),\n",
       "  (11, 12, 14, 4, 10, 14),\n",
       "  (12,),\n",
       "  (12, 14),\n",
       "  (12, 14, 4),\n",
       "  (12, 14, 4, 10),\n",
       "  (12, 14, 4, 10, 14),\n",
       "  (14,),\n",
       "  (14, 4),\n",
       "  (14, 4, 10),\n",
       "  (14, 4, 10, 14),\n",
       "  (14, 11),\n",
       "  (14, 11, 12),\n",
       "  (14, 11, 12, 14),\n",
       "  (14, 11, 12, 14, 4),\n",
       "  (14, 11, 12, 14, 4, 10),\n",
       "  (14, 11, 12, 14, 4, 10, 14)},\n",
       " 26)"
      ]
     },
     "execution_count": 426,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "evenSubarray([14, 11, 12, 14, 4, 10, 14], 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 394,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 394,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "evenSubarray(arr, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 427,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "({(11,), (11, 11)}, 2)"
      ]
     },
     "execution_count": 427,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "evenSubarray(arr1, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 428,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "({(1,),\n",
       "  (1, 2),\n",
       "  (1, 2, 3),\n",
       "  (1, 2, 3, 1),\n",
       "  (2,),\n",
       "  (2, 3),\n",
       "  (2, 3, 1),\n",
       "  (3,),\n",
       "  (3, 1)},\n",
       " 9)"
      ]
     },
     "execution_count": 428,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "evenSubarray(arr2, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 410,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 4\n",
    "e = 5\n",
    "\n",
    "friends_nodes = 4\n",
    "friends_edges = 5\n",
    "\n",
    "friends_from = [1, 1, 2, 2, 2]\n",
    "friends_to = [2, 2, 3, 3, 4]\n",
    "friends_weight = [2, 3, 1, 3, 4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 414,
   "metadata": {},
   "outputs": [],
   "source": [
    "from operator import mul\n",
    "from functools import reduce\n",
    "from itertools import combinations\n",
    "from collections import defaultdict\n",
    "\n",
    "def sharedInterests(friends_nodes, friends_edges, friends_from, friends_to, friends_weight):\n",
    "    weight_map = {}\n",
    "    int_arr = defaultdict(list)\n",
    "    \n",
    "    for weight in set(friends_weight):\n",
    "        weight_map[weight] = set()\n",
    "\n",
    "    for i, weight in enumerate(friends_weight):\n",
    "        weight_map[weight].add(friends_from[i])\n",
    "        weight_map[weight].add(friends_to[i])\n",
    "    \n",
    "    def create_combinations(val):\n",
    "        return list(combinations(val, 2))\n",
    "    \n",
    "    for key, val in weight_map.items():\n",
    "        combs = create_combinations(list(val))\n",
    "        for comb in combs:\n",
    "            int_arr[comb].append(key)\n",
    "\n",
    "    total_arr = [len(arr) for arr in int_arr.values()]\n",
    "    \n",
    "    m = max(total_arr)\n",
    "    idx_m = [i for i, j in enumerate(total_arr) if j == m]\n",
    "\n",
    "    total_prod = [reduce(mul, list_, 1) for list_ in int_arr.keys()]\n",
    "\n",
    "    total_prod_req = [total_prod[i] for i in idx_m]\n",
    "    \n",
    "    return max(total_prod_req)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 421,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 421,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sharedInterests(friends_nodes, friends_edges, friends_from, friends_to, friends_weight)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 420,
   "metadata": {},
   "outputs": [],
   "source": [
    "from operator import mul\n",
    "from functools import reduce\n",
    "from itertools import combinations\n",
    "from collections import defaultdict\n",
    "\n",
    "def sharedInterests(friends_nodes, friends_edges, friends_from, friends_to, friends_weight):\n",
    "    weight_map = {}\n",
    "    int_arr = defaultdict(list)\n",
    "    \n",
    "    for weight in set(friends_weight):\n",
    "        weight_map[weight] = set()\n",
    "    \n",
    "    for i, weight in enumerate(friends_weight):\n",
    "        weight_map[weight].add(friends_from[i])\n",
    "        weight_map[weight].add(friends_to[i])\n",
    "    \n",
    "    def create_combinations(val):\n",
    "        return list(combinations(val, 2))\n",
    "    \n",
    "    for key, val in weight_map.items():\n",
    "        combs = create_combinations(list(val))\n",
    "        for comb in combs:\n",
    "            int_arr[comb].append(key)\n",
    "            \n",
    "    total_arr = [len(arr) for arr in int_arr.values()]\n",
    "    \n",
    "    m = max(total_arr)\n",
    "    idx_m = [i for i, j in enumerate(total_arr) if j == m]\n",
    "    \n",
    "    total_prod = [reduce(mul, list_, 1) for list_ in int_arr.keys()]\n",
    "    total_prod_req = [total_prod[i] for i in idx_m]\n",
    "    \n",
    "    return max(total_prod_req)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 333,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = [\"1/3/2012 16:00:00 Missing_1\",\n",
    "\"1/4/2012 16:00:00 27.47\",\n",
    "\"1/5/2012 16:00:00 27.728\",\n",
    "\"1/6/2012 16:00:00 28.19\",\n",
    "\"1/9/2012 16:00:00 28.1\",\n",
    "\"1/10/2012 16:00:00 28.15\",\n",
    "\"12/13/2012 16:00:00 27.52\",\n",
    "\"12/14/2012 16:00:00 Missing_19\",\n",
    "\"12/17/2012 16:00:00 27.215\",\n",
    "\"12/18/2012 16:00:00 27.63\",\n",
    "\"12/19/2012 16:00:00 27.75\",\n",
    "\"12/20/2012 16:00:00 Missing_20\",\n",
    "\"12/21/2012 16:00:00 27.49\",\n",
    "\"12/24/2012 13:00:00 27.25\",\n",
    "\"12/26/2012 16:00:00 27.2\",\n",
    "\"12/27/2012 16:00:00 27.09\",\n",
    "\"12/28/2012 16:00:00 26.9\",\n",
    "\"12/31/2012 16:00:00 26.77\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 340,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[27.47, 27.44375, 27.619999999999997]"
      ]
     },
     "execution_count": 340,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "\n",
    "data1 = [line.split() for line in data]\n",
    "arr1 = pd.DataFrame(data1, columns=['date', 'time', 'val'])\n",
    "\n",
    "arr1['val'] = pd.to_numeric(arr1['val'], errors='coerce')\n",
    "missing_index = arr1[arr1['val'].isnull()].index\n",
    "\n",
    "arr1['date_time'] = pd.to_datetime(arr1['date'] + ' ' + arr1['time'])\n",
    "\n",
    "arr1.index = arr1.date_time\n",
    "\n",
    "ans = arr1['val'].interpolate(method='time', limit_direction='both')\n",
    "\n",
    "ans[missing_index].to_list() # output a list of missing values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 343,
   "metadata": {},
   "outputs": [],
   "source": [
    "def addTwoDigits(n):\n",
    "    temp = str(n)\n",
    "    a = int(temp[0])\n",
    "    b = int(temp[1])\n",
    "    return a + b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 346,
   "metadata": {},
   "outputs": [],
   "source": [
    "levels = [\"08/02/2012 12:00:00 27.52\", \n",
    " \"08/03/2012 12:00:00 27.13\", \n",
    " \"08/04/2012 12:00:00 27.082\", \n",
    " \"08/05/2012 12:00:00 27.405\", \n",
    " \"08/06/2012 12:00:00 28.223\", \n",
    " \"08/07/2012 12:00:00 28.093\", \n",
    " \"08/08/2012 12:00:00 Missing_1\", \n",
    " \"08/09/2012 12:00:00 27.56\", \n",
    " \"08/10/2012 12:00:00 Missing_2\", \n",
    " \"08/11/2012 12:00:00 29.035\", \n",
    " \"08/12/2012 12:00:00 28.187\", \n",
    " \"08/13/2012 12:00:00 Missing_3\", \n",
    " \"08/14/2012 12:00:00 27.347\", \n",
    " \"08/15/2012 12:00:00 26.357\", \n",
    " \"08/16/2012 12:00:00 Missing_4\", \n",
    " \"08/17/2012 12:00:00 25.681\", \n",
    " \"08/18/2012 12:00:00 26.254\", \n",
    " \"08/19/2012 12:00:00 25.638\", \n",
    " \"08/20/2012 12:00:00 25.446\", \n",
    " \"08/21/2012 12:00:00 24.776\", \n",
    " \"08/22/2012 12:00:00 24.195\", \n",
    " \"08/23/2012 12:00:00 24.915\", \n",
    " \"08/24/2012 12:00:00 25.015\", \n",
    " \"08/25/2012 12:00:00 25.613\", \n",
    " \"08/26/2012 12:00:00 26.318\", \n",
    " \"08/27/2012 12:00:00 27.308\", \n",
    " \"08/28/2012 12:00:00 27.86\", \n",
    " \"08/29/2012 12:00:00 28.148\", \n",
    " \"08/30/2012 12:00:00 29.014\", \n",
    " \"08/31/2012 12:00:00 29.076\", \n",
    " \"09/01/2012 12:00:00 29.788\", \n",
    " \"09/02/2012 12:00:00 Missing_5\", \n",
    " \"09/03/2012 12:00:00 29.606\", \n",
    " \"09/04/2012 12:00:00 30.21\", \n",
    " \"09/05/2012 12:00:00 30.527\", \n",
    " \"09/06/2012 12:00:00 30.021\", \n",
    " \"09/07/2012 12:00:00 30.402\", \n",
    " \"09/08/2012 12:00:00 30.683\", \n",
    " \"09/09/2012 12:00:00 29.969\", \n",
    " \"09/10/2012 12:00:00 29.553\", \n",
    " \"09/11/2012 12:00:00 28.852\", \n",
    " \"09/12/2012 12:00:00 29.411\", \n",
    " \"09/13/2012 12:00:00 30.343\", \n",
    " \"09/14/2012 12:00:00 29.806\", \n",
    " \"09/15/2012 12:00:00 29.697\", \n",
    " \"09/16/2012 12:00:00 30.669\", \n",
    " \"09/17/2012 12:00:00 30.426\", \n",
    " \"09/18/2012 12:00:00 31.278\", \n",
    " \"09/19/2012 12:00:00 31.968\", \n",
    " \"09/20/2012 12:00:00 32.833\", \n",
    " \"09/21/2012 12:00:00 33.699\", \n",
    " \"09/22/2012 12:00:00 34.38\", \n",
    " \"09/23/2012 12:00:00 34.868\", \n",
    " \"09/24/2012 12:00:00 35.467\", \n",
    " \"09/25/2012 12:00:00 35.173\", \n",
    " \"09/26/2012 12:00:00 35.404\", \n",
    " \"09/27/2012 12:00:00 36.221\", \n",
    " \"09/28/2012 12:00:00 36.823\", \n",
    " \"09/29/2012 12:00:00 36.255\", \n",
    " \"09/30/2012 12:00:00 35.712\", \n",
    " \"10/01/2012 12:00:00 35.329\", \n",
    " \"10/02/2012 12:00:00 36.295\", \n",
    " \"10/03/2012 12:00:00 35.738\", \n",
    " \"10/04/2012 12:00:00 34.888\", \n",
    " \"10/05/2012 12:00:00 34.129\", \n",
    " \"10/06/2012 12:00:00 34.901\", \n",
    " \"10/07/2012 12:00:00 34.191\", \n",
    " \"10/08/2012 12:00:00 33.737\", \n",
    " \"10/09/2012 12:00:00 32.81\", \n",
    " \"10/10/2012 12:00:00 33.215\", \n",
    " \"10/11/2012 12:00:00 33.612\", \n",
    " \"10/12/2012 12:00:00 34.044\", \n",
    " \"10/13/2012 12:00:00 34.958\", \n",
    " \"10/14/2012 12:00:00 35.235\", \n",
    " \"10/15/2012 12:00:00 35.246\", \n",
    " \"10/16/2012 12:00:00 36.113\", \n",
    " \"10/17/2012 12:00:00 36.934\", \n",
    " \"10/18/2012 12:00:00 37.777\", \n",
    " \"10/19/2012 12:00:00 37.221\", \n",
    " \"10/20/2012 12:00:00 37.108\", \n",
    " \"10/21/2012 12:00:00 36.396\", \n",
    " \"10/22/2012 12:00:00 36.35\", \n",
    " \"10/23/2012 12:00:00 35.565\", \n",
    " \"10/24/2012 12:00:00 Missing_6\", \n",
    " \"10/25/2012 12:00:00 34.452\", \n",
    " \"10/26/2012 12:00:00 33.76\", \n",
    " \"10/27/2012 12:00:00 33.49\", \n",
    " \"10/28/2012 12:00:00 Missing_7\", \n",
    " \"10/29/2012 12:00:00 32.354\", \n",
    " \"10/30/2012 12:00:00 33.027\", \n",
    " \"10/31/2012 12:00:00 Missing_8\", \n",
    " \"11/01/2012 12:00:00 Missing_9\", \n",
    " \"11/02/2012 12:00:00 32.844\", \n",
    " \"11/03/2012 12:00:00 32.808\", \n",
    " \"11/04/2012 12:00:00 32.52\", \n",
    " \"11/05/2012 12:00:00 32.251\", \n",
    " \"11/06/2012 12:00:00 31.305\", \n",
    " \"11/07/2012 12:00:00 31.523\", \n",
    " \"11/08/2012 12:00:00 Missing_10\", \n",
    " \"11/09/2012 12:00:00 33.328\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 347,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "\n",
    "def fillingInData(levels):\n",
    "    # Split levels\n",
    "    level_split = [level.split() for level in levels]\n",
    "    # Make dataFrame\n",
    "    df = pd.DataFrame(level_split, columns=['date', 'time', 'val'])\n",
    "    \n",
    "    df['val'] = pd.to_numeric(df['val'], errors='coerce')\n",
    "    missing_index = df[df['val'].isnull()].index\n",
    "    \n",
    "    # Create datetime index for interpolation\n",
    "    df['date_time'] = pd.to_datetime(df['date'] + ' ' + df['time'])\n",
    "\n",
    "    df.index = df.date_time\n",
    "\n",
    "    ans = df['val'].interpolate(method='time', limit_direction='both')\n",
    "\n",
    "    return ans[missing_index].to_list() # output a list of missing values\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 352,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[27.826500000000003,\n",
       " 28.2975,\n",
       " 27.766999999999996,\n",
       " 26.019,\n",
       " 29.697,\n",
       " 35.0085,\n",
       " 32.922,\n",
       " 32.966,\n",
       " 32.905,\n",
       " 32.4255]"
      ]
     },
     "execution_count": 352,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fillingInData(levels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 351,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "\n",
    "def fillingInData(levels):\n",
    "    # Split levels\n",
    "    level_split = [level.split() for level in levels]\n",
    "    \n",
    "    \n",
    "    # create dataframe\n",
    "    df = pd.DataFrame(level_split, columns=['date', 'time', 'mercury_level'])\n",
    "    \n",
    "    df['mercury_level'] = pd.to_numeric(df['mercury_level'], errors='coerce')\n",
    "    # get missing\n",
    "    missing_index = df[df['mercury_level'].isnull()].index\n",
    "    \n",
    "    # create dataframe for interpolation\n",
    "    df['date_time'] = pd.to_datetime(df['date'] + ' ' + df['time'])\n",
    "    \n",
    "    df.index = df.date_time\n",
    "    \n",
    "    missing_levels = df.mercury_level.interpolate(method='time', limit_direction='both')\n",
    "    \n",
    "    return missing_levels[missing_index].to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# LeetCode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pivotIndex(nums: List[int]) -> int:\n",
    "    length = len(nums)\n",
    "    sum_prev = 0\n",
    "    sum_next = 0\n",
    "    for i in range(length):\n",
    "        sum_prev = sum(nums[0:i]\n",
    "        sum_next = nums[i+1:]\n",
    "        print(sum_prev, sum_next)\n",
    "        if sum_prev == sum_next:\n",
    "            return i\n",
    "\n",
    "    return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "arr = [1,7,3,6,5,6]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[] [7, 3, 6, 5, 6]\n",
      "[1] [3, 6, 5, 6]\n",
      "[1, 7] [6, 5, 6]\n",
      "[1, 7, 3] [5, 6]\n",
      "[1, 7, 3, 6] [6]\n",
      "[1, 7, 3, 6, 5] []\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pivotIndex(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    " def dominantIndex(nums: List[int]) -> int:\n",
    "        max_num = max(nums)\n",
    "        for i in len(nums):\n",
    "            if max_num < 2*numa[i]:\n",
    "                return -1\n",
    "        return nums.index(max_num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plusOne(digits: List[int]) -> List[int]:\n",
    "    x = ''.join([str(elem) for elem in digits]) \n",
    "    return [int(y) for y in str(int(x)+1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 7, 3, 6, 5, 7]"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "plusOne(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "unexpected EOF while parsing (<ipython-input-30-acdbfea7803f>, line 18)",
     "output_type": "error",
     "traceback": [
      "\u001b[0;36m  File \u001b[0;32m\"<ipython-input-30-acdbfea7803f>\"\u001b[0;36m, line \u001b[0;32m18\u001b[0m\n\u001b[0;31m    if one_sol not in seen:\u001b[0m\n\u001b[0m                           ^\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\u001b[0;31m:\u001b[0m unexpected EOF while parsing\n"
     ]
    }
   ],
   "source": [
    "def DistinctSubKOdds(nums, k):\n",
    "    sol = {}\n",
    "    \n",
    "    for i in range(len(nums)):\n",
    "        sol.add(nums[i])\n",
    "        \n",
    "        odd_count = 0\n",
    "        A_sol = []\n",
    "        \n",
    "        for j in range(i, len(nums)):\n",
    "            if nums[j]%2 != 0:\n",
    "                odd_count += 1\n",
    "                if odd_count > k:\n",
    "                    break\n",
    "                    \n",
    "            A_sol.append(nums[j])\n",
    "            \n",
    "            if one_sol not in seen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100'"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "addBinary('11', '1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "def strStr(haystack: str, needle: str) -> int:\n",
    "    len_h = len(haystack)\n",
    "    len_n = len(needle)\n",
    "    j = 0\n",
    "    k = len_n\n",
    "    if len_n == 0:\n",
    "        return 0\n",
    "\n",
    "    for i in range(len_h):\n",
    "        j +=1\n",
    "        k +=1\n",
    "        if haystack[j:k]==needle:\n",
    "            return j\n",
    "    return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "strStr('hello', 'll')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}