w****x
发帖数: 2483 | 1 /*
Given a collection of integer, design a class that supports:
add(data) - insert an element
delete(data) - delete an element
getRandom(data) - return a random element
*/
class Solution
{
public:
void add(int x)
{
if (m_mp.find(x) != m_mp.end())
return;
m_vec.push_back(x);
m_mp[x] = m_vec.size()-1;
}
void del(int x)
{
if (m_mp.find(x) == m_mp.end())
return;
int index = m_mp[x];
m_mp.erase(m_mp.find(x));
... 阅读全帖 |
|
w****x
发帖数: 2483 | 2 /*
Given a collection of integer, design a class that supports:
add(data) - insert an element
delete(data) - delete an element
getRandom(data) - return a random element
*/
class Solution
{
public:
void add(int x)
{
if (m_mp.find(x) != m_mp.end())
return;
m_vec.push_back(x);
m_mp[x] = m_vec.size()-1;
}
void del(int x)
{
if (m_mp.find(x) == m_mp.end())
return;
int index = m_mp[x];
m_mp.erase(m_mp.find(x));
... 阅读全帖 |
|
K******g
发帖数: 1870 | 3 感觉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 | 4 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).
... 阅读全帖 |
|
K******g
发帖数: 1870 | 5 感觉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*******t
发帖数: 7549 | 6 F
电面和onsite都是在西雅图本地面的。此分部是在downtown附近租的两层，有近360度
的景观，十分漂亮。分部总共有不到200人，很多是从微软来的，从A挖来的倒不多，原
因不明。午饭质量不错，小分部就不指望有中餐咯。
电面
1. 国人大哥，问了几个常见题，最难的题具体细节记不清了，大概是01矩阵上的DFS，
随便聊了会儿直接拿到onsite。
Onsite
1. 白女，亚马逊manager出身的女工程师，主问culture fit问题，比如为什么想来FB
。Coding题是恶心的罗马数字。因为鄙视这道题所以没在leetcode上刷过，还好是简单
题，很快写出来了。
2. 一个搞后端处理data的中国哥们，问sort linked list。随手写了个merge sort过
关，merge的时候没用dummy node方法，if语句用的很多，比较蛋疼。讨论了一下具体
的算法复杂度，直接背答案的人估计会被考倒。所以说做面试题的目的主要还是掌握算
法并能灵活用于解题，不太可能所有题都能练到随手就写出最优算法bug free的程度。
3. 午饭不算正式面试，跟一个呆了六七年的fron... 阅读全帖 |
|
o*q
发帖数: 630 | 7 # Title Editorial Acceptance Difficulty Frequency
1
Two Sum 28.3% Easy
292
Nim Game 54.4% Easy
344
Reverse String 57.3% Easy
136
Single Number 52.2% Easy
2
Add Two Numbers 25.6% Medium
371
Sum of Two Integers 51.6% Easy
4
Median of Two Sorted Arrays
20.4% Hard
6
ZigZag Conversion 25.6% Easy
13
Roman to Integer 42.7% Easy
237
... 阅读全帖 |
|
i**********e
发帖数: 1145 | 8 我的想法是用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 |
|
s******5
发帖数: 673 | 9 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 | 10 ihasleetcode： delete肯定是delete一个具体的元素
larrabee ： 那个是cache的实现方法吧？怎么实现getRandom，并且是O(1)？
sweet845： Linked list肯定不行啊，insert和delete全部都是O（n）
面试的人提醒了，考虑hash function，但是我没有想明白。 |
|
K******g
发帖数: 1870 | 11 sorry，我搞混了，你的对，呵呵
但是getRandom很难O（1） |
|
s******5
发帖数: 673 | 12
could you elaborate why 但是getRandom很难O（1） ?
(it is ok...you are very strong!) |
|
K******g
发帖数: 1870 | 13 我意思是说用linked list很难做到getRandom是O(1)，如果你有办法，说说看。 |
|
n******n
发帖数: 12088 | 14
，使劲的追问那种，弄得我脑子很乱。
没有答好，面试fail掉了，郁闷了好几天。
三个操作，尽量做到最优。
what is getRandom？
case复杂度还是average复杂度。然后问要更好的办法。
balanced bst.
生一个整数，很有可能那个整数在这个collection里不存在，我说那就再产生一个，知
道找到为止，面试的人不满意。
的range很大，该怎么办之类的。 |
|
s*****n
发帖数: 5488 | 15 then you can use linked list as an array. pointer is the index of the
element.
getrandom is trivial. |
|
j******c
发帖数: 294 | 16 在不考虑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
发帖数: 1870 | 17 加入删除一个呢，你也要跟新这个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 |
|
d******a
发帖数: 238 | 19 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.... |
|
f*******h
发帖数: 53 | 20 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****d
发帖数: 35 | 21 我咋感觉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是已有元素的数目 |
|
l*********b
发帖数: 1541 | 22 恕我眼拙。
hashtable不是号称lookup/delete都是O(1)吗？
如果lookup是O(1)， getrandom也该是O(1)：
首先随机选择一个bucket,然后在这个bucket随机选择一个element. |
|
h**********d
发帖数: 4313 | 23 我叫着这题和cache那题不差不多吗，就用hashtable + doubly linked list就可以实
现insert, delete in O(1)
至于getRandom(), 可以在insert的时候吧hashcode再用一个数组或者list存下来，然
后生产一个random数，在数组里找到相应的hashcode，再去hashtable里面，和doubly
linked list里面删？ |
|
i**********e
发帖数: 1145 | 24 我也在想这个问题，
有个解决方法，就是 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 |
|
j********x
发帖数: 2330 | 25 this doesnt support O(1) getRandom() |
|
P********l
发帖数: 452 | 26 post #1:
"我就说hashtable，他们就问怎么实现，还说getRandom的复杂度太高了，如果随机产
生一个整数，很有可能那个整数在这个collection里不存在，我说那就再产生一个，知
道找到为止，面试的人不满意。"
the
not
.. |
|
I*******l
发帖数: 203 | 27 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 ... 阅读全帖 |
|
d*****o
发帖数: 28 | 28 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很大，该怎么办之类的。 |
|
I*******l
发帖数: 203 | 29 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 ... 阅读全帖 |
|
d*****o
发帖数: 28 | 30 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很大，该怎么办之类的。 |
|
A**u
发帖数: 2458 | 31 没看懂
insert时候，插入hashtable,添加到array end?
delete时候，从hashtable删除简单， 你怎么从array删除，你怎么O(1)找到那个数在
array的位置
getrandom时候， 经过很多次inerst,delete后，你的数组里元素还是连续的吗
for
many
of
generate |
|
b**a
发帖数: 62 | 32 一個疑似老印，兩個題
有一個map的interface，要實現get, put, remove, getRandom
可以用任何語言 我用的java 然後可以用任何java api
我就直接用了一個hashmap
remove那個我說return是要boolean還是object 他說up to you，我就隨便搞了個
boolean
如果hashset.remove(k)是null，就return false 結果他指出來如果那個k對於的value
本來就是null怎麼辦 我剛說that could be a problem 他就說that's fine 沒讓我接
著改
第二個有n台機器 第一台有一個大文件size f，寫pseudo code怎麼transmit到所有機
器上 然後問了時間複雜度
剩下就問問現在的工作 喜歡做什麼樣的工作
感覺也沒問什麽算法 尤其第一個不知道考點在哪
大家能給分析下不 |
|
t**********h
发帖数: 2273 | 33 膜拜面g的牛人
一個疑似老印，兩個題有一個map的interface，要實現get, put, remove, getRandom
可以用任何語言 我用的java 然後可以用任何java api........
★ Sent from iPhone App: iReader Mitbbs Lite 7.56 |
|
b**a
发帖数: 62 | 34 這樣啊 當時也沒想到這麼多 在getRandom的時候我是先getValues然後得到一個array
然後在生成一個隨機數 不知道這樣行不行 |
|
w****x
发帖数: 2483 | 35
map太抽象了, 可以用RB-tree也可以用hash, 这题考在getRandom和其他操作都要O(1) |
|
z****e
发帖数: 54598 | 36 第一个你应该还需要写一个getRandom的实现方法
考点应该在keyset();还有values();还有random();这三个上
然后针对keyset这个collection，要toarray，然后要用math.randon()取出一个随机数
然后转换这个随机数到某个整数，然后再从toarry的结果list中给get出来
value |
|
j*****o
发帖数: 394 | 37 这个题有朋友面过
K差不多算是第K次插入的数吧
class mystruct
{
public:
int a[100];
int b[100]; //numbers should be in [0, 99]
int count; //count of valid numbers in a[]
mystruct()
{
count=0;
for (int i=0; i<100; i++) { a[i]=0; b[i]=-1;}
}
void insert(int x) { a[count]=x; b[x]=count; count++;}
void remove(int x) { int tmp=b[x]; b[x]=-1; a[tmp]=a[count-1]; b[a[tmp]]
=tmp; count--;}
int getrandom() { srand(time(0)); return a[rand()%count];}
}; |
|
g*******r
发帖数: 44 | 38 google 店面
就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
spanner那篇论文.
twitter 店面
第一轮.
1.如何判断一棵树是BST.
2.用2个栈实现队列。
第二轮
1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
2. 关于图的简单BFS的一道题。
然后就是onsite了，这个我真的是是准备有问题，第一天面的google, 第二天面
twitter, 去google面试第一天坐了8个小时飞机，到了都晚上8点了，搞得第二天不在
状态了。
google onsite
第一轮，一个front end的人就问了一道题，写个程序，接收客户端的请求，如何保证
每秒钟只发送10个请求给服务器。这题他的意思我现在都不明白，他的意思是用平均速
度，看当前请求的时间和上个请求的时间相差多少，如果大于0.1秒就转发，否则就丢
弃。我觉得有问题啊，然后就郁闷了
。。
第二轮，一个印度哥们问如何用mutex和condition variable实现读写锁。这个好久没
碰了，答得也不好。
... 阅读全帖 |
|
j******2
发帖数: 362 | 39
什么东西find, insert, delete,getrandom? vector? |
|
w********p
发帖数: 948 | 40 看的我心惊胆寒。
两个面试里都有我的盲点，就是一个字都写不出的那种。
更不要说bug free
电面第一题，看了下答案。思路上和我想的差不多。find O(1) 只有hash了， insert,
getRandom, 要用array
delete O(2) 在array 里可以。
不过当时电话里写这题的code，真的头大。
楼主遇到的题都是貌似不难，下手不易的题。
谢谢楼主分享。再接再厉，拿到好的offer. |
|
g*******r
发帖数: 44 | 41 google 店面
就是如何实现find, insert, delete, getRandom 都是O(1)，然后扯了下google的
spanner那篇论文.
twitter 店面
第一轮.
1.如何判断一棵树是BST.
2.用2个栈实现队列。
第二轮
1.讨论hash table和如何解决collision, 各种解决策略的优缺点.
2. 关于图的简单BFS的一道题。
然后就是onsite了，这个我真的是是准备有问题，第一天面的google, 第二天面
twitter, 去google面试第一天坐了8个小时飞机，到了都晚上8点了，搞得第二天不在
状态了。
google onsite
第一轮，一个front end的人就问了一道题，写个程序，接收客户端的请求，如何保证
每秒钟只发送10个请求给服务器。这题他的意思我现在都不明白，他的意思是用平均速
度，看当前请求的时间和上个请求的时间相差多少，如果大于0.1秒就转发，否则就丢
弃。我觉得有问题啊，然后就郁闷了
。。
第二轮，一个印度哥们问如何用mutex和condition variable实现读写锁。这个好久没
碰了，答得也不好。
... 阅读全帖 |
|
j******2
发帖数: 362 | 42
什么东西find, insert, delete,getrandom? vector? |
|
w********p
发帖数: 948 | 43 看的我心惊胆寒。
两个面试里都有我的盲点，就是一个字都写不出的那种。
更不要说bug free
电面第一题，看了下答案。思路上和我想的差不多。find O(1) 只有hash了， insert,
getRandom, 要用array
delete O(2) 在array 里可以。
不过当时电话里写这题的code，真的头大。
楼主遇到的题都是貌似不难，下手不易的题。
谢谢楼主分享。再接再厉，拿到好的offer. |
|
p*****e
发帖数: 537 | 44 请问这道题怎么做？“如何实现find, insert, delete, getRandom 都是O(1)” |
|
s****r
发帖数: 28 | 45 大家有什么思路么？
How would you define a data structure that stores a set of values (i.e., a
value cannot appear more than one time), and implements the following
functions:
add(p)--adds the value p to the set
delete(p)--removes the value p from the set
getrandom()--returns a random value from the set (all items should be
equally likely). (Assume you have access to some nice random() function.) |
|
f*****7
发帖数: 92 | 46 BST可以嘛？
add，delete就是常规操作
getRandom，就用蓄水池抽样，inorder一次 |
|
p*****2
发帖数: 21240 | 47
getrandom的复杂度应该是O（1）的，虽然LZ忘记说明了。 |
|
x*******6
发帖数: 262 | 48 这个跟设计一个类，支持add delete getRandom时间复杂度为O(1)是一个套路吧，用一
个hashmap和一个array |
|
G****A
发帖数: 4160 | 49 之前讨论过，不过找不到原帖了。请大家给点思路
考虑过用map寻址, vector存数据. 但是这样没法handle duplicated key的情况。难道
还要自己implement hash with collision resolution? |
|
|
