{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "This notebook was prepared by [Donne Martin](https://github.com/donnemartin). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Solution Notebook" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Problem: Given an array of (unix_timestamp, num_people, EventType.ENTER or EventType.EXIT), find the busiest period.\n", "\n", "* [Constraints](#Constraints)\n", "* [Test Cases](#Test-Cases)\n", "* [Algorithm](#Algorithm)\n", "* [Code](#Code)\n", "* [Unit Test](#Unit-Test)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Constraints\n", "\n", "* Can we assume the input array is valid?\n", " * Check for None\n", "* Can we assume the elements of the input array are valid?\n", " * Yes\n", "* Is the input sorted by time?\n", " * No\n", "* Can you have enter and exit elements for the same timestamp?\n", " * Yes you can, order of enter and exit is not guaranteed\n", "* Could we have multiple enter events (or multiple exit events) for the same timestamp?\n", " * No\n", "* What is the format of the output?\n", " * An array of timestamps [t1, t2]\n", "* Can we assume the starting number of people is zero?\n", " * Yes\n", "* Can we assume the inputs are valid?\n", " * No\n", "* Can we assume this fits memory?\n", " * Yes" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Test Cases\n", "\n", "* None -> TypeError\n", "* [] -> None\n", "* General case\n", "\n", "
```\n",
"timestamp  num_people  event_type\n",
"3          2           EventType.EXIT\n",
"1          2           EventType.ENTER\n",
"3          1           EventType.ENTER\n",
"7          3           EventType.ENTER\n",
"9          2           EventType.EXIT\n",
"8          2           EventType.EXIT\n",
"\n",
"result = Period(7, 8)\n",
"```
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Algorithm\n", "\n", "Since the input is not sorted, we'll need to sort it first by timestamp, ascending.\n", "\n", "For each interval in the data set:\n", "\n", "* If this is an \"enter\" event, increment `curr_people`, else, decrement\n", "* Since we can have an \"enter\" and \"exit\" event for the same timestamp, we'll need to look ahead one\n", " * If the next element has the same timestamp, hold off (continue) on updating `max_people` and `max_period`\n", " * Watch out for indexing out-of-bounds at the end of the array\n", "* Update `max_people` and `max_period`\n", "\n", "Sorted:\n", "\n", "
```\n",
"timestamp  num_people  event_type       curr_people  max_people       max_period\n",
"1          2           EventType.ENTER  2            2                [1, 3]\n",
"3          1           EventType.ENTER  3            2 (not updated)  [1, 3]\n",
"3          2           EventType.EXIT   1            2                [3, 7]\n",
"7          3           EventType.ENTER  4            4                [7, 8]\n",
"8          2           EventType.EXIT   2            4                [7, 8]\n",
"9          2           EventType.EXIT   0            4                [7, 8]\n",
"```
\n", "\n", "Complexity:\n", "* Time: O(nlog(n)) for the sort\n", "* Space: O(1), assuming the sort is in-place" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Code" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "from enum import Enum\n", "\n", "\n", "class Data(object):\n", "\n", " def __init__(self, timestamp, num_people, event_type):\n", " self.timestamp = timestamp\n", " self.num_people = num_people\n", " self.event_type = event_type\n", "\n", " def __lt__(self, other):\n", " return self.timestamp < other.timestamp\n", "\n", "\n", "class Period(object):\n", "\n", " def __init__(self, start, end):\n", " self.start = start\n", " self.end = end\n", "\n", " def __eq__(self, other):\n", " return self.start == other.start and self.end == other.end\n", "\n", " def __repr__(self):\n", " return str(self.start) + ', ' + str(self.end)\n", "\n", "\n", "class EventType(Enum):\n", "\n", " ENTER = 0\n", " EXIT = 1" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "class Solution(object):\n", "\n", " def find_busiest_period(self, data):\n", " if data is None:\n", " raise TypeError('data cannot be None')\n", " if not data:\n", " return None\n", " data.sort()\n", " max_period = Period(0, 0)\n", " max_people = 0\n", " curr_people = 0\n", " for index, interval in enumerate(data):\n", " if interval.event_type == EventType.ENTER:\n", " curr_people += interval.num_people\n", " elif interval.event_type == EventType.EXIT:\n", " curr_people -= interval.num_people\n", " else:\n", " raise ValueError('Invalid event type')\n", " if (index < len(data) - 1 and \n", " data[index].timestamp == data[index + 1].timestamp):\n", " continue\n", " if curr_people > max_people:\n", " max_people = curr_people\n", " max_period.start = data[index].timestamp\n", " if index < len(data) - 1:\n", " max_period.end = data[index + 1].timestamp\n", " else:\n", " max_period.end = data[index].timestamp\n", " return max_period" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Unit Test" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Overwriting test_find_busiest_period.py\n" ] } ], "source": [ "%%writefile test_find_busiest_period.py\n", "import unittest\n", "\n", "\n", "class TestSolution(unittest.TestCase):\n", "\n", " def test_find_busiest_period(self):\n", " solution = Solution()\n", " self.assertRaises(TypeError, solution.find_busiest_period, None)\n", " self.assertEqual(solution.find_busiest_period([]), None)\n", " data = [\n", " Data(3, 2, EventType.EXIT),\n", " Data(1, 2, EventType.ENTER),\n", " Data(3, 1, EventType.ENTER),\n", " Data(7, 3, EventType.ENTER),\n", " Data(9, 2, EventType.EXIT),\n", " Data(8, 2, EventType.EXIT),\n", " ]\n", " self.assertEqual(solution.find_busiest_period(data), Period(7, 8))\n", " print('Success: test_find_busiest_period')\n", "\n", "\n", "def main():\n", " test = TestSolution()\n", " test.test_find_busiest_period()\n", "\n", "\n", "if __name__ == '__main__':\n", " main()" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Success: test_find_busiest_period\n" ] } ], "source": [ "%run -i test_find_busiest_period.py" ] } ], "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.2" } }, "nbformat": 4, "nbformat_minor": 1 }