Neetcode - Binary Search - Time Based Key-Value Store.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Neetcode - Binary Search - Time Based Key-Value Store.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyNx+DKfVhsF6b+tY65IvOQ0",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/sahug/neetcode/blob/main/Neetcode%20-%20Binary%20Search%20-%20Time%20Based%20Key-Value%20Store.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Neetcode - Binary Search - Time Based Key-Value Store**\n",
        "\n",
        "Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key's value at a certain timestamp.\n",
        "\n",
        "Implement the `TimeMap` class:\n",
        "\n",
        "- `TimeMap()` Initializes the object of the data structure.\n",
        "- `void set(String key, String value, int timestamp)` Stores the key key with the value value at the given time `timestamp`.\n",
        "- `String get(String key, int timestamp)` Returns a value such that set was called previously, with `timestamp_prev <= timestamp`. If there are multiple such values, it returns the value associated with the largest `timestamp_prev`. If there are no values, it returns \"\".\n",
        "\n",
        "**Example 1:**\n",
        "```\n",
        "Input\n",
        "\n",
        "[\"TimeMap\", \"set\", \"get\", \"get\", \"set\", \"get\", \"get\"]\n",
        "[[], [\"foo\", \"bar\", 1], [\"foo\", 1], [\"foo\", 3], [\"foo\", \"bar2\", 4], [\"foo\", 4], [\"foo\", 5]]\n",
        "\n",
        "Output\n",
        "\n",
        "[null, null, \"bar\", \"bar\", null, \"bar2\", \"bar2\"]\n",
        "\n",
        "Explanation\n",
        "\n",
        "TimeMap timeMap = new TimeMap();\n",
        "timeMap.set(\"foo\", \"bar\", 1);  // store the key \"foo\" and value \"bar\" along with timestamp = 1.\n",
        "timeMap.get(\"foo\", 1);         // return \"bar\"\n",
        "timeMap.get(\"foo\", 3);         // return \"bar\", since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is \"bar\".\n",
        "timeMap.set(\"foo\", \"bar2\", 4); // store the key \"foo\" and value \"bar2\" along with timestamp = 4.\n",
        "timeMap.get(\"foo\", 4);         // return \"bar2\"\n",
        "timeMap.get(\"foo\", 5);         // return \"bar2\"\n",
        "```"
      ],
      "metadata": {
        "id": "qdLtXtlMOJWF"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Approach 1**"
      ],
      "metadata": {
        "id": "bDHI8UFVqXlg"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 84,
      "metadata": {
        "id": "HPQX47bpKBWS"
      },
      "outputs": [],
      "source": [
        "from collections import defaultdict\n",
        "class TimeMap():\n",
        "\n",
        "  def __init__(self):    \n",
        "    self.tkv = [0]*10000\n",
        "  \n",
        "  def set(self, key:str, value: str, timestamp: int) -> None:      \n",
        "    self.tkv.insert(timestamp, {key: value})\n",
        "\n",
        "  def get(self, key: str, timestamp: str) -> str:\n",
        "    l, r = 0, len(self.tkv) - 1\n",
        "    while l <= r:\n",
        "      mid = (r + l)//2                        \n",
        "      if timestamp == mid:       \n",
        "        while self.tkv[mid] == 0:\n",
        "          mid = mid - 1          \n",
        "        return self.tkv[mid].get(key, \"\")                    \n",
        "      elif timestamp > mid:\n",
        "        l = mid + 1\n",
        "      else: r = mid - 1\n",
        "    return \"\""
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "timeMap = TimeMap()\n",
        "timeMap.set(\"foo\", \"bar\", 1)\n",
        "print(timeMap.get(\"foo\", 1))\n",
        "print(timeMap.get(\"foo\", 3))\n",
        "timeMap.set(\"foo\", \"bar2\", 4)\n",
        "print(timeMap.get(\"foo\", 4))\n",
        "print(timeMap.get(\"foo\", 5))\n",
        "print(timeMap.get(\"foi\", 5))\n",
        "print(timeMap.get(\"foi\", 4))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Fil4vuu_PMK9",
        "outputId": "f5238931-b2c6-468a-a4e1-448f466ab89c"
      },
      "execution_count": 86,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "bar\n",
            "bar\n",
            "bar2\n",
            "bar2\n",
            "\n",
            "\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Approach 2**"
      ],
      "metadata": {
        "id": "M3iCEjOAqZyo"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "class TimeMap:\n",
        "\n",
        "    def __init__(self):\n",
        "        \"\"\"\n",
        "        Initialize your data structure here.\n",
        "        \"\"\"\n",
        "        self.keyStore = {} # key : list of [val, timestamp]\n",
        "        \n",
        "    def set(self, key: str, value: str, timestamp: int) -> None:\n",
        "        if key not in self.keyStore:\n",
        "            self.keyStore[key] = []\n",
        "        self.keyStore[key].append([value, timestamp])\n",
        "\n",
        "    def get(self, key: str, timestamp: int) -> str:\n",
        "        res, values = \"\", self.keyStore.get(key, [])\n",
        "        l, r = 0, len(values) - 1\n",
        "        while l <= r:\n",
        "            m = (l + r) // 2\n",
        "            if values[m][1] <= timestamp:\n",
        "                res = values[m][0]\n",
        "                l = m + 1\n",
        "            else:\n",
        "                r = m - 1\n",
        "        return res"
      ],
      "metadata": {
        "id": "V2PFmWbaqbpu"
      },
      "execution_count": 82,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "timeMap = TimeMap()\n",
        "timeMap.set(\"foo\", \"bar\", 1)\n",
        "print(timeMap.get(\"foo\", 1))\n",
        "print(timeMap.get(\"foo\", 3))\n",
        "timeMap.set(\"foo\", \"bar2\", 4)\n",
        "print(timeMap.get(\"foo\", 4))\n",
        "print(timeMap.get(\"foo\", 5))\n",
        "print(timeMap.get(\"foi\", 5))\n",
        "print(timeMap.get(\"foi\", 4))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "oOjIlk6qqgWP",
        "outputId": "a6e5a110-1b58-4415-9dad-75156a6af464"
      },
      "execution_count": 83,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "bar\n",
            "bar\n",
            "bar2\n",
            "bar2\n",
            "\n",
            "\n"
          ]
        }
      ]
    }
  ]
}