f*******4
发帖数: 1401 | 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*****s
发帖数: 758 | |
g*********s
发帖数: 1782 | 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*********s
发帖数: 1782 | 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**********d
发帖数: 4313 | |
b***u
发帖数: 22891 | |
f*******4
发帖数: 1401 | 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*******4
发帖数: 1401 | 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*********s
发帖数: 1782 | 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*********s
发帖数: 1782 | 10 random shuffle, or shuffle with pattern? i don't see the connection b/w
permutation and the algorithm correctness...
【在 f*******4 的大作中提到】
: 就是洗牌
|
|
|
b******n
发帖数: 4509 | 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*******4
发帖数: 1401 | 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*********s
发帖数: 1782 | 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*******e
发帖数: 7583 | 14 一轮电面就给onsite啦？LZ看来背景很强阿
pre con！
【在 f*******4 的大作中提到】
: 今天下午刚面的 第一轮 新鲜出炉 题目觉得还不错 有些没见过
: 1. 一组数有很多重复 找所有重复的数
: 2. 1 ~ 10000 有一个数重复了 找出来
: 3. 哈希表，如果有n个key，怎么决定哈希表的大小？n小的时候
: 怎么办 大的时候怎么办
: (我昏了。。。)
: 4. 如果有人知道了你的hash表来对你的哈希表进行攻击，让你的
: 哈希表变慢，怎么办？（假设有key从一个stream源源不断
: 地来而你不知道key的性质）
: （又昏，想了半天最后说重新建一个hash table。面试官
|
l******y
发帖数: 472 | 15 一轮电面就onsite了啊，真不错。lz是找内部人refer的么？
【在 f*******4 的大作中提到】
: 今天下午刚面的 第一轮 新鲜出炉 题目觉得还不错 有些没见过
: 1. 一组数有很多重复 找所有重复的数
: 2. 1 ~ 10000 有一个数重复了 找出来
: 3. 哈希表，如果有n个key，怎么决定哈希表的大小？n小的时候
: 怎么办 大的时候怎么办
: (我昏了。。。)
: 4. 如果有人知道了你的hash表来对你的哈希表进行攻击，让你的
: 哈希表变慢，怎么办？（假设有key从一个stream源源不断
: 地来而你不知道key的性质）
: （又昏，想了半天最后说重新建一个hash table。面试官
|
l*****a
发帖数: 14598 | 16 n很小的时候就数组就的了，不用哈西
大的时候再决定对对象怎么分类，尽可能均匀。。
【在 f*******4 的大作中提到】
: 今天下午刚面的 第一轮 新鲜出炉 题目觉得还不错 有些没见过
: 1. 一组数有很多重复 找所有重复的数
: 2. 1 ~ 10000 有一个数重复了 找出来
: 3. 哈希表，如果有n个key，怎么决定哈希表的大小？n小的时候
: 怎么办 大的时候怎么办
: (我昏了。。。)
: 4. 如果有人知道了你的hash表来对你的哈希表进行攻击，让你的
: 哈希表变慢，怎么办？（假设有key从一个stream源源不断
: 地来而你不知道key的性质）
: （又昏，想了半天最后说重新建一个hash table。面试官
|
g*********s
发帖数: 1782 | 17 如果小，用hash开销也不会大。
【在 l*****a 的大作中提到】
: n很小的时候就数组就的了，不用哈西
: 大的时候再决定对对象怎么分类，尽可能均匀。。
|
i**********e
发帖数: 1145 | 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**q
发帖数: 189 | 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*******e
发帖数: 114 | 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*******4
发帖数: 1401 | 21 恩 是找朋友refer的
我是跟HR说我有别的offer pending，叫他们加快速度的
【在 l******y 的大作中提到】
: 一轮电面就onsite了啊，真不错。lz是找内部人refer的么？
|
f*******4
发帖数: 1401 | 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!
: 一些常见面试题的答案与总结 -
|
