由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 请教个面经里的设计题
相关主题
hash_map 的遍历问题Bloomberg 电面
问个最近面试里的题目谁有那个 nested hashmap iteration 的讨论阿?
请教一道面试题谁来解释下hashtable的iterator是怎么实现的
请教一道数据结构的设计题dropbox一道题
解法讨论:(给定一个array和一个target,找出是否存在两个数之和为target)Scala怎么通过index访问set或者array
L家的高频题merge k sorted arrays giving iterators求讨论!一道纠结的题,狗家的。
reverse an array新鲜Amazon面经(附参考答案) 顺便求各种大公司refer
请教 Iterator 一题面经(L)
相关话题的讨论汇总
话题: array话题: map话题: clear话题: hashmap话题: boolean
进入JobHunting版参与讨论
1 (共1页)
j**********3
发帖数: 3211
1
设计个map data structure,实现add, delete, clear 都是o(1), iteration o(n)
其他的都还好,这个clear操作怎么能做到O(1) 呢?
来自版上的面经。请教了很多朋友,没找到合适的solution。
l*********8
发帖数: 4642
2
刚想了一下。 可以用个valid start time. 每个map entry也保存一个time stamp.
只有time stamp 比valid start time新的时候,才认为 entry valid.

n)

【在 j**********3 的大作中提到】
: 设计个map data structure,实现add, delete, clear 都是o(1), iteration o(n)
: 其他的都还好,这个clear操作怎么能做到O(1) 呢?
: 来自版上的面经。请教了很多朋友,没找到合适的solution。

l*********8
发帖数: 4642
3
请问iteration o(n)是怎么做到的?

n)

【在 j**********3 的大作中提到】
: 设计个map data structure,实现add, delete, clear 都是o(1), iteration o(n)
: 其他的都还好,这个clear操作怎么能做到O(1) 呢?
: 来自版上的面经。请教了很多朋友,没找到合适的solution。

j**********3
发帖数: 3211
4
这样,是不是直接设一个boolean值更直接?
感觉不是在这个上边做文章,隐隐约约觉得应该用其他data structure,比如array或
者list什么的实现。。。
但。。。完全没思路啊。。。

.

【在 l*********8 的大作中提到】
: 刚想了一下。 可以用个valid start time. 每个map entry也保存一个time stamp.
: 只有time stamp 比valid start time新的时候,才认为 entry valid.
:
: n)

j**********3
发帖数: 3211
5
我。。。以为。。。hashmap本身得就是o(n)呢?

【在 l*********8 的大作中提到】
: 请问iteration o(n)是怎么做到的?
:
: n)

r****s
发帖数: 1025
6
你把map底层的datastructure(array)直接set null扔掉,重新做一个新array,不就是
O(1)?

n)

【在 j**********3 的大作中提到】
: 设计个map data structure,实现add, delete, clear 都是o(1), iteration o(n)
: 其他的都还好,这个clear操作怎么能做到O(1) 呢?
: 来自版上的面经。请教了很多朋友,没找到合适的solution。

j**********3
发帖数: 3211
7
我有想过这个。但感觉不对吧?

【在 r****s 的大作中提到】
: 你把map底层的datastructure(array)直接set null扔掉,重新做一个新array,不就是
: O(1)?
:
: n)

e***l
发帖数: 710
8
一个boolean就行了

【在 j**********3 的大作中提到】
: 我有想过这个。但感觉不对吧?
d****n
发帖数: 12461
9
和一个空的map swap就可以了,被swap的交给gc,所以cost就不算在这个map上面了。

n)

【在 j**********3 的大作中提到】
: 设计个map data structure,实现add, delete, clear 都是o(1), iteration o(n)
: 其他的都还好,这个clear操作怎么能做到O(1) 呢?
: 来自版上的面经。请教了很多朋友,没找到合适的solution。

j**********3
发帖数: 3211
10
我就是这么想的,但后来想想,好像连boolean都不需要了。。。
直接new一个就可以了。。。
但感觉不对吧??

【在 e***l 的大作中提到】
: 一个boolean就行了
相关主题
L家的高频题merge k sorted arrays giving iterators求讨论!Bloomberg 电面
reverse an array谁有那个 nested hashmap iteration 的讨论阿?
请教 Iterator 一题谁来解释下hashtable的iterator是怎么实现的
进入JobHunting版参与讨论
j**********3
发帖数: 3211
11
和new一个新的比,怎么样?

