TimeTravelingHashTable - Uber Interview

http://www.1point3acres.com/bbs/thread-141712-1-1.html
Implement TimeTravelingHashTable的get和insert方法
* TimeTravelingHashTable
* insert(key, value, timestamp)
* get(key, timestamp)
* get(key) // returns value associated with key at latest time. 
答的一般吧，写出来了但是最后有两个testcase没过，而且不是最优解。
* insert("k1", "v1", 10)
* get("k1") // returns "v1"
* get("k1", 11) // returns "v1"
* insert("k1", "v2", 20)
* get("k1", 15) // returns "v1" 
* get("k1", 11) // returns "v1"
* get("k1", 21)....

用treemap作value：

class keyToBSTMap<K, V>{

        Map<K, TreeMap<Float, V>> keyToBSTMap = new HashMap<>();

        public V get(K k, Float time){

                if(keyToBSTMap.containsKey(k) == false) return null;

                if(keyToBSTMap.get(k).containsKey(time))

                        return  keyToBSTMap.get(k).get(time);

                else

                        return  keyToBSTMap.get(k).lowerEntry(time).getValue();

        }

        public void put(K k , Float time, V value){

                if(keyToBSTMap.containsKey(k)) keyToBSTMap.get(k).put(time, value);

                else{

                        TreeMap<Float, V> t = new TreeMap<>();

                        t.put(time, value);

                        keyToBSTMap.put(k, t);

                }

        }info on 1point3acres.com

}

TreeMap uses balances red black tree, so finding the closest time / latest time value only costs O(logn)
Compared to LinkedListHashMap O(n)

https://gist.github.com/bookybooky/a4161cdd3fdd6200cd33d06014a68019

// <key : <timestamp : value>> = <key: sorted values on timestamp> = <key : treemap>

HashMap<String, TreeMap<Integer, String>> map = new HashMap<>();

// insert <timestamp, value> into hashmap

public void insert(String key, String value, int timestamp) {

        if(map.containsKey(key)) {

                Map<Integer, String> values = map.get(key);

                values.put(timestamp, value);

        } else {

                TreeMap<Integer, String> values = new TreeMap<>();

                values.put(timestamp, value);

                map.put(key, values);

        }

}

// get the floor value on timestamp

public String get(String key, int timestamp) {

        if(!map.containsKey(key)) return null;

        return map.get(key).floorEntry(timestamp).getValue();         

}

// Return the latest value on timestamp

public String get(String key) {

        return map.get(key).lastEntry().getValue();

}