一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2167|回复: 14
收起左侧

google 老题。。。

[复制链接] |试试Instant~ |关注本帖
dimi 发表于 2016-8-25 10:32:07 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 本科 全职@Google - 内推 - Onsite |Other其他

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
Top K Voted 个人
给一堆votes(candidate, timestamp),问当前时刻T 得票最高的人是谁。Follow up 问得票最高
的前K 个人. from: 1point3acres.com/bbs
(Q,T) represents at time T, a query Q comes. Each query may appear many times.
(q1, t1), (q2,t2),(q1,t3),(q3,t4)....
Write a class, which contains a function of enQuery(T,Q) and a function TopK
which will return K query, which appear most times within t
(q1,0),(q2,0),(q1,1),(q2,2),(q3,3) (q1,3). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

这个题目谁说说思路。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
已知条件是一堆votes.   List<Vote> ;
Vote : { candidate,  timestamp}-google 1point3acres

要实现的函数就是 给定T,返回得票最高的人,扩展是得票最多的k个人

评分

1

查看全部评分

本帖被以下淘专辑推荐:

wtcupup 发表于 2016-8-25 10:47:59 | 显示全部楼层
回复 支持 反对

使用道具 举报

rjfrjf1 发表于 2016-8-25 11:37:45 | 显示全部楼层
请问楼主,这个时间T是之前任意的时间,还是指当前时间。
回复 支持 反对

使用道具 举报

 楼主| dimi 发表于 2016-8-25 12:38:46 | 显示全部楼层
rjfrjf1 发表于 2016-8-25 11:37
请问楼主,这个时间T是之前任意的时间,还是指当前时间。

T 是函数输入值。 就是所有投票数据都是给你给好的。
回复 支持 反对

使用道具 举报

chaosMonkey 发表于 2016-8-25 15:32:49 | 显示全部楼层
dimi 发表于 2016-8-25 12:38
T 是函数输入值。 就是所有投票数据都是给你给好的。

我觉得他的意思是说T这个时间是否可以取过去的某个时间点,求之前那个时间点的TopK,还是说调用TopK这个函数时的时间点
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-8-25 15:42:20 | 显示全部楼层
Hashmap<timeStamp, treemap<count, id>>
回复 支持 反对

使用道具 举报

chaosMonkey 发表于 2016-8-25 15:48:26 | 显示全部楼层
说一下我自己的想法.. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
利用的数据结构是map<int, vector<int>> ,其中 key 是Q,value是记录投票给Q的时间戳的数组,
寻找到某个时间点t为止的得票最多的Q,可以遍历这个map,寻找数组中,小于t的元素个数,如果query都是根据时间戳从小到大加入map的,数组中的时间戳肯定是有序的,可以用二分法,或者直接调用C++的upper_bound库函数。以此求出最大得票的Q
topk的话利用大小为K的小顶堆,根据上面方法,得到每个人的投票数,放入堆,最后留在堆内的就是TOPK。
上面想法都是比较自然而然能想到的,不知道是否能有更为巧妙的数据结构来保存投票数据
回复 支持 反对

使用道具 举报

llatjob 发表于 2016-8-25 20:48:10 | 显示全部楼层
Most frequent cache
回复 支持 反对

使用道具 举报

greentrail 发表于 2016-8-26 05:01:35 | 显示全部楼层

.鏈枃鍘熷垱鑷1point3acres璁哄潧详细说说
回复 支持 反对

使用道具 举报

greentrail 发表于 2016-8-26 05:24:48 | 显示全部楼层
chaosMonkey 发表于 2016-8-25 15:48
说一下我自己的想法.
利用的数据结构是map ,其中 key 是Q,value是记录投票给Q的时间戳的数组,. visit 1point3acres.com for more.
寻找到 ...

这个方法应该可行。觉得数据结构用unordered_map<int, set<int>>更合理一些。可以直接利用set的upper_bound算有多少vote在T之前。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
这个方法不好的一点是每给定一个时间T,都要遍历一遍hash table。


补充内容 (2016-8-26 05:26):
如果查询T和T+1, 重复算了很多。
回复 支持 反对

使用道具 举报