【在 d****n 的大作中提到】
: 和一个空的map swap就可以了,被swap的交给gc,所以cost就不算在这个map上面了。
:
: n)

u*****n
发帖数: 126
12
上面思路都错了。
提示:把clear和lookup放在一起看。不是每个pointer都是valid的,怎么判断?
j**********3
发帖数: 3211
13
其实,我也觉得整个思路走偏了,所以请大牛您来看看。。。
看了提示,还是不知道呀。。。。
求继续指教。。。

【在 u*****n 的大作中提到】
: 上面思路都错了。
: 提示:把clear和lookup放在一起看。不是每个pointer都是valid的,怎么判断?

u*****n
发帖数: 126
14
你不需要erase整个map里所有的内容,也就是说你既不用删除旧的元素,也不必建立新
的空间。你只需要在lookup的时候知道它们是不是valid的就可以了。怎么判断是不是
valid 的呢?
l*********8
发帖数: 4642
15
我之前思路说用time stamp, 也错了吗?

【在 u*****n 的大作中提到】
: 你不需要erase整个map里所有的内容,也就是说你既不用删除旧的元素,也不必建立新
: 的空间。你只需要在lookup的时候知道它们是不是valid的就可以了。怎么判断是不是
: valid 的呢?

z*******3
发帖数: 13709
16
clean操作你定义一个额外的变量isclean
每次都先check这个变量
然后读写的时候要记得放timestamp
isclean一样要放timestamp
对比两个timestamp先后来决定用哪个
就是上一次clean的timestamp之前的所有数据都不可用
都应该返回空
不过这题有个取巧的方法
你每次clean都new一个全新的数据结构,java有gc,丢掉的东西怎么clean
那是gc的事,跟你操作无关

n)

【在 j**********3 的大作中提到】
: 设计个map data structure,实现add, delete, clear 都是o(1), iteration o(n)
: 其他的都还好,这个clear操作怎么能做到O(1) 呢?
: 来自版上的面经。请教了很多朋友,没找到合适的solution。

l*********8
发帖数: 4642
17
请问zhaoce大牛, map内部是如何实现iteration O(n)的? hash table + linked
list?

【在 z*******3 的大作中提到】
: clean操作你定义一个额外的变量isclean
: 每次都先check这个变量
: 然后读写的时候要记得放timestamp
: isclean一样要放timestamp
: 对比两个timestamp先后来决定用哪个
: 就是上一次clean的timestamp之前的所有数据都不可用
: 都应该返回空
: 不过这题有个取巧的方法
: 你每次clean都new一个全新的数据结构,java有gc,丢掉的东西怎么clean
: 那是gc的事,跟你操作无关

z*******3
发帖数: 13709
18
不牛,上面有牛,那头牛已经说了
map底层是array和list
array就可以实现o(n)的iteration了

linked

【在 l*********8 的大作中提到】
: 请问zhaoce大牛, map内部是如何实现iteration O(n)的? hash table + linked
: list?

u*****n
发帖数: 126
19
抱歉没仔细看你的解法。很好的思路。
原题的解法类似,只不过题目本身比较特殊,完整的题目如下。因为是整数,你可以假
设有很大的内存,同时不必考虑collision。
设计一个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)
所以我们需要把这两个方法整合起来。

【在 l*********8 的大作中提到】
: 我之前思路说用time stamp, 也错了吗?
j**********3
发帖数: 3211
20
就是说,设一个boolean值,然后clear了,这个map就不valid了?然后再查它,就不
valid了,那clear了之后,再想往里边塞东西怎么办呢?

【在 u*****n 的大作中提到】
: 你不需要erase整个map里所有的内容,也就是说你既不用删除旧的元素,也不必建立新
: 的空间。你只需要在lookup的时候知道它们是不是valid的就可以了。怎么判断是不是
: valid 的呢?

