一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 1123|回复: 1
收起左侧

Vertica的 assignment

[复制链接] |试试Instant~ |关注本帖
爱吃肉的羊 发表于 2015-2-20 04:16:42 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Vertica - 校园招聘会 - 校园招聘会 |Other

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

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

x
题目是有两个很大的xml 需要分析,一个user, 一个post 其实就是相当于两个数据库的表,现在让我从这个xml里读取top 10发帖最多的user, 其实就是相当于join两个table 然后拿出top 10。 要求是尽量减少空间、时间复杂度,群里的大大有什么思路吗?
ourlord 发表于 2015-10-6 05:38:27 | 显示全部楼层
啊我也刚面过,当时我自己想的太复杂了,于是后来貌似没跑好吧,反正挂了。

交完第二天我自己想了一想觉得很简单的其实

需要一个这样的数据结构
struct Recorder
{int post; int answer;}
std::vector<Recorder>          (或者用map更好,我只是懒得用c++11,所以开了个够大的vector,想想世界上人口也才6b,你开个1b存3个int也就是几MB的事情)

然后跑xml的每一行,更新这个vector或者map就是了,角标是userid,post对应帖子数,answer是回答数-google 1point3acres

然后排序来了,用std::set就可以了,for一记之前的vector,然后这么操作
Wrapper. 1point 3acres 璁哄潧
{int userid; int count;}
重载operator<,让根据count来排序
std::set<Wrapper> posts, answers;
for (auto &v : vector)
{
     posts.insert(v);
     answers.insert(v); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
     if (posts.size() > 10) posts.erase(posts.begin());
     if (answers.size() > 10) answers.erase(answers.begin());
}

最后再把这20个userid去小的xml里找一下用户名就可以了。
这样肯定跑的出,而且不用很多内存,那个vector真的没啥内存,用map就更少了。但其实这个数据结构有个前提是post_id是primary key,意思是不能有重复的。。。但给的数据其实可以发现这一点,我觉得最好还是说一下比较好。

如果还要optimize的话可以在读数据的时候mutltithread一下,但是数据容易跑花,我自己随便实现了一下发现不太可靠,后来也没有再去想这个问题....
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-12-17 14:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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