买房小白任秀坡在湾区买房经历(一)

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
国内机会:实时大数据分析领域领导者
Web/大数据/机器学习/产品等职位
日志易机器大数据行业践行者Web/大数据/机器学习等职位-北京or深圳
把贵司招聘信息放这里
查看: 4888|回复: 17
收起左侧

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

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

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

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

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

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

评分

1

查看全部评分

Fustang 发表于 2016-6-11 21:03:57 | 显示全部楼层
占个坑看讨论。之前粗略想过用heap
首先每个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).-google 1point3acres
the greedy + max heap looks more correct to me.
回复 支持 反对

使用道具 举报

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

使用道具 举报

ydzhang12345 发表于 2017-1-10 04:08:34 | 显示全部楼层
感谢分享,马克
回复 支持 反对

使用道具 举报

Lelouch1989 发表于 2017-1-10 09:01:28 | 显示全部楼层
```
struct Cluster{

  Cluster(int wl,int mc) : workload(wl), machine_count(mc) { }

  double workload;

  double machine_count;-google 1point3acres

};
.鏈枃鍘熷垱鑷1point3acres璁哄潧

. visit 1point3acres.com for more.
// Functor to compare Cluster

struct MoreWorkload {
. from: 1point3acres.com/bbs
  bool operator()(const Cluster & left, const Cluster & right) {

    // notice that I used double instead of integer here.

    double left_workload  = left.workload/left.machine_count;

    double right_workload = right.workload/right.machine_count;

    return left_workload < right_workload;. 鍥磋鎴戜滑@1point 3 acres

  }

};. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷



typedef std::priority_queue<Cluster,vector<Cluster>,MoreWorkload > MaxHeap;



int AdjustWorkload(vector<int> & workloads,int cluster_num,int machine_num) {

  MaxHeap cluster_workloads;



  // each cluster has at least one machine

  for (int i=0;i<cluster_num;++i) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    cluster_workloads.push(Cluster(workloads[i],1));. from: 1point3acres.com/bbs

    -- machine_num;// reduce machine number

  }

  // always add machine to the cluster which has maximum workload

  for (int i=0;i<machine_num;++i) {

    Cluster max_cluster = cluster_workloads.top();

    cluster_workloads.pop();

    ++ max_cluster.machine_count;

    cluster_workloads.push(max_cluster);
. from: 1point3acres.com/bbs
  }
. visit 1point3acres.com for more.


  return cluster_workloads.top().workload/cluster_workloads.top().machine_count;

}



void UnitTest() {

  // test 1

  vector<int> workloads = {200,450};

  int cluster_num = 2, machine_num = 7;

  assert(AdjustWorkload(workloads,cluster_num,machine_num) == 100);
.鐣欏璁哄潧-涓浜-涓夊垎鍦

.鐣欏璁哄潧-涓浜-涓夊垎鍦
  // test 2

  workloads = {200,450,300,720};

  cluster_num = 4, machine_num = 10;-google 1point3acres

  assert( AdjustWorkload(workloads,cluster_num,machine_num) == 200 );

}



int main() {
. 鍥磋鎴戜滑@1point 3 acres
  UnitTest();

  return 0;
. 鍥磋鎴戜滑@1point 3 acres
}
```
回复 支持 反对

使用道具 举报

Lelouch1989 发表于 2017-1-10 09:02:57 | 显示全部楼层
Lelouch1989 发表于 2017-1-10 09:01. Waral 鍗氬鏈夋洿澶氭枃绔,
```
struct Cluster{

方法就是用一个Heap来存Cluster的信息,每次都往workload最大的cluster上面加机器就行了。注意的是每个cluster至少有一个机器
回复 支持 反对

使用道具 举报

winnieliuzzz 发表于 2017-1-14 01:02:02 | 显示全部楼层
我觉得就是用二分法,但右边界应该是Min(ai), 因为每个cluster至少要有一台机器.
回复 支持 反对

使用道具 举报

winnieliuzzz 发表于 2017-1-14 01:06:34 | 显示全部楼层
贴代码,欢迎讨论
int minimizeWordLoad(int clusters, int machines, vector<int> workloads). Waral 鍗氬鏈夋洿澶氭枃绔,
{
        int start = 1;. 1point3acres.com/bbs
        int end = INT_MAX;
        for (int i=0; i<workloads.size(); i++)
        {
                end = min(end, workloads[i]);
        }

        while (start+1<end)
        {
-google 1point3acres                int mid = start+(end-start)/2;
                int total = machinesNeedForLoad(workloads, mid);
                if (total<machines). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        end = mid;
                else if (total>machines)
                        start = mid;
                else
                        return mid;
        }
        int total = machinesNeedForLoad(workloads, start);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        if (total<=machines)
                return start;
        else-google 1point3acres
                return end;
}. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

int machinesNeedForLoad(vector<int>& workloads, int load)
{
        int total=0;. Waral 鍗氬鏈夋洿澶氭枃绔,
        for (int i=0; i<workloads.size(); i++)
        {
                int w = workloads[i];. more info on 1point3acres.com
                while (w>load). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                {
                        w = w-load;
                        total++;. visit 1point3acres.com for more.
                }
                if (w>0)
                        total++;
        }
        return total;
}
回复 支持 反对

使用道具 举报

mcphil 发表于 2017-2-19 11:26:35 | 显示全部楼层
winnieliuzzz 发表于 2017-1-14 01:06.1point3acres缃
贴代码,欢迎讨论
int minimizeWordLoad(int clusters, int machines, vector workloads)
{

为啥end是minLoad? Cluster分别是100, 300, 两台机器,肯定答案是300吧
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-388663-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-4-19 18:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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