logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
问一个狗狗的OnSite题
avatar
问一个狗狗的OnSite题# JobHunting - 待字闺中
w*x
1 楼
设计一个集合数据结构(set,只存unique的value)要求
能在O(1)时间内insert，delete，random query(比如目前set中有n个元素，给一个介
于1到n的随机数k，可以在O(1)时间内返回第k个value)
比如：+表示插入，-表示删除
+1+1+3+3+5-3-1+8+1+4
最后的set是{5814}
k=2，返回8
avatar
f*e
2 楼
不知道下面这个对不对？
CLRS 3rd
11.2-4

【在 w****x 的大作中提到】
: 设计一个集合数据结构(set,只存unique的value)要求
: 能在O(1)时间内insert，delete，random query(比如目前set中有n个元素，给一个介
: 于1到n的随机数k，可以在O(1)时间内返回第k个value)
: 比如：+表示插入，-表示删除
: +1+1+3+3+5-3-1+8+1+4
: 最后的set是{5814}
: k=2，返回8
avatar
w*x
3 楼

没见

【在 f*****e 的大作中提到】
: 不知道下面这个对不对？
: CLRS 3rd
: 11.2-4
avatar
f*e
4 楼
习题11.2-4啊。

【在 w****x 的大作中提到】
:
: 没见
avatar
a*y
5 楼
这个难道用个hashtable 和一个array不就行了吗？
hashtable 存(value, index in array)
avatar
w*x
6 楼

没说要random access啊

【在 f*****e 的大作中提到】
: 习题11.2-4啊。
avatar
w*x
7 楼

不行啊， 删除一个所有后面的index都要减小一个

【在 a*******y 的大作中提到】
: 这个难道用个hashtable 和一个array不就行了吗？
: hashtable 存(value, index in array)
avatar
a*y
8 楼
No 啊，
after delete，你move the last element into this empty shit pot, and change
the index for the last element.

【在 w****x 的大作中提到】
:
: 不行啊， 删除一个所有后面的index都要减小一个
avatar
w*x
9 楼

那你random access就不对了

【在 a*******y 的大作中提到】
: No 啊，
: after delete，你move the last element into this empty shit pot, and change
: the index for the last element.
avatar
a*o
10 楼
你这个例子他是对的，但是比如A[]= 1,2,3,4,5
delete （2） 然后get(A[1])还要返回3就不行了，只能返回5，不过本来就是random，
返回3，返回5意义不大

【在 w****x 的大作中提到】
:
: 那你random access就不对了
avatar
t*7
11 楼
HashMap + Array吧,想法跟楼上那个哥们差不多,
不同就是记录一下delCount,楼主你那个例子删除了2个元素,那最后要找K=2,就等于2+2
=4第四个放进数组的元素也就是8...这样一直用ARRAY记录,等ARRAY快满的时候就重置
ARRAY,并且delCount=0,假如空间还不够就COPY ARRAY去一个更大的ARRAY空间...不知
道这样行不行...
avatar
w*x
12 楼

+2
这样不对啊， 要是+0+1+1+3+4-1 ==> 034 现在取第一个应该还是0, 你的逻辑就是3了

【在 t*********7 的大作中提到】
: HashMap + Array吧,想法跟楼上那个哥们差不多,
: 不同就是记录一下delCount,楼主你那个例子删除了2个元素,那最后要找K=2,就等于2+2
: =4第四个放进数组的元素也就是8...这样一直用ARRAY记录,等ARRAY快满的时候就重置
: ARRAY,并且delCount=0,假如空间还不够就COPY ARRAY去一个更大的ARRAY空间...不知
: 道这样行不行...
avatar
f*e
13 楼
我觉得random access应为getRandomElement，你题目看错了，或者理解错了。

【在 w****x 的大作中提到】
:
: +2
: 这样不对啊， 要是+0+1+1+3+4-1 ==> 034 现在取第一个应该还是0, 你的逻辑就是3了
avatar
w*x
14 楼

哦， 可能是这样， 这样就简单了....

【在 f*****e 的大作中提到】
: 我觉得random access应为getRandomElement，你题目看错了，或者理解错了。
avatar
h*3
15 楼
唉，我有次电话面试就是这题。
能不能这样：
一个array + hash+queque，queque里面放avaiable index，如果删除以后，index 可
以回收到queque里面。通过hash可以random access了。
avatar
z*e
16 楼
How about this:
Use one global counter and two HashMap
counter will be increased by 1 when insert one value.
HashMap to save value and it's counter as index.
Another HashMap to save the index and its value.
When delete, both the value-index pair and index-value pair removed from the
hashmap.
when random access with one index, check whether the value is existed in the
second hashmap as key, if not, increase the index by 1 and continue to find
it in the hashmap, until the index == counter, which means no value found
and return null.
insert and delete with O(1) time, cannot prove random access with O(1) time.
相关阅读
国内的IT DIRECTOR年薪就50万人民币Amazon offer求建议今年弯曲小黑屋的主人们可能要含泪贱卖了 (转载)DNN就是hype现在去pre-ipo的Saas还有意义吗？急问：开101进城要收费么？880要收费么？Zenefit还用考虑吗？我来猜一个：以后的面试趋势是上机化ICC会影响以后申请绿卡吗？请问oo design的题，回答格式是什么Google Quantitative Analyst internship 求Host收留跪求谈包裹策略：跳槽微软 Data Scientist 2我来说说买房这事帮忙看看google选组tmd, Comcast 也够烂的google的recruiter说team match后再递交给HC？google面经求解，可以让两个不同公司一起申请h1b吗？PIP了，要不要辞职？base 0%，bonus 0%，0 benefits 它姥姥的
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。