四月中狗家店面

jaychsu 发表于 2018-4-19 07:37
怎么感觉这题就是写一个 memcache? 我猜 followup 是不是问加上 ttl 使过期时间戳的 key 失效

恩，感觉也蛮像的，不过我的f -u不是这个，就是主要跟面试官交流了一下get set method的性能，有什么优化一类的

huzihao46 发表于 2018-4-19 06:39
这题就是二叉树查找吧。。。

感觉这个主要是建数据结构，理解成树也可以（不一定是二叉），加node和查node的操作吧

楼主最后实现的时间复杂度是多少？ 插入，查询都是 lg n 吗？

markpen 发表于 2018-4-22 00:03
楼主最后实现的时间复杂度是多少？ 插入，查询都是 lg n 吗？

查询是O1，因为都是hashmap O1； 插入是lgn优化之后，但这个取决于题目中的一个假设，就是可以查询任意时刻，如果这个时刻没有就返回跟他最近的时刻；如果题目的假设是如果这个时刻没有，就返回最后时刻的话，那么不需要优化，也是o1；这个是小小的不同，要讨论一下

xietianyi 发表于 2018-4-22 02:26
查询是O1，因为都是hashmap O1； 插入是lgn优化之后，但这个取决于题目中的一个假设，就是可以查询任意时 ...

给楼主加大米了，有个疑问。
如果只用key查找的话，是不是需要另外建一个map来存key和newest value， 才能实现O(1)时间。
插入为什么优化之后是log n呢？
Map<Key, Value> map1;
Map<Key, Map<Timestamp, Value>> map2;
查找的时候只有key的话，查询map1；有key和timestamp的情况，查询map2.
插入的话同时更新map1，和map2.但是这个时间复杂度是O(1)。所以没太理解楼主说的log n时间。

Yanainusa 发表于 2018-4-30 11:16
给楼主加大米了，有个疑问。
如果只用key查找的话，是不是需要另外建一个map来存key和newest value， 才 ...

我觉得楼主的意思是 因为查询的时候如果没有输入的timestamp在structure里，要返回与之最近的timestamp。所以插入的时候要有顺序。

楼主决定去狗家了么，是的话可以加下google full time 2018的群

我只想到HashMap of TreeMap的做法。 查询和添加都是logn。

HashMap of HashMap的话，查询的时候：
如果题目是： 没找到就返回最后一个entry，那也不会是O(1)吧？ 因为HashMap里的entries不都是unsorted的吗? 哪怕是返回最后一个entry，也是get不到的呀。
如果题目是： 没找到就返回最接近的timestamp对应的value，楼主说是查询可以O(1)，插入是logn，楼上有人分析是因为后边的map已经sort过了才能O(1)查到，请问怎么实现这是？

求诸位解惑~ 谢~

remix 发表于 2018-10-9 05:29
我只想到HashMap of TreeMap的做法。 查询和添加都是logn。

HashMap of HashMap的话，查询的时候：

我只想到HashMap of TreeMap的做法。 查询和添加都是logn
我也只想到这种做法, 然后用floorkey来做.