LeetCode: Time Based Key-Value Store C#

Question

https://leetcode.com/problems/time-based-key-value-store/

Create a timebased key-value store class TimeMap, that supports two operations.

1. set(string key, string value, int timestamp)

Stores the key and value, along with the given timestamp.

2. get(string key, int timestamp)

Returns a value such that set(key, value, timestamp_prev) was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the one with the largest timestamp_prev. If there are no values, it returns the empty string ("").

Example 1:

Input: inputs = ["TimeMap","set","get","get","set","get","get"], inputs = [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
Output: [null,null,"bar","bar",null,"bar2","bar2"]
Explanation:   
TimeMap kv;   
kv.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1   
kv.get("foo", 1);  // output "bar"   
kv.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"   
kv.set("foo", "bar2", 4);   
kv.get("foo", 4); // output "bar2"   
kv.get("foo", 5); //output "bar2"   

Example 2:

Input: 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]]
Output: [null,null,null,"","high","high","low","low"] 

Note:

All key/value strings are lowercase. All key/value strings have length in the range [1, 100] The timestamps for all TimeMap.set operations are strictly increasing. 1 <= timestamp <= 10^7 TimeMap.set and TimeMap.get functions will be called a total of 120000 times (combined) per test case.

using System.Collections.Generic;
using System.Collections.Specialized;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace SortingQuestions
{   /// <summary>
    /// https://leetcode.com/problems/time-based-key-value-store/
    /// </summary>
    [TestClass]
    public class TimeBasedKeyValueStoreTest
    {
        [TestMethod]
        public void TestMethod1()
        {
            TimeMap kv = new TimeMap();
            kv.Set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1
            Assert.AreEqual("bar", kv.Get("foo", 1)); // output "bar"
            Assert.AreEqual("bar", kv.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"
            kv.Set("foo", "bar2", 4);
            Assert.AreEqual("bar2", kv.Get("foo", 4)); // output "bar2"
            Assert.AreEqual("bar2", kv.Get("foo", 5)); // output "bar2"
        }
    }


    public class TimeMap
    {
        public Dictionary<string, List<KeyValuePair<int, string>>> Hash { get; set; }
        /** Initialize your data structure here. */
        public TimeMap()
        {
            Hash = new Dictionary<string, List<KeyValuePair<int, string>>>();
        }

        public void Set(string key, string value, int timestamp)
        {
            if (!Hash.TryGetValue(key, out var list))
            {
                list = Hash[key] = new List<KeyValuePair<int, string>>();
            }
            list.Add(new KeyValuePair<int, string>(timestamp, value));
        }

        public string Get(string key, int timestamp)
        {
            if (!Hash.ContainsKey(key))
            {
                return string.Empty;
            }

            var list = Hash[key];
            int i = list.BinarySearch(0, list.Count, new KeyValuePair<int, string>(timestamp, "}"), new TimeComparer());

            if (i >= 0)
            {
                return list[i].Value;
            }
            else if (i == -1)
            {
                return string.Empty;
            }
            else
            {
                //   value is negative
                int tempKey = -1 * i - 2;
                return list[tempKey].Value;
            }
        }
    }

    public class TimeComparer : IComparer<KeyValuePair<int, string>>
    {
        public int Compare(KeyValuePair<int, string> x, KeyValuePair<int, string> y)
        {
            if (x.Key == y.Key)
            {
                return 0;
            }
            if (x.Key > y.Key)
            {
                return 1;
            }
            return -1;
        }
    }
}

Answer 1

    public int Compare(KeyValuePair<int, string> x, KeyValuePair<int, string> y)
    {
        if (x.Key == y.Key)
        {
            return 0;
        }
        if (x.Key > y.Key)
        {
            return 1;
        }
        return -1;
    }

can just be implemented through Key:

    public int Compare(KeyValuePair<int, string> x, KeyValuePair<int, string> y)
    {
        return x.Key.CompareTo(y.Key);
    }

---

list.BinarySearch(0, list.Count, new KeyValuePair<int, string>(timestamp, "}"), new TimeComparer());

The first two arguments to list.BinarySearch are the default behaviour, so this can be simplified to:

list.BinarySearch(new KeyValuePair<int, string>(timestamp, "}"), new TimeComparer());

Also, the use of BinarySearch assumes that list is sorted. Is it? (Note: I see that this is handled in the challenge, assuming it for your API is maybe not the best thing still)

---

            //   value is negative
            int tempKey = -1 * i - 2;

Deserves maybe a bit more comments than value is negative. If BinarySearch returns a negative number, it respresents the binary complement of the index of the first item in list that is higher than the item we looked for. Since we want the first item that is one lower, -1.

And then replace the operation for retrieving the correct index in terms of the actual definition:

int tempKey = ~i - 1;

---

Assuming your list is sorted, you can quite easily check if the timestamp is present to begin with: compare it to the first and last items in the list for early exits.

---

Hash (weird name for a dictionary) doesn't need to be public; it is exposed through get and set. Make it a private readonly field.

The same goes for the TimeStampComparer class, its functionality is specific to TimeMap, so nest the class and make it private.