j*****8
发帖数: 3635 | 1 版上考古出来的
15分钟聊项目
后面出了一道题，写一个class实现下面功能：
put(key,value,time)
get(key, time)
要求get返回给定time前面的那个值.一个map，value用一个sort list，然后binary
search查找
有个兄弟留言如下
我也被问了这题 用hash table加 sorted map秒杀。
这个用hashtable和sorted map怎么搞阿？ | e***i
发帖数: 231 | 2 抛个砖：
试着hash时间段，而不是时间点。
【在 j*****8 的大作中提到】
: 版上考古出来的
: 15分钟聊项目
: 后面出了一道题，写一个class实现下面功能：
: put(key,value,time)
: get(key, time)
: 要求get返回给定time前面的那个值.一个map，value用一个sort list，然后binary
: search查找
: 有个兄弟留言如下
: 我也被问了这题 用hash table加 sorted map秒杀。
: 这个用hashtable和sorted map怎么搞阿？
| w****a
发帖数: 710 | 3 class TimeTravelingHashTable {
public:
void insert(const string& key, const string& val, int time) {
data[key][time] = val;
}
string get(const string& key, int time) {
return data[key].lower_bound(time)->second;
}
string get(const string& key) {
return data[key].begin()->second;
}
private:
unordered_map>> data;
};
好使么？ | t**r
发帖数: 3428 | 4 hashmap==>
key -> key,
value -> set of [ time, value] pair stored in sorted map sorted by
time.
| j*****8
发帖数: 3635 | 5 明白了。java的话，value 用 treemap存 就行了
多谢楼上各位大侠！ | h*********n
发帖数: 1002 | 6 Can we also use hashmap instead of sorted map for the value itself? hashmap
is faster than sorted map. space concern? | M******1
发帖数: 90 | 7 import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
public class UberTest {
List data = new ArrayList<>();
public void fillData(){
//Use integer to denote Time here.. you can change it to DateTime
type.
data.add(new TimedKvPair(new KvPair("name1","Bnn"), 1) );
data.add(new TimedKvPair(new KvPair("name2","Dee"), 2) );
data.add(new TimedKvPair(new KvPair("name1","Alice"), 3) );
data.add(new TimedKvPair(new KvPair("name4","Bob"), 4) );
data.add(new TimedKvPair(new KvPair("name2","Dan"), 5) );
data.add(new TimedKvPair(new KvPair("name1","Jane"), 6) );
data.add(new TimedKvPair(new KvPair("name4","James"), 7) );
data.add(new TimedKvPair(new KvPair("name4","Jimmy"), 7) );
}
public static TreeMap createTreeMap(){
TreeMap map = new TreeMap(new
Comparator() {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
return map;
}
public static Map> createTreeMapHashMap(
List data){
Map> hashMap = new HashMap<>();
for(TimedKvPair d : data){
TreeMap treeMap;
if(hashMap.get(d.kv.key)==null){
treeMap = createTreeMap();
treeMap.put(d.dt, d.kv.value);
hashMap.put(d.kv.key, treeMap);
} else {
treeMap = hashMap.get(d.kv.key);
treeMap.put(d.dt, d.kv.value);
hashMap.put(d.kv.key, treeMap);
}
}
return hashMap;
// map.put(0, "Kid");
// map.put(11, "Teens");
// map.put(20, "Twenties");
// map.put(30, "Thirties");
// map.put(40, "Forties");
// map.put(50, "Senior");
// map.put(100, "OMG OMG OMG!");
// System.out.println(map.get(map.ceilingKey(29)));
// System.out.println(map.get(map.floorKey(13))); // Teens
// System.out.println(map.get(map.floorKey(29))); // Twenties
// System.out.println(map.get(map.floorKey(30))); // Thirties
// System.out.println(map.floorEntry(42).getValue()); // Forties
}
public String getData(Map> map, String
key, int time){
TreeMap curMap = map.get(key);
Integer queryTimeKey = curMap.ceilingKey(time);
System.out.println("queryTimeKey is "+ queryTimeKey);
return map.get(key).get(queryTimeKey);
}
public void dumpMapData(Map> map){
System.out.println(map);
}
public static void main(String[] args){
// createTreeMap();
UberTest ttm = new UberTest();
ttm.fillData();
Map> hashMap = ttm.
createTreeMapHashMap(ttm.data);
System.out.println(" get data " + ttm.getData(hashMap, "name1", 5));
ttm.dumpMapData(hashMap);
}
public class KvPair {
public KvPair(String key, String value) {
super();
this.key = key;
this.value = value;
}
public String key;
public String value;
}
public class TimedKvPair {
public TimedKvPair(KvPair kv, int dt) {
super();
this.kv = kv;
this.dt = dt;
}
KvPair kv;
int dt;
}
} |
|
