谈谈使用过的几款咖啡机

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 5018|回复: 17
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
我的人缘0
singledog2016 发表于 2016-6-11 12:28:02 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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

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

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

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

评分

参与人数 1大米 +60 收起 理由
whdawn + 60

查看全部评分


上一篇:Snapchat 6.10 电面
下一篇:狗家6月onsite经验分享。。。
我的人缘0
Fustang 发表于 2016-6-11 21:03:57 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
占个坑看讨论。之前粗略想过用heap
首先每个cluster至少分一台machine,然后全都放到heap里,按照task/min排序
对于剩下的B-N台,每次都从heap pop出当前最大的task/min的cluster 然后给其添加一个machine, push back to heap
其实就是greedy. 不知道能不能过大case;哪位给个更好的算法
回复 支持 反对

使用道具 举报

我的人缘0
Altynai 发表于 2016-6-11 22:20:28 | 显示全部楼层
  此人我要顶:
 
100% (9) 【我投】
  此人我要踩:
 
0% (0) 【我投】
你们想复杂了吧,就是二分答案,o(nlogn)的复杂度
回复 支持 反对

使用道具 举报

我的人缘0
Altynai 发表于 2016-6-11 22:29:01 | 显示全部楼层
  此人我要顶:
 
100% (9) 【我投】
  此人我要踩:
 
0% (0) 【我投】
说错了,是o(nlog*max(ai)). From 1point 3acres bbs
二分1~max(ai),作为最后的解,然后去算每个cluster最少的机器数(多出来的机器无所谓,因为随便放到一个cluster里面,会更加减小答案),验证可行性就行啦

评分

参与人数 1大米 +10 收起 理由
mnmunknown + 10 回答的很好!

查看全部评分

回复 支持 反对

使用道具 举报

我的人缘0
Fustang 发表于 2016-6-11 22:58:24 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
Altynai 发表于 2016-6-11 22:29
说错了,是o(nlog*max(ai)).留学论坛-一亩-三分地
二分1~max(ai),作为最后的解,然后去算每个cluster最少的机器数(多出来的机 ...

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

使用道具 举报

我的人缘0
 楼主| singledog2016 发表于 2016-6-12 00:55:45 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
Altynai 发表于 2016-6-11 22:29. Waral 博客有更多文章,
说错了,是o(nlog*max(ai))
二分1~max(ai),作为最后的解,然后去算每个cluster最少的机器数(多出来的机 ...

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

使用道具 举报

我的人缘0
ruiqin 发表于 2016-6-17 14:28:28 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
没理解Altynai说的二分到底是怎么做, 能不能再稍微详细讲下
回复 支持 反对

使用道具 举报

我的人缘0
andrewmasj 发表于 2016-6-18 02:52:52 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
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.
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
andrewmasj 发表于 2016-6-18 06:26:42 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
I created a solution here:.本文原创自1point3acres论坛
http://www.1point3acres.com/bbs/thread-193470-1-1.html
回复 支持 反对

使用道具 举报

我的人缘0
xdrealmadrid 发表于 2016-6-20 03:22:57 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
感觉Altynai说的和heap解法一个意思?
回复 支持 反对

使用道具 举报

我的人缘0
seenome 发表于 2016-7-4 14:51:28 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
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).
. visit 1point3acres for more.the greedy + max heap looks more correct to me.
回复 支持 反对

使用道具 举报

我的人缘0
小飞飞一起飞 发表于 2016-11-26 12:06:14 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
leetcode好像有一道类似的题目 是用二分查找发
回复 支持 反对

使用道具 举报

我的人缘0
ydzhang12345 发表于 2017-1-10 04:08:34 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
感谢分享,马克
回复 支持 反对

使用道具 举报

我的人缘0
Lelouch1989 发表于 2017-1-10 09:01:28 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
```
struct Cluster{
-google 1point3acres
  Cluster(int wl,int mc) : workload(wl), machine_count(mc) { }

  double workload;

  double machine_count;

};
. 围观我们@1point 3 acres


// Functor to compare Cluster

struct MoreWorkload {

  bool operator()(const Cluster & left, const Cluster & right) {

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

    double left_workload  = left.workload/left.machine_count;. 留学申请论坛-一亩三分地

    double right_workload = right.workload/right.machine_count;
. from: 1point3acres
    return left_workload < right_workload;

  }

};

. Waral 博客有更多文章,

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



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

  MaxHeap cluster_workloads;



.本文原创自1point3acres论坛  // each cluster has at least one machine
. 围观我们@1point 3 acres
  for (int i=0;i<cluster_num;++i) {

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

    -- 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);

  }

. 一亩-三分-地,独家发布

  return cluster_workloads.top().workload/cluster_workloads.top().machine_count;. 留学申请论坛-一亩三分地
. 牛人云集,一亩三分地
}



void UnitTest() {

  // test 1
. more info on 1point3acres
  vector<int> workloads = {200,450};

  int cluster_num = 2, machine_num = 7;

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



  // test 2. 1point3acres

  workloads = {200,450,300,720};
.留学论坛-一亩-三分地
  cluster_num = 4, machine_num = 10;. from: 1point3acres

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

}. 围观我们@1point 3 acres



int main() {
. 一亩-三分-地,独家发布
  UnitTest();

  return 0;

}
```
回复 支持 反对

使用道具 举报

我的人缘0
Lelouch1989 发表于 2017-1-10 09:02:57 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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

使用道具 举报

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

使用道具 举报

我的人缘0
winnieliuzzz 发表于 2017-1-14 01:06:34 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
贴代码,欢迎讨论
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]);
        }. more info on 1point3acres

        while (start+1<end)
        {
                int mid = start+(end-start)/2;
                int total = machinesNeedForLoad(workloads, mid);
                if (total<machines)
                        end = mid;
                else if (total>machines)
                        start = mid;
                else. visit 1point3acres for more.
                        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;. 1point 3acres 论坛
        for (int i=0; i<workloads.size(); i++)
        {
                int w = workloads[i];
                while (w>load). more info on 1point3acres
                {
                        w = w-load;
                        total++;
                }
                if (w>0). 留学申请论坛-一亩三分地
                        total++; 来源一亩.三分地论坛.
        }-google 1point3acres
        return total;
}
回复 支持 反对

使用道具 举报

我的人缘0
mcphil 发表于 2017-2-19 11:26:35 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
winnieliuzzz 发表于 2017-1-14 01:06
贴代码,欢迎讨论
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-405991-1-1.html

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

custom counter

GMT+8, 2018-6-24 07:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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