相关主题
dropbox一道题新鲜Amazon面经(附参考答案) 顺便求各种大公司refer
Scala怎么通过index访问set或者array面经(L)
一道纠结的题,狗家的。问道G 的题
进入JobHunting版参与讨论
S******1
发帖数: 216
21
3个数组来做,
一个a是普通的bucket, 元素存储array b 的index
一个array b, 递增存储值, 删除就swap然后更新a的index值, 有一个len维护这个数
组b的有效长度,a的index如果小于len就当作无效。
clear的时候set len = 0;
一个back ward validation array c. 如果a有两个bucket都是index 3, 这个数组做
validation.
或者两个数组,但是数组b是
class Rec {
int val;
int a'sIndex;
}
u*****n
发帖数: 126
22
A binary state is insufficient

【在 j**********3 的大作中提到】
: 就是说,设一个boolean值,然后clear了,这个map就不valid了?然后再查它,就不
: valid了,那clear了之后,再想往里边塞东西怎么办呢?

j**********3
发帖数: 3211
23
先说第一个方法,每一次add的时候,都加timestamp?那岂不是add的操作要增加很多
东西咯。然后存储空间也变大了?

【在 z*******3 的大作中提到】
: clean操作你定义一个额外的变量isclean
: 每次都先check这个变量
: 然后读写的时候要记得放timestamp
: isclean一样要放timestamp
: 对比两个timestamp先后来决定用哪个
: 就是上一次clean的timestamp之前的所有数据都不可用
: 都应该返回空
: 不过这题有个取巧的方法
: 你每次clean都new一个全新的数据结构,java有gc,丢掉的东西怎么clean
: 那是gc的事,跟你操作无关

j**********3
发帖数: 3211
24
所以,还是不能直接用hashmap,需要用array 和 list?

【在 z*******3 的大作中提到】
: 不牛,上面有牛,那头牛已经说了
: map底层是array和list
: array就可以实现o(n)的iteration了
:
: linked

u*****n
发帖数: 126
25
Emm, you need one variable, but not a Boolean.

【在 j**********3 的大作中提到】
: 先说第一个方法,每一次add的时候,都加timestamp?那岂不是add的操作要增加很多
: 东西咯。然后存储空间也变大了?

z*******3
发帖数: 13709
26
不增加复杂度

【在 j**********3 的大作中提到】
: 先说第一个方法,每一次add的时候,都加timestamp?那岂不是add的操作要增加很多
: 东西咯。然后存储空间也变大了?

z*******3
发帖数: 13709
27
hashmap本身就是map,用map实现什么map?

【在 j**********3 的大作中提到】
: 所以,还是不能直接用hashmap,需要用array 和 list?
l*********8
发帖数: 4642
28
谢谢zhaoce和unichen!

【在 u*****n 的大作中提到】
: 抱歉没仔细看你的解法。很好的思路。
: 原题的解法类似,只不过题目本身比较特殊,完整的题目如下。因为是整数,你可以假
: 设有很大的内存,同时不必考虑collision。
: 设计一个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)

j**********3
发帖数: 3211
29
哦哦。。。感觉有点混淆上边各种方法了。。我回头查一下。。

【在 u*****n 的大作中提到】
: Emm, you need one variable, but not a Boolean.
j**********3
发帖数: 3211
30
你看懂了?来解释解释呗?

【在 l*********8 的大作中提到】
: 谢谢zhaoce和unichen!
相关主题
也贴个转罗马数字的code问个最近面试里的题目
一个算法和设计的题目请教一道面试题
hash_map 的遍历问题请教一道数据结构的设计题
进入JobHunting版参与讨论
j**********3
发帖数: 3211
31
因为hashmap本身很多要求都可以实现了,只是clear o(1)不行啊。。。

【在 z*******3 的大作中提到】
: hashmap本身就是map,用map实现什么map?
f*********5
发帖数: 576
32
map=null;
or
map=new HashMap<,>();
不可以吗?

【在 j**********3 的大作中提到】
: 因为hashmap本身很多要求都可以实现了,只是clear o(1)不行啊。。。
j**********3
发帖数: 3211
33
上边问了。。。
ls各位大牛给解释了。。。。
虽然。。。俺也没弄明白。。。
请明白人解释一下

【在 f*********5 的大作中提到】
: map=null;
: or
: map=new HashMap<,>();
: 不可以吗?

f*********5
发帖数: 576
34
哪解释了
zhaoce牛也是这么答的阿
看不出来有什么问题

【在 j**********3 的大作中提到】
: 上边问了。。。
: ls各位大牛给解释了。。。。
: 虽然。。。俺也没弄明白。。。
: 请明白人解释一下

