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.
相关阅读
求助一个onsite的问题电面后两周无消息是不是等于默拒了。急问 关于export license调查称多数Facebook员工IPO后选择退休 (转载)onsite以后，公司怎么联系candidates呢？请问design pattern是不是看几个就行了，那么多怎么都掌握？都是一些什么不靠谱的人啊 呵呵为什么master里面IE比其他E好找工作商科转CS？统计硕士？还是 DBA?如何判断一个职位是绿卡广告还是真的招人？h1b的申请费一般是多少？为何H1b REF Response寄出好几周状态还是"Request for REF"内推：Business Development/Analysis职位，化工行业USCIS收到OPT的申请文件过多久会给你WAC号码软件公司应该大力游说SOPA通过啊 (转载)关于不满2年 relocation fee 要自负的问题新人真诚向各位求教 接下去的安排现在是H1B，如果transfer H1B被拒，理论上我是否马上失去身份？ (转载)简历是否有讲究？jobs @ nuance : software engineer in speech recognition
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。