Jun 7 - 2024.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# sq root will be between 0 and 5\n",
    "left = 0\n",
    "right = 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Left:  2.2265625 , Right:  2.265625\n",
      "GUess:  2.24609375\n",
      "5.0449371337890625\n"
     ]
    }
   ],
   "source": [
    "print(\"Left: \", left, \", Right: \", right)\n",
    "guess = (left+right)/2 # 2.5 0----2.5----5\n",
    "print(\"GUess: \", guess)\n",
    "square_of_guess = guess*guess # 6.25\n",
    "print(square_of_guess)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "right = guess"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "left = guess"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def pth_sqrt(n, p):\n",
    "    TOL = 1e-9 #0.00001\n",
    "    left = 0\n",
    "    right = n\n",
    "    while True:\n",
    "        guess = (left+right)/2\n",
    "        sq_of_guess = guess**p\n",
    "        diff = abs(sq_of_guess - n)\n",
    "        if diff < TOL:\n",
    "            return guess\n",
    "        elif sq_of_guess > n:\n",
    "            right = guess\n",
    "        else:\n",
    "            left = guess"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.154434690019116"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pth_sqrt(10, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def FindSQRT(n):\n",
    "    start, end = 0, n\n",
    "    while 1:\n",
    "        mid = (start + end) / 2\n",
    "        if abs(mid * mid - n) < 0.01:\n",
    "            break\n",
    "        elif mid * mid < n:\n",
    "            start = mid\n",
    "        else:\n",
    "            end = mid\n",
    "    return mid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def sqrt(n):\n",
    "    TOL = 1e-9 #0.00001\n",
    "    left = 0\n",
    "    right = n\n",
    "    while True:\n",
    "        guess = (left+right)/2\n",
    "        sq_of_guess = guess*guess\n",
    "        diff = abs(sq_of_guess - n)\n",
    "        if diff < TOL:\n",
    "            return guess\n",
    "        elif sq_of_guess > n:\n",
    "            right = guess\n",
    "        else:\n",
    "            left = guess"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.162277660157997"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y = sqrt(10)\n",
    "y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.1622776601683795"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import math\n",
    "x = math.sqrt(10)\n",
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "TOL = 1e-5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1e-05\n"
     ]
    }
   ],
   "source": [
    "print(TOL)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'bisect' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-2-7baf5207a010>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mbisect\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m: name 'bisect' is not defined"
     ]
    }
   ],
   "source": [
    "bisect"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# BInary Search - Bisection Method\n",
    "#Q1: Given array of sorted numbers, check if a number exists in them"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "\n",
    "def search(arr, n):\n",
    "    left = 0\n",
    "    right = len(arr) - 1\n",
    "    while left <= right:\n",
    "        mid = (left + right)//2\n",
    "        print(f\"left: {left}, right: {right}, mid: {mid}, arr[mid]: {arr[mid]}\")\n",
    "        if arr[mid] == n:\n",
    "            return True\n",
    "        elif arr[mid] < n:\n",
    "            left = mid + 1\n",
    "        else:\n",
    "            right = mid - 1\n",
    "        print(f\"After Change: left: {left}, right: {right}\")\n",
    "        print(\"---------------\")\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "left: 0, right: 3, mid: 1, arr[mid]: 2\n",
      "After Change: left: 0, right: 0\n",
      "---------------\n",
      "left: 0, right: 0, mid: 0, arr[mid]: 1\n",
      "After Change: left: 1, right: 0\n",
      "---------------\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search([1, 2, 2, 2],1.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "arr = [1, 2, 3.3, 4, [5.6]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [1, 2, 3.3, 4, 5.6]\n",
    "search(arr, 1) # return True\n",
    "search(arr, 0) # return False\n",
    "search(arr, 2.5) # return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "def search(arr, n):\n",
    "    for i in arr:\n",
    "        if n == i:\n",
    "            return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [1, 2, 3.3, 4, 5.6]\n",
    "search(arr, 1) # return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search(arr, 0) # return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "search(arr, 2.5) # return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Complexity of binary search is log2(n) -> log(n)\n",
    "\n",
    "# sqrt - log(n/0.00001) -> log(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "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]) -> 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [],
   "source": [
    "def count_zeros(arr):\n",
    "    count = 0\n",
    "    for i in range(len(arr)):\n",
    "        if arr[i] == 1:\n",
    "            break\n",
    "        count += 1\n",
    "    return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "count_zeros([0,0,0,0,0,1,1,1,1,1,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Complexity: Order of n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [],
   "source": [
    "def count_zeros(arr):\n",
    "    return len(arr) - sum(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "count_zeros([0,0,0,0,0,1,1,1,1,1,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [],
   "source": [
    "# You have a set of numbers in an arr. find duplicates.\n",
    "# sort the data. find the neighbouring duplcates."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'count_one' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-87-2dae75c06ba8>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;31m# Q3: # Count 1s in a sorted array of numbers\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0mcount_one\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m1.1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m1.2\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m: name 'count_one' is not defined"
     ]
    }
   ],
   "source": [
    "# Q3: # Count 1s in a sorted array of numbers\n",
    "count_one([0,0,0,0,0,1,1,1,1,1,1,1.1, 1.2, 2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Q4 Given a number represented as string convert it integer\n",
    "\n",
    "def to_num(string):\n",
    "    return num\n",
    "\n",
    "to_num(\"123\") -> 123\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "123"
      ]
     },
     "execution_count": 88,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "int(\"123\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 92,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ord(\"9\") - ord(\"0\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"123\" -> \"12\" * 10 + \"3\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3]"
      ]
     },
     "execution_count": 93,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = [1,2,3,4]\n",
    "a[:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4]"
      ]
     },
     "execution_count": 94,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a[-1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def to_num(s):\n",
    "    if len(s) == 0:\n",
    "        return 0\n",
    "    elif len(s) == 1:\n",
    "        return ord(s) - ord(\"0\")\n",
    "    else:\n",
    "        return to_num(s[:-1])*10 + to_num(s[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "123"
      ]
     },
     "execution_count": 103,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "to_num(\"123\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {},
   "outputs": [],
   "source": [
    "# What is the order of complexity?\n",
    "# Order of n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a list of 100,000 phrases and 10 million resumes. Find the best matches resumes for these phrases."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Best - O(1) - O(log(n)) -- O(n) -- O(nlogn) -- O(n**2) --.. unbearable. --- O(n^n) - slow."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Qn: You have two lists of numbers: \n",
    "#     First list: 100 numbers. not sorted m\n",
    "#     Second List: Millions of numbers. not sorted n\n",
    "# Find all numbers which are common in these two lists."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "100 * million"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sort the second list - n log(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Sort second list - n log(n)\n",
    "# for every element in first list, do binary search in second list m * log(n)\n",
    "# n log(n) + m log(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Sorting - n log n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Go thru the codebase:\n",
    "# List down the various testscase."
   ]
  },
  {
   "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
}