一亩三分地论坛

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

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

A solution to 2 sigma OA problem

[复制链接] |试试Instant~ |关注本帖
andrewmasj 发表于 2016-6-18 06:25:46 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 本科 全职@2 sigma - 网上海投 - 其他 |Other其他

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

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

x
This is my solution to a problem posted in http://www.1point3acres.com/bbs/ ... D311%26sortid%3D311. from: 1point3acres.com/bbs

apologize in advance if you disagree that I should open a new post. I want to know some feedbacks too and this way is easier to find out.
.鏈枃鍘熷垱鑷1point3acres璁哄潧
So assuming you already passed in all the paremeters, here  is a solution. it assume all clusters are new and empty. The question does not provide how many machihes are already there so this assumption is valid.

static int[] distributeMachineToClusters(int b,int n,int[] a){. 鍥磋鎴戜滑@1point 3 acres
//define distribution array and initialize it with 1 distribution, which is minimum num of distr. more info on 1point3acres.com
//also maximum of load               
                int[] distributions = new int[n];
                for(int i=0;i<n;i++){//O(n)
                        distributions = 1;//at least one distribution-google 1point3acres
                }
                b-=n;//used n already
                while(b>0){//O(bxn)
                        int j = -1;
                        int leastMax=Integer.MIN_VALUE;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                        for(int i=0;i<n;i++){
                                //distribute to each of cluster, pick the one that drops load the least
                                if(a/(distributions+1)>leastMax){. 鍥磋鎴戜滑@1point 3 acres
                                        leastMax = a/(distributions+1);
                                        j=i;
                                }
                        }
                        b--;
                        distributions[j]++;
                }
                return distributions;
        }
       

ruiqin 发表于 2016-6-18 06:39:19 | 显示全部楼层
这个和用max heap做的思路一样的把   都是找load最高的cluster  加一个machine进去
heap的bigO还要快一点    但是要写个class包含clusterid, load, machineNum之类的. from: 1point3acres.com/bbs
不知道heap和楼主这样暴力做哪个实际run起来会快一点    就怕会超时
回复 支持 反对

使用道具 举报

 楼主| andrewmasj 发表于 2016-6-18 08:22:11 | 显示全部楼层
first to make it work, then to make it tuned. most important thing is to understand it.

here's heap solution.

        static int[] distributeMachineToClustersPQ(int b,int n,int[] a){
                class Entry<K,V,N> {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        K cluster; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                        V avgLoad;. 鍥磋鎴戜滑@1point 3 acres
                        N numMachine;
                        public Entry(K k,V v,N c){.鐣欏璁哄潧-涓浜-涓夊垎鍦
                                cluster=k;-google 1point3acres
                                avgLoad = v;
                                numMachine = c;
                        }
                }
                //now instead of thinking dropping load the least, thinking to mitigate the one having most average load                                int[] distributions = new int[n];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                PriorityQueue<Entry<Integer, Integer, Integer>> pq = new PriorityQueue<Entry<Integer,Integer, Integer>>(                        . 鍥磋鎴戜滑@1point 3 acres
                        new Comparator<Entry<Integer,Integer, Integer>>() {
                                        @Override-google 1point3acres
                                        public int compare(Entry<Integer, Integer, Integer> o1,
                                                        Entry<Integer, Integer, Integer> o2) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
                                                return o2.avgLoad-o1.avgLoad;. 鍥磋鎴戜滑@1point 3 acres
                                        }
                        }
                        );. 鍥磋鎴戜滑@1point 3 acres

                        for(int i=0;i<n;i++){//O(n)
                                Entry<Integer,Integer,Integer> e = new Entry<Integer,Integer,Integer>(i,a[i],1);//maximum load per machine
                                pq.add(e);. From 1point 3acres bbs
                        }. 1point 3acres 璁哄潧
                        b-=n;//used n already

                        while(b>0){//O(bxn)
                                Entry<Integer,Integer,Integer> e = pq.poll();. from: 1point3acres.com/bbs
                                b--;.鏈枃鍘熷垱鑷1point3acres璁哄潧
                                e.avgLoad=(e.avgLoad*e.numMachine)/(e.numMachine+1);
                                e.numMachine++;
                                pq.add(e);
                        }
//prepare result
                        int distributions[] = new int[n];
                        for(Entry<Integer,Integer,Integer> e:pq){
                                distributions[e.cluster] =e.numMachine;
                        }
                        return distributions;. visit 1point3acres.com for more.
        }
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

 楼主| andrewmasj 发表于 2016-6-18 08:23:39 | 显示全部楼层
looking forward to better solutions ...
回复 支持 反对

使用道具 举报

TonyLic 发表于 2016-7-4 07:21:30 | 显示全部楼层
贴个C++的,思路和上面的一样,用max heap,始终给最大的average load的cluster加一个machine,更新其average load,再放入heap中
Time complexty: O(KlogN)
  1. class cluster.鐣欏璁哄潧-涓浜-涓夊垎鍦
  2. {
  3. public:. From 1point 3acres bbs
  4.         cluster(int p1, int p2, int p3, int p4) : work_load(p1), avg_load(p2), index(p3), num_machine(p4) {}
  5.         int work_load;-google 1point3acres
  6.         int avg_load;
  7.         int index;
  8.         int num_machine;
  9. };. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  10. struct mycmp
  11. {
  12.         bool operator()(cluster& c1, cluster& c2) { return c1.avg_load < c2.avg_load; }
  13. }; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  14. vector<int> loadBalance(vector<int>& loads, int b)
  15. {
  16.         vector<int> res(loads.size());
  17.         if (b < loads.size()) return res;
  18.         priority_queue < cluster, vector < cluster >, mycmp> pq;
  19.         for (int i = 0; i < loads.size(); ++i). from: 1point3acres.com/bbs
  20.                 pq.emplace(loads[i], loads[i], i, 1);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  21.         b -= loads.size();
  22.         while (b--). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  23.         {
  24.                 auto temp = pq.top();. 鍥磋鎴戜滑@1point 3 acres
  25.                 pq.pop();
  26.                 temp.num_machine++;-google 1point3acres
  27.                 temp.avg_load = temp.work_load / temp.num_machine;
  28.                 pq.push(temp);
  29.         }
    .1point3acres缃
  30.         while (!pq.empty())
  31.         { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  32.                 auto temp = pq.top();
    . From 1point 3acres bbs
  33.                 pq.pop();
  34.                 res[temp.index] = temp.num_machine;. from: 1point3acres.com/bbs
  35.         }
  36.         return res;
  37. }

  38. int main()
  39. {
  40.         vector<int> loads = { 200, 450 };.1point3acres缃
  41.         auto res = loadBalance(loads, 7);
  42.         printVector(res);. 鍥磋鎴戜滑@1point 3 acres
  43.         return 0;
  44. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-25 07:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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