Google电面面经 + onsite求祝福 - 未名空间MITBBS历史存档

Google电面面经 + onsite求祝福# JobHunting - 待字闺中

f*42011-02-15 08:02

1 楼

今天下午刚面的第一轮新鲜出炉题目觉得还不错有些没见过
1. 一组数有很多重复找所有重复的数
2. 1 ~ 10000 有一个数重复了找出来
3. 哈希表，如果有n个key，怎么决定哈希表的大小？n小的时候
怎么办大的时候怎么办
(我昏了。。。)
4. 如果有人知道了你的hash表来对你的哈希表进行攻击，让你的
哈希表变慢，怎么办？（假设有key从一个stream源源不断
地来而你不知道key的性质）
（又昏，想了半天最后说重新建一个hash table。面试官
说可以。）
5. 写代码：对一个数组shuffle
follow up：为什么n个数共有n!个不同的permutation
（很汗。。。）
follow up：为什么你用的shuffle算法是正确的
（和permutation是有关系的）
3个小时后收到HR的onsite邀请求祝福

P*s2011-02-15 08:02

2 楼

bless~

g*s2011-02-15 08:02

3 楼

what u mean by "很多重复", a lot of numbers having a couple duplicates, or
a couple of numbers having a lot of duplicates, or both?
anyway, hash.
assuming you have 10001 numbers ranging in [1..10000], with exactly one
occurs twice? sum(X) - sum(1,10000).
load factor.
universal hashing.

【在 f*******4 的大作中提到】

: 今天下午刚面的第一轮新鲜出炉题目觉得还不错有些没见过
: 1. 一组数有很多重复找所有重复的数
: 2. 1 ~ 10000 有一个数重复了找出来
: 3. 哈希表，如果有n个key，怎么决定哈希表的大小？n小的时候
: 怎么办大的时候怎么办
: (我昏了。。。)
: 4. 如果有人知道了你的hash表来对你的哈希表进行攻击，让你的
: 哈希表变慢，怎么办？（假设有key从一个stream源源不断
: 地来而你不知道key的性质）
: （又昏，想了半天最后说重新建一个hash table。面试官

g*s2011-02-15 08:02

4 楼

5. 写代码：对一个数组shuffle
what u mean by "shuffle" here, std::random_shuffle()?
follow up：为什么n个数共有n!个不同的permutation
（很汗。。。）
follow up：为什么你用的shuffle算法是正确的
（和permutation是有关系的）
no idea about what the shuffle algorithm is and thus no comments on
correctness.

or
one

【在 g*********s 的大作中提到】

:
: what u mean by "很多重复", a lot of numbers having a couple duplicates, or
: a couple of numbers having a lot of duplicates, or both?
: anyway, hash.
: assuming you have 10001 numbers ranging in [1..10000], with exactly one
: occurs twice? sum(X) - sum(1,10000).
: load factor.
: universal hashing.

h*d2011-02-15 08:02

5 楼

bless

b*u2011-02-15 08:02

6 楼

bless

f*42011-02-15 08:02

7 楼

就是洗牌

【在 g*********s 的大作中提到】

: 5. 写代码：对一个数组shuffle
: what u mean by "shuffle" here, std::random_shuffle()?
: follow up：为什么n个数共有n!个不同的permutation
: （很汗。。。）
: follow up：为什么你用的shuffle算法是正确的
: （和permutation是有关系的）
: no idea about what the shuffle algorithm is and thus no comments on
: correctness.
:
: or

f*42011-02-15 08:02

8 楼

1. 对就是hash
2. 我说了这个也说了XOR 面试官说也行但不是他想的答案。对了这个题不允许用其
他存储空间。
3. 好像不是这个意思。n是固定的。只是问在n的大小是多少时候分别怎么选。
4. 咳这个俺真不懂了。。。
我觉得答得一般般...

【在 g*********s 的大作中提到】

: 5. 写代码：对一个数组shuffle
: what u mean by "shuffle" here, std::random_shuffle()?
: follow up：为什么n个数共有n!个不同的permutation
: （很汗。。。）
: follow up：为什么你用的shuffle算法是正确的
: （和permutation是有关系的）
: no idea about what the shuffle algorithm is and thus no comments on
: correctness.
:
: or

