Redian新闻
>
Google电面面经 + onsite求祝福
avatar
Google电面面经 + onsite求祝福# JobHunting - 待字闺中
f*4
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邀请 求祝福
avatar
P*s
2
bless~
avatar
g*s
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。面试官

avatar
g*s
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.

avatar
h*d
5
bless
avatar
b*u
6
bless
avatar
f*4
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

avatar
f*4
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

avatar
g*s
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. 咳 这个俺真不懂了。。。
: 我觉得答得一般般...

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

【在 f*******4 的大作中提到】
: 就是洗牌
avatar
b*n
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...

avatar
f*4
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...

avatar
g*s
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
:
: 用其

avatar
r*e
14
一轮电面就给onsite啦?LZ看来背景很强阿
pre con!

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

avatar
l*y
15
一轮电面就onsite了啊,真不错。lz是找内部人refer的么?

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

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

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

avatar
g*s
17
如果小,用hash开销也不会大。

【在 l*****a 的大作中提到】
: n很小的时候就数组就的了,不用哈西
: 大的时候再决定对对象怎么分类,尽可能均匀。。

avatar
i*e
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。面试官

avatar
m*q
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!
: 一些常见面试题的答案与总结 -

avatar
L*e
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!
: 一些常见面试题的答案与总结 -

avatar
f*4
21
恩 是找朋友refer的
我是跟HR说我有别的offer pending,叫他们加快速度的

【在 l******y 的大作中提到】
: 一轮电面就onsite了啊,真不错。lz是找内部人refer的么?
avatar
f*4
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!
: 一些常见面试题的答案与总结 -

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。