请教几个题目 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教几个题目

请教几个题目# JobHunting - 待字闺中

y*32014-02-12 08:02

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*a2014-02-12 08:02

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*a2014-02-12 08:02

3 楼

两个list?
一个存顺序，一个存max sofar
满100W以后，每次remove the oldest then remove from max sofar
再插入最新的到相应位置
###内存不够的话再说

【在 y*****3 的大作中提到】

w*d2014-02-12 08:02

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*n2014-02-12 08:02

5 楼

3. 无限数据流，怎样求最近的100万个数字中最大的数？
每次比较，记录3个最大值，和他们的位置。如果位置超过100M，找新的更新最大值。
这个什么意思？
2. 很多machine发message，怎么样才能不发重复的？

l*62014-02-12 08:02

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*62014-02-12 08:02

7 楼

2.
hash the message , assign messages with hash values within hashValueRangei
to machinei, remove duplicate within the machine