j**********3
发帖数: 3211
35
我就是说没看明白,能说说么。。。

【在 f*********5 的大作中提到】
: 哪解释了
: zhaoce牛也是这么答的阿
: 看不出来有什么问题

p*****2
发帖数: 21240
36
new一下时间复杂度多少?
new一下的cost不小吧?
p*****2
发帖数: 21240
37

加timestamp能保证O(1)吗?

【在 l*********8 的大作中提到】
: 我之前思路说用time stamp, 也错了吗?
p*****2
发帖数: 21240
38

什么是randomly accessed array, 什么是sequential array?

【在 u*****n 的大作中提到】
: 抱歉没仔细看你的解法。很好的思路。
: 原题的解法类似,只不过题目本身比较特殊,完整的题目如下。因为是整数,你可以假
: 设有很大的内存,同时不必考虑collision。
: 设计一个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)

j**********3
发帖数: 3211
39
我这不是也没看懂,才问的么。。。
上边讨论的解法,您看懂了么?看懂了给俺解释一下?

【在 p*****2 的大作中提到】
:
: 什么是randomly accessed array, 什么是sequential array?

p*****2
发帖数: 21240
40

longway的解法比较靠谱,注意一下reuse。

【在 j**********3 的大作中提到】
: 我这不是也没看懂,才问的么。。。
: 上边讨论的解法,您看懂了么?看懂了给俺解释一下?

相关主题
请教一道数据结构的设计题reverse an array
解法讨论:(给定一个array和一个target,找出是否存在两个数之和为target)请教 Iterator 一题
L家的高频题merge k sorted arrays giving iterators求讨论!Bloomberg 电面
进入JobHunting版参与讨论
f********x
发帖数: 2086
41

.
意思就是clear()O(1)其实就是把valid start time设置成现在时间,则map内所有元
素都invalid了?

【在 l*********8 的大作中提到】
: 刚想了一下。 可以用个valid start time. 每个map entry也保存一个time stamp.
: 只有time stamp 比valid start time新的时候,才认为 entry valid.
:
: n)

f********x
发帖数: 2086
42

这个方法,a数组里的数组怎么delete?时间长了全是无效指针了?

【在 S******1 的大作中提到】
: 3个数组来做,
: 一个a是普通的bucket, 元素存储array b 的index
: 一个array b, 递增存储值, 删除就swap然后更新a的index值, 有一个len维护这个数
: 组b的有效长度,a的index如果小于len就当作无效。
: clear的时候set len = 0;
: 一个back ward validation array c. 如果a有两个bucket都是index 3, 这个数组做
: validation.
: 或者两个数组,但是数组b是
: class Rec {
: int val;

p*****3
发帖数: 488
43

不需要delete, 小于counter的不算,还有validation array

【在 f********x 的大作中提到】
:
: 这个方法,a数组里的数组怎么delete?时间长了全是无效指针了?

s********k
发帖数: 2352
44
直接用实现hashmap的算法, 稍微改动一下就好了吧?

【在 j**********3 的大作中提到】
: 因为hashmap本身很多要求都可以实现了,只是clear o(1)不行啊。。。
d****n
发帖数: 233
45
use two hashmap and a globle version number.
one map store the real data, another one store the corresponding version

n)

【在 j**********3 的大作中提到】
: 设计个map data structure,实现add, delete, clear 都是o(1), iteration o(n)
: 其他的都还好,这个clear操作怎么能做到O(1) 呢?
: 来自版上的面经。请教了很多朋友,没找到合适的solution。

j**********3
发帖数: 3211
46
设计个map data structure,实现add, delete, clear 都是o(1), iteration o(n)
其他的都还好,这个clear操作怎么能做到O(1) 呢?
来自版上的面经。请教了很多朋友,没找到合适的solution。
l*********8
发帖数: 4642
47
刚想了一下。 可以用个valid start time. 每个map entry也保存一个time stamp.
只有time stamp 比valid start time新的时候,才认为 entry valid.

n)

【在 j**********3 的大作中提到】
: 设计个map data structure,实现add, delete, clear 都是o(1), iteration o(n)
: 其他的都还好,这个clear操作怎么能做到O(1) 呢?
: 来自版上的面经。请教了很多朋友,没找到合适的solution。

l*********8
发帖数: 4642
48
请问iteration o(n)是怎么做到的?

n)

