由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 请教一道数据结构的设计题
相关主题
请教一道面试题一个data structure design的问题,求助
Pure Storage面经Given an array of N integers from range [0, N] and one is missing. Find the missing number.
请问pure storage 的那道map 数据结构题what is the internal implementation of Deque
array contains two integer that sum up to 7google 一题
问个题目,找不在区间内的所有数请教一道题目
问个最近面试里的题目一个小公司面经
请教个面经里的设计题一道算法题目
L家的高频题merge k sorted arrays giving iterators求讨论!details 2nd smallest element in an array
相关话题的讨论汇总
话题: integer话题: array话题: clear话题: elements话题: iterate
进入JobHunting版参与讨论
1 (共1页)
x*****0
发帖数: 452
1
下面这道题是在版上看到的一道题。请问大家有什么想法吗?
设计一个Map,满足下面的时间复杂度。
add: O(1) deletion: O(1) lookup: O(1) clear:O(1) iterate: O(number of
elements)。
提示:
如果我们用randomly accessed array,复杂度如下:
add: O(1) deletion: O(1) lookup: O(1) clear: O(size of array) iterate:
O(size of array)
如果我么用sequential array, 复杂度如下:
add: O(1) deletion: O(number of elements) lookup:O(number of elements)
clear: O(1) iterate:O(number of elements)
所以我们需要把这两个方法整合起来。
对于这题的提示,sequential array指的就是link list? 把每一对 >作为一个node不断的加入link list?
randomly accessed array 是说可以直接用中的第一个Integer 作
为index吗?
x*****0
发帖数: 452
2
自己顶一个
l******u
发帖数: 1174
3
不就用一个Array, 每个元素放两个指针,元素的index对应key的hash值。第一个指针
指向一个linked list的头,另一个指针指向这个list的尾;这个list里面的key都有相
同的hash. (尾指针可以省去)。不知这样符合要求吗?
k*****u
发帖数: 136
4
那clear为什么是o(1)?

【在 l******u 的大作中提到】
: 不就用一个Array, 每个元素放两个指针,元素的index对应key的hash值。第一个指针
: 指向一个linked list的头,另一个指针指向这个list的尾;这个list里面的key都有相
: 同的hash. (尾指针可以省去)。不知这样符合要求吗?

z******t
发帖数: 25
5
每个元素添加一个generation value,并维护一个global generation,每次插入一个
元素,给它赋值当前的global generation。每次clear被调用,则global generation
+ 1。访问任何元素的时候,如果发现其generation value不等于global generation,
则说明这个元素是无效的。增加这个机制可以是clear操作也达到O(1)
x*****0
发帖数: 452
6
也就是说,clear的时候,只要global generation + 1 就把所有的元素打成无效了。
谢谢啊!太感激了。

generation

【在 z******t 的大作中提到】
: 每个元素添加一个generation value,并维护一个global generation,每次插入一个
: 元素,给它赋值当前的global generation。每次clear被调用,则global generation
: + 1。访问任何元素的时候,如果发现其generation value不等于global generation,
: 则说明这个元素是无效的。增加这个机制可以是clear操作也达到O(1)

e********c
发帖数: 66
7
也许设计只是个幌子, 真正是看你知不知道LinkedHashMap。
1 (共1页)
进入JobHunting版参与讨论
相关主题
details 2nd smallest element in an array问个题目,找不在区间内的所有数
问一道老题问个最近面试里的题目
一FG家常见题请教个面经里的设计题
partition array problemL家的高频题merge k sorted arrays giving iterators求讨论!
请教一道面试题一个data structure design的问题,求助
Pure Storage面经Given an array of N integers from range [0, N] and one is missing. Find the missing number.
请问pure storage 的那道map 数据结构题what is the internal implementation of Deque
array contains two integer that sum up to 7google 一题
相关话题的讨论汇总
话题: integer话题: array话题: clear话题: elements话题: iterate