y*****3
发帖数: 451 | 1 朋友内推的groupon goods，过几天就要电面了，考古发现几个groupon的面经，有几个
题目请教一下：
1. unfair coin，flip的几率是：head 1/4，tail 3/4，请写个function返回投head和
tail各是50%
2. 很多machine发message，怎么样才能不发重复的？
3. 无限数据流，怎样求最近的100万个数字中最大的数？
顺便问下，groupon goods的电面难不难？谢谢！ |
l*****a
发帖数: 14598 | 2
扔2次或多次
ignore head,head/tail,tail
then head,tail/tail,head各返回50%
【在 y*****3 的大作中提到】
: 朋友内推的groupon goods，过几天就要电面了，考古发现几个groupon的面经，有几个
: 题目请教一下：
: 1. unfair coin，flip的几率是：head 1/4，tail 3/4，请写个function返回投head和
: tail各是50%
: 2. 很多machine发message，怎么样才能不发重复的？
: 3. 无限数据流，怎样求最近的100万个数字中最大的数？
: 顺便问下，groupon goods的电面难不难？谢谢！
|
l*****a
发帖数: 14598 | 3
两个list?
一个存顺序，一个存max sofar
满100W以后，每次remove the oldest then remove from max sofar
再插入最新的到相应位置
###内存不够的话再说
【在 y*****3 的大作中提到】
: 朋友内推的groupon goods，过几天就要电面了，考古发现几个groupon的面经，有几个
: 题目请教一下：
: 1. unfair coin，flip的几率是：head 1/4，tail 3/4，请写个function返回投head和
: tail各是50%
: 2. 很多machine发message，怎么样才能不发重复的？
: 3. 无限数据流，怎样求最近的100万个数字中最大的数？
: 顺便问下，groupon goods的电面难不难？谢谢！
|
w*****d
发帖数: 105 | 4 3. 无限数据流，怎样求最近的100万个数字中最大的数？
我觉得应该用multiset + list，每次得到一个数后：
1)insert into multiset, get iterator;
2)list.push_back(iterator);
3)if list.size() > 100w, multiset.erase(list.front()) and list.pop_front();
max value is always (*multiset.begin()); |
o*****n
发帖数: 189 | 5 3. 无限数据流，怎样求最近的100万个数字中最大的数？
每次比较，记录3个最大值， 和他们的位置。如果位置超过100M， 找新的更新最大值。
这个什么意思？
2. 很多machine发message，怎么样才能不发重复的？ |
l******6
发帖数: 340 | 6 3.
struct data{
int idx;
int val;
data(int id , int v):idx(id),val(v){}
};
int wlen = 100M;
int curVal;
int curIdx = 0;
list window;
while(cin >> curVal)
{
while(!window.empty() && window.back().val <= curVal)
window.pop_back();
window.push_back(data(curIdx , curVal));
curIdx ++;
if(curIdx - window.front().idx > wlen)
window.pop_front();
cout << window.front().val<
} |
l******6
发帖数: 340 | 7 2.
hash the message , assign messages with hash values within hashValueRangei
to machinei, remove duplicate within the machine |