llatjob 发表于 2016-8-27 05:51:16 | 显示全部楼层
// suppose topK should be called multiple time
// support there is only one candidate voted at one timestamp(this is possible if the timestamp is second based)
// use multimap to record the frequency of candidates: data, since candidates may have same number of votes
// use unordered_map to record the position of one candidate in the data: data_map
// store all the votes as timestamp, candidate pairs;
// record cur_timestamp, for each call of topK, check the timestamp with last cur_timestamp
// timestamp < cur_timestamp: put votes in this range to the multimap
// timestamp > cur_timestamp: remove votes in this range to the multimap. From 1point 3acres bbs
// get k elements from the multimap
.鏈枃鍘熷垱鑷1point3acres璁哄潧
class SortCandidates {
private:
        unsigned cur_timestamp;
        std::multimap<unsigned, std::string, std::less<unsigned> > data;
        typedef std::multimap<unsigned, std::string, std::less<unsigned> >::iterator Iter;
        std::unordered_map<std::string, Iter> data_map;
        std::map<unsigned, std::string> votes;

        void init(const std::vector<std::pair<std::string, unsigned> >& input_votes) {. 1point 3acres 璁哄潧
                // initialize. Waral 鍗氬鏈夋洿澶氭枃绔,
                for (auto v : input_votes) {
                        votes.emplace(v.second, v.first);
                        insert(v.first);
                }
                cur_timestamp = votes.rbegin()->first;. 1point3acres.com/bbs
        }

        void insert(std::string& v) {
                // insert one vote to the data
                auto pos = data_map.find(v);. more info on 1point3acres.com
                if (pos == data_map.end()) {
                        data_map[v] = data.emplace(1, v);
                }. more info on 1point3acres.com
                else {
                        unsigned count = pos->second->first + 1;
                        data.erase(pos->second);
                        data_map[v] = data.emplace(count, v);. 鍥磋鎴戜滑@1point 3 acres
                }
        }
        void remove(unsigned timestamp) {
                // remove one vote from data
                auto pos = votes.find(timestamp);
                if (pos == votes.end()) {
                        return;
                }
                std::string& cand = pos->second;
                auto iter = data_map.find(cand)->second;
                if (1 == iter->first) {
                        data.erase(iter);
                }
                else {
                        size_t count = iter->first - 1;
                        data.erase(iter);
                        data_map[cand] = data.emplace(count, cand);
                }
        }. Waral 鍗氬鏈夋洿澶氭枃绔,
public:
        SortCandidates(const std::vector<std::pair<std::string, unsigned> >& input_votes) {
                init(input_votes);
        }
        std::vector<std::string> topK(unsigned k, unsigned timestamp) {
                std::vector<std::string> result;
                if (0 == k) {. from: 1point3acres.com/bbs
                        return result;
                }
                result.reserve(k);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                if (timestamp > cur_timestamp) {
                        while (cur_timestamp < timestamp) {
                                ++cur_timestamp;-google 1point3acres
                                auto pos = votes.find(cur_timestamp);
                                if (pos != votes.end()) {. Waral 鍗氬鏈夋洿澶氭枃绔,
                                        insert(pos->second);
                                }. 1point 3acres 璁哄潧
                        }
                }-google 1point3acres
                else if (timestamp < cur_timestamp) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                        do {.鐣欏璁哄潧-涓浜-涓夊垎鍦
                                remove(cur_timestamp);
                                --cur_timestamp;
                        } while (cur_timestamp > timestamp);
                }
                auto iter = data.begin();
                while (iter != data.end() && k) {
                        result.push_back(iter->second);
                        ++iter;
                        --k;
                }
                return result;
        }.1point3acres缃
};. Waral 鍗氬鏈夋洿澶氭枃绔,
回复 支持 反对

使用道具 举报

greentrail 发表于 2016-8-27 06:31:22 | 显示全部楼层
llatjob 发表于 2016-8-27 05:51
// suppose topK should be called multiple time
// support there is only one candidate voted at one  ...

不理解为啥要remove vote. vote 应该是一直累加的。
回复 支持 反对

使用道具 举报

llatjob 发表于 2016-8-27 07:55:55 | 显示全部楼层
因为有可能要过去摸个时间点的topk
回复 支持 反对

使用道具 举报

burself 发表于 2016-9-4 19:18:57 | 显示全部楼层
如果vote一直保持按时间排序是不是可以保持一个堆来获取每个时间最大值啊?堆元素是{vote#,candidate},按vote#排序,另有一个hashmap用于查找candidate在堆里的value,每次candidate有新vote就调用堆的increase_value。每当时间戳变化时,将当前堆顶值写入vector作为前一个时间戳的得票最高者。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 02:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表