Internal Exam 1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Instruction\n",
    "\n",
    "__Never__ use an additional import statement."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 1\n",
    "(10 marks)\n",
    "\n",
    "You are given a list of strings. \n",
    "\n",
    "1) Write a function to construct a Binary Search Tree from the list using the lengths of the strings as keys. Do _not_ store the keys in a list or tuple. Return the tree using the Node class given below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, key, value, left=None, right=None):\n",
    "        self.k = key\n",
    "        self.v = value\n",
    "        self.left = left\n",
    "        self.right = right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Write your Answer here. Write any other function if necessary.\n",
    "\n",
    "def build_bst(slist):\n",
    "    \"\"\"\n",
    "    Input: a list of strings\n",
    "    Output: A binary search tree with the strings as values \n",
    "     and their lengths as keys.\n",
    "    \"\"\"\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test for checking your answer.\n",
    "\n",
    "nd = build_bst([\"ab\", \"cde\", \"f\"])\n",
    "assert nd.k == 2 and nd.v == \"ab\"\n",
    "assert (nd.left).k == 1 and (nd.left).v == \"f\"\n",
    "assert (nd.right).k == 3 and (nd.right).v == \"cde\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2) Using the functions you wrote for the last question, write a function to sort the strings in _decreasing_ order of their lengths."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your answer here:\n",
    "\n",
    "def sort_reverse_bst(slist):\n",
    "    \"\"\"\n",
    "    Input: a list of strings\n",
    "    Output: a list of strings where the strings are sorted in \n",
    "     descending order of lengths. \n",
    "    \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test\n",
    "\n",
    "assert sort_reverse_bst([\"ghij\", \"ab\", \"cde\", \"f\"]) == [\"ghij\", \"cde\", \"ab\", \"f\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 2\n",
    "\n",
    "(10 marks)\n",
    "\n",
    "A number of people are available to do a particular job. Each person has an initial rating from $0$ to $5$ associated with him/her. At each time step, the person with the highest rating is hired for the job. The job always lasts exactly one time-step. At the end of the job, the hired person is freed and his/her performance is rated by the employer. The new rating would be the average of all the ratings he/she has receieved so far (including the initial rating). For example, suppose Bob is the only person in the pool and suppose his initial rating is 4. Being the only person, he will be hired when required. If he then gets a rating of $3$, his effective rating would become $(4+3)/2$. After another hiring episode, if he gets a rating of $3.5$, his effective rating would be $(4+3+3.5)/3$ at the end of the job.\n",
    "\n",
    "Using Heaps, implement a class with a function for picking the current best-rated person and a function for updating his/her ratings. The class will get a list of tuples (person, initial-rating) as input."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Write any other necessary classes and/or functions. \n",
    "# The skeleton of only one class is given here.\n",
    "\n",
    "\n",
    "class Hiring:\n",
    "    def __init__(self, pratings):\n",
    "        # Complete the code. Remember to use self. when necessary.\n",
    "        # Remember also that the __init__ function should not return anything.\n",
    "        \n",
    "        \n",
    "        \n",
    "    def hire(self):\n",
    "        # Return the best person.\n",
    "        \n",
    "    def update(self, new_rating):\n",
    "        # Update the rating of the last hired person.\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test\n",
    "hr = Hiring([(\"alice\", 3.0), (\"mary\", 3.5), (\"eve\", 2.5)])\n",
    "assert hr.hire() == \"mary\"\n",
    "hr.update(3.0)\n",
    "assert hr.hire() == \"mary\"\n",
    "hr.update(2.0)\n",
    "assert hr.hire() == \"alice\"\n",
    "hr.update(1.5)\n",
    "assert hr.hire() == \"mary\"\n",
    "hr.update(1.0)\n",
    "assert hr.hire() == \"eve\"\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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}