d****g
发帖数: 153 | 1 已跪。。。
15分钟聊项目
后面出了一道题，写一个class实现下面功能：
put(key,value,time)
get(key, time)
要求get返回给定time前面的那个值.一个map，value用一个sort list，然后binary
search查找
code写的不熟，时间到了还没编译过。。。 |
z*********8
发帖数: 2070 | 2 why use sorted list instead of BST for values? |
y******l
发帖数: 16 | |
l******s
发帖数: 3045 | 4 hashmap+linkedlist应该可以实现O(1)。
【在 d****g 的大作中提到】
: 已跪。。。
: 15分钟聊项目
: 后面出了一道题，写一个class实现下面功能：
: put(key,value,time)
: get(key, time)
: 要求get返回给定time前面的那个值.一个map，value用一个sort list，然后binary
: search查找
: code写的不熟，时间到了还没编译过。。。
|
p*****2
发帖数: 21240 | 5
treemap是不是更好一点？
【在 d****g 的大作中提到】
: 已跪。。。
: 15分钟聊项目
: 后面出了一道题，写一个class实现下面功能：
: put(key,value,time)
: get(key, time)
: 要求get返回给定time前面的那个值.一个map，value用一个sort list，然后binary
: search查找
: code写的不熟，时间到了还没编译过。。。
|
d****g
发帖数: 153 | 6 能具体讲讲吗？
【在 l******s 的大作中提到】
: hashmap+linkedlist应该可以实现O(1)。
|
d****g
发帖数: 153 | 7 投的是backend
【在 y******l 的大作中提到】
: 请问面的哪个组阿？
|
d****g
发帖数: 153 | 8 yeh 是用的BST，我没说清楚
【在 z*********8 的大作中提到】
: why use sorted list instead of BST for values?
|
i**********u
发帖数: 119 | 9 我也被问了这题 用hash table加 sorted map秒杀 结果实现get的时候用stl的map：：
lower_bound死活返回不对的值 面试官也不知道为什么
后来我说我自己实现map。用bst写了个。运行加测试用例写了十几个，通过。
两个小时后recruiter发信说让去onsite |
h*********n
发帖数: 1002 | 10 这种live coding可以选择语言吗？比如 C#。还有提供什么IDE？ |
|
|
l******s
发帖数: 3045 | 11 一开始以为time是根据实时流水数据来的，如果这个假定被面试官否了就不能O(1)了。
不过在实际生产环境中，根据流水来的可能性很大。
【在 d****g 的大作中提到】
: 能具体讲讲吗？
|
z*********8
发帖数: 2070 | 12 同问
如果是用python这种没有built-in的tree的语言 该咋办……
【在 h*********n 的大作中提到】
: 这种live coding可以选择语言吗？比如 C#。还有提供什么IDE？
|
z******n
发帖数: 1183 | 13
应该都多准备几门语言备用吧
【在 z*********8 的大作中提到】
: 同问
: 如果是用python这种没有built-in的tree的语言 该咋办……
|
b*****t
发帖数: 296 | 14 两级hash不久搞定了，如果value只有一个（题目上说是“那个”值）。如果value有多
个，再加一级hash，然后记频率 |
b******z
发帖数: 410 | 15 lower_bound 返回比time大或等于time的第一个值， 不是题目要求，应该返回lower_
bound前的一个值。
【在 i**********u 的大作中提到】
: 我也被问了这题 用hash table加 sorted map秒杀 结果实现get的时候用stl的map：：
: lower_bound死活返回不对的值 面试官也不知道为什么
: 后来我说我自己实现map。用bst写了个。运行加测试用例写了十几个，通过。
: 两个小时后recruiter发信说让去onsite
|
b******z
发帖数: 410 | 16 lower_bound 返回比time大或等于time的第一个值， 不是题目要求，应该返回lower_
bound前的一个值。
【在 i**********u 的大作中提到】
: 我也被问了这题 用hash table加 sorted map秒杀 结果实现get的时候用stl的map：：
: lower_bound死活返回不对的值 面试官也不知道为什么
: 后来我说我自己实现map。用bst写了个。运行加测试用例写了十几个，通过。
: 两个小时后recruiter发信说让去onsite
|
w*****z
发帖数: 42 | 17 这题应该要先问一下put操作的time是不是递增的吧？
首先外面用一个hash map，key就是key，value如果time递增就是再一个vector，否则
就是tree map。这样找的时候就二分或者lower_bound |
