f*****u
发帖数: 308 | 1 两道题来自不同的公司.
题一:
有N个node,每个都不停的向外发送timestamps,具体发送哪些timestamp是每个node决定
的,从其他node来说是随机的.现在要收集这些node发送的所有timestamp.如果某个
timestamp被发现从超过99%的node上发送出来,记录下来.需要怎么做?这些timestamp很
多,是不能完全放进去内存里面的.如果node非常多,怎么scale?
题二:
一个mxn的grid,要在里面随机生成K个格子.最直接的方法是一个for循环从1到K生成K个
随机格子,但是对每个当前生成的格子,需要检查前面是否已经生成过了,如果重复了需
要重新生成,这样时间上就超过了O(K).有方法在O(K)时间内实现吗? | s*i
发帖数: 5025 | 2 第二个用hashset记载生成过的
【在 f*****u 的大作中提到】
: 两道题来自不同的公司.
: 题一:
: 有N个node,每个都不停的向外发送timestamps,具体发送哪些timestamp是每个node决定
: 的,从其他node来说是随机的.现在要收集这些node发送的所有timestamp.如果某个
: timestamp被发现从超过99%的node上发送出来,记录下来.需要怎么做?这些timestamp很
: 多,是不能完全放进去内存里面的.如果node非常多,怎么scale?
: 题二:
: 一个mxn的grid,要在里面随机生成K个格子.最直接的方法是一个for循环从1到K生成K个
: 随机格子,但是对每个当前生成的格子,需要检查前面是否已经生成过了,如果重复了需
: 要重新生成,这样时间上就超过了O(K).有方法在O(K)时间内实现吗?
| p*****2
发帖数: 21240 | 3
第一题的解决方案就是kafka+spark+cassandra可以搞定了。
【在 f*****u 的大作中提到】
: 两道题来自不同的公司.
: 题一:
: 有N个node,每个都不停的向外发送timestamps,具体发送哪些timestamp是每个node决定
: 的,从其他node来说是随机的.现在要收集这些node发送的所有timestamp.如果某个
: timestamp被发现从超过99%的node上发送出来,记录下来.需要怎么做?这些timestamp很
: 多,是不能完全放进去内存里面的.如果node非常多,怎么scale?
: 题二:
: 一个mxn的grid,要在里面随机生成K个格子.最直接的方法是一个for循环从1到K生成K个
: 随机格子,但是对每个当前生成的格子,需要检查前面是否已经生成过了,如果重复了需
: 要重新生成,这样时间上就超过了O(K).有方法在O(K)时间内实现吗?
| p*****2
发帖数: 21240 | 4
二维矩阵就是一维数组，参看经典的洗牌技术。
【在 f*****u 的大作中提到】
: 两道题来自不同的公司.
: 题一:
: 有N个node,每个都不停的向外发送timestamps,具体发送哪些timestamp是每个node决定
: 的,从其他node来说是随机的.现在要收集这些node发送的所有timestamp.如果某个
: timestamp被发现从超过99%的node上发送出来,记录下来.需要怎么做?这些timestamp很
: 多,是不能完全放进去内存里面的.如果node非常多,怎么scale?
: 题二:
: 一个mxn的grid,要在里面随机生成K个格子.最直接的方法是一个for循环从1到K生成K个
: 随机格子,但是对每个当前生成的格子,需要检查前面是否已经生成过了,如果重复了需
: 要重新生成,这样时间上就超过了O(K).有方法在O(K)时间内实现吗?
| f*****u
发帖数: 308 | 5 大牛你就别在这儿开玩笑了吧.我是真心来请教一些可行方案的.你面试这么说必死无疑
的吧.很明显面试官想听的是一套lower level的解决方案的.
【在 p*****2 的大作中提到】
:
: 二维矩阵就是一维数组，参看经典的洗牌技术。
| f*****u
发帖数: 308 | 6 大牛你是说Fisher–Yates shuffle算法?能再稍微解释下这里怎么用不?
【在 p*****2 的大作中提到】
:
: 二维矩阵就是一维数组，参看经典的洗牌技术。
| p*****2
发帖数: 21240 | 7
这个方案应该是工业界认可的。如果面试官希望听到一些low level的，你可以给他们
讲讲到底地层是如何工作的。
【在 f*****u 的大作中提到】
: 大牛你就别在这儿开玩笑了吧.我是真心来请教一些可行方案的.你面试这么说必死无疑
: 的吧.很明显面试官想听的是一套lower level的解决方案的.
| w***n
发帖数: 58 | 8 knuth shuffle is o(n) >> o(k).....
To pick random K out of N, first pick 1 out of N, then pick 1 out of N - 1..
.. pick 1 out of N - K +1. Every time you pick you could map range to the
left over numbers. You just need to use a sorted list to keep track of
elements already picked. O(klgk) | l*********b
发帖数: 65 | 9 第一题：如果每个node不会发送相同的时间戳的话： hashmap
戳收到的数量> 如果相同node会发送相同的时间戳： hashmap
存储哪些node发送过这个时间戳> 然后应该有个数字代表99%的 node吧 如果hashmap的
value （对于第二种情况就是value的size） 超过了这个数字 就记录这个时间戳。
对于超多数据 根据时间戳进行hash 这样相同时间戳的数据会被分到同一台机器上 就
可以了吧
第二题： 想半天不知道咋做 看到回复里说洗牌算法 亮瞎狗眼 好聪明。。。 | S********e
发帖数: 74 | 10 第一题感觉可以把timestamp hash到不同的机器上，继而计算tiamstamp的个数
第二题是reservior sampling 的变种把
【在 f*****u 的大作中提到】
: 两道题来自不同的公司.
: 题一:
: 有N个node,每个都不停的向外发送timestamps,具体发送哪些timestamp是每个node决定
: 的,从其他node来说是随机的.现在要收集这些node发送的所有timestamp.如果某个
: timestamp被发现从超过99%的node上发送出来,记录下来.需要怎么做?这些timestamp很
: 多,是不能完全放进去内存里面的.如果node非常多,怎么scale?
: 题二:
: 一个mxn的grid,要在里面随机生成K个格子.最直接的方法是一个for循环从1到K生成K个
: 随机格子,但是对每个当前生成的格子,需要检查前面是否已经生成过了,如果重复了需
: 要重新生成,这样时间上就超过了O(K).有方法在O(K)时间内实现吗?
| f*******w
发帖数: 1243 | 11 第二题resevoir sampling都overkill了吧，因为size是已知的
不过思路是一样的 | f*******w
发帖数: 1243 | 12 写了一下第二题，O(k)，用hash来实现swap..
vector randomPick(vector > &input, int k) {
int n = input[0].size(), total = input.size() * n;
unordered_map visited;
vector res; int start = 0;
for (int i = 0; i < k; ++i) {
int pos = rand() % (total - start) + start;
int x = pos / n, y = pos % n;
if (visited.find(pos) != visited.end()) {
res.push_back(visited[pos]);
int tmp = visited[pos];
visited[pos] = (visited.find(start) == visited.end()) ? input[
start / n][start % n] : visited[start];
visited[start] = tmp;
} else {
res.push_back(input[x][y]);
visited[pos] = (visited.find(start) == visited.end()) ? input[
start / n][start % n] : visited[start];
visited[start] = input[x][y];
}
++start;
}
return res;
} |
|