【在 j**********3 的大作中提到】
: 设计个map data structure,实现add, delete, clear 都是o(1), iteration o(n)
: 其他的都还好,这个clear操作怎么能做到O(1) 呢?
: 来自版上的面经。请教了很多朋友,没找到合适的solution。

j**********3
发帖数: 3211
49
这样,是不是直接设一个boolean值更直接?
感觉不是在这个上边做文章,隐隐约约觉得应该用其他data structure,比如array或
者list什么的实现。。。
但。。。完全没思路啊。。。

.

【在 l*********8 的大作中提到】
: 刚想了一下。 可以用个valid start time. 每个map entry也保存一个time stamp.
: 只有time stamp 比valid start time新的时候,才认为 entry valid.
:
: n)

j**********3
发帖数: 3211
50
我。。。以为。。。hashmap本身得就是o(n)呢?

【在 l*********8 的大作中提到】
: 请问iteration o(n)是怎么做到的?
:
: n)

相关主题
谁有那个 nested hashmap iteration 的讨论阿?Scala怎么通过index访问set或者array
谁来解释下hashtable的iterator是怎么实现的一道纠结的题,狗家的。
dropbox一道题新鲜Amazon面经(附参考答案) 顺便求各种大公司refer
进入JobHunting版参与讨论
r****s
发帖数: 1025
51
你把map底层的datastructure(array)直接set null扔掉,重新做一个新array,不就是
O(1)?

n)

【在 j**********3 的大作中提到】
: 设计个map data structure,实现add, delete, clear 都是o(1), iteration o(n)
: 其他的都还好,这个clear操作怎么能做到O(1) 呢?
: 来自版上的面经。请教了很多朋友,没找到合适的solution。

j**********3
发帖数: 3211
52
我有想过这个。但感觉不对吧?

【在 r****s 的大作中提到】
: 你把map底层的datastructure(array)直接set null扔掉,重新做一个新array,不就是
: O(1)?
:
: n)

e***l
发帖数: 710
53
一个boolean就行了

【在 j**********3 的大作中提到】
: 我有想过这个。但感觉不对吧?
d****n
发帖数: 12461
54
和一个空的map swap就可以了,被swap的交给gc,所以cost就不算在这个map上面了。

n)

【在 j**********3 的大作中提到】
: 设计个map data structure,实现add, delete, clear 都是o(1), iteration o(n)
: 其他的都还好,这个clear操作怎么能做到O(1) 呢?
: 来自版上的面经。请教了很多朋友,没找到合适的solution。

j**********3
发帖数: 3211
55
我就是这么想的,但后来想想,好像连boolean都不需要了。。。
直接new一个就可以了。。。
但感觉不对吧??

【在 e***l 的大作中提到】
: 一个boolean就行了
j**********3
发帖数: 3211
56
和new一个新的比,怎么样?

【在 d****n 的大作中提到】
: 和一个空的map swap就可以了,被swap的交给gc,所以cost就不算在这个map上面了。
:
: n)

u*****n
发帖数: 126
57
上面思路都错了。
提示:把clear和lookup放在一起看。不是每个pointer都是valid的,怎么判断?
j**********3
发帖数: 3211
58
其实,我也觉得整个思路走偏了,所以请大牛您来看看。。。
看了提示,还是不知道呀。。。。
求继续指教。。。

【在 u*****n 的大作中提到】
: 上面思路都错了。
: 提示:把clear和lookup放在一起看。不是每个pointer都是valid的,怎么判断?

u*****n
发帖数: 126
59
你不需要erase整个map里所有的内容,也就是说你既不用删除旧的元素,也不必建立新
的空间。你只需要在lookup的时候知道它们是不是valid的就可以了。怎么判断是不是
valid 的呢?
l*********8
发帖数: 4642
60
我之前思路说用time stamp, 也错了吗?

【在 u*****n 的大作中提到】
: 你不需要erase整个map里所有的内容,也就是说你既不用删除旧的元素,也不必建立新
: 的空间。你只需要在lookup的时候知道它们是不是valid的就可以了。怎么判断是不是
: valid 的呢?

