Jun 8 - 2024.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "0. Number System\n",
    "\n",
    "1. Statements / Variables\n",
    "2. If-else\n",
    "3. Loops - ..\n",
    "4. Functions / Recursion\n",
    "5. Binary Search\n",
    "6. Arrays / Strings\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from bisect import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bisect_left([1,2,3,4,4,4], 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Q2: You have a list of 0s and 1s....find the count of 0s. the array is sorted.\n",
    "# count_zeros([0,0,0,0,0,1,1,1,1,1,1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_last_zero(L):\n",
    "    left = 0\n",
    "    right = len(L) - 1\n",
    "    while left <= right:\n",
    "        mid = (left + right)//2\n",
    "        if L[mid] != 0:\n",
    "            right = mid - 1\n",
    "        else:\n",
    "            if mid == (len(L)-1):\n",
    "                return mid\n",
    "            else:\n",
    "                if L[mid + 1] != 0:\n",
    "                    return mid\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "    return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tester(test_cases):\n",
    "    for test_case in test_cases:\n",
    "        arr, expected = test_case\n",
    "        actual = find_last_zero(arr)\n",
    "        print(\"Testing: \", arr)\n",
    "        if actual == expected:\n",
    "            print(\"\\tSuccess! \")\n",
    "        else:\n",
    "            print(f\"\\tFailed!. Expected {expected} but got {actual}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = [\n",
    "    ([0], 0),\n",
    "    ([0, 1, 1], 0),\n",
    "    ([0, 0, 1], 1),    \n",
    "    ([1, 1, 1], -1),\n",
    "    ([0, 0, 0], 2),\n",
    "    ([1], -1),\n",
    "    ([], -1),\n",
    "    ([0]*100 + [1]*200, 99)\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Testing:  [0]\n",
      "\tSuccess! \n",
      "Testing:  [0, 1, 1]\n",
      "\tSuccess! \n",
      "Testing:  [0, 0, 1]\n",
      "\tSuccess! \n",
      "Testing:  [1, 1, 1]\n",
      "\tSuccess! \n",
      "Testing:  [0, 0, 0]\n",
      "\tSuccess! \n",
      "Testing:  [1]\n",
      "\tSuccess! \n",
      "Testing:  []\n",
      "\tSuccess! \n",
      "Testing:  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n",
      "\tSuccess! \n"
     ]
    }
   ],
   "source": [
    "tester(test_cases)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "27.77777777777778"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "100*1000/60/60 hours"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Approach1: count(arr) - sum(arr), for-loop\n",
    "#     - Order of n\n",
    "#     - 10 -> 1 ms\n",
    "#     - 100 -> 10 ms\n",
    "#     - 10000 -> 1000 ms\n",
    "#     - 1 million -> 100,000 ms\n",
    "#     - 1 billions -> 100 millions mseconds -> 100 * 1000 seconds = 100*1000/60/60\n",
    "\n",
    "# Approach2: Binary Search\n",
    "#     - Order of log n\n",
    "#     - 10 -> 1 ms\n",
    "#     - 100 -> 2 ms\n",
    "#     - 10,000 -> 4 ms\n",
    "#     - 1 million -> 6 ms\n",
    "#     - 1 billions -> 9 ms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 1/t2 = log(10)/log(10^9)\n",
    "# 1/t2 = 1/9\n",
    "# t2 = 9ms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [],
   "source": [
    "def loop_search(arr):\n",
    "    return len(arr) - sum(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "large_arr = [0]*500000000 + [1]*50000000\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4.51 s ± 48.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "timeit loop_search(large_arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8.45 µs ± 270 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n"
     ]
    }
   ],
   "source": [
    "timeit find_last_zero(large_arr) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Q: You have increasing and then decreasing numbers. Find the max value.\n",
    "#     [1,2,3,4,3,2.5, 1.5, -2] -> 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Q: You have decreasing and then increasing numbers. Find the minimum value.\n",
    "#     [100, 10, 5, 0, -2, 1, 3, 5, 1000, 3000] -> -2"
   ]
  },
  {
   "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.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
}