四月中狗家店面

周一店面的，发个面经赞一波人品题目只有一道，地里的面经题，就是写一个class是一个带timestamp 历史的hashmap；
准确点说就是，这个数据结构可以想hashmap那样存key-value pair，同时也要保存timestamp；

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

补充内容 (2018-4-19 07:47):
楼主回复这么及时，觉得有用的朋友们加点米呗 ~~

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时间。

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

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

求诸位解惑~ 谢~

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

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

楼主多久收到pass消息

luobaobao3 发表于 2018-4-19 06:17
楼主多久收到pass消息

刚刚收到

不太明白，所以key不是唯一的？同一个key不同的timestamp可以有不同的value？

idatascience 发表于 2018-4-19 06:24
不太明白，所以key不是唯一的？同一个key不同的timestamp可以有不同的value？

当然啦，你就想，这首先是一个hashmap，他的key肯定是唯一的；
但是一个key对应的timestamp可以存很多，value也可以存很多，所以你要想一个结构再存timestamp和value的对应关系

这题就是二叉树查找吧。。。

https://www.careercup.com/question?id=5689672300756992
楼主的题目跟这里的一样吗？

xietianyi 发表于 2018-4-19 06:28
当然啦，你就想，这首先是一个hashmap，他的key肯定是唯一的；
但是一个key对应的timestamp可以存很多， ...

Map<key, Map<Timestamp, Value>>吧？

怎么感觉这题就是写一个 memcache? 我猜 followup 是不是问加上 ttl 使过期时间戳的 key 失效

lakeshore 发表于 2018-4-19 07:02
https://www.careercup.com/question?id=5689672300756992
楼主的题目跟这里的一样吗？

差不多，基本是这样的