相关主题
面经(L)一个算法和设计的题目
问道G 的题hash_map 的遍历问题
也贴个转罗马数字的code问个最近面试里的题目
进入JobHunting版参与讨论
z*******3
发帖数: 13709
61
clean操作你定义一个额外的变量isclean
每次都先check这个变量
然后读写的时候要记得放timestamp
isclean一样要放timestamp
对比两个timestamp先后来决定用哪个
就是上一次clean的timestamp之前的所有数据都不可用
都应该返回空
不过这题有个取巧的方法
你每次clean都new一个全新的数据结构,java有gc,丢掉的东西怎么clean
那是gc的事,跟你操作无关

n)

【在 j**********3 的大作中提到】
: 设计个map data structure,实现add, delete, clear 都是o(1), iteration o(n)
: 其他的都还好,这个clear操作怎么能做到O(1) 呢?
: 来自版上的面经。请教了很多朋友,没找到合适的solution。

l*********8
发帖数: 4642
62
请问zhaoce大牛, map内部是如何实现iteration O(n)的? hash table + linked
list?

【在 z*******3 的大作中提到】
: clean操作你定义一个额外的变量isclean
: 每次都先check这个变量
: 然后读写的时候要记得放timestamp
: isclean一样要放timestamp
: 对比两个timestamp先后来决定用哪个
: 就是上一次clean的timestamp之前的所有数据都不可用
: 都应该返回空
: 不过这题有个取巧的方法
: 你每次clean都new一个全新的数据结构,java有gc,丢掉的东西怎么clean
: 那是gc的事,跟你操作无关

z*******3
发帖数: 13709
63
不牛,上面有牛,那头牛已经说了
map底层是array和list
array就可以实现o(n)的iteration了

linked

【在 l*********8 的大作中提到】
: 请问zhaoce大牛, map内部是如何实现iteration O(n)的? hash table + linked
: list?

u*****n
发帖数: 126
64
抱歉没仔细看你的解法。很好的思路。
原题的解法类似,只不过题目本身比较特殊,完整的题目如下。因为是整数,你可以假
设有很大的内存,同时不必考虑collision。
设计一个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)
所以我们需要把这两个方法整合起来。

【在 l*********8 的大作中提到】
: 我之前思路说用time stamp, 也错了吗?
j**********3
发帖数: 3211
65
就是说,设一个boolean值,然后clear了,这个map就不valid了?然后再查它,就不
valid了,那clear了之后,再想往里边塞东西怎么办呢?

【在 u*****n 的大作中提到】
: 你不需要erase整个map里所有的内容,也就是说你既不用删除旧的元素,也不必建立新
: 的空间。你只需要在lookup的时候知道它们是不是valid的就可以了。怎么判断是不是
: valid 的呢?

S******1
发帖数: 216
66
3个数组来做,
一个a是普通的bucket, 元素存储array b 的index
一个array b, 递增存储值, 删除就swap然后更新a的index值, 有一个len维护这个数
组b的有效长度,a的index如果小于len就当作无效。
clear的时候set len = 0;
一个back ward validation array c. 如果a有两个bucket都是index 3, 这个数组做
validation.
或者两个数组,但是数组b是
class Rec {
int val;
int a'sIndex;
}
u*****n
发帖数: 126
67
A binary state is insufficient

【在 j**********3 的大作中提到】
: 就是说,设一个boolean值,然后clear了,这个map就不valid了?然后再查它,就不
: valid了,那clear了之后,再想往里边塞东西怎么办呢?

j**********3
发帖数: 3211
68
先说第一个方法,每一次add的时候,都加timestamp?那岂不是add的操作要增加很多
东西咯。然后存储空间也变大了?

【在 z*******3 的大作中提到】
: clean操作你定义一个额外的变量isclean
: 每次都先check这个变量
: 然后读写的时候要记得放timestamp
: isclean一样要放timestamp
: 对比两个timestamp先后来决定用哪个
: 就是上一次clean的timestamp之前的所有数据都不可用
: 都应该返回空
: 不过这题有个取巧的方法
: 你每次clean都new一个全新的数据结构,java有gc,丢掉的东西怎么clean
: 那是gc的事,跟你操作无关

j**********3
发帖数: 3211
69
所以,还是不能直接用hashmap,需要用array 和 list?

【在 z*******3 的大作中提到】
: 不牛,上面有牛,那头牛已经说了
: map底层是array和list
: array就可以实现o(n)的iteration了
:
: linked

u*****n
发帖数: 126
70
Emm, you need one variable, but not a Boolean.