g*s2011-02-15 08:02

9 楼

how come xor works? that one is for all but one twice, i believe.

【在 f*******4 的大作中提到】

: 1. 对就是hash
: 2. 我说了这个也说了XOR 面试官说也行但不是他想的答案。对了这个题不允许用其
: 他存储空间。
: 3. 好像不是这个意思。n是固定的。只是问在n的大小是多少时候分别怎么选。
: 4. 咳这个俺真不懂了。。。
: 我觉得答得一般般...

g*s2011-02-15 08:02

10 楼

random shuffle, or shuffle with pattern? i don't see the connection b/w
permutation and the algorithm correctness...

【在 f*******4 的大作中提到】

: 就是洗牌

b*n2011-02-15 08:02

11 楼

you xor all the number and then 1-10000

用其

【在 g*********s 的大作中提到】

: random shuffle, or shuffle with pattern? i don't see the connection b/w
: permutation and the algorithm correctness...

f*42011-02-15 08:02

12 楼

random shuffle
可以用类似random shuffle的办法，就是每个人和它后面的随机的一个人
swap，来产生所有permutation，不是么？

【在 g*********s 的大作中提到】

: random shuffle, or shuffle with pattern? i don't see the connection b/w
: permutation and the algorithm correctness...

g*s2011-02-15 08:02

13 楼

interesting solution. i see two advantages of this:
1. although it's a two-pass solution, xor is much faster than addition.
2. no overflow concerns.

【在 b******n 的大作中提到】

: you xor all the number and then 1-10000
:
: 用其

r*e2011-02-15 08:02

14 楼

一轮电面就给onsite啦？LZ看来背景很强阿
pre con！

【在 f*******4 的大作中提到】

: 今天下午刚面的第一轮新鲜出炉题目觉得还不错有些没见过
: 1. 一组数有很多重复找所有重复的数
: 2. 1 ~ 10000 有一个数重复了找出来
: 3. 哈希表，如果有n个key，怎么决定哈希表的大小？n小的时候
: 怎么办大的时候怎么办
: (我昏了。。。)
: 4. 如果有人知道了你的hash表来对你的哈希表进行攻击，让你的
: 哈希表变慢，怎么办？（假设有key从一个stream源源不断
: 地来而你不知道key的性质）
: （又昏，想了半天最后说重新建一个hash table。面试官

l*y2011-02-15 08:02

15 楼

一轮电面就onsite了啊，真不错。lz是找内部人refer的么？

【在 f*******4 的大作中提到】

: 今天下午刚面的第一轮新鲜出炉题目觉得还不错有些没见过
: 1. 一组数有很多重复找所有重复的数
: 2. 1 ~ 10000 有一个数重复了找出来
: 3. 哈希表，如果有n个key，怎么决定哈希表的大小？n小的时候
: 怎么办大的时候怎么办
: (我昏了。。。)
: 4. 如果有人知道了你的hash表来对你的哈希表进行攻击，让你的
: 哈希表变慢，怎么办？（假设有key从一个stream源源不断
: 地来而你不知道key的性质）
: （又昏，想了半天最后说重新建一个hash table。面试官

l*a2011-02-15 08:02

16 楼

n很小的时候就数组就的了，不用哈西
大的时候再决定对对象怎么分类，尽可能均匀。。

【在 f*******4 的大作中提到】

: 今天下午刚面的第一轮新鲜出炉题目觉得还不错有些没见过
: 1. 一组数有很多重复找所有重复的数
: 2. 1 ~ 10000 有一个数重复了找出来
: 3. 哈希表，如果有n个key，怎么决定哈希表的大小？n小的时候
: 怎么办大的时候怎么办
: (我昏了。。。)
: 4. 如果有人知道了你的hash表来对你的哈希表进行攻击，让你的
: 哈希表变慢，怎么办？（假设有key从一个stream源源不断
: 地来而你不知道key的性质）
: （又昏，想了半天最后说重新建一个hash table。面试官

g*s2011-02-15 08:02

17 楼

如果小，用hash开销也不会大。

【在 l*****a 的大作中提到】

: n很小的时候就数组就的了，不用哈西
: 大的时候再决定对对象怎么分类，尽可能均匀。。

