2019年度TOTY最佳玩具榜单# Parenting - 为人父母
g*n
1 楼
就是类似于LRU Cache的问题，感觉给我这类题，完全无从下手，只有看了答案才知道
该怎么做。
有没有其他类似的题，可以练习？
该怎么做。
有没有其他类似的题，可以练习？
f*a
2 楼
2019年度TOTY最佳玩具榜单，link：
https://t.co/BzpVRmp9Z5
https://t.co/BzpVRmp9Z5
m*x
3 楼
需要对ds比较熟悉。我觉得lru是无准备情况下最能考察ds熟悉程度的题目。
准备方法是详细了解每种ds的big o和实现细节。
【在 g********n 的大作中提到】
: 就是类似于LRU Cache的问题，感觉给我这类题，完全无从下手，只有看了答案才知道
: 该怎么做。
: 有没有其他类似的题，可以练习？
准备方法是详细了解每种ds的big o和实现细节。
【在 g********n 的大作中提到】
: 就是类似于LRU Cache的问题，感觉给我这类题，完全无从下手，只有看了答案才知道
: 该怎么做。
: 有没有其他类似的题，可以练习？
h*e
4 楼
O(1) 插入删除 修改 那个有没有人有答案什么的。
l*a
5 楼
不详细说题谁知道你再说什么
【在 h*******e 的大作中提到】
: O(1) 插入删除 修改 那个有没有人有答案什么的。
【在 h*******e 的大作中提到】
: O(1) 插入删除 修改 那个有没有人有答案什么的。
h*e
6 楼
设计一个数据结构 ， 使 删除 查找 添加 修改得复杂度都是 O（1）时间。 G 家很经
典的一道题哦
【在 l*****a 的大作中提到】
: 不详细说题谁知道你再说什么
典的一道题哦
【在 l*****a 的大作中提到】
: 不详细说题谁知道你再说什么
j*8
7 楼
双链表+hashmap
【在 h*******e 的大作中提到】
: 设计一个数据结构 ， 使 删除 查找 添加 修改得复杂度都是 O（1）时间。 G 家很经
: 典的一道题哦
【在 h*******e 的大作中提到】
: 设计一个数据结构 ， 使 删除 查找 添加 修改得复杂度都是 O（1）时间。 G 家很经
: 典的一道题哦
l*a
8 楼
需求加上O(1) get random你咋作
【在 j*****8 的大作中提到】
: 双链表+hashmap
【在 j*****8 的大作中提到】
: 双链表+hashmap
l*f
9 楼
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搞定
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
10 楼
感谢精彩回答。 这个数据结构性质这么好， 在各种工程里面有没有实际的应用。
【在 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*****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
11 楼
如何体现最近的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
12 楼
～～～ 这是两道题， 楼主说的题目leetcode上有，我说的还有这位仁兄解答的是另
一道高频数据结构面试题O(1)时间插入删除修改查找，getrandom()的数据结构设计。
【在 y***i 的大作中提到】
:
: 如何体现最近的N次读取。hottest的被缓存的几个
一道高频数据结构面试题O(1)时间插入删除修改查找，getrandom()的数据结构设计。
【在 y***i 的大作中提到】
:
: 如何体现最近的N次读取。hottest的被缓存的几个
g*i
13 楼
说实话你静下心来读几个开源系统的代码就都会了。
举个例子，LRU除了楼上几位说的实现，实践中你还得考虑并发，然后展开来如何提高
parallelism，如何设计封锁协议，最后进一步，可以问你，如果每次都new/malloc一
个新的item，然后evict旧的，这个代价是否太大，如何优化，等等。
会hash ＋ array只是一个进本要求，都不用你实现代码，以上只是就是口头提问就能
摸出你的水平了。多认真复习基础知识吧，切题只是一个敲门砖。
举个例子，LRU除了楼上几位说的实现，实践中你还得考虑并发，然后展开来如何提高
parallelism，如何设计封锁协议，最后进一步，可以问你，如果每次都new/malloc一
个新的item，然后evict旧的，这个代价是否太大，如何优化，等等。
会hash ＋ array只是一个进本要求，都不用你实现代码，以上只是就是口头提问就能
摸出你的水平了。多认真复习基础知识吧，切题只是一个敲门砖。
h*e
14 楼
并发这个是不是不做系统的人就不会被问阿，感觉vmware，cisco 最喜欢问多线程多进
程的问题了，操作系统课的时候老师还请过他们的vmware founder给讲虚拟机架构，听得
是云里雾里的～～～
【在 g******i 的大作中提到】
: 说实话你静下心来读几个开源系统的代码就都会了。
: 举个例子，LRU除了楼上几位说的实现，实践中你还得考虑并发，然后展开来如何提高
: parallelism，如何设计封锁协议，最后进一步，可以问你，如果每次都new/malloc一
: 个新的item，然后evict旧的，这个代价是否太大，如何优化，等等。
: 会hash ＋ array只是一个进本要求，都不用你实现代码，以上只是就是口头提问就能
: 摸出你的水平了。多认真复习基础知识吧，切题只是一个敲门砖。
程的问题了，操作系统课的时候老师还请过他们的vmware founder给讲虚拟机架构，听得
是云里雾里的～～～
【在 g******i 的大作中提到】
: 说实话你静下心来读几个开源系统的代码就都会了。
: 举个例子，LRU除了楼上几位说的实现，实践中你还得考虑并发，然后展开来如何提高
: parallelism，如何设计封锁协议，最后进一步，可以问你，如果每次都new/malloc一
: 个新的item，然后evict旧的，这个代价是否太大，如何优化，等等。
: 会hash ＋ array只是一个进本要求，都不用你实现代码，以上只是就是口头提问就能
: 摸出你的水平了。多认真复习基础知识吧，切题只是一个敲门砖。
m*p
15 楼
大牛可不可以展开说说，读那些开源系统啊？
【在 g******i 的大作中提到】
: 说实话你静下心来读几个开源系统的代码就都会了。
: 举个例子，LRU除了楼上几位说的实现，实践中你还得考虑并发，然后展开来如何提高
: parallelism，如何设计封锁协议，最后进一步，可以问你，如果每次都new/malloc一
: 个新的item，然后evict旧的，这个代价是否太大，如何优化，等等。
: 会hash ＋ array只是一个进本要求，都不用你实现代码，以上只是就是口头提问就能
: 摸出你的水平了。多认真复习基础知识吧，切题只是一个敲门砖。
【在 g******i 的大作中提到】
: 说实话你静下心来读几个开源系统的代码就都会了。
: 举个例子，LRU除了楼上几位说的实现，实践中你还得考虑并发，然后展开来如何提高
: parallelism，如何设计封锁协议，最后进一步，可以问你，如果每次都new/malloc一
: 个新的item，然后evict旧的，这个代价是否太大，如何优化，等等。
: 会hash ＋ array只是一个进本要求，都不用你实现代码，以上只是就是口头提问就能
: 摸出你的水平了。多认真复习基础知识吧，切题只是一个敲门砖。
m*a
16 楼
被问到这道题 不能用现成的class吗，比如java 里现成的linkedhashmap？
【在 j*****8 的大作中提到】
: 双链表+hashmap
【在 j*****8 的大作中提到】
: 双链表+hashmap
g*n
17 楼
就是类似于LRU Cache的问题，感觉给我这类题，完全无从下手，只有看了答案才知道
该怎么做。
有没有其他类似的题，可以练习？
该怎么做。
有没有其他类似的题，可以练习？
m*x
18 楼
需要对ds比较熟悉。我觉得lru是无准备情况下最能考察ds熟悉程度的题目。
准备方法是详细了解每种ds的big o和实现细节。
【在 g********n 的大作中提到】
: 就是类似于LRU Cache的问题，感觉给我这类题，完全无从下手，只有看了答案才知道
: 该怎么做。
: 有没有其他类似的题，可以练习？
准备方法是详细了解每种ds的big o和实现细节。
【在 g********n 的大作中提到】
: 就是类似于LRU Cache的问题，感觉给我这类题，完全无从下手，只有看了答案才知道
: 该怎么做。
: 有没有其他类似的题，可以练习？
h*e
19 楼
O(1) 插入删除 修改 那个有没有人有答案什么的。
l*a
20 楼
不详细说题谁知道你再说什么
【在 h*******e 的大作中提到】
: O(1) 插入删除 修改 那个有没有人有答案什么的。
【在 h*******e 的大作中提到】
: O(1) 插入删除 修改 那个有没有人有答案什么的。
h*e
21 楼
设计一个数据结构 ， 使 删除 查找 添加 修改得复杂度都是 O（1）时间。 G 家很经
典的一道题哦
【在 l*****a 的大作中提到】
: 不详细说题谁知道你再说什么
典的一道题哦
【在 l*****a 的大作中提到】
: 不详细说题谁知道你再说什么
j*8
22 楼
双链表+hashmap
【在 h*******e 的大作中提到】
: 设计一个数据结构 ， 使 删除 查找 添加 修改得复杂度都是 O（1）时间。 G 家很经
: 典的一道题哦
【在 h*******e 的大作中提到】
: 设计一个数据结构 ， 使 删除 查找 添加 修改得复杂度都是 O（1）时间。 G 家很经
: 典的一道题哦
l*a
23 楼
需求加上O(1) get random你咋作
【在 j*****8 的大作中提到】
: 双链表+hashmap
【在 j*****8 的大作中提到】
: 双链表+hashmap
l*f
24 楼
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搞定
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
25 楼
感谢精彩回答。 这个数据结构性质这么好， 在各种工程里面有没有实际的应用。
【在 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*****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
26 楼
如何体现最近的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
27 楼
～～～ 这是两道题， 楼主说的题目leetcode上有，我说的还有这位仁兄解答的是另
一道高频数据结构面试题O(1)时间插入删除修改查找，getrandom()的数据结构设计。
【在 y***i 的大作中提到】
:
: 如何体现最近的N次读取。hottest的被缓存的几个
一道高频数据结构面试题O(1)时间插入删除修改查找，getrandom()的数据结构设计。
【在 y***i 的大作中提到】
:
: 如何体现最近的N次读取。hottest的被缓存的几个
g*i
28 楼
说实话你静下心来读几个开源系统的代码就都会了。
举个例子，LRU除了楼上几位说的实现，实践中你还得考虑并发，然后展开来如何提高
parallelism，如何设计封锁协议，最后进一步，可以问你，如果每次都new/malloc一
个新的item，然后evict旧的，这个代价是否太大，如何优化，等等。
会hash ＋ array只是一个进本要求，都不用你实现代码，以上只是就是口头提问就能
摸出你的水平了。多认真复习基础知识吧，切题只是一个敲门砖。
举个例子，LRU除了楼上几位说的实现，实践中你还得考虑并发，然后展开来如何提高
parallelism，如何设计封锁协议，最后进一步，可以问你，如果每次都new/malloc一
个新的item，然后evict旧的，这个代价是否太大，如何优化，等等。
会hash ＋ array只是一个进本要求，都不用你实现代码，以上只是就是口头提问就能
摸出你的水平了。多认真复习基础知识吧，切题只是一个敲门砖。
h*e
29 楼
并发这个是不是不做系统的人就不会被问阿，感觉vmware，cisco 最喜欢问多线程多进
程的问题了，操作系统课的时候老师还请过他们的vmware founder给讲虚拟机架构，听得
是云里雾里的～～～
【在 g******i 的大作中提到】
: 说实话你静下心来读几个开源系统的代码就都会了。
: 举个例子，LRU除了楼上几位说的实现，实践中你还得考虑并发，然后展开来如何提高
: parallelism，如何设计封锁协议，最后进一步，可以问你，如果每次都new/malloc一
: 个新的item，然后evict旧的，这个代价是否太大，如何优化，等等。
: 会hash ＋ array只是一个进本要求，都不用你实现代码，以上只是就是口头提问就能
: 摸出你的水平了。多认真复习基础知识吧，切题只是一个敲门砖。
程的问题了，操作系统课的时候老师还请过他们的vmware founder给讲虚拟机架构，听得
是云里雾里的～～～
【在 g******i 的大作中提到】
: 说实话你静下心来读几个开源系统的代码就都会了。
: 举个例子，LRU除了楼上几位说的实现，实践中你还得考虑并发，然后展开来如何提高
: parallelism，如何设计封锁协议，最后进一步，可以问你，如果每次都new/malloc一
: 个新的item，然后evict旧的，这个代价是否太大，如何优化，等等。
: 会hash ＋ array只是一个进本要求，都不用你实现代码，以上只是就是口头提问就能
: 摸出你的水平了。多认真复习基础知识吧，切题只是一个敲门砖。
m*p
30 楼
大牛可不可以展开说说，读那些开源系统啊？
【在 g******i 的大作中提到】
: 说实话你静下心来读几个开源系统的代码就都会了。
: 举个例子，LRU除了楼上几位说的实现，实践中你还得考虑并发，然后展开来如何提高
: parallelism，如何设计封锁协议，最后进一步，可以问你，如果每次都new/malloc一
: 个新的item，然后evict旧的，这个代价是否太大，如何优化，等等。
: 会hash ＋ array只是一个进本要求，都不用你实现代码，以上只是就是口头提问就能
: 摸出你的水平了。多认真复习基础知识吧，切题只是一个敲门砖。
【在 g******i 的大作中提到】
: 说实话你静下心来读几个开源系统的代码就都会了。
: 举个例子，LRU除了楼上几位说的实现，实践中你还得考虑并发，然后展开来如何提高
: parallelism，如何设计封锁协议，最后进一步，可以问你，如果每次都new/malloc一
: 个新的item，然后evict旧的，这个代价是否太大，如何优化，等等。
: 会hash ＋ array只是一个进本要求，都不用你实现代码，以上只是就是口头提问就能
: 摸出你的水平了。多认真复习基础知识吧，切题只是一个敲门砖。
m*a
31 楼
被问到这道题 不能用现成的class吗，比如java 里现成的linkedhashmap？
【在 j*****8 的大作中提到】
: 双链表+hashmap
【在 j*****8 的大作中提到】
: 双链表+hashmap
d*l
32 楼
请问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*****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
33 楼
我觉得可以直接用。当然你要知道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
34 楼
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.
https://github.com/android/platform_frameworks_support/blob/master/v4/java/
android/support/v4/util/LruCache.java
Most are pretty basic.
i*n
35 楼
看下Linux kernel
相关阅读
你家孩子有没有拖延症？怎么对待的？急贴！补充宝宝大脑智慧的食物 (转载)对0-6岁的宝宝而言，危害视力的“第一杀手”竟是它？！ Zz中国女排证明推娃没有中间路线请教几个小学数学题。炮灰就炮灰呗，瞎操心别人的孩子干嘛？父母不理解孩子，总是拿自己想法说孩子二年纪英语阅读提高美国14月大女婴补牙麻醉死亡 验尸发现没蛀牙什么是父母（转）婴儿成长中的8个历史性飞跃 Zz哪里能给保姆做乙肝2对半的体检？没有保险乍寒乍暖之下怎样预防宝宝生病 (转载)幼儿园小男孩淘气顽皮怎么解？如何进行孩子的智力开发 (转载)版里有没有主要是娃爸负责管学习推娃的，娃妈基本不管的英国园艺工跑决赛前发现只带了一只钉鞋？ (转载)关于孩子身高增长慢的帖子职场竞争，我们应该从印度人那里学到什么（转载）经济不宽裕的离婚家庭的孩子，是不是上便宜点的大学?