【在 j**********3 的大作中提到】
: 先说第一个方法,每一次add的时候,都加timestamp?那岂不是add的操作要增加很多
: 东西咯。然后存储空间也变大了?

相关主题
问个最近面试里的题目解法讨论:(给定一个array和一个target,找出是否存在两个数之和为target)
请教一道面试题L家的高频题merge k sorted arrays giving iterators求讨论!
请教一道数据结构的设计题reverse an array
进入JobHunting版参与讨论
z*******3
发帖数: 13709
71
不增加复杂度

【在 j**********3 的大作中提到】
: 先说第一个方法,每一次add的时候,都加timestamp?那岂不是add的操作要增加很多
: 东西咯。然后存储空间也变大了?

z*******3
发帖数: 13709
72
hashmap本身就是map,用map实现什么map?

【在 j**********3 的大作中提到】
: 所以,还是不能直接用hashmap,需要用array 和 list?
l*********8
发帖数: 4642
73
谢谢zhaoce和unichen!

【在 u*****n 的大作中提到】
: 抱歉没仔细看你的解法。很好的思路。
: 原题的解法类似,只不过题目本身比较特殊,完整的题目如下。因为是整数,你可以假
: 设有很大的内存,同时不必考虑collision。
: 设计一个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)

j**********3
发帖数: 3211
74
哦哦。。。感觉有点混淆上边各种方法了。。我回头查一下。。

【在 u*****n 的大作中提到】
: Emm, you need one variable, but not a Boolean.
j**********3
发帖数: 3211
75
你看懂了?来解释解释呗?

【在 l*********8 的大作中提到】
: 谢谢zhaoce和unichen!
j**********3
发帖数: 3211
76
因为hashmap本身很多要求都可以实现了,只是clear o(1)不行啊。。。

【在 z*******3 的大作中提到】
: hashmap本身就是map,用map实现什么map?
f*********5
发帖数: 576
77
map=null;
or
map=new HashMap<,>();
不可以吗?

【在 j**********3 的大作中提到】
: 因为hashmap本身很多要求都可以实现了,只是clear o(1)不行啊。。。
j**********3
发帖数: 3211
78
上边问了。。。
ls各位大牛给解释了。。。。
虽然。。。俺也没弄明白。。。
请明白人解释一下

【在 f*********5 的大作中提到】
: map=null;
: or
: map=new HashMap<,>();
: 不可以吗?

f*********5
发帖数: 576
79
哪解释了
zhaoce牛也是这么答的阿
看不出来有什么问题

【在 j**********3 的大作中提到】
: 上边问了。。。
: ls各位大牛给解释了。。。。
: 虽然。。。俺也没弄明白。。。
: 请明白人解释一下

j**********3
发帖数: 3211
80
我就是说没看明白,能说说么。。。

【在 f*********5 的大作中提到】
: 哪解释了
: zhaoce牛也是这么答的阿
: 看不出来有什么问题

相关主题
请教 Iterator 一题谁来解释下hashtable的iterator是怎么实现的
Bloomberg 电面dropbox一道题
谁有那个 nested hashmap iteration 的讨论阿?Scala怎么通过index访问set或者array
进入JobHunting版参与讨论
p*****2
发帖数: 21240
81
new一下时间复杂度多少?
new一下的cost不小吧?
p*****2
发帖数: 21240
82

加timestamp能保证O(1)吗?

【在 l*********8 的大作中提到】
: 我之前思路说用time stamp, 也错了吗?
p*****2
发帖数: 21240
83

什么是randomly accessed array, 什么是sequential array?

【在 u*****n 的大作中提到】
: 抱歉没仔细看你的解法。很好的思路。
: 原题的解法类似,只不过题目本身比较特殊,完整的题目如下。因为是整数,你可以假
: 设有很大的内存,同时不必考虑collision。
: 设计一个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)

j**********3
发帖数: 3211
84
我这不是也没看懂,才问的么。。。
上边讨论的解法,您看懂了么?看懂了给俺解释一下?

【在 p*****2 的大作中提到】
:
: 什么是randomly accessed array, 什么是sequential array?

p*****2
发帖数: 21240
85

longway的解法比较靠谱,注意一下reuse。

【在 j**********3 的大作中提到】
: 我这不是也没看懂,才问的么。。。
: 上边讨论的解法,您看懂了么?看懂了给俺解释一下?

