logo
Redian新闻
>未名空间
>gardening - 拈花惹草
>
结了好多好多的李子
avatar
结了好多好多的李子# gardening - 拈花惹草
K*g
1 楼
感觉twitter的面试比较难，二面派了两个人同时面，就像一面一样，反复纠缠细节，使劲的追问那种，弄得我脑子很乱。
面试是上周进行的，基本的东西不说了，整个面试中真正的题目就是下面这道，由于没有答好，面试fail掉了，郁闷了好几天。
a collection of integer,设计data structure，支持delete, insert, getRandom三个操作，尽量做到最优。
我先提出来BST，复杂度分别是O(logn），O（logn），O（n），然后被追问是worst case复杂度还是average复杂度。然后问要更好的办法。
我就说hashtable，他们就问怎么实现，还说getRandom的复杂度太高了，如果随机产生一个整数，很有可能那个整数在这个collection里不存在，我说那就再产生一个，知道找到为止，面试的人不满意。
然后我还说了bitmap，仍然不满意。中间纠缠了很久，还被问到collection里的整数的range很大，该怎么办之类的。
最后那个面试的人提醒我，考虑hash function。
其实面试的人的最终要求就是三个操作的复杂度都是O（1）.
请教高手。
avatar
d*n
2 楼
今年果树大年
树都压弯了
只好买了不少stake给撑起来
avatar
i*e
3 楼
我的想法是用array建立一个类似queue的data structure。
insert 就把新的元素放在最后面。利用 knuth shuffle 的原理，每次insert一个element就与 a[j] swap,j 是 0..N-1 的随机数。
delete 一个element的话就直接把 size 降一。(除非你delete是要delete某一个
element，那这方法就没法做到O(1)，因为要挪动array).
getRandom 就直接 return 最后的一个 element，然后把 size 降一。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
avatar
T*4
4 楼
涝得涝死啊
avatar
l*e
5 楼
double linked list + hash

【在 K******g 的大作中提到】
: 感觉twitter的面试比较难，二面派了两个人同时面，就像一面一样，反复纠缠细节，使劲的追问那种，弄得我脑子很乱。
: 面试是上周进行的，基本的东西不说了，整个面试中真正的题目就是下面这道，由于没有答好，面试fail掉了，郁闷了好几天。
: a collection of integer,设计data structure，支持delete, insert, getRandom三个操作，尽量做到最优。
: 我先提出来BST，复杂度分别是O(logn），O（logn），O（n），然后被追问是worst case复杂度还是average复杂度。然后问要更好的办法。
: 我就说hashtable，他们就问怎么实现，还说getRandom的复杂度太高了，如果随机产生一个整数，很有可能那个整数在这个collection里不存在，我说那就再产生一个，知道找到为止，面试的人不满意。
: 然后我还说了bitmap，仍然不满意。中间纠缠了很久，还被问到collection里的整数的range很大，该怎么办之类的。
: 最后那个面试的人提醒我，考虑hash function。
: 其实面试的人的最终要求就是三个操作的复杂度都是O（1）.
: 请教高手。
avatar
g*r
6 楼
羡慕

【在 d***n 的大作中提到】
: 今年果树大年
: 树都压弯了
: 只好买了不少stake给撑起来
avatar
s*5
7 楼
Can you use LinkedList?
Insertion and Deletion are O(1).
For getRandom(), i am not sure how much time Random().nextInt() cost...
For hashtable, the insertion could be more than O(1) if there are collisions
.
avatar
d*n
8 楼
大家说现在要施肥么
如果要的话有什么organic的推荐的
avatar
K*g
9 楼
ihasleetcode： delete肯定是delete一个具体的元素
larrabee ： 那个是cache的实现方法吧？怎么实现getRandom，并且是O(1)？
sweet845： Linked list肯定不行啊，insert和delete全部都是O（n）
面试的人提醒了，考虑hash function，但是我没有想明白。

【在 K******g 的大作中提到】
: 感觉twitter的面试比较难，二面派了两个人同时面，就像一面一样，反复纠缠细节，使劲的追问那种，弄得我脑子很乱。
: 面试是上周进行的，基本的东西不说了，整个面试中真正的题目就是下面这道，由于没有答好，面试fail掉了，郁闷了好几天。
: a collection of integer,设计data structure，支持delete, insert, getRandom三个操作，尽量做到最优。
: 我先提出来BST，复杂度分别是O(logn），O（logn），O（n），然后被追问是worst case复杂度还是average复杂度。然后问要更好的办法。
: 我就说hashtable，他们就问怎么实现，还说getRandom的复杂度太高了，如果随机产生一个整数，很有可能那个整数在这个collection里不存在，我说那就再产生一个，知道找到为止，面试的人不满意。
: 然后我还说了bitmap，仍然不满意。中间纠缠了很久，还被问到collection里的整数的range很大，该怎么办之类的。
: 最后那个面试的人提醒我，考虑hash function。
: 其实面试的人的最终要求就是三个操作的复杂度都是O（1）.
: 请教高手。
avatar
f*c
10 楼
怀念小时候吃的青色的，脆脆的李子
avatar
s*5
11 楼

I think you mistook add/delete with look up(find)?
insert an element to an listed array(not necessary to be sorted), you can
always insert to the end...and you can always delete the last or the first
element. And I donot know why it takes O(n)...

【在 K******g 的大作中提到】
: ihasleetcode： delete肯定是delete一个具体的元素
: larrabee ： 那个是cache的实现方法吧？怎么实现getRandom，并且是O(1)？
: sweet845： Linked list肯定不行啊，insert和delete全部都是O（n）
: 面试的人提醒了，考虑hash function，但是我没有想明白。
avatar
X*o
12 楼
你们都属于涝死的！

【在 T*******4 的大作中提到】
: 涝得涝死啊
avatar
K*g
13 楼
sorry，我搞混了，你的对，呵呵
但是getRandom很难O（1）

【在 s******5 的大作中提到】
:
: I think you mistook add/delete with look up(find)?
: insert an element to an listed array(not necessary to be sorted), you can
: always insert to the end...and you can always delete the last or the first
: element. And I donot know why it takes O(n)...
avatar
b*h
14 楼
就是

【在 T*******4 的大作中提到】
: 涝得涝死啊
avatar
s*5
15 楼

could you elaborate why 但是getRandom很难O（1） ?
(it is ok...you are very strong!)

【在 K******g 的大作中提到】
: sorry，我搞混了，你的对，呵呵
: 但是getRandom很难O（1）
avatar
p*y
16 楼
恭喜

【在 d***n 的大作中提到】
: 今年果树大年
: 树都压弯了
: 只好买了不少stake给撑起来
avatar
z*9
17 楼
搂主还在面啦？看来OP还是在乎钱，twitter和脸书除了潜在的股票受益外，我真看不
出来这种专注social的公司有什么核心技术和前途，一家只言，别见怪
avatar
y*8
18 楼
好多啊！等收获的时候记得上来引一下同学们的哗哗口水。

今年果树大年
树都压弯了
只好买了不少stake给撑起来

【在 d***n 的大作中提到】
: 今年果树大年
: 树都压弯了
: 只好买了不少stake给撑起来
avatar
K*g
19 楼
我意思是说用linked list很难做到getRandom是O(1)，如果你有办法，说说看。

【在 s******5 的大作中提到】
:
: could you elaborate why 但是getRandom很难O（1） ?
: (it is ok...you are very strong!)
avatar
T*4
20 楼
我的果树都刚栽了-------------

【在 X*******o 的大作中提到】
: 你们都属于涝死的！
avatar
n*n
21 楼

，使劲的追问那种，弄得我脑子很乱。
没有答好，面试fail掉了，郁闷了好几天。
三个操作，尽量做到最优。
what is getRandom？
case复杂度还是average复杂度。然后问要更好的办法。
balanced bst.
生一个整数，很有可能那个整数在这个collection里不存在，我说那就再产生一个，知
道找到为止，面试的人不满意。
的range很大，该怎么办之类的。

【在 K******g 的大作中提到】
: 感觉twitter的面试比较难，二面派了两个人同时面，就像一面一样，反复纠缠细节，使劲的追问那种，弄得我脑子很乱。
: 面试是上周进行的，基本的东西不说了，整个面试中真正的题目就是下面这道，由于没有答好，面试fail掉了，郁闷了好几天。
: a collection of integer,设计data structure，支持delete, insert, getRandom三个操作，尽量做到最优。
: 我先提出来BST，复杂度分别是O(logn），O（logn），O（n），然后被追问是worst case复杂度还是average复杂度。然后问要更好的办法。
: 我就说hashtable，他们就问怎么实现，还说getRandom的复杂度太高了，如果随机产生一个整数，很有可能那个整数在这个collection里不存在，我说那就再产生一个，知道找到为止，面试的人不满意。
: 然后我还说了bitmap，仍然不满意。中间纠缠了很久，还被问到collection里的整数的range很大，该怎么办之类的。
: 最后那个面试的人提醒我，考虑hash function。
: 其实面试的人的最终要求就是三个操作的复杂度都是O（1）.
: 请教高手。
avatar
s*n
22 楼
then you can use linked list as an array. pointer is the index of the
element.
getrandom is trivial.

【在 K******g 的大作中提到】
: sorry，我搞混了，你的对，呵呵
: 但是getRandom很难O（1）
avatar
j*c
23 楼
在不考虑hash collision的情况下Hashtable 的delete和insert都是O(1)的.
对于getRandom(), 如果用array + linklist 来实现buckets的话,随机生成一个array
index, 从该index所指向的bucket
取一个value, 这样的实现应该是O(1) 吧.
没有仔细验证,请高手指正

，使劲的追问那种，弄得我脑子很
乱。
没有答好，面试fail掉了，郁闷了好
几天。
三个操作，尽量做到最优。
case复杂度还是average复杂
度。然后问要更好的办法。
生一个整数，很有可能那个整数
在这个collection里不存在，我说那就再产生一个，知道找到为止，面试的人不满意。
的range很大，该怎么办之类的。

【在 K******g 的大作中提到】
: 感觉twitter的面试比较难，二面派了两个人同时面，就像一面一样，反复纠缠细节，使劲的追问那种，弄得我脑子很乱。
: 面试是上周进行的，基本的东西不说了，整个面试中真正的题目就是下面这道，由于没有答好，面试fail掉了，郁闷了好几天。
: a collection of integer,设计data structure，支持delete, insert, getRandom三个操作，尽量做到最优。
: 我先提出来BST，复杂度分别是O(logn），O（logn），O（n），然后被追问是worst case复杂度还是average复杂度。然后问要更好的办法。
: 我就说hashtable，他们就问怎么实现，还说getRandom的复杂度太高了，如果随机产生一个整数，很有可能那个整数在这个collection里不存在，我说那就再产生一个，知道找到为止，面试的人不满意。
: 然后我还说了bitmap，仍然不满意。中间纠缠了很久，还被问到collection里的整数的range很大，该怎么办之类的。
: 最后那个面试的人提醒我，考虑hash function。
: 其实面试的人的最终要求就是三个操作的复杂度都是O（1）.
: 请教高手。
avatar
j*c
24 楼
关于那个buckets的实现可能说的不够清除, 可以参考下面链接的图片
http://fortranwiki.org/fortran/show/Hash+tables

array

【在 j******c 的大作中提到】
: 在不考虑hash collision的情况下Hashtable 的delete和insert都是O(1)的.
: 对于getRandom(), 如果用array + linklist 来实现buckets的话,随机生成一个array
: index, 从该index所指向的bucket
: 取一个value, 这样的实现应该是O(1) 吧.
: 没有仔细验证,请高手指正
:
: ，使劲的追问那种，弄得我脑子很
: 乱。
: 没有答好，面试fail掉了，郁闷了好
: 几天。
avatar
K*g
25 楼
当然要面啊，直到找到自己满意的offer为止，否则永远不会甘心

【在 z***9 的大作中提到】
: 搂主还在面啦？看来OP还是在乎钱，twitter和脸书除了潜在的股票受益外，我真看不
: 出来这种专注social的公司有什么核心技术和前途，一家只言，别见怪
avatar
K*g
26 楼
加入删除一个呢，你也要跟新这个array吧？只要array一出现，delete就不会和O（1）了
我感觉这题他考察我的是hash fuction的设计，怎么设计一个hash fuction，使得
getRandom是O（1）。因为如果我们随机产生一个位置，那个位置也许是空的。

array

【在 j******c 的大作中提到】
: 在不考虑hash collision的情况下Hashtable 的delete和insert都是O(1)的.
: 对于getRandom(), 如果用array + linklist 来实现buckets的话,随机生成一个array
: index, 从该index所指向的bucket
: 取一个value, 这样的实现应该是O(1) 吧.
: 没有仔细验证,请高手指正
:
: ，使劲的追问那种，弄得我脑子很
: 乱。
: 没有答好，面试fail掉了，郁闷了好
: 几天。
avatar
j*c
27 楼
No,insert and delete are both O(1).
for example, insert an Integer x is like following:
int hash = hashcode(x);
int index = (hash) % array.length;
then you put x into array[index]
delete an entry is similar.

）了

【在 K******g 的大作中提到】
: 加入删除一个呢，你也要跟新这个array吧？只要array一出现，delete就不会和O（1）了
: 我感觉这题他考察我的是hash fuction的设计，怎么设计一个hash fuction，使得
: getRandom是O（1）。因为如果我们随机产生一个位置，那个位置也许是空的。
:
: array
avatar
i*e
28 楼
用两个hash table肯定可以，但不知道有没有更好的方法。
所有 elements 用linked list 来储存。
第一个 hash from index to 指针，指向那个 index 的 element.这样我们就可以O(1)
来GetRandom().
第二个 hash from element's value to 指针，指向那个 element 的所在地方。这样
我们就可以O(1)来 delete 任意一个 specific element.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

array

【在 j******c 的大作中提到】
: 在不考虑hash collision的情况下Hashtable 的delete和insert都是O(1)的.
: 对于getRandom(), 如果用array + linklist 来实现buckets的话,随机生成一个array
: index, 从该index所指向的bucket
: 取一个value, 这样的实现应该是O(1) 吧.
: 没有仔细验证,请高手指正
:
: ，使劲的追问那种，弄得我脑子很
: 乱。
: 没有答好，面试fail掉了，郁闷了好
: 几天。
avatar
i*e
29 楼
Could you explain how can you insert an element into array in O(1)?
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 j******c 的大作中提到】
: No,insert and delete are both O(1).
: for example, insert an Integer x is like following:
: int hash = hashcode(x);
: int index = (hash) % array.length;
: then you put x into array[index]
: delete an entry is similar.
:
: ）了
avatar
j*c
30 楼
Ok, following pseudo code insert integer x into hashtable:
int hash = hashcode(x);
int index = (hash) % array.length;
array[index].add(x);
hashcode() is the hash function.
array[] stores linkedlist references.

【在 i**********e 的大作中提到】
: Could you explain how can you insert an element into array in O(1)?
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
avatar
d*a
31 楼
if you want to getRandom in O(1), we might need to use array and keep all
the exsiting elemetns adjacent. So maybe we could use hashtable and big
array together.
For hashtable's pair, key is what we insert. value is the index
for array, and array[value] = key.
But how to synchronize hashtable and array is a problem....
avatar
h*n
32 楼
how about bloom filter, which has multiple hash functions

，使劲的追问那种，弄得我脑子很乱。
没有答好，面试fail掉了，郁闷了好几天。
三个操作，尽量做到最优。
case复杂度还是average复杂度。然后问要更好的办法。
生一个整数，很有可能那个整数在这个collection里不存在，我说那就再产生一个，知
道找到为止，面试的人不满意。
的range很大，该怎么办之类的。

【在 K******g 的大作中提到】
: 感觉twitter的面试比较难，二面派了两个人同时面，就像一面一样，反复纠缠细节，使劲的追问那种，弄得我脑子很乱。
: 面试是上周进行的，基本的东西不说了，整个面试中真正的题目就是下面这道，由于没有答好，面试fail掉了，郁闷了好几天。
: a collection of integer,设计data structure，支持delete, insert, getRandom三个操作，尽量做到最优。
: 我先提出来BST，复杂度分别是O(logn），O（logn），O（n），然后被追问是worst case复杂度还是average复杂度。然后问要更好的办法。
: 我就说hashtable，他们就问怎么实现，还说getRandom的复杂度太高了，如果随机产生一个整数，很有可能那个整数在这个collection里不存在，我说那就再产生一个，知道找到为止，面试的人不满意。
: 然后我还说了bitmap，仍然不满意。中间纠缠了很久，还被问到collection里的整数的range很大，该怎么办之类的。
: 最后那个面试的人提醒我，考虑hash function。
: 其实面试的人的最终要求就是三个操作的复杂度都是O（1）.
: 请教高手。
avatar
f*h
33 楼
LinkedList + Hashtable
Insert+Delete to Linkedlist. On insert, also insert the value and address
of the node to hashtable. On delete, also remove the value from hashtable.
On random, generate a random number with in the size 0..sizeof hashtable,
return the address of the node in that position.
All O(1)
avatar
i*e
34 楼
Could you lookup the hashtable according to value AND index?
Hashtable could only lookup according to one type of key only.
That's why I suggested using two hashtables.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

.

【在 f*******h 的大作中提到】
: LinkedList + Hashtable
: Insert+Delete to Linkedlist. On insert, also insert the value and address
: of the node to hashtable. On delete, also remove the value from hashtable.
: On random, generate a random number with in the size 0..sizeof hashtable,
: return the address of the node in that position.
: All O(1)
avatar
s*5
35 楼

In Java, it has Hashset, which is a value only Hash structure.

【在 i**********e 的大作中提到】
: Could you lookup the hashtable according to value AND index?
: Hashtable could only lookup according to one type of key only.
: That's why I suggested using two hashtables.
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
:
: .
avatar
f*h
36 楼
Sorry. Value should be index.
The linkedlist data structure will be 13->19->-909->1999
The corresponding hashtable will be (1,add1),(2,add2),(3,add3),(4,add4)
when you delete, it always remove the last element in the list and also
delete the corresponding element in hashtable (assume delete and insert at
the end of the list).
So, if delete 1999, the (4, add4) also be deleted.
Getrandom will return any number from 1 to 4. There will be a variable to
keep recording current size of the list.
avatar
i*e
37 楼
But according to LZ, delete has to delete a specific element (not always at
the end). What if I want to delete 19 from the list?
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 f*******h 的大作中提到】
: Sorry. Value should be index.
: The linkedlist data structure will be 13->19->-909->1999
: The corresponding hashtable will be (1,add1),(2,add2),(3,add3),(4,add4)
: when you delete, it always remove the last element in the list and also
: delete the corresponding element in hashtable (assume delete and insert at
: the end of the list).
: So, if delete 1999, the (4, add4) also be deleted.
: Getrandom will return any number from 1 to 4. There will be a variable to
: keep recording current size of the list.
avatar
f*h
38 楼
No, he didn't mention that. That should be a lookup data structure. It's not the purpose of this interview question I guess.

at

【在 i**********e 的大作中提到】
: But according to LZ, delete has to delete a specific element (not always at
: the end). What if I want to delete 19 from the list?
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
avatar
i*e
39 楼
...
He mentioned that in post #5.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

not the purpose of this interview question I guess.

【在 f*******h 的大作中提到】
: No, he didn't mention that. That should be a lookup data structure. It's not the purpose of this interview question I guess.
:
: at
avatar
K*g
40 楼
insert， delete一个具体的integer，不是design 什么cache
3个操作都要是O（1）
请大家往hash function方向想把，要通过多个hashtable/list来实现，好像不可能。
面试的人都提醒了，hash fuction。

【在 i**********e 的大作中提到】
: ...
: He mentioned that in post #5.
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
:
: not the purpose of this interview question I guess.
avatar
s*3
41 楼
lz你好，问下twitter一面和二面之间隔了多久？谢谢

【在 K******g 的大作中提到】
: insert， delete一个具体的integer，不是design 什么cache
: 3个操作都要是O（1）
: 请大家往hash function方向想把，要通过多个hashtable/list来实现，好像不可能。
: 面试的人都提醒了，hash fuction。
avatar
g*e
42 楼
是linklist，deleting 19有什么问题？记得fb有类似的题，也是linklist+ht or
array+ht.

at

【在 i**********e 的大作中提到】
: But according to LZ, delete has to delete a specific element (not always at
: the end). What if I want to delete 19 from the list?
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
avatar
P*b
43 楼
这个题讨论出结果了吗？

，使劲的追问那种，弄得我脑子很乱。
没有答好，面试fail掉了，郁闷了好几天。
三个操作，尽量做到最优。
case复杂度还是average复杂度。然后问要更好的办法。
生一个整数，很有可能那个整数在这个collection里不存在，我说那就再产生一个，知
道找到为止，面试的人不满意。
的range很大，该怎么办之类的。

【在 K******g 的大作中提到】
: 感觉twitter的面试比较难，二面派了两个人同时面，就像一面一样，反复纠缠细节，使劲的追问那种，弄得我脑子很乱。
: 面试是上周进行的，基本的东西不说了，整个面试中真正的题目就是下面这道，由于没有答好，面试fail掉了，郁闷了好几天。
: a collection of integer,设计data structure，支持delete, insert, getRandom三个操作，尽量做到最优。
: 我先提出来BST，复杂度分别是O(logn），O（logn），O（n），然后被追问是worst case复杂度还是average复杂度。然后问要更好的办法。
: 我就说hashtable，他们就问怎么实现，还说getRandom的复杂度太高了，如果随机产生一个整数，很有可能那个整数在这个collection里不存在，我说那就再产生一个，知道找到为止，面试的人不满意。
: 然后我还说了bitmap，仍然不满意。中间纠缠了很久，还被问到collection里的整数的range很大，该怎么办之类的。
: 最后那个面试的人提醒我，考虑hash function。
: 其实面试的人的最终要求就是三个操作的复杂度都是O（1）.
: 请教高手。
avatar
i*s
44 楼
hashtable + array is the answer:
The array's element has link to the hash map entry and vice verses.
insert: insert an element to the hashtable, also append an element in the
array.
delete: remove the entry from the hashtable, using the link to find the
corresponding entry in the array. Remove the array element by moving the
last element to the current position.
random: generate a random number between 1 to sizeof array. pick an position
and corresponding entry in the hash table.
avatar
c*t
45 楼
这个也不行啊。
delete的时候，如何能够delete第一个hashtable，而且还要update index,也不是O(1)
啊。

1)

【在 i**********e 的大作中提到】
: 用两个hash table肯定可以，但不知道有没有更好的方法。
: 所有 elements 用linked list 来储存。
: 第一个 hash from index to 指针，指向那个 index 的 element.这样我们就可以O(1)
: 来GetRandom().
: 第二个 hash from element's value to 指针，指向那个 element 的所在地方。这样
: 我们就可以O(1)来 delete 任意一个 specific element.
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
:
: array
avatar
c*t
46 楼
pick an position and corresponding entry in the hash table？？
hashtable不是只有用key lookup吗？能用index吗？

position

【在 i********s 的大作中提到】
: hashtable + array is the answer:
: The array's element has link to the hash map entry and vice verses.
: insert: insert an element to the hashtable, also append an element in the
: array.
: delete: remove the entry from the hashtable, using the link to find the
: corresponding entry in the array. Remove the array element by moving the
: last element to the current position.
: random: generate a random number between 1 to sizeof array. pick an position
: and corresponding entry in the hash table.
avatar
P*l
47 楼
+1

position

【在 i********s 的大作中提到】
: hashtable + array is the answer:
: The array's element has link to the hash map entry and vice verses.
: insert: insert an element to the hashtable, also append an element in the
: array.
: delete: remove the entry from the hashtable, using the link to find the
: corresponding entry in the array. Remove the array element by moving the
: last element to the current position.
: random: generate a random number between 1 to sizeof array. pick an position
: and corresponding entry in the hash table.
avatar
i*d
48 楼
我咋感觉Ullman Set可以做
有点类似之前有人说到的array + hashtable
其实跟TAOCP的那道稀疏数组初始化的题目有点像
只要实现O(1)的insert, delete, get, getTotalNum就可以了
其中getTotalNum就是势查询，返回当前数据结构中元素数目
insert delete是要求的
get + getTotalNum 合起来就可以实现getRandom
Ullman set需要O(n)的空间，这个有点不符合要求
但Ullman set是用俩数组做的，把其中的索引数组换成hash表就符合要求了
第二个数组是紧凑的，只需要O(m)空间，m是已有元素的数目

【在 P*******b 的大作中提到】
: 这个题讨论出结果了吗？
:
: ，使劲的追问那种，弄得我脑子很乱。
: 没有答好，面试fail掉了，郁闷了好几天。
: 三个操作，尽量做到最优。
: case复杂度还是average复杂度。然后问要更好的办法。
: 生一个整数，很有可能那个整数在这个collection里不存在，我说那就再产生一个，知
: 道找到为止，面试的人不满意。
: 的range很大，该怎么办之类的。
avatar
l*b
49 楼
恕我眼拙。
hashtable不是号称lookup/delete都是O(1)吗？
如果lookup是O(1)， getrandom也该是O(1)：
首先随机选择一个bucket,然后在这个bucket随机选择一个element.
avatar
l*a
50 楼
怎么能够知道随机出来的bucket里面一定有element？

【在 l*********b 的大作中提到】
: 恕我眼拙。
: hashtable不是号称lookup/delete都是O(1)吗？
: 如果lookup是O(1)， getrandom也该是O(1)：
: 首先随机选择一个bucket,然后在这个bucket随机选择一个element.
avatar
h*d
51 楼
我叫着这题和cache那题不差不多吗，就用hashtable + doubly linked list就可以实
现insert, delete in O(1)
至于getRandom(), 可以在insert的时候吧hashcode再用一个数组或者list存下来，然
后生产一个random数，在数组里找到相应的hashcode，再去hashtable里面，和doubly
linked list里面删？
avatar
l*a
52 楼
这么做，插入和删除操作也需要对'数组或者list'进行维护，那么插入和删除就不能是
O（1）了。

doubly

【在 h**********d 的大作中提到】
: 我叫着这题和cache那题不差不多吗，就用hashtable + doubly linked list就可以实
: 现insert, delete in O(1)
: 至于getRandom(), 可以在insert的时候吧hashcode再用一个数组或者list存下来，然
: 后生产一个random数，在数组里找到相应的hashcode，再去hashtable里面，和doubly
: linked list里面删？
avatar
f*g
53 楼
数组保存value
Hashtable保存value在数组中的位置。
插入：存在数组末尾，并将位置插入Hashtable。O(1)
随机：直接生成随机数，从数组中读。O(1)
删除：首先删除相应的元素，然后把数组最后一位移动到删除的位置并更新位置。O(1)
avatar
i*e
54 楼
赞 简单又有效的解法！
你的解法是跟 ineedlexus 一样的。
最关键的是可以利用数组来储存元素，而删除又不需要挪动之后的元素。
只要把最后的元素填补于被删除的位置即可。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

1)

【在 f***g 的大作中提到】
: 数组保存value
: Hashtable保存value在数组中的位置。
: 插入：存在数组末尾，并将位置插入Hashtable。O(1)
: 随机：直接生成随机数，从数组中读。O(1)
: 删除：首先删除相应的元素，然后把数组最后一位移动到删除的位置并更新位置。O(1)
avatar
m*d
56 楼
删除步骤中，把数组最后一位移动到删除的位置并更新位置，这时那个被移动的元素的
value就变了吧，在hash表中也相应的会变

1)

【在 f***g 的大作中提到】
: 数组保存value
: Hashtable保存value在数组中的位置。
: 插入：存在数组末尾，并将位置插入Hashtable。O(1)
: 随机：直接生成随机数，从数组中读。O(1)
: 删除：首先删除相应的元素，然后把数组最后一位移动到删除的位置并更新位置。O(1)
avatar
P*l
57 楼
please check http://www.sureinterview.com/shwqst/1019005/91011
Here is the delete part.
//delete
T delete(T data) {
int pos = hashFunction(data);
T dat = dataArr[pos].data;
dataArr[pos].data = null;
//to avoid moving large data block left, the data at the tail is
moved to middle instead.
//so the pointers needs to be adjusted.
rndArr[pos] = rndArr[size]; //move pointer to middle
dataArr[rndArr[size]].idx = pos; // adjust the pointer in data array.
size--;
return dat;
}
BTW, I don't think storing data only in the array will work. Or any DaXia
can explain the implementation in detail?
avatar
s*e
58 楼
public class RandomHash {
HashMap hashmap = new HashMap();
Vector vec = new Vector();
public void insert(K key) {
vec.add(key);
hashmap.put(key, new Integer(vec.size()-1));
}
public K getRand() {
if(vec.size()<=0)
return null;
Random randomGenerator = new Random();
int rndnum = randomGenerator.nextInt(vec.size());
return vec.get(rndnum);
}
public boolean delete(K key) {
if(!hashmap.containsKey(key))
return false;
Integer deleteIndex = hashmap.remove(key);
int replaceIndex = vec.size()-1;
K replaceKey = vec.remove(replaceIndex);
if(deleteIndex.intValue()!=replaceIndex) {
vec.set(deleteIndex.intValue(), replaceKey);
hashmap.put(replaceKey, deleteIndex);
}
return true;
}
}
avatar
i*e
59 楼
Last element should be rndArray[size-1] bah...
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 P********l 的大作中提到】
: please check http://www.sureinterview.com/shwqst/1019005/91011
: Here is the delete part.
: //delete
: T delete(T data) {
: int pos = hashFunction(data);
: T dat = dataArr[pos].data;
: dataArr[pos].data = null;
: //to avoid moving large data block left, the data at the tail is
: moved to middle instead.
: //so the pointers needs to be adjusted.
avatar
c*t
60 楼
赞！
如果有duplicate value怎么办？

1)

【在 f***g 的大作中提到】
: 数组保存value
: Hashtable保存value在数组中的位置。
: 插入：存在数组末尾，并将位置插入Hashtable。O(1)
: 随机：直接生成随机数，从数组中读。O(1)
: 删除：首先删除相应的元素，然后把数组最后一位移动到删除的位置并更新位置。O(1)
avatar
c*t
61 楼
是的，感谢两位给出codes的童鞋。能不能说一下如果有duplicate value怎么办？

【在 i**********e 的大作中提到】
: Last element should be rndArray[size-1] bah...
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
avatar
i*e
62 楼
我也在想这个问题，
有个解决方法，就是 hash table 的 key, value pair = (value, vector
indexes).
例如，如果第一次 insert 3 的时候在 index 5, table[3] = {5}.
第二次 insert 3 的时候在 index 10, table[3] = {5, 10}.
如果删除 3 的时候，就随便选其中一个index 来删除，index 5 或者 10 都无所谓，
反正不影响 getRandom 。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 c********t 的大作中提到】
: 是的，感谢两位给出codes的童鞋。能不能说一下如果有duplicate value怎么办？
avatar
c*t
63 楼
不错，这个可行！

【在 i**********e 的大作中提到】
: 我也在想这个问题，
: 有个解决方法，就是 hash table 的 key, value pair = (value, vector
: indexes).
: 例如，如果第一次 insert 3 的时候在 index 5, table[3] = {5}.
: 第二次 insert 3 的时候在 index 10, table[3] = {5, 10}.
: 如果删除 3 的时候，就随便选其中一个index 来删除，index 5 或者 10 都无所谓，
: 反正不影响 getRandom 。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
avatar
P*l
64 楼
add a counting field in 'Data' class or index array for possible duplicated
data.

【在 i**********e 的大作中提到】
: 我也在想这个问题，
: 有个解决方法，就是 hash table 的 key, value pair = (value, vector
: indexes).
: 例如，如果第一次 insert 3 的时候在 index 5, table[3] = {5}.
: 第二次 insert 3 的时候在 index 10, table[3] = {5, 10}.
: 如果删除 3 的时候，就随便选其中一个index 来删除，index 5 或者 10 都无所谓，
: 反正不影响 getRandom 。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
avatar
s*e
65 楼
可以用 hashset 来替代 vector ,
public class RandomHash {
HashMap > hashmap = new HashMapLinkedHashSet>();
Vector vec = new Vector();
public void insert(K key) {
vec.add(key);
if( ! hashmap.containsKey(key) ) {
LinkedHashSet hashSet = new
LinkedHashSet();
hashSet.add(new Integer(vec.size()-1));
hashmap.put(key,hashSet);
} else {
hashmap.get(key).add(new Integer(vec.size()-1));
}
}
public K getRand() {
if(vec.size()<=0)
return null;
Random randomGenerator = new Random();
int rndnum = randomGenerator.nextInt(vec.size());
return vec.get(rndnum);
}
public boolean delete(K key) {
if(!hashmap.containsKey(key))
return false;
LinkedHashSet hashSet = hashmap.get(key);
Integer deleteIndex = hashSet.iterator().next();
hashSet.remove(deleteIndex);
if(hashSet.size()<=0)
hashmap.remove(key);
int replaceIndex = vec.size()-1;
K replaceKey = vec.remove(replaceIndex);
if(deleteIndex.intValue()!=replaceIndex) {
vec.set(deleteIndex.intValue(), replaceKey);
LinkedHashSet replaceHashSet =
hashmap.get(replaceKey);
replaceHashSet.remove(new
Integer(replaceIndex));
replaceHashSet.add(deleteIndex);
}
return true;
}
}

【在 i**********e 的大作中提到】
: 我也在想这个问题，
: 有个解决方法，就是 hash table 的 key, value pair = (value, vector
: indexes).
: 例如，如果第一次 insert 3 的时候在 index 5, table[3] = {5}.
: 第二次 insert 3 的时候在 index 10, table[3] = {5, 10}.
: 如果删除 3 的时候，就随便选其中一个index 来删除，index 5 或者 10 都无所谓，
: 反正不影响 getRandom 。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
avatar
i*e
66 楼
In C++, using hash_mutlimap should be fine.
hash_multimap supports duplicate values to be inserted.
http://msdn.microsoft.com/en-us/library/2ffwdw2d%28v=vs.80%29.a
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 s******e 的大作中提到】
: 可以用 hashset 来替代 vector ,
: public class RandomHash {
: HashMap > hashmap = new HashMap: LinkedHashSet>();
: Vector vec = new Vector();
: public void insert(K key) {
: vec.add(key);
: if( ! hashmap.containsKey(key) ) {
: LinkedHashSet hashSet = new
: LinkedHashSet();
avatar
j*x
67 楼
this doesnt support O(1) getRandom()

【在 l******e 的大作中提到】
: double linked list + hash
avatar
j*x
68 楼
Use hashtable along can do the job
The trick to give a O(1) getRandom() is to guarantee the load factor of the
hashtable. To achieve this, pick a fill_ratio_upper_bound, shrink the
hashtable by half if fill ratio drops below fill_ratio_upper_bound / 4.
Expand hashtable by half if exceeds fill_ratio_upper_bound.
Any time insertion and deletion is O(1)
For getRandom(), keep picking random postion of bucket, until find one is
not empty. Since load factor is lower-bounded, this is a O(1) (average).
The problem is that the load factor and occupancy ratio of buckects are not
equvalent, I believe at least the above scheme shall work... No proof yet...
avatar
P*l
69 楼
post #1:
"我就说hashtable，他们就问怎么实现，还说getRandom的复杂度太高了，如果随机产
生一个整数，很有可能那个整数在这个collection里不存在，我说那就再产生一个，知
道找到为止，面试的人不满意。"

the
not
..

【在 j********x 的大作中提到】
: Use hashtable along can do the job
: The trick to give a O(1) getRandom() is to guarantee the load factor of the
: hashtable. To achieve this, pick a fill_ratio_upper_bound, shrink the
: hashtable by half if fill ratio drops below fill_ratio_upper_bound / 4.
: Expand hashtable by half if exceeds fill_ratio_upper_bound.
: Any time insertion and deletion is O(1)
: For getRandom(), keep picking random postion of bucket, until find one is
: not empty. Since load factor is lower-bounded, this is a O(1) (average).
: The problem is that the load factor and occupancy ratio of buckects are not
: equvalent, I believe at least the above scheme shall work... No proof yet...
avatar
j*x
70 楼
The key is to preserve the load factor...
That's why I post this after reading the best solution

【在 P********l 的大作中提到】
: post #1:
: "我就说hashtable，他们就问怎么实现，还说getRandom的复杂度太高了，如果随机产
: 生一个整数，很有可能那个整数在这个collection里不存在，我说那就再产生一个，知
: 道找到为止，面试的人不满意。"
:
: the
: not
: ..
avatar
z*e
72 楼
QQ is basically a social network.
core technology of social network is distributed system, cluster, or fancier
name "map reduce". You think facebook is just regular PHP webpage +
Database running on a linux? Many previous "research only" technologies find
their positions in social network, graph/data mining/parallel computing/
whatever. --- while these technologies were mostly for theory research in
previous software products (OS/console application/etc.).
Regarding the future of SNS, we don't know, and people are willing to take
the risk. It's not about social, it's about user base. When you have enough
users, there will be far more things can be done (e.g. social games,customized
devices like kindle/android, or whatever. Do you think Android will be so successful if Google just jump into mobbile phone market without having a huge number of users first? IPhone will be so popular without having iPod users first?). Microsoft is successful on windows/office because of the user base; Google succeed by having large user base for searching; Facebook has unbeatable user base; same for QQ/Youtube/etc. User base is the best way to sell your product/service, and social network is now identified as the best way to build user base.
Moving to HTML5, with the new feautres like web socket, there could be
other innovations for web applications.

【在 z***9 的大作中提到】
: 搂主还在面啦？看来OP还是在乎钱，twitter和脸书除了潜在的股票受益外，我真看不
: 出来这种专注social的公司有什么核心技术和前途，一家只言，别见怪
avatar
j*u
73 楼
说的好，必须要顶！

fancier
find
enough

【在 z***e 的大作中提到】
: QQ is basically a social network.
: core technology of social network is distributed system, cluster, or fancier
: name "map reduce". You think facebook is just regular PHP webpage +
: Database running on a linux? Many previous "research only" technologies find
: their positions in social network, graph/data mining/parallel computing/
: whatever. --- while these technologies were mostly for theory research in
: previous software products (OS/console application/etc.).
: Regarding the future of SNS, we don't know, and people are willing to take
: the risk. It's not about social, it's about user base. When you have enough
: users, there will be far more things can be done (e.g. social games,customized
avatar
i*d
74 楼
这个就是Ullman Set啊。。。。

1)

【在 f***g 的大作中提到】
: 数组保存value
: Hashtable保存value在数组中的位置。
: 插入：存在数组末尾，并将位置插入Hashtable。O(1)
: 随机：直接生成随机数，从数组中读。O(1)
: 删除：首先删除相应的元素，然后把数组最后一位移动到删除的位置并更新位置。O(1)
avatar
c*6
75 楼
只用hash function？
不解
用神马数据结构？
avatar
d*d
76 楼
hash这个random怎么搞?

，使劲的追问那种，弄得我脑子很乱。
没有答好，面试fail掉了，郁闷了好几天。
三个操作，尽量做到最优。
case复杂度还是average复杂度。然后问要更好的办法。
生一个整数，很有可能那个整数在这个collection里不存在，我说那就再产生一个，知
道找到为止，面试的人不满意。
的range很大，该怎么办之类的。

【在 K******g 的大作中提到】
: 感觉twitter的面试比较难，二面派了两个人同时面，就像一面一样，反复纠缠细节，使劲的追问那种，弄得我脑子很乱。
: 面试是上周进行的，基本的东西不说了，整个面试中真正的题目就是下面这道，由于没有答好，面试fail掉了，郁闷了好几天。
: a collection of integer,设计data structure，支持delete, insert, getRandom三个操作，尽量做到最优。
: 我先提出来BST，复杂度分别是O(logn），O（logn），O（n），然后被追问是worst case复杂度还是average复杂度。然后问要更好的办法。
: 我就说hashtable，他们就问怎么实现，还说getRandom的复杂度太高了，如果随机产生一个整数，很有可能那个整数在这个collection里不存在，我说那就再产生一个，知道找到为止，面试的人不满意。
: 然后我还说了bitmap，仍然不满意。中间纠缠了很久，还被问到collection里的整数的range很大，该怎么办之类的。
: 最后那个面试的人提醒我，考虑hash function。
: 其实面试的人的最终要求就是三个操作的复杂度都是O（1）.
: 请教高手。
avatar
s*i
77 楼
顶!
avatar
I*l
78 楼
How about using one hash table together with one array? The hash table can
be used to support O(1)-time insertions and deletions and use the array for
getRandom. Basically we maintain an array (or more precisely, a dynamic
array) of pointers for the integers in the set and a counter k for how many
integers the hash table currently contains. We will also store the index of
an element in the array in the hash table of that element. When an integer
is inserted, we add a new entry to the end of the array and increment the
counter; when delete an entry, we use hash table to retrieve its index in
the array, move the entry at the end of the array to this vacant one and
update the hash table accordingly. To get a random element, simply generate
a random integer and get its modulo k.
avatar
y*w
79 楼
bless
avatar
d*n
80 楼
sounds doable, although the insertion cannot be guaranteed O(1) due to array
resizing

for
many
of
generate

【在 I*******l 的大作中提到】
: How about using one hash table together with one array? The hash table can
: be used to support O(1)-time insertions and deletions and use the array for
: getRandom. Basically we maintain an array (or more precisely, a dynamic
: array) of pointers for the integers in the set and a counter k for how many
: integers the hash table currently contains. We will also store the index of
: an element in the array in the hash table of that element. When an integer
: is inserted, we add a new entry to the end of the array and increment the
: counter; when delete an entry, we use hash table to retrieve its index in
: the array, move the entry at the end of the array to this vacant one and
: update the hash table accordingly. To get a random element, simply generate
avatar
q*x
81 楼
on average it's O(1).

array

【在 d***n 的大作中提到】
: sounds doable, although the insertion cannot be guaranteed O(1) due to array
: resizing
:
: for
: many
: of
: generate
avatar
d*o
82 楼
May be hash table. Get O(1), Delete O(1)
Don't know it is OK to customize the Hashtable implementation. if it is, we
can define one hash function, one random function. each time call
getRandom, internally, it call random function to get the value, and also O(
1)

，使劲的追问那种，弄得我脑子很乱。
没有答好，面试fail掉了，郁闷了好几天。
三个操作，尽量做到最优。
case复杂度还是average复杂度。然后问要更好的办法。
生一个整数，很有可能那个整数在这个collection里不存在，我说那就再产生一个，知
道找到为止，面试的人不满意。
的range很大，该怎么办之类的。

【在 K******g 的大作中提到】
: 感觉twitter的面试比较难，二面派了两个人同时面，就像一面一样，反复纠缠细节，使劲的追问那种，弄得我脑子很乱。
: 面试是上周进行的，基本的东西不说了，整个面试中真正的题目就是下面这道，由于没有答好，面试fail掉了，郁闷了好几天。
: a collection of integer,设计data structure，支持delete, insert, getRandom三个操作，尽量做到最优。
: 我先提出来BST，复杂度分别是O(logn），O（logn），O（n），然后被追问是worst case复杂度还是average复杂度。然后问要更好的办法。
: 我就说hashtable，他们就问怎么实现，还说getRandom的复杂度太高了，如果随机产生一个整数，很有可能那个整数在这个collection里不存在，我说那就再产生一个，知道找到为止，面试的人不满意。
: 然后我还说了bitmap，仍然不满意。中间纠缠了很久，还被问到collection里的整数的range很大，该怎么办之类的。
: 最后那个面试的人提醒我，考虑hash function。
: 其实面试的人的最终要求就是三个操作的复杂度都是O（1）.
: 请教高手。
avatar
j*x
83 楼
均摊复杂度到O(1)
这题老题了，还是挺有意思的

array

【在 d***n 的大作中提到】
: sounds doable, although the insertion cannot be guaranteed O(1) due to array
: resizing
:
: for
: many
: of
: generate
avatar
K*g
84 楼
感觉twitter的面试比较难，二面派了两个人同时面，就像一面一样，反复纠缠细节，使劲的追问那种，弄得我脑子很乱。
面试是上周进行的，基本的东西不说了，整个面试中真正的题目就是下面这道，由于没有答好，面试fail掉了，郁闷了好几天。
a collection of integer,设计data structure，支持delete, insert, getRandom三个操作，尽量做到最优。
我先提出来BST，复杂度分别是O(logn），O（logn），O（n），然后被追问是worst case复杂度还是average复杂度。然后问要更好的办法。
我就说hashtable，他们就问怎么实现，还说getRandom的复杂度太高了，如果随机产生一个整数，很有可能那个整数在这个collection里不存在，我说那就再产生一个，知道找到为止，面试的人不满意。
然后我还说了bitmap，仍然不满意。中间纠缠了很久，还被问到collection里的整数的range很大，该怎么办之类的。
最后那个面试的人提醒我，考虑hash function。
其实面试的人的最终要求就是三个操作的复杂度都是O（1）.
请教高手。
avatar
c*6
85 楼
只用hash function？
不解
用神马数据结构？
avatar
d*d
86 楼
hash这个random怎么搞?

，使劲的追问那种，弄得我脑子很乱。
没有答好，面试fail掉了，郁闷了好几天。
三个操作，尽量做到最优。
case复杂度还是average复杂度。然后问要更好的办法。
生一个整数，很有可能那个整数在这个collection里不存在，我说那就再产生一个，知
道找到为止，面试的人不满意。
的range很大，该怎么办之类的。

【在 K******g 的大作中提到】
: 感觉twitter的面试比较难，二面派了两个人同时面，就像一面一样，反复纠缠细节，使劲的追问那种，弄得我脑子很乱。
: 面试是上周进行的，基本的东西不说了，整个面试中真正的题目就是下面这道，由于没有答好，面试fail掉了，郁闷了好几天。
: a collection of integer,设计data structure，支持delete, insert, getRandom三个操作，尽量做到最优。
: 我先提出来BST，复杂度分别是O(logn），O（logn），O（n），然后被追问是worst case复杂度还是average复杂度。然后问要更好的办法。
: 我就说hashtable，他们就问怎么实现，还说getRandom的复杂度太高了，如果随机产生一个整数，很有可能那个整数在这个collection里不存在，我说那就再产生一个，知道找到为止，面试的人不满意。
: 然后我还说了bitmap，仍然不满意。中间纠缠了很久，还被问到collection里的整数的range很大，该怎么办之类的。
: 最后那个面试的人提醒我，考虑hash function。
: 其实面试的人的最终要求就是三个操作的复杂度都是O（1）.
: 请教高手。
avatar
s*i
87 楼
顶!
avatar
I*l
88 楼
How about using one hash table together with one array? The hash table can
be used to support O(1)-time insertions and deletions and use the array for
getRandom. Basically we maintain an array (or more precisely, a dynamic
array) of pointers for the integers in the set and a counter k for how many
integers the hash table currently contains. We will also store the index of
an element in the array in the hash table of that element. When an integer
is inserted, we add a new entry to the end of the array and increment the
counter; when delete an entry, we use hash table to retrieve its index in
the array, move the entry at the end of the array to this vacant one and
update the hash table accordingly. To get a random element, simply generate
a random integer and get its modulo k.
avatar
y*w
89 楼
bless
avatar
d*n
90 楼
sounds doable, although the insertion cannot be guaranteed O(1) due to array
resizing

for
many
of
generate

【在 I*******l 的大作中提到】
: How about using one hash table together with one array? The hash table can
: be used to support O(1)-time insertions and deletions and use the array for
: getRandom. Basically we maintain an array (or more precisely, a dynamic
: array) of pointers for the integers in the set and a counter k for how many
: integers the hash table currently contains. We will also store the index of
: an element in the array in the hash table of that element. When an integer
: is inserted, we add a new entry to the end of the array and increment the
: counter; when delete an entry, we use hash table to retrieve its index in
: the array, move the entry at the end of the array to this vacant one and
: update the hash table accordingly. To get a random element, simply generate
avatar
q*x
91 楼
on average it's O(1).

array

【在 d***n 的大作中提到】
: sounds doable, although the insertion cannot be guaranteed O(1) due to array
: resizing
:
: for
: many
: of
: generate
avatar
d*o
92 楼
May be hash table. Get O(1), Delete O(1)
Don't know it is OK to customize the Hashtable implementation. if it is, we
can define one hash function, one random function. each time call
getRandom, internally, it call random function to get the value, and also O(
1)

，使劲的追问那种，弄得我脑子很乱。
没有答好，面试fail掉了，郁闷了好几天。
三个操作，尽量做到最优。
case复杂度还是average复杂度。然后问要更好的办法。
生一个整数，很有可能那个整数在这个collection里不存在，我说那就再产生一个，知
道找到为止，面试的人不满意。
的range很大，该怎么办之类的。

【在 K******g 的大作中提到】
: 感觉twitter的面试比较难，二面派了两个人同时面，就像一面一样，反复纠缠细节，使劲的追问那种，弄得我脑子很乱。
: 面试是上周进行的，基本的东西不说了，整个面试中真正的题目就是下面这道，由于没有答好，面试fail掉了，郁闷了好几天。
: a collection of integer,设计data structure，支持delete, insert, getRandom三个操作，尽量做到最优。
: 我先提出来BST，复杂度分别是O(logn），O（logn），O（n），然后被追问是worst case复杂度还是average复杂度。然后问要更好的办法。
: 我就说hashtable，他们就问怎么实现，还说getRandom的复杂度太高了，如果随机产生一个整数，很有可能那个整数在这个collection里不存在，我说那就再产生一个，知道找到为止，面试的人不满意。
: 然后我还说了bitmap，仍然不满意。中间纠缠了很久，还被问到collection里的整数的range很大，该怎么办之类的。
: 最后那个面试的人提醒我，考虑hash function。
: 其实面试的人的最终要求就是三个操作的复杂度都是O（1）.
: 请教高手。
avatar
j*x
93 楼
均摊复杂度到O(1)
这题老题了，还是挺有意思的

array

【在 d***n 的大作中提到】
: sounds doable, although the insertion cannot be guaranteed O(1) due to array
: resizing
:
: for
: many
: of
: generate
avatar
J*n
94 楼
店面还是onsite？

，使劲的追问那种，弄得我脑子很乱。
没有答好，面试fail掉了，郁闷了好几天。
三个操作，尽量做到最优。
case复杂度还是average复杂度。然后问要更好的办法。
生一个整数，很有可能那个整数在这个collection里不存在，我说那就再产生一个，知
道找到为止，面试的人不满意。
的range很大，该怎么办之类的。

【在 K******g 的大作中提到】
: 感觉twitter的面试比较难，二面派了两个人同时面，就像一面一样，反复纠缠细节，使劲的追问那种，弄得我脑子很乱。
: 面试是上周进行的，基本的东西不说了，整个面试中真正的题目就是下面这道，由于没有答好，面试fail掉了，郁闷了好几天。
: a collection of integer,设计data structure，支持delete, insert, getRandom三个操作，尽量做到最优。
: 我先提出来BST，复杂度分别是O(logn），O（logn），O（n），然后被追问是worst case复杂度还是average复杂度。然后问要更好的办法。
: 我就说hashtable，他们就问怎么实现，还说getRandom的复杂度太高了，如果随机产生一个整数，很有可能那个整数在这个collection里不存在，我说那就再产生一个，知道找到为止，面试的人不满意。
: 然后我还说了bitmap，仍然不满意。中间纠缠了很久，还被问到collection里的整数的range很大，该怎么办之类的。
: 最后那个面试的人提醒我，考虑hash function。
: 其实面试的人的最终要求就是三个操作的复杂度都是O（1）.
: 请教高手。
avatar
a*m
95 楼
随机数看能不能碰上还有bitmap确实不是好方法。
avatar
a*n
96 楼
能不能HASHMAP加上数组？就向LINKEDHASHMAP一样。。。虽然空间重复。。
avatar
p*2
97 楼

for
many
of
generate
随机数碰到的是空的element怎么办呢？

【在 I*******l 的大作中提到】
: How about using one hash table together with one array? The hash table can
: be used to support O(1)-time insertions and deletions and use the array for
: getRandom. Basically we maintain an array (or more precisely, a dynamic
: array) of pointers for the integers in the set and a counter k for how many
: integers the hash table currently contains. We will also store the index of
: an element in the array in the hash table of that element. When an integer
: is inserted, we add a new entry to the end of the array and increment the
: counter; when delete an entry, we use hash table to retrieve its index in
: the array, move the entry at the end of the array to this vacant one and
: update the hash table accordingly. To get a random element, simply generate
avatar
H*e
98 楼
哪来的空的？

【在 p*****2 的大作中提到】
:
: for
: many
: of
: generate
: 随机数碰到的是空的element怎么办呢？
avatar
p*2
99 楼

对。应该是连续的。不错。

【在 H***e 的大作中提到】
: 哪来的空的？
avatar
A*u
100 楼
没看懂
insert时候，插入hashtable,添加到array end?
delete时候，从hashtable删除简单， 你怎么从array删除，你怎么O(1)找到那个数在
array的位置
getrandom时候， 经过很多次inerst,delete后，你的数组里元素还是连续的吗

for
many
of
generate

【在 I*******l 的大作中提到】
: How about using one hash table together with one array? The hash table can
: be used to support O(1)-time insertions and deletions and use the array for
: getRandom. Basically we maintain an array (or more precisely, a dynamic
: array) of pointers for the integers in the set and a counter k for how many
: integers the hash table currently contains. We will also store the index of
: an element in the array in the hash table of that element. When an integer
: is inserted, we add a new entry to the end of the array and increment the
: counter; when delete an entry, we use hash table to retrieve its index in
: the array, move the entry at the end of the array to this vacant one and
: update the hash table accordingly. To get a random element, simply generate
avatar
f*m
101 楼
大家有什么想法，对下面的题？

，使劲的追问那种，弄得我脑子很乱。
没有答好，面试fail掉了，郁闷了好几天。
三个操作，尽量做到最优。
case复杂度还是average复杂度。然后问要更好的办法。
生一个整数，很有可能那个整数在这个collection里不存在，我说那就再产生一个，知
道找到为止，面试的人不满意。
的range很大，该怎么办之类的。

【在 K******g 的大作中提到】
: 感觉twitter的面试比较难，二面派了两个人同时面，就像一面一样，反复纠缠细节，使劲的追问那种，弄得我脑子很乱。
: 面试是上周进行的，基本的东西不说了，整个面试中真正的题目就是下面这道，由于没有答好，面试fail掉了，郁闷了好几天。
: a collection of integer,设计data structure，支持delete, insert, getRandom三个操作，尽量做到最优。
: 我先提出来BST，复杂度分别是O(logn），O（logn），O（n），然后被追问是worst case复杂度还是average复杂度。然后问要更好的办法。
: 我就说hashtable，他们就问怎么实现，还说getRandom的复杂度太高了，如果随机产生一个整数，很有可能那个整数在这个collection里不存在，我说那就再产生一个，知道找到为止，面试的人不满意。
: 然后我还说了bitmap，仍然不满意。中间纠缠了很久，还被问到collection里的整数的range很大，该怎么办之类的。
: 最后那个面试的人提醒我，考虑hash function。
: 其实面试的人的最终要求就是三个操作的复杂度都是O（1）.
: 请教高手。
avatar
h*e
103 楼
這是經典題吧。。
avatar
Q*e
104 楼
这个很有趣
最近twitter招了不少人
上市的前兆?
相关阅读
五区的空心菜是否该拔了，长得贼慢这是什么野草漂亮、丰满、性感、高产又好吃的西红柿！求高手推荐苹果树大盒子店买来花以后有人试过ebay上的巨峰葡萄籽吗？开始养鸡请问班上有好心交换点点天津麻叶青的白菜子dallisgrass快把我逼疯了什么虫子能把玫瑰叶子吃得像筛子一样？请问有PoppySeed可以分享吗？zz 葫芦雌花出现的位置以及掐尖(打顶)的目的和效果！【擂台赛】谁的毛瓜比我的大草发黄是什么原因？找拍篇之--------四川女人(赌输了俺就是虫，赌赢了俺就是龙！和小裴打赌！香菜cilantro的问题非洲紫罗兰谢小裴，也发个五彩柿子请教个丝瓜的问题
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。