一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 3371|回复: 17
收起左侧

求大神解答 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 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
占个坑看讨论。之前粗略想过用heap. more info on 1point3acres.com
首先每个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 | 显示全部楼层
关注一亩三分地微博:
Warald
你们想复杂了吧,就是二分答案,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... 多谢
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

 楼主| singledog2016 发表于 2016-6-12 00:55:45 | 显示全部楼层
Altynai 发表于 2016-6-11 22:29
说错了,是o(nlog*max(ai)).1point3acres缃
二分1~max(ai),作为最后的解,然后去算每个cluster最少的机器数(多出来的机 ...
. visit 1point3acres.com for more.
还是没理解。。。 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好像有一道类似的题目 是用二分查找发
回复 支持 反对

使用道具 举报

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) { }. from: 1point3acres.com/bbs

  double workload;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  double machine_count;

};



// Functor to compare Cluster

struct MoreWorkload {-google 1point3acres

  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;
. 1point3acres.com/bbs
    return left_workload < right_workload;
.1point3acres缃
  }

};



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.鐣欏璁哄潧-涓浜-涓夊垎鍦
. from: 1point3acres.com/bbs
  for (int i=0;i<cluster_num;++i) {.1point3acres缃

    cluster_workloads.push(Cluster(workloads[i],1));

    -- machine_num;// reduce machine number

  }

  // always add machine to the cluster which has maximum workload. visit 1point3acres.com for more.

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

    Cluster max_cluster = cluster_workloads.top();

    cluster_workloads.pop();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

    ++ max_cluster.machine_count;. 鍥磋鎴戜滑@1point 3 acres

    cluster_workloads.push(max_cluster);
. 1point 3acres 璁哄潧
  }.1point3acres缃



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

}

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

void UnitTest() {.鐣欏璁哄潧-涓浜-涓夊垎鍦
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  // test 1
. 鍥磋鎴戜滑@1point 3 acres
  vector<int> workloads = {200,450};

  int cluster_num = 2, machine_num = 7;

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

.1point3acres缃
.鏈枃鍘熷垱鑷1point3acres璁哄潧
  // test 2

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

  cluster_num = 4, machine_num = 10;

  assert( AdjustWorkload(workloads,cluster_num,machine_num) == 200 );-google 1point3acres
. visit 1point3acres.com for more.
} 鏉ユ簮涓浜.涓夊垎鍦拌鍧.



int main() {
-google 1point3acres
  UnitTest();

  return 0;

}
```
回复 支持 反对

使用道具 举报

Lelouch1989 发表于 2017-1-10 09:02:57 | 显示全部楼层
Lelouch1989 发表于 2017-1-10 09:01
```. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
struct Cluster{
. Waral 鍗氬鏈夋洿澶氭枃绔,
方法就是用一个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)
{
        int start = 1;
        int end = INT_MAX;
        for (int i=0; i<workloads.size(); i++)
        {
                end = min(end, workloads[i]);
        }

        while (start+1<end)
        {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                int mid = start+(end-start)/2;-google 1point3acres
                int total = machinesNeedForLoad(workloads, mid);
                if (total<machines)
                        end = mid;
                else if (total>machines)-google 1point3acres
                        start = mid;
                else
                        return mid;
        }
        int total = machinesNeedForLoad(workloads, start);
        if (total<=machines)
                return start;
        else
                return end;
}

int machinesNeedForLoad(vector<int>& workloads, int load). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
{
        int total=0;
        for (int i=0; i<workloads.size(); i++) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        {-google 1point3acres
                int w = workloads[i];
                while (w>load)
                {. 1point3acres.com/bbs
                        w = w-load;
                        total++;
                } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                if (w>0)
                        total++;
        }
        return total;. 1point 3acres 璁哄潧
}
回复 支持 反对

使用道具 举报

mcphil 发表于 2017-2-19 11:26:35 | 显示全部楼层
winnieliuzzz 发表于 2017-1-14 01:06. Waral 鍗氬鏈夋洿澶氭枃绔,
贴代码,欢迎讨论
int minimizeWordLoad(int clusters, int machines, vector workloads)
{

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-3-28 17:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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