week5_1practice.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "deletable": false,
    "editable": true,
    "id": "ck4jLznJiooB",
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "38b4cbfd496d80940cfa87c97061e3be",
     "grade": false,
     "grade_id": "cell-b1db85bf05a65a79",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    },
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "### Lecture 5 Practice: Two Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "deletable": false,
    "editable": true,
    "id": "7e5PDMTdlnhr",
    "nbgrader": {
     "cell_type": "markdown",
     "checksum": "028c604f7c4a6b0fd489eb9063fb71bd",
     "grade": false,
     "grade_id": "cell-473f900194560999",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    },
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "Given an array of integers nums and an integer `target`, return indices of the two numbers such that they add up to `target`.\n",
    "\n",
    "You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.\n",
    "\n",
    "**Note:**: This is a classical interview question and will be the same question for HW5."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {
    "deletable": false,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "def two_sum_brute_force(nums, target):\n",
    "    O(n^2) solution using brute force approach.\n",
    "    store = 0\n",
    "    list = []\n",
    "    for i in range(len(nums)-1):\n",
    "        a = nums[i]\n",
    "        b = nums[i+1]\n",
    "        if a+b  == target:\n",
    "            list.append(i)\n",
    "            list.append(i+1)\n",
    "            return list\n",
    "\"\"\"\n",
    "\n",
    "def two_sum_brute_force(nums, target):\n",
    "    \"\"\"\n",
    "    O(n^2) solution using brute force approach.\n",
    "    \"\"\"\n",
    "    for i in range(len(nums)):\n",
    "        for j in range(i+1,len(nums)):\n",
    "            if nums[i] + nums[j] == target:\n",
    "                return [i,j]\n",
    "    return [None,None]\n",
    "\n",
    "def two_sum_dict(nums, target):\n",
    "    \"\"\"\n",
    "    O(n) solution using hash table(dictionary) approach.\n",
    "    \"\"\"\n",
    "    table = {}\n",
    "    for idx, n in enumerate(nums):\n",
    "        other = target - n\n",
    "        if other in table:\n",
    "            return [table[other],idx]\n",
    "        else:\n",
    "            table[n] = idx\n",
    "    return [None,None]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "assert two_sum_brute_force([2, 7, 11, 15], 9) == [0, 1], \"Test case 1 failed\"\n",
    "assert two_sum_brute_force([3, 2, 4], 6) == [1, 2], \"Test case 2 failed\"\n",
    "assert two_sum_dict([2, 7, 11, 15], 9) == [0, 1], \"Test case 1 failed\"\n",
    "assert two_sum_dict([3, 2, 4], 6) == [1, 2], \"Test case 2 failed\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2: Profiling \n",
    "Implement a function called `profile_function` that measures the execution time of any given function. The function should:\n",
    "\n",
    "1) Accept a function func as its first argument and any number of additional arguments `*arg` to be passed to func. Recall that `*arg` is a special syntax that allows a function to accept any number of positional arguments.\n",
    "2) Return a tuple containing the result of the function call and the execution time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Profiling\n",
    "import time\n",
    "def profile_function(func, *args):\n",
    "    start = time.perf_counter()\n",
    "    result = func(*args)\n",
    "    end = time.perf_counter()\n",
    "    diff = end-start\n",
    "    return result,diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Input: nums = [2, 7, 11, 15], target = 9\n",
      "Brute Force: Result = [0, 1], Time = 0.000004 seconds\n",
      "Using dictionary: Result = [0, 1], Time = 0.000003 seconds\n",
      "\n",
      "Input: nums = [3, 2, 4], target = 6\n",
      "Brute Force: Result = [1, 2], Time = 0.000005 seconds\n",
      "Using dictionary: Result = [1, 2], Time = 0.000003 seconds\n"
     ]
    }
   ],
   "source": [
    "nums1 = [2, 7, 11, 15]\n",
    "target1 = 9\n",
    "nums2 = [3, 2, 4]\n",
    "target2 = 6\n",
    "for nums, target in [(nums1, target1), (nums2, target2)]:\n",
    "    print(f\"\\nInput: nums = {nums}, target = {target}\")\n",
    "    \n",
    "    bf_result, bf_time = profile_function(two_sum_brute_force, nums, target)\n",
    "    print(f\"Brute Force: Result = {bf_result}, Time = {bf_time:.6f} seconds\")\n",
    "    \n",
    "    ht_result, ht_time = profile_function(two_sum_dict, nums, target)\n",
    "    print(f\"Using dictionary: Result = {ht_result}, Time = {ht_time:.6f} seconds\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 3 Just for fun!\n",
    "Implement the following functions with the desired runtime complexity. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3.1 Given an array of integers `nums` which is sorted in ascending order, and an integer `target`, write a function to search `target` in `nums`. If `target` exists, then return its index. Otherwise, return `-1`. You must write an algorithm with `O(logn)` runtime complexity."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_search(t, elmt):\n",
    "    start = 0\n",
    "    end = len(t) - 1\n",
    "    while start <= end:\n",
    "        middle = (start + end) // 2\n",
    "        if t[middle] == elmt:\n",
    "            return True\n",
    "        elif t[middle] < elmt:\n",
    "            start = middle + 1\n",
    "        else:\n",
    "            end = middle - 1\n",
    "    return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def search(nums, target):\n",
    "    # YOUR CODE HERE\n",
    "    raise NotImplementedError()"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "Lecture 2 practice Solution.ipynb",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "general",
   "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.11.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}