g********n
发帖数: 447 | 1 就是类似于LRU Cache的问题，感觉给我这类题，完全无从下手，只有看了答案才知道
该怎么做。
有没有其他类似的题，可以练习？ |
m******x
发帖数: 58 | 2 需要对ds比较熟悉。我觉得lru是无准备情况下最能考察ds熟悉程度的题目。
准备方法是详细了解每种ds的big o和实现细节。
【在 g********n 的大作中提到】
: 就是类似于LRU Cache的问题，感觉给我这类题，完全无从下手，只有看了答案才知道
: 该怎么做。
: 有没有其他类似的题，可以练习？
|
h*******e
发帖数: 1377 | 3 O(1) 插入删除 修改 那个有没有人有答案什么的。 |
l*****a
发帖数: 14598 | 4 不详细说题谁知道你再说什么
【在 h*******e 的大作中提到】
: O(1) 插入删除 修改 那个有没有人有答案什么的。
|
h*******e
发帖数: 1377 | 5 设计一个数据结构 ， 使 删除 查找 添加 修改得复杂度都是 O（1）时间。 G 家很经
典的一道题哦
【在 l*****a 的大作中提到】
: 不详细说题谁知道你再说什么
|
j*****8
发帖数: 3635 | 6 双链表+hashmap
【在 h*******e 的大作中提到】
: 设计一个数据结构 ， 使 删除 查找 添加 修改得复杂度都是 O（1）时间。 G 家很经
: 典的一道题哦
|
l*****a
发帖数: 14598 | 7 需求加上O(1) get random你咋作
【在 j*****8 的大作中提到】
: 双链表+hashmap
|
l*****f
发帖数: 259 | 8 Array + Hash
Hash的key是array里面的值，value是index
getrandom就直接生成index random access array
insert就insert在array最后，同时update hash
delete就先用hash找到对应的index，假设为i。然后swap第i个和array最后一个，然后
删掉array最后一个，同时更新hash
lookup直接hash搞定 |
h*******e
发帖数: 1377 | 9 感谢精彩回答。 这个数据结构性质这么好， 在各种工程里面有没有实际的应用。
【在 l*****f 的大作中提到】
: Array + Hash
: Hash的key是array里面的值，value是index
: getrandom就直接生成index random access array
: insert就insert在array最后，同时update hash
: delete就先用hash找到对应的index，假设为i。然后swap第i个和array最后一个，然后
: 删掉array最后一个，同时更新hash
: lookup直接hash搞定
|
y***i
发帖数: 414 | 10
如何体现最近的N次读取。hottest的被缓存的几个
【在 l*****f 的大作中提到】
: Array + Hash
: Hash的key是array里面的值，value是index
: getrandom就直接生成index random access array
: insert就insert在array最后，同时update hash
: delete就先用hash找到对应的index，假设为i。然后swap第i个和array最后一个，然后
: 删掉array最后一个，同时更新hash
: lookup直接hash搞定
|
|
|
h*******e
发帖数: 1377 | 11 ～～～ 这是两道题， 楼主说的题目leetcode上有，我说的还有这位仁兄解答的是另
一道高频数据结构面试题O(1)时间插入删除修改查找，getrandom()的数据结构设计。
【在 y***i 的大作中提到】
:
: 如何体现最近的N次读取。hottest的被缓存的几个
|
g******i
发帖数: 16 | 12 说实话你静下心来读几个开源系统的代码就都会了。
举个例子，LRU除了楼上几位说的实现，实践中你还得考虑并发，然后展开来如何提高
parallelism，如何设计封锁协议，最后进一步，可以问你，如果每次都new/malloc一
个新的item，然后evict旧的，这个代价是否太大，如何优化，等等。
会hash ＋ array只是一个进本要求，都不用你实现代码，以上只是就是口头提问就能
摸出你的水平了。多认真复习基础知识吧，切题只是一个敲门砖。 |
h*******e
发帖数: 1377 | 13 并发这个是不是不做系统的人就不会被问阿，感觉vmware，cisco 最喜欢问多线程多进
程的问题了，操作系统课的时候老师还请过他们的vmware founder给讲虚拟机架构，听得
是云里雾里的～～～
【在 g******i 的大作中提到】
: 说实话你静下心来读几个开源系统的代码就都会了。
: 举个例子，LRU除了楼上几位说的实现，实践中你还得考虑并发，然后展开来如何提高
: parallelism，如何设计封锁协议，最后进一步，可以问你，如果每次都new/malloc一
: 个新的item，然后evict旧的，这个代价是否太大，如何优化，等等。
: 会hash ＋ array只是一个进本要求，都不用你实现代码，以上只是就是口头提问就能
: 摸出你的水平了。多认真复习基础知识吧，切题只是一个敲门砖。
|
m**p
发帖数: 189 | 14 大牛可不可以展开说说，读那些开源系统啊？
【在 g******i 的大作中提到】
: 说实话你静下心来读几个开源系统的代码就都会了。
: 举个例子，LRU除了楼上几位说的实现，实践中你还得考虑并发，然后展开来如何提高
: parallelism，如何设计封锁协议，最后进一步，可以问你，如果每次都new/malloc一
: 个新的item，然后evict旧的，这个代价是否太大，如何优化，等等。
: 会hash ＋ array只是一个进本要求，都不用你实现代码，以上只是就是口头提问就能
: 摸出你的水平了。多认真复习基础知识吧，切题只是一个敲门砖。
|
m********a
发帖数: 128 | 15 被问到这道题 不能用现成的class吗，比如java 里现成的linkedhashmap？
【在 j*****8 的大作中提到】
: 双链表+hashmap
|
g********n
发帖数: 447 | 16 就是类似于LRU Cache的问题，感觉给我这类题，完全无从下手，只有看了答案才知道
该怎么做。
有没有其他类似的题，可以练习？ |
m******x
发帖数: 58 | 17 需要对ds比较熟悉。我觉得lru是无准备情况下最能考察ds熟悉程度的题目。
准备方法是详细了解每种ds的big o和实现细节。
【在 g********n 的大作中提到】
: 就是类似于LRU Cache的问题，感觉给我这类题，完全无从下手，只有看了答案才知道
: 该怎么做。
: 有没有其他类似的题，可以练习？
|
h*******e
发帖数: 1377 | 18 O(1) 插入删除 修改 那个有没有人有答案什么的。 |
l*****a
发帖数: 14598 | 19 不详细说题谁知道你再说什么
【在 h*******e 的大作中提到】
: O(1) 插入删除 修改 那个有没有人有答案什么的。
|
h*******e
发帖数: 1377 | 20 设计一个数据结构 ， 使 删除 查找 添加 修改得复杂度都是 O（1）时间。 G 家很经
典的一道题哦
【在 l*****a 的大作中提到】
: 不详细说题谁知道你再说什么
|
|
|
j*****8
发帖数: 3635 | 21 双链表+hashmap
【在 h*******e 的大作中提到】
: 设计一个数据结构 ， 使 删除 查找 添加 修改得复杂度都是 O（1）时间。 G 家很经
: 典的一道题哦
|
l*****a
发帖数: 14598 | 22 需求加上O(1) get random你咋作
【在 j*****8 的大作中提到】
: 双链表+hashmap
|
l*****f
发帖数: 259 | 23 Array + Hash
Hash的key是array里面的值，value是index
getrandom就直接生成index random access array
insert就insert在array最后，同时update hash
delete就先用hash找到对应的index，假设为i。然后swap第i个和array最后一个，然后
删掉array最后一个，同时更新hash
lookup直接hash搞定 |
h*******e
发帖数: 1377 | 24 感谢精彩回答。 这个数据结构性质这么好， 在各种工程里面有没有实际的应用。
【在 l*****f 的大作中提到】
: Array + Hash
: Hash的key是array里面的值，value是index
: getrandom就直接生成index random access array
: insert就insert在array最后，同时update hash
: delete就先用hash找到对应的index，假设为i。然后swap第i个和array最后一个，然后
: 删掉array最后一个，同时更新hash
: lookup直接hash搞定
|
y***i
发帖数: 414 | 25
如何体现最近的N次读取。hottest的被缓存的几个
【在 l*****f 的大作中提到】
: Array + Hash
: Hash的key是array里面的值，value是index
: getrandom就直接生成index random access array
: insert就insert在array最后，同时update hash
: delete就先用hash找到对应的index，假设为i。然后swap第i个和array最后一个，然后
: 删掉array最后一个，同时更新hash
: lookup直接hash搞定
|
h*******e
发帖数: 1377 | 26 ～～～ 这是两道题， 楼主说的题目leetcode上有，我说的还有这位仁兄解答的是另
一道高频数据结构面试题O(1)时间插入删除修改查找，getrandom()的数据结构设计。
【在 y***i 的大作中提到】
:
: 如何体现最近的N次读取。hottest的被缓存的几个
|
g******i
发帖数: 16 | 27 说实话你静下心来读几个开源系统的代码就都会了。
举个例子，LRU除了楼上几位说的实现，实践中你还得考虑并发，然后展开来如何提高
parallelism，如何设计封锁协议，最后进一步，可以问你，如果每次都new/malloc一
个新的item，然后evict旧的，这个代价是否太大，如何优化，等等。
会hash ＋ array只是一个进本要求，都不用你实现代码，以上只是就是口头提问就能
摸出你的水平了。多认真复习基础知识吧，切题只是一个敲门砖。 |
h*******e
发帖数: 1377 | 28 并发这个是不是不做系统的人就不会被问阿，感觉vmware，cisco 最喜欢问多线程多进
程的问题了，操作系统课的时候老师还请过他们的vmware founder给讲虚拟机架构，听得
是云里雾里的～～～
【在 g******i 的大作中提到】
: 说实话你静下心来读几个开源系统的代码就都会了。
: 举个例子，LRU除了楼上几位说的实现，实践中你还得考虑并发，然后展开来如何提高
: parallelism，如何设计封锁协议，最后进一步，可以问你，如果每次都new/malloc一
: 个新的item，然后evict旧的，这个代价是否太大，如何优化，等等。
: 会hash ＋ array只是一个进本要求，都不用你实现代码，以上只是就是口头提问就能
: 摸出你的水平了。多认真复习基础知识吧，切题只是一个敲门砖。
|
m**p
发帖数: 189 | 29 大牛可不可以展开说说，读那些开源系统啊？
【在 g******i 的大作中提到】
: 说实话你静下心来读几个开源系统的代码就都会了。
: 举个例子，LRU除了楼上几位说的实现，实践中你还得考虑并发，然后展开来如何提高
: parallelism，如何设计封锁协议，最后进一步，可以问你，如果每次都new/malloc一
: 个新的item，然后evict旧的，这个代价是否太大，如何优化，等等。
: 会hash ＋ array只是一个进本要求，都不用你实现代码，以上只是就是口头提问就能
: 摸出你的水平了。多认真复习基础知识吧，切题只是一个敲门砖。
|
m********a
发帖数: 128 | 30 被问到这道题 不能用现成的class吗，比如java 里现成的linkedhashmap？
【在 j*****8 的大作中提到】
: 双链表+hashmap
|
|
|
d*l
发帖数: 1810 | 31 请问array如何解决插入时容量不够需要分配更多内存情况？
【在 l*****f 的大作中提到】
: Array + Hash
: Hash的key是array里面的值，value是index
: getrandom就直接生成index random access array
: insert就insert在array最后，同时update hash
: delete就先用hash找到对应的index，假设为i。然后swap第i个和array最后一个，然后
: 删掉array最后一个，同时更新hash
: lookup直接hash搞定
|
L***s
发帖数: 1148 | 32
我觉得可以直接用。当然你要知道LinkedHashMap怎么实现的。
我面某司的时候，就直接用python的OrderedDict做的，事后整理如下。
然后被问及OrderedDict的实现，就说了句环形双链表加哈希，就pass到下一题了。
from collections import OrderedDict
class LRUCache (object):
def __init__(self, capacity):
self._cache = OrderedDict()
self.capacity = capacity
def __setitem__(self, key, value):
if key in self._cache:
self._cache.pop(key)
self._cache[key] = value
else:
self._cache[key] = value
if len(self._cache) > self.capacity:
self._cache.popitem(last=False) # FIFO pop
def __getitem__(self, key):
if key not in self._cache:
return None
#self._cache.move_to_end(key)
value = self._cache.pop(key)
self._cache[key] = value # pop and add to back
return value
def keys(self):
return list(self._cache.keys())
if __name__ == '__main__':
cache = LRUCache(4)
cache[1] = cache[3] = cache[2] = 'used'
print(cache.keys()) # [1, 3, 2]
cache[1]
print(cache.keys()) # [3, 2, 1]
cache[5] = 'used'
print(cache.keys()) # [3, 2, 1, 5]
cache[4] = 'used'
print(cache.keys()) # [2, 1, 5, 3]
【在 m********a 的大作中提到】
: 被问到这道题 不能用现成的class吗，比如java 里现成的linkedhashmap？
|
l********s
发帖数: 358 | 33 Check Android's LRUCache code:
https://github.com/android/platform_frameworks_support/blob/master/v4/java/
android/support/v4/util/LruCache.java
Most are pretty basic. |
i**********n
发帖数: 196 | |
