求教一道狗家的面试题

求教一道狗家的面试题。题目是:
设计一个HashMap,需要完成put(key, value, ttl), get(key), size()。题目中的ttl是time to live。就是过多长时间这个value就失效了。

我能想出来O(N)的方法和O(logN)的方法,但是我觉得都不是面试官想要的。求教能不能有O(1)的方法。

面经题。过期map。

有link吗?或者能给我说说大概怎么搞?

我当时也面了这道题,只不过我存的是一个object吧。 用pq做 get可以到o(1).

不过我就是挂到这个题了,。。哈哈哈哈哈哈哈

expire map
https://cse.google.com/cse?cx=000913529356448796655:sh9y7rdatki

https://www.1point3acres.com/bbs/thread-230236-1-1.html

是用LinkedHashMap嘛?和leetcode 146 LRU cache 那题差不多嘛?

祝楼主好运!!!!!!

有没有说key是什么类型?还是说generic的?

我给的解法是BST,也跪了。我面试最后问他你能不能给我一个大概思路,他说狗家的policy说不行。我又问他说解法不告诉我算了,你告诉我一下你需要的时间复杂度。妈的死阿三就是不说。搞得我想了好几天,好几天都没睡好觉了…

key和value都无所谓

不好使,我第一个想到就是这个,结果发现时间复杂度是O(N),被人啪啪打脸