K******g
发帖数: 1870 | 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）.
请教高手。 |
i**********e
发帖数: 1145 | 2 我的想法是用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 |
l******e
发帖数: 12192 | 3 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）.
: 请教高手。
|
s******5
发帖数: 673 | 4 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
. |
K******g
发帖数: 1870 | 5 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）.
: 请教高手。
|
s******5
发帖数: 673 | 6
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，但是我没有想明白。
|
K******g
发帖数: 1870 | 7 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)...
|
s******5
发帖数: 673 | 8
could you elaborate why 但是getRandom很难O（1） ?
(it is ok...you are very strong!)
【在 K******g 的大作中提到】
: sorry，我搞混了，你的对，呵呵
: 但是getRandom很难O（1）
|
z***9
发帖数: 696 | 9 搂主还在面啦？看来OP还是在乎钱，twitter和脸书除了潜在的股票受益外，我真看不
出来这种专注social的公司有什么核心技术和前途，一家只言，别见怪 |
K******g
发帖数: 1870 | 10 我意思是说用linked list很难做到getRandom是O(1)，如果你有办法，说说看。
【在 s******5 的大作中提到】
:
: could you elaborate why 但是getRandom很难O（1） ?
: (it is ok...you are very strong!)
|
|
|
n******n
发帖数: 12088 | 11
，使劲的追问那种，弄得我脑子很乱。
没有答好，面试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）.
: 请教高手。
|
s*****n
发帖数: 5488 | 12 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）
|
j******c
发帖数: 294 | 13 在不考虑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）.
: 请教高手。
|
j******c
发帖数: 294 | 14 关于那个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掉了，郁闷了好
: 几天。
|
K******g
发帖数: 1870 | 15 当然要面啊，直到找到自己满意的offer为止，否则永远不会甘心
【在 z***9 的大作中提到】
: 搂主还在面啦？看来OP还是在乎钱，twitter和脸书除了潜在的股票受益外，我真看不
: 出来这种专注social的公司有什么核心技术和前途，一家只言，别见怪
|
K******g
发帖数: 1870 | 16 加入删除一个呢，你也要跟新这个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掉了，郁闷了好
: 几天。
|
j******c
发帖数: 294 | 17 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
|
i**********e
发帖数: 1145 | 18 用两个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掉了，郁闷了好
: 几天。
|
i**********e
发帖数: 1145 | 19 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.
:
: ）了
|
j******c
发帖数: 294 | 20 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
|
|
|
d******a
发帖数: 238 | 21 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.... |
h***n
发帖数: 276 | 22 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）.
: 请教高手。
|
f*******h
发帖数: 53 | 23 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) |
i**********e
发帖数: 1145 | 24 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)
|
s******5
发帖数: 673 | 25
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
:
: .
|
f*******h
发帖数: 53 | 26 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. |
i**********e
发帖数: 1145 | 27 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.
|
f*******h
发帖数: 53 | 28 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
|
i**********e
发帖数: 1145 | 29 ...
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
|
K******g
发帖数: 1870 | 30 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.
|
|
|
s*******3
发帖数: 134 | 31 lz你好，问下twitter一面和二面之间隔了多久？谢谢
【在 K******g 的大作中提到】
: insert， delete一个具体的integer，不是design 什么cache
: 3个操作都要是O（1）
: 请大家往hash function方向想把，要通过多个hashtable/list来实现，好像不可能。
: 面试的人都提醒了，hash fuction。
|
g*****e
发帖数: 282 | 32 是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
|
P*******b
发帖数: 1001 | 33 这个题讨论出结果了吗？
，使劲的追问那种，弄得我脑子很乱。
没有答好，面试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）.
: 请教高手。
|
i********s
发帖数: 133 | 34 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. |
c********t
发帖数: 5706 | 35 这个也不行啊。
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
|
c********t
发帖数: 5706 | 36 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.
|
P********l
发帖数: 452 | 37 +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.
|
i****d
发帖数: 35 | 38 我咋感觉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很大，该怎么办之类的。
|
l*********b
发帖数: 1541 | 39 恕我眼拙。
hashtable不是号称lookup/delete都是O(1)吗？
如果lookup是O(1)， getrandom也该是O(1)：
首先随机选择一个bucket,然后在这个bucket随机选择一个element. |
l*****a
发帖数: 559 | 40 怎么能够知道随机出来的bucket里面一定有element？
【在 l*********b 的大作中提到】
: 恕我眼拙。
: hashtable不是号称lookup/delete都是O(1)吗？
: 如果lookup是O(1)， getrandom也该是O(1)：
: 首先随机选择一个bucket,然后在这个bucket随机选择一个element.
|
|
|
h**********d
发帖数: 4313 | 41 我叫着这题和cache那题不差不多吗，就用hashtable + doubly linked list就可以实
现insert, delete in O(1)
至于getRandom(), 可以在insert的时候吧hashcode再用一个数组或者list存下来，然
后生产一个random数，在数组里找到相应的hashcode，再去hashtable里面，和doubly
linked list里面删？ |
l*****a
发帖数: 559 | 42 这么做，插入和删除操作也需要对'数组或者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里面删？
|
f***g
发帖数: 214 | 43 数组保存value
Hashtable保存value在数组中的位置。
插入：存在数组末尾，并将位置插入Hashtable。O(1)
随机：直接生成随机数，从数组中读。O(1)
删除：首先删除相应的元素，然后把数组最后一位移动到删除的位置并更新位置。O(1) |
i**********e
发帖数: 1145 | 44 赞 简单又有效的解法！
你的解法是跟 ineedlexus 一样的。
最关键的是可以利用数组来储存元素，而删除又不需要挪动之后的元素。
只要把最后的元素填补于被删除的位置即可。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
1)
【在 f***g 的大作中提到】
: 数组保存value
: Hashtable保存value在数组中的位置。
: 插入：存在数组末尾，并将位置插入Hashtable。O(1)
: 随机：直接生成随机数，从数组中读。O(1)
: 删除：首先删除相应的元素，然后把数组最后一位移动到删除的位置并更新位置。O(1)
|
P********l
发帖数: 452 | |
m*******d
发帖数: 9 | 46 删除步骤中，把数组最后一位移动到删除的位置并更新位置，这时那个被移动的元素的
value就变了吧，在hash表中也相应的会变
1)
【在 f***g 的大作中提到】
: 数组保存value
: Hashtable保存value在数组中的位置。
: 插入：存在数组末尾，并将位置插入Hashtable。O(1)
: 随机：直接生成随机数，从数组中读。O(1)
: 删除：首先删除相应的元素，然后把数组最后一位移动到删除的位置并更新位置。O(1)
|
P********l
发帖数: 452 | 47 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? |
s******e
发帖数: 108 | 48 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;
}
} |
i**********e
发帖数: 1145 | 49 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.
|
c********t
发帖数: 5706 | 50 赞！
如果有duplicate value怎么办？
1)
【在 f***g 的大作中提到】
: 数组保存value
: Hashtable保存value在数组中的位置。
: 插入：存在数组末尾，并将位置插入Hashtable。O(1)
: 随机：直接生成随机数，从数组中读。O(1)
: 删除：首先删除相应的元素，然后把数组最后一位移动到删除的位置并更新位置。O(1)
|
|
|
c********t
发帖数: 5706 | 51 是的，感谢两位给出codes的童鞋。能不能说一下如果有duplicate value怎么办？
【在 i**********e 的大作中提到】
: Last element should be rndArray[size-1] bah...
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
|
i**********e
发帖数: 1145 | 52 我也在想这个问题，
有个解决方法，就是 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怎么办？
|
c********t
发帖数: 5706 | 53 不错，这个可行！
【在 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
|
P********l
发帖数: 452 | 54 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
|
s******e
发帖数: 108 | 55 可以用 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();
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
|
i**********e
发帖数: 1145 | 56 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();
|
j********x
发帖数: 2330 | 57 this doesnt support O(1) getRandom()
【在 l******e 的大作中提到】
: double linked list + hash
|
j********x
发帖数: 2330 | 58 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... |
P********l
发帖数: 452 | 59 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...
|
j********x
发帖数: 2330 | 60 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
: ..
|
|
|
P********l
发帖数: 452 | |
z***e
发帖数: 5393 | 62 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的公司有什么核心技术和前途，一家只言，别见怪
|
j*****u
发帖数: 1133 | 63 说的好，必须要顶！
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
|
i****d
发帖数: 35 | 64 这个就是Ullman Set啊。。。。
1)
【在 f***g 的大作中提到】
: 数组保存value
: Hashtable保存value在数组中的位置。
: 插入：存在数组末尾，并将位置插入Hashtable。O(1)
: 随机：直接生成随机数，从数组中读。O(1)
: 删除：首先删除相应的元素，然后把数组最后一位移动到删除的位置并更新位置。O(1)
|
c**********6
发帖数: 105 | 65 只用hash function？
不解
用神马数据结构？ |
d*******d
发帖数: 2050 | 66 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）.
: 请教高手。
|
s****i
发帖数: 661 | |
I*******l
发帖数: 203 | 68 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. |
y******w
发帖数: 2220 | |
d***n
发帖数: 65 | 70 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
|
|
|
q****x
发帖数: 7404 | 71 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
|
d*****o
发帖数: 28 | 72 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）.
: 请教高手。
|
j********x
发帖数: 2330 | 73 均摊复杂度到O(1)
这题老题了，还是挺有意思的
array
【在 d***n 的大作中提到】
: sounds doable, although the insertion cannot be guaranteed O(1) due to array
: resizing
:
: for
: many
: of
: generate
|
K******g
发帖数: 1870 | 74 感觉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）.
请教高手。 |
c**********6
发帖数: 105 | 75 只用hash function？
不解
用神马数据结构？ |
d*******d
发帖数: 2050 | 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）.
: 请教高手。
|
s****i
发帖数: 661 | |
I*******l
发帖数: 203 | 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. |
y******w
发帖数: 2220 | |
d***n
发帖数: 65 | 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
|
|
|
q****x
发帖数: 7404 | 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
|
d*****o
发帖数: 28 | 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）.
: 请教高手。
|
j********x
发帖数: 2330 | 83 均摊复杂度到O(1)
这题老题了，还是挺有意思的
array
【在 d***n 的大作中提到】
: sounds doable, although the insertion cannot be guaranteed O(1) due to array
: resizing
:
: for
: many
: of
: generate
|
J*********n
发帖数: 370 | 84 店面还是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）.
: 请教高手。
|
a********m
发帖数: 15480 | 85 随机数看能不能碰上还有bitmap确实不是好方法。 |
a*****n
发帖数: 158 | 86 能不能HASHMAP加上数组？就向LINKEDHASHMAP一样。。。虽然空间重复。。 |
p*****2
发帖数: 21240 | 87
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
|
H***e
发帖数: 476 | 88 哪来的空的？
【在 p*****2 的大作中提到】
:
: for
: many
: of
: generate
: 随机数碰到的是空的element怎么办呢？
|
p*****2
发帖数: 21240 | 89
对。应该是连续的。不错。
【在 H***e 的大作中提到】
: 哪来的空的？
|
A**u
发帖数: 2458 | 90 没看懂
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
|
|
|
f*********m
发帖数: 726 | 91 大家有什么想法，对下面的题？
，使劲的追问那种，弄得我脑子很乱。
没有答好，面试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）.
: 请教高手。
|
l*****a
发帖数: 559 | |
h*******e
发帖数: 1377 | |
Q*******e
发帖数: 939 | 94 这个很有趣
最近twitter招了不少人
上市的前兆? |
