狗狗新鲜电面

上午刚面的，不难，发个面筋攒个人品求个onsite

准点打电话，听不出哪里人，应该不是三哥，先问了五分钟简历和为什么选择狗狗，然后让说一下map是什么。。。Java里有哪些map， 我只知道HashMap和TreeMap就说了这俩，又扯了五分钟，然后上题，没见过原题，但是似曾相识

设计一个Map,

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

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

emove。面试的时候特别紧张，头脑有点空白，所以平时练习时不会犯的错面试的时候有的时候想不到，不知道大家有没有好的解决办法面试头脑空白容易犯错的问题？

对3个操作time complexity有要求吗？都需要O(1) 吗？O(logn)可以吗？

我觉得可以这样，如果logn允许的话。

设计一个Node class, 里面有 int key, int value, expiration time
设计一个HashMap<Integer, Node>。key就是对应的key，Node就是对应的Node
设计一个TreeMap<Integer, Set<Integer>> key 是 expiration time，Set 是对应的那个时间点expire的key

对于get操作，查看是否有key在map里面，
没的话，返回null。
有的话，查看是否expire，没expire，返回value。
expire的话，删除hashmap 里面的node，删除treemap 里面对应的expiration的那个set里面的key
删完后如果treemap那个expiration time对应set空了话，删除这个expiration time。

对于set，同时更新treemap和hashmap，如果之前已经有过set expiration的话

对于clear，从treemap first key开始，删除所有expire的key。


补充内容 (2017-2-23 04:39):
额，set操作话说一半没说完，如果之前对一个值已经set过的话，找到原来的expiration time找到在treemap中expiration time的key，删掉这个key，找到新的expiration time，将key插入到新的treemap的位置。

每个人面试多少都会有些紧张，可能会犯一些平时不会出的错。这是你可能求胜心比较强，实际多面试几次慢慢的心里素质自然会强大了。出错率也会降低。所以没有太好的办法，只有多面，另外你听说过艺高人胆大，你如果刷题功夫下的比较多，可能心就不会这么紧张了。别太在意这些，每个面试者大部分人都有这个经历，慢慢随着你面试机会多了。你的感觉会好多了。

DWill008 发表于 2017-2-23 04:35
对3个操作time complexity有要求吗？都需要O(1) 吗？O(logn)可以吗？

我觉得可以这样，如果logn允许的话 ...

看了一下大家的回复，总结一下第二种思路：如果同一个key没有多个Value的话，可以考虑用Map加priorityqueue, 根据expire time从小到大排序，建议把expire time转换成具体时间点。get时直接检查是否小时当前时间，如果小于，返回null。set时同时更新Map和priorityqueue。更新priorityqueue时，直接加入新的Node，原来的先不做处理。cleanup的时候，检查从pq poll出来的node的expire time和map里是否一样，如果不同或者map里不存在这个node，只删除pq里的node，否则同时删除两边的。

如果set之后expiration time 变短了呢，如何在heap中更新

jiaguofang 发表于 2017-2-22 08:59
如果set之后expiration time 变短了呢，如何在heap中更新

不用更新，clean 的时候把所有 expire 的从 heap 中 poll出来就行了， poll出来的不一定还存在在 map中

supergin 发表于 2017-2-22 09:13
不用更新，clean 的时候把所有 expire 的从 heap 中 poll出来就行了， poll出来的不一定还存在在 map中

我的意思是：
假如你用min heap，越早expire的存在顶端。某次set之后，某个key的expiration time变短，照道理要往顶端推，但是你如果不更新它，就有可能poll不出来。因为其expiration time还是old值。

这个是类似于PassiveExpringMap吗

DWill008 发表于 2017-2-23 04:35
对3个操作time complexity有要求吗？都需要O(1) 吗？O(logn)可以吗？

我觉得可以这样，如果logn允许的话 ...

这个时间复杂度和用heap没什么区别啊

PriorityQueue没法更新，如果set了一个新的expiration time从heap里更新，在heap里找到应该是O（n），感觉TreeMap好一点

楼主后面这轮电话面试过了吗？ 话说这个面试官人怎么样？