2020-12-06_max-gauge.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This problem was asked by Amazon.\n",
    "\n",
    "You are given a list of data entries that represent entries and exits of groups of people into a building. An entry looks like this:\n",
    "```\n",
    "{\"timestamp\": 1526579928, count: 3, \"type\": \"enter\"}\n",
    "```\n",
    "This means 3 people entered the building. An exit looks like this:\n",
    "```\n",
    "{\"timestamp\": 1526580382, count: 2, \"type\": \"exit\"}\n",
    "```\n",
    "This means that 2 people exited the building. timestamp is in Unix time.\n",
    "\n",
    "Find the busiest period in the building, that is, the time with the most people in the building. Return it as a pair of `(start, end)` timestamps. You can assume the building always starts off and ends up empty, i.e. with 0 people inside."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import namedtuple\n",
    "\n",
    "Entry = namedtuple('Entry', [\"timestamp\", \"count\", \"type\"])\n",
    "\n",
    "def busiest_period(entries):\n",
    "    \"\"\"Return the busiest (start, end) period given entry/exit data sorted by timestamp.\n",
    "    \n",
    "    Args:\n",
    "        entries (iterable): An iterable over Entry objects, sorted by timestamp.\n",
    "    \"\"\"\n",
    "    assert is_sorted(entries), \"entries must be sorted by timestamp\"\n",
    "    \n",
    "    busy_start = busy_end = None\n",
    "    max_count = 0\n",
    "    current_count = 0\n",
    "    for time, count, _type in entries:\n",
    "        assert(count != 0)\n",
    "        \n",
    "        if _type == \"exit\":\n",
    "            count = -count\n",
    "            if max_count == current_count:\n",
    "                busy_end = time\n",
    "\n",
    "        current_count += count\n",
    "        assert(current_count >= 0)\n",
    "        \n",
    "        if _type == \"enter\":\n",
    "            if current_count >= max_count:\n",
    "                busy_start = time\n",
    "                max_count = current_count\n",
    "\n",
    "    return busy_start, busy_end\n",
    "    \n",
    "\n",
    "def is_sorted(entries):\n",
    "    \"\"\"Return True if entries are sorted by timestamp, False if not.\"\"\"\n",
    "    prev_timestamp = None\n",
    "    for timestamp, _, _ in entries:\n",
    "        if prev_timestamp is not None and timestamp < prev_timestamp:\n",
    "            return False\n",
    "        prev_timestamp = timestamp\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(None, None)"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "busiest_period([])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0, None)"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "busiest_period([Entry(0, 1, \"enter\")])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0, 3)"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "busiest_period([Entry(0, 1, \"enter\"), Entry(3, 1, \"exit\")])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3, 4)"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "busiest_period([Entry(0, 2, \"enter\"), Entry(3, 1, \"enter\"), Entry(4, 2, \"exit\")])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3, 4)"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "busiest_period([\n",
    "    Entry(0, 2, \"enter\"),\n",
    "    Entry(2, 2, \"exit\"),\n",
    "    Entry(3, 3, \"enter\"),\n",
    "    Entry(4, 2, \"exit\"),\n",
    "])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0, 2)"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "busiest_period([\n",
    "    Entry(0, 3, \"enter\"),\n",
    "    Entry(2, 2, \"exit\"),\n",
    "    Entry(3, 1, \"enter\"),\n",
    "    Entry(4, 2, \"exit\"),\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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}