f********x
发帖数: 2086
86

.
意思就是clear()O(1)其实就是把valid start time设置成现在时间,则map内所有元
素都invalid了?

【在 l*********8 的大作中提到】
: 刚想了一下。 可以用个valid start time. 每个map entry也保存一个time stamp.
: 只有time stamp 比valid start time新的时候,才认为 entry valid.
:
: n)

f********x
发帖数: 2086
87

这个方法,a数组里的数组怎么delete?时间长了全是无效指针了?

【在 S******1 的大作中提到】
: 3个数组来做,
: 一个a是普通的bucket, 元素存储array b 的index
: 一个array b, 递增存储值, 删除就swap然后更新a的index值, 有一个len维护这个数
: 组b的有效长度,a的index如果小于len就当作无效。
: clear的时候set len = 0;
: 一个back ward validation array c. 如果a有两个bucket都是index 3, 这个数组做
: validation.
: 或者两个数组,但是数组b是
: class Rec {
: int val;

p*****3
发帖数: 488
88

不需要delete, 小于counter的不算,还有validation array

【在 f********x 的大作中提到】
:
: 这个方法,a数组里的数组怎么delete?时间长了全是无效指针了?

s********k
发帖数: 2352
89
直接用实现hashmap的算法, 稍微改动一下就好了吧?

【在 j**********3 的大作中提到】
: 因为hashmap本身很多要求都可以实现了,只是clear o(1)不行啊。。。
d****n
发帖数: 233
90
use two hashmap and a globle version number.
one map store the real data, another one store the corresponding version

n)

【在 j**********3 的大作中提到】
: 设计个map data structure,实现add, delete, clear 都是o(1), iteration o(n)
: 其他的都还好,这个clear操作怎么能做到O(1) 呢?
: 来自版上的面经。请教了很多朋友,没找到合适的solution。

相关主题
一道纠结的题,狗家的。问道G 的题
新鲜Amazon面经(附参考答案) 顺便求各种大公司refer也贴个转罗马数字的code
面经(L)一个算法和设计的题目
进入JobHunting版参与讨论
y**********a
发帖数: 824
91
为什么不直接用 hashmap 的设计?
j**********3
发帖数: 3211
92
这帖子竟然还在
y**********a
发帖数: 824
93
为什么不直接用 hashmap 的设计?
j**********3
发帖数: 3211
94
这帖子竟然还在
u******n
发帖数: 2
95


【在 S******1 的大作中提到】
: 3个数组来做,
: 一个a是普通的bucket, 元素存储array b 的index
: 一个array b, 递增存储值, 删除就swap然后更新a的index值, 有一个len维护这个数
: 组b的有效长度,a的index如果小于len就当作无效。
: clear的时候set len = 0;
: 一个back ward validation array c. 如果a有两个bucket都是index 3, 这个数组做
: validation.
: 或者两个数组,但是数组b是
: class Rec {
: int val;

u******n
发帖数: 2
96
请问这个 a bucket 是怎么实现的呢?它是一个数组吗?怎样将key和a联系在一起呢?
如果key与a的index联系,那么是不是内存不够呢?

【在 S******1 的大作中提到】
: 3个数组来做,
: 一个a是普通的bucket, 元素存储array b 的index
: 一个array b, 递增存储值, 删除就swap然后更新a的index值, 有一个len维护这个数
: 组b的有效长度,a的index如果小于len就当作无效。
: clear的时候set len = 0;
: 一个back ward validation array c. 如果a有两个bucket都是index 3, 这个数组做
: validation.
: 或者两个数组,但是数组b是
: class Rec {
: int val;

1 (共1页)
进入JobHunting版参与讨论
相关主题
面经(L)解法讨论:(给定一个array和一个target,找出是否存在两个数之和为target)
问道G 的题L家的高频题merge k sorted arrays giving iterators求讨论!
也贴个转罗马数字的codereverse an array
一个算法和设计的题目请教 Iterator 一题
hash_map 的遍历问题Bloomberg 电面
问个最近面试里的题目谁有那个 nested hashmap iteration 的讨论阿?
请教一道面试题谁来解释下hashtable的iterator是怎么实现的
请教一道数据结构的设计题dropbox一道题
相关话题的讨论汇总
话题: array话题: map话题: clear话题: hashmap话题: boolean