i*e2011-02-15 08:02

18 楼

1.Hash 是对的
2.第二题可以如果只要找其中一个重复数而不用额外空间，这题 Programming Pearls
的习题提到了，提示用 Binary search，很经典的解法 :)
3. 主要看 hash 的分布. 如果分布均匀的话，可以取平均值，使得 collision 尽量减
低。
4. another hash table in hash table?
5. knuth shuffle. 要证明这个 shuffle 结果让每个 permutation 都 equally
likely 的话，可以画 shuffle generation tree 出来，证明每一个树的节点都是 1/N!
祝福 LZ!
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 f*******4 的大作中提到】

: 今天下午刚面的第一轮新鲜出炉题目觉得还不错有些没见过
: 1. 一组数有很多重复找所有重复的数
: 2. 1 ~ 10000 有一个数重复了找出来
: 3. 哈希表，如果有n个key，怎么决定哈希表的大小？n小的时候
: 怎么办大的时候怎么办
: (我昏了。。。)
: 4. 如果有人知道了你的hash表来对你的哈希表进行攻击，让你的
: 哈希表变慢，怎么办？（假设有key从一个stream源源不断
: 地来而你不知道key的性质）
: （又昏，想了半天最后说重新建一个hash table。面试官

m*q2011-02-15 08:02

19 楼

第一个是不是可以用bit map数组做统计，每个数字
对应两个bit，表示没出现，出现一次，出现多次这三个状态。
hash的话可能会有冲突的情况吧？

Pearls
/N!

【在 i**********e 的大作中提到】

: 1.Hash 是对的
: 2.第二题可以如果只要找其中一个重复数而不用额外空间，这题 Programming Pearls
: 的习题提到了，提示用 Binary search，很经典的解法 :)
: 3. 主要看 hash 的分布. 如果分布均匀的话，可以取平均值，使得 collision 尽量减
: 低。
: 4. another hash table in hash table?
: 5. knuth shuffle. 要证明这个 shuffle 结果让每个 permutation 都 equally
: likely 的话，可以画 shuffle generation tree 出来，证明每一个树的节点都是 1/N!
: 祝福 LZ!
: 一些常见面试题的答案与总结 -

L*e2011-02-15 08:02

20 楼

不太懂，第二题怎么用Binary Search, 还是要先sort吧.

Pearls
/N!

【在 i**********e 的大作中提到】

: 1.Hash 是对的
: 2.第二题可以如果只要找其中一个重复数而不用额外空间，这题 Programming Pearls
: 的习题提到了，提示用 Binary search，很经典的解法 :)
: 3. 主要看 hash 的分布. 如果分布均匀的话，可以取平均值，使得 collision 尽量减
: 低。
: 4. another hash table in hash table?
: 5. knuth shuffle. 要证明这个 shuffle 结果让每个 permutation 都 equally
: likely 的话，可以画 shuffle generation tree 出来，证明每一个树的节点都是 1/N!
: 祝福 LZ!
: 一些常见面试题的答案与总结 -

f*42011-02-15 08:02

21 楼

恩是找朋友refer的
我是跟HR说我有别的offer pending，叫他们加快速度的

【在 l******y 的大作中提到】

: 一轮电面就onsite了啊，真不错。lz是找内部人refer的么？

f*42011-02-15 08:02

22 楼

2. 唉我PP都没时间看才开了个头惭愧
3. 去平均值？神马意思？
4. 我说了这个也说了多层hash
5. 恩这个题其实还挺精妙的

Pearls
/N!

【在 i**********e 的大作中提到】

: 1.Hash 是对的
: 2.第二题可以如果只要找其中一个重复数而不用额外空间，这题 Programming Pearls
: 的习题提到了，提示用 Binary search，很经典的解法 :)
: 3. 主要看 hash 的分布. 如果分布均匀的话，可以取平均值，使得 collision 尽量减
: 低。
: 4. another hash table in hash table?
: 5. knuth shuffle. 要证明这个 shuffle 结果让每个 permutation 都 equally
: likely 的话，可以画 shuffle generation tree 出来，证明每一个树的节点都是 1/N!
: 祝福 LZ!
: 一些常见面试题的答案与总结 -