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
相关阅读
最近大批天才父母涌进本版找来找去找不到我娃的天才迹象生存伎俩无师自通让人汗颜多娃之间的嫉妒问题扑通娃接地气教育贴pre-K小朋友学认字有专门论坛让GTparents分享教育资源和体会老公独生子，一天打三场牌的婆婆老了以后我要管她吗？(zz)网上找到的喜羊羊面具，适合春节给小朋友手工！请问美赞臣一段的奶粉在哪里买比较好？AMAZON上的可靠吗？给daycare准备了点春节的材料，需要的留电邮小孩美国国籍，请问给小孩办中国签证最快需要多久[继往开来]最喜欢什么？父母签证请大家说说 montesorry school 的优缺点 谢谢求高清中文儿歌视频下载链接。儿子和第一任女友拜了。会弹钢琴的家长帮看看如何引导孩子面对竞技比赛中的竞争？双胞胎过生日送一个礼物够吗？