一亩三分地论坛

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

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

求大神解答 two sigma 这道oa怎么做

[复制链接] |试试Instant~ |关注本帖
singledog2016 发表于 2016-6-11 12:28:02 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 博士 全职@TwoSigma - 内推 - 在线笔试 |Otherfresh grad应届毕业生

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

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

x
如图,地里有人贴的two sigma 的oa,跟传统的friend cycle , string chain不同。 感觉这题难度很大。求解答啊
Untitled2.png

评分

1

查看全部评分

Fustang 发表于 2016-6-11 21:03:57 | 显示全部楼层
占个坑看讨论。之前粗略想过用heap. 鍥磋鎴戜滑@1point 3 acres
首先每个cluster至少分一台machine,然后全都放到heap里,按照task/min排序
对于剩下的B-N台,每次都从heap pop出当前最大的task/min的cluster 然后给其添加一个machine, push back to heap
其实就是greedy. 不知道能不能过大case;哪位给个更好的算法
回复 支持 反对

使用道具 举报

Altynai 发表于 2016-6-11 22:20:28 | 显示全部楼层
你们想复杂了吧,就是二分答案,o(nlogn)的复杂度
回复 支持 反对

使用道具 举报

Altynai 发表于 2016-6-11 22:29:01 | 显示全部楼层
说错了,是o(nlog*max(ai))
二分1~max(ai),作为最后的解,然后去算每个cluster最少的机器数(多出来的机器无所谓,因为随便放到一个cluster里面,会更加减小答案),验证可行性就行啦

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

Fustang 发表于 2016-6-11 22:58:24 | 显示全部楼层
Altynai 发表于 2016-6-11 22:29
说错了,是o(nlog*max(ai))
二分1~max(ai),作为最后的解,然后去算每个cluster最少的机器数(多出来的机 ...

soga 原来是play ai... 多谢
回复 支持 反对

使用道具 举报

 楼主| singledog2016 发表于 2016-6-12 00:55:45 | 显示全部楼层
Altynai 发表于 2016-6-11 22:29
说错了,是o(nlog*max(ai))
二分1~max(ai),作为最后的解,然后去算每个cluster最少的机器数(多出来的机 ...

还是没理解。。。 play ai是啥?   max(ai)
回复 支持 反对

使用道具 举报

ruiqin 发表于 2016-6-17 14:28:28 | 显示全部楼层
没理解Altynai说的二分到底是怎么做, 能不能再稍微详细讲下
回复 支持 反对

使用道具 举报

andrewmasj 发表于 2016-6-18 02:52:52 | 显示全部楼层
I think the quiz has a problem. it assumes clusters to add machine in are empty. otherwise, you can not simply adding two machines to bring down 200/sec to 100/sec. etc But if following that assumption, the solution is simple. just try to find a middle point two clusters' load is about same.
回复 支持 反对

使用道具 举报

andrewmasj 发表于 2016-6-18 06:26:42 | 显示全部楼层
I created a solution here:
http://www.1point3acres.com/bbs/thread-193470-1-1.html
回复 支持 反对

使用道具 举报

xdrealmadrid 发表于 2016-6-20 03:22:57 | 显示全部楼层
感觉Altynai说的和heap解法一个意思?
回复 支持 反对

使用道具 举报

seenome 发表于 2016-7-4 14:51:28 | 显示全部楼层
binary ai doesn't seem correct. Assume there are way many machines so that each cluster will at least have 2 so that the average load could be 0.5*min(ai).
the greedy + max heap looks more correct to me.
回复 支持 反对

使用道具 举报

小飞飞一起飞 发表于 2016-11-26 12:06:14 | 显示全部楼层
leetcode好像有一道类似的题目 是用二分查找发
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 05:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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