来讨论个uber的电面题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

来讨论个uber的电面题

来讨论个uber的电面题# JobHunting - 待字闺中

j*82015-10-13 07:10

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*i2015-10-13 07:10

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*a2015-10-13 07:10

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*r2015-10-13 07:10

4 楼

hashmap==>
key -> key,
value -> set of [ time, value] pair stored in sorted map sorted by
time.

j*82015-10-13 07:10

5 楼

明白了。java的话，value 用 treemap存就行了
多谢楼上各位大侠！

h*n2015-10-13 07:10

6 楼

Can we also use hashmap instead of sorted map for the value itself? hashmap
is faster than sorted map. space concern?

M*12015-10-13 07:10

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;
}
}