codekofi
← All questions

Time Based Key-Value Store

HardBinary Search

The problem

Design a store where every write is stamped with a time, and a read asks for the value a key held at a given moment.

A read returns the value written at the largest stamp not after the moment asked for, or the empty string if the key had no value yet. Writes for a key always arrive with increasing stamps.

The design is driven by a script of operations with their keys, values and stamps; writes report "null".

runTimeMap({"set","get","get"}, {"foo","foo","foo"}, {"bar","",""}, {1,1,3})

One of these three is correct

Two lines apart, at the closest.

The wrong ones are this same code with between two and five lines changed. Some of those changes do not compile. There is no Run button: running all three would turn this into a vote rather than a reading.

1struct Store {
2
3 map<string, vector<pair<int, string>>> history;
4
5 void put(const string& key, const string& value, int at) {
6 history[key].push_back({at, value});
7 }
8
9 string get(const string& key, int at) {
10
11 const auto& stamps = history[key];
12
13 int lo = 0;
14 int hi = (int)stamps.size() - 1;
15 string found;
16
17 while (lo <= hi) {
18
19 int mid = lo + (hi - lo) / 2;
20
21 if (stamps[mid].first <= at) {
22 found = stamps[mid].second;
23 lo = mid + 1;
24 } else {
25 hi = mid - 1;
26 }
27 }
28
29 return found;
30 }
31};
32
33vector<string> runTimeMap(const vector<string>& ops,
34 const vector<string>& keys,
35 const vector<string>& values,
36 const vector<int>& times) {
37
38 Store store;
39 vector<string> ans;
40
41 int n = ops.size();
42
43 for (int i = 0; i < n; i++) {
44
45 if (ops[i] == "set") {
46 store.put(keys[i], values[i], times[i]);
47 ans.push_back("null");
48
49 } else {
50 ans.push_back(store.get(keys[i], times[i]));
51 }
52 }
53
54 return ans;
55}
1struct Store {
2
3 map<string, vector<pair<int, string>>> history;
4
5 void put(const string& key, const string& value, int at) {
6 history[key - 1].push_back({at, value});
7 }
8
9 string get(const string& key, int at) {
10
11 const auto& stamps = history[key - 1];
12
13 int lo = 0;
14 int hi = (int)stamps.size() - 1;
15 string found;
16
17 while (lo <= hi) {
18
19 int mid = lo + (hi - lo) / 2;
20
21 if (stamps[mid].first <= at) {
22 found = stamps[mid].second;
23 lo = mid + 1;
24 } else {
25 hi = mid - 1;
26 }
27 }
28
29 return found;
30 }
31};
32
33vector<string> runTimeMap(const vector<string>& ops,
34 const vector<string>& keys,
35 const vector<string>& values,
36 const vector<int>& times) {
37
38 Store store;
39 vector<string> ans;
40
41 int n = ops.size();
42
43 for (int i = 0; i < n; i++) {
44
45 if (ops[i] == "set") {
46 store.put(keys[i], values[i], times[i]);
47 ans.push_back("null");
48
49 } else {
50 ans.push_back(store.get(keys[i], times[i]));
51 }
52 }
53
54 return ans;
55}
1struct Store {
2
3 map<string, vector<pair<int, string>>> history;
4
5 void put(const string& key, const string& value, int at) {
6 history[key - 1].push_back({at, value});
7 }
8
9 string get(const string& key, int at) {
10
11 const auto& stamps = history[key];
12
13 int lo = 1;
14 int hi = (int)stamps.size() - 1;
15 string found;
16
17 while (lo <= hi) {
18
19 int mid = lo + (hi - lo) / 2;
20
21 if (stamps[mid].first <= at) {
22 found = stamps[mid - 1].second;
23 lo = mid + 1;
24 } else {
25 hi = mid - 1;
26 }
27 }
28
29 return found;
30 }
31};
32
33vector<string> runTimeMap(const vector<string>& ops,
34 const vector<string>& keys,
35 const vector<string>& values,
36 const vector<int>& times) {
37
38 Store store;
39 vector<string> ans;
40
41 int n = ops.size();
42
43 for (int i = 0; i < n; i++) {
44
45 if (ops[i] == "set") {
46 store.put(keys[i], values[i], times[i]);
47 ans.push_back("null");
48
49 } else {
50 ans.push_back(store.get(keys[i], times[i]));
51 }
52 }
53
54 return ans;
55}