{"id":4691,"date":"2019-01-26T21:49:45","date_gmt":"2019-01-27T05:49:45","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4691"},"modified":"2019-01-27T13:55:04","modified_gmt":"2019-01-27T21:55:04","slug":"leetcode-981-time-based-key-value-store","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-981-time-based-key-value-store\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 981. Time Based Key-Value Store"},"content":{"rendered":"\n<p>Create a timebased key-value store class&nbsp;<code>TimeMap<\/code>, that supports two operations.<\/p>\n\n\n\n<p>1.&nbsp;<code>set(string key, string value, int timestamp)<\/code><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Stores the&nbsp;<code>key<\/code>&nbsp;and&nbsp;<code>value<\/code>, along with the given&nbsp;<code>timestamp<\/code>.<\/li><\/ul>\n\n\n\n<p>2.&nbsp;<code>get(string key, int timestamp)<\/code><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Returns a value such that&nbsp;<code>set(key, value, timestamp_prev)<\/code>&nbsp;was called previously, with&nbsp;<code>timestamp_prev &lt;= timestamp<\/code>.<\/li><li>If there are multiple such values, it returns the one with the largest&nbsp;<code>timestamp_prev<\/code>.<\/li><li>If there are no values, it returns the empty string (<code>\"\"<\/code>).<\/li><\/ul>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input: <\/strong>inputs = [\"TimeMap\",\"set\",\"get\",\"get\",\"set\",\"get\",\"get\"], inputs = [[],[\"foo\",\"bar\",1],[\"foo\",1],[\"foo\",3],[\"foo\",\"bar2\",4],[\"foo\",4],[\"foo\",5]]\n<strong>Output: <\/strong>[null,null,\"bar\",\"bar\",null,\"bar2\",\"bar2\"]\n<strong>Explanation: <\/strong>&nbsp; \nTimeMap kv; &nbsp; \nkv.set(\"foo\", \"bar\", 1); \/\/ store the key \"foo\" and value \"bar\" along with timestamp = 1 &nbsp; \nkv.get(\"foo\", 1);  \/\/ output \"bar\" &nbsp; \nkv.get(\"foo\", 3); \/\/ output \"bar\" since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 ie \"bar\" &nbsp; \nkv.set(\"foo\", \"bar2\", 4); &nbsp; \nkv.get(\"foo\", 4); \/\/ output \"bar2\" &nbsp; \nkv.get(\"foo\", 5); \/\/output \"bar2\" &nbsp; \n\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Input: <\/strong>inputs = [\"TimeMap\",\"set\",\"set\",\"get\",\"get\",\"get\",\"get\",\"get\"], inputs = [[],[\"love\",\"high\",10],[\"love\",\"low\",20],[\"love\",5],[\"love\",10],[\"love\",15],[\"love\",20],[\"love\",25]]\n<strong>Output: <\/strong>[null,null,null,\"\",\"high\",\"high\",\"low\",\"low\"]\n<\/pre>\n\n\n\n<p><strong>Note:<\/strong><\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>All key\/value strings are lowercase.<\/li><li>All key\/value strings have&nbsp;length in the range&nbsp;<code>[1, 100]<\/code><\/li><li>The&nbsp;<code>timestamps<\/code>&nbsp;for all&nbsp;<code>TimeMap.set<\/code>&nbsp;operations are strictly increasing.<\/li><li><code>1 &lt;= timestamp &lt;= 10^7<\/code><\/li><li><code>TimeMap.set<\/code>&nbsp;and&nbsp;<code>TimeMap.get<\/code>&nbsp;functions will be called a total of&nbsp;<code>120000<\/code>&nbsp;times (combined) per test case.<\/li><\/ol>\n\n\n\n<h2 class=\"wp-block-heading\">Solution: HashTable + Map<\/h2>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua, running time: 200 ms\nclass TimeMap {\npublic:\n  \/** Initialize your data structure here. *\/\n  TimeMap() {}\n\n  void set(string key, string value, int timestamp) {\n    s_[key].emplace(timestamp, std::move(value));\n  }\n\n  string get(string key, int timestamp) {\n    auto m = s_.find(key);\n    if (m == s_.end()) return \"\";    \n    auto it = m->second.upper_bound(timestamp);\n    if (it == begin(m->second)) return \"\";\n    return prev(it)->second;\n  }\nprivate:\n  unordered_map<string, map<int, string>> s_; \n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Create a timebased key-value store class&nbsp;TimeMap, that supports two operations. 1.&nbsp;set(string key, string value, int timestamp) Stores the&nbsp;key&nbsp;and&nbsp;value, along with the given&nbsp;timestamp. 2.&nbsp;get(string key, int&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70],"tags":[52,82,454,177,148],"class_list":["post-4691","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-binary-search","tag-hashtable","tag-kv","tag-medium","tag-pair","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4691","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4691"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4691\/revisions"}],"predecessor-version":[{"id":4722,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4691\/revisions\/4722"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4691"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4691"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4691"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}