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