Two_Sum.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "\n",
    "# O(n)\n",
    "# the retrival speed is O(1) since dictionary uses hashmap\n",
    "\n",
    "def dict_sol2(nums: List[int], target: int) -> List[int]:\n",
    "    hashtable = {}\n",
    "    for i, v in enumerate(nums):\n",
    "        complement = target - v\n",
    "        if complement in hashtable:\n",
    "            print(f'{complement} = {target} - {v}')\n",
    "            return [hashtable[complement], i]\n",
    "        hashtable[v] = i\n",
    "            \n",
    "            \n",
    "def dict_sol(nums: List[int], target: int) -> List[int]:\n",
    "    d = {}\n",
    "\n",
    "    for i, v in enumerate(nums):\n",
    "        d[v] = i\n",
    "\n",
    "    size = len(nums)\n",
    "    for i, v in enumerate(nums):\n",
    "        b = target - v\n",
    "        if b in d and d[b] != i:\n",
    "            return [i, d[b]]\n",
    "\n",
    "        \n",
    "# O(n^2)\n",
    "def slow_sol(nums: List[int], target: int) -> List[int]:\n",
    "    for i, v in enumerate(nums):\n",
    "        for j, m in enumerate(nums):\n",
    "            if i != j and v + m == target:\n",
    "                return [i, j]\n",
    "\n",
    "\n",
    "# O(n^2)\n",
    "def slow_sol_2(nums: List[int], target: int) -> List[int]:\n",
    "    size = len(nums)\n",
    "    for i, v in enumerate(nums):\n",
    "        m = i + 1\n",
    "        while m < size:\n",
    "            if v + nums[m] == target:\n",
    "                return [i, m]\n",
    "            else:\n",
    "                m = m + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "test_cases = {16021: np.append(np.arange(0,25197,2),8011),\n",
    "              6: [3,3],\n",
    "              9: [2,7,11,15]\n",
    "             }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "input: [0 2 4 6 8]...\n",
      "target: 16021\n",
      "==============\n",
      "\n",
      "dict_sol:\n",
      "result: [4005, 12599]\n",
      "time: [0.004319382666665206]\n",
      "\n",
      "dict_sol2:\n",
      "result: [4005, 12599]\n",
      "time: [0.00529464266666461]\n",
      "\n",
      "slow_sol:\n",
      "result: [4005, 12599]\n",
      "time: [16.841463064]\n",
      "\n",
      "slow_sol_2:\n",
      "result: [4005, 12599]\n",
      "time: [15.980644644000014]\n",
      "\n",
      "----------------------\n",
      "\n",
      "\n",
      "input: [3, 3]\n",
      "target: 6\n",
      "==============\n",
      "\n",
      "dict_sol:\n",
      "result: [0, 1]\n",
      "time: [2.170333326982169e-06]\n",
      "\n",
      "dict_sol2:\n",
      "result: [0, 1]\n",
      "time: [1.6476666739132877e-06]\n",
      "\n",
      "slow_sol:\n",
      "result: [0, 1]\n",
      "time: [1.4886666690472339e-06]\n",
      "\n",
      "slow_sol_2:\n",
      "result: [0, 1]\n",
      "time: [1.3046666632969088e-06]\n",
      "\n",
      "----------------------\n",
      "\n",
      "\n",
      "input: [2, 7, 11, 15]\n",
      "target: 9\n",
      "==============\n",
      "\n",
      "dict_sol:\n",
      "result: [0, 1]\n",
      "time: [2.310333343302773e-06]\n",
      "\n",
      "dict_sol2:\n",
      "result: [0, 1]\n",
      "time: [1.5690000054746633e-06]\n",
      "\n",
      "slow_sol:\n",
      "result: [0, 1]\n",
      "time: [1.4546666496547307e-06]\n",
      "\n",
      "slow_sol_2:\n",
      "result: [0, 1]\n",
      "time: [1.2923333467066793e-06]\n",
      "\n",
      "----------------------\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "import inspect \n",
    "import sys\n",
    "\n",
    "methods = {}\n",
    "for name, obj in inspect.getmembers(sys.modules[__name__],inspect.isfunction):\n",
    "    if name != 'obj':\n",
    "        methods[name] = obj\n",
    "        \n",
    "for k,v in test_cases.items():\n",
    "    target = k\n",
    "    nums = v\n",
    "    print('input: {}{}\\ntarget: {}'.format(nums if len(nums) <=5 else nums[:5],\n",
    "                                            '' if len(nums) <= 5 else '...',\n",
    "                                           target), \n",
    "                                           end='\\n==============\\n\\n')\n",
    "    for name, _ in methods.items():\n",
    "        result = methods[name](nums, target)\n",
    "        time = %timeit -n 3 -r 1 -o -q methods[name](nums, target)\n",
    "        print(f'{name}:\\nresult: {result}\\ntime: {time.timings}', end='\\n\\n')\n",
    "        \n",
    "    print('----------------------\\n\\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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}