Jul 19.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Binary Search Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Q; When do you use Binary Search?\n",
    "\n",
    "If you have a list that is sorted and you don't insert ofter. \n",
    "Or\n",
    "If you have static data and you have to search multiple times.\n",
    "\n",
    "Q: When do you use binary search tree?\n",
    "When insertion and deletions are happening very frequently.\n",
    "\n",
    "Q: Why not dictionary?\n",
    "A: When too much memory not available.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "a  = {}\n",
    "a[\"sandeep\"] = 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'sandeep': 10}"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 2, 3, 4, 5)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1, 2, 3, 4, 5,\n",
    "\n",
    "# Q: Since the BST is prone to imbalance, multiple strategies have come\n",
    "#Red Black Trees, AVL Trees\n",
    "#https://www.cs.usfca.edu/~galles/visualization/RedBlack.html"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Q: what if my data does not fit in the memory.\n",
    "#Use B-Trees or B+ Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Q: You need to build a scheduler. \n",
    "- UNix - Cron, Calendar\n",
    "\n",
    "It finds the task which is of smallest(earliest) date/time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- task1: execute at 1pm,\n",
    "- task2: execute at 12:30pm\n",
    "- task3: 2pm\n",
    "- task2: 11am\n",
    "\n",
    "# Strategy: 1\n",
    "    * WHenever a task is added, sort the list of tasks. n * n * log(n) * \n",
    "\n",
    "    Insertion: n log n\n",
    "\n",
    "    FindMin:\n",
    "    order of (1)\n",
    "\n",
    "    delete:\n",
    "    order of (n)\n",
    "\n",
    "# Strategy: 2\n",
    "    * Linked List.*\n",
    "\n",
    "    Inserting a task:\n",
    "    Order of n\n",
    "\n",
    "    Deletion:\n",
    "    Order(1)\n",
    "\n",
    "# Strategy #3\n",
    "\n",
    "    *BST / Redblack / AVL*\n",
    "\n",
    "    Insertion: log (n)\n",
    "    FindMin & Deletion: log(n)\n",
    "\n",
    "# Strategy #4\n",
    "    - Create a list of 1000*24*60*60 elements. for thousand days\n",
    "    - Use a dictionary for a more optimum space.\n",
    "    - Insertion - O(1)\n",
    "    - Find - O(1)\n",
    "    - Deletion - O(1)\n",
    "    \n",
    "# Strategy #5\n",
    "    - maintain per 10 minutes window tasks\n",
    "\n",
    "# Strategy #6\n",
    "    - MinHeap\n",
    "    # Min Heap\n",
    "    Insertion: O(logn)\n",
    "    FindMin: O(1)\n",
    "    Deletion: O(logn)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = [0]*1000*24*60*60"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "691200000"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1000*24*60*60"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "691200064"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import sys\n",
    "sys.getsizeof(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Linked List Node\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.next = None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "import heapq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = [3,4,5,1, 2, 8, 9, -30]\n",
    "heapq.heapify(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-30, 1, 5, 3, 2, 8, 9, 4]"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heapq.heappop(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 5, 4, 9, 8]"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heapq.heappop(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 4, 5, 8, 9]"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "# https://docs.python.org/3/library/heapq.html"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Traversal of Tree\n",
    "\n",
    "# Depth first\n",
    "\n",
    "# Breath First\n"
   ]
  }
 ],
 "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.6.8"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}