一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 786|回复: 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
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
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.

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){-google 1point3acres
//define distribution array and initialize it with 1 distribution, which is minimum num of distr
//also maximum of load               
                int[] distributions = new int[n];. more info on 1point3acres.com
                for(int i=0;i<n;i++){//O(n)
                        distributions = 1;//at least one distribution
                }. Waral 鍗氬鏈夋洿澶氭枃绔,
                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. 鍥磋鎴戜滑@1point 3 acres
                                if(a/(distributions+1)>leastMax){.鏈枃鍘熷垱鑷1point3acres璁哄潧
                                        leastMax = a/(distributions+1);
                                        j=i;
                                }
                        }
                        b--;. Waral 鍗氬鏈夋洿澶氭枃绔,
                        distributions[j]++;.鏈枃鍘熷垱鑷1point3acres璁哄潧
                }
                return distributions;
        }
       

ruiqin 发表于 2016-6-18 06:39:19 | 显示全部楼层
这个和用max heap做的思路一样的把   都是找load最高的cluster  加一个machine进去. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
heap的bigO还要快一点    但是要写个class包含clusterid, load, machineNum之类的
不知道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.
. 1point3acres.com/bbs
        static int[] distributeMachineToClustersPQ(int b,int n,int[] a){
                class Entry<K,V,N> {. more info on 1point3acres.com
                        K cluster;
                        V avgLoad;
                        N numMachine;
                        public Entry(K k,V v,N c){
                                cluster=k;
. Waral 鍗氬鏈夋洿澶氭枃绔,                                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>>(                       
                        new Comparator<Entry<Integer,Integer, Integer>>() {. from: 1point3acres.com/bbs
                                        @Override.鐣欏璁哄潧-涓浜-涓夊垎鍦
                                        public int compare(Entry<Integer, Integer, Integer> o1,. visit 1point3acres.com for more.
                                                        Entry<Integer, Integer, Integer> o2) {
                                                return o2.avgLoad-o1.avgLoad;
                                        }
. from: 1point3acres.com/bbs                         }
                        );. From 1point 3acres bbs

                        for(int i=0;i<n;i++){//O(n). 1point3acres.com/bbs
                                Entry<Integer,Integer,Integer> e = new Entry<Integer,Integer,Integer>(i,a[i],1);//maximum load per machine 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                                pq.add(e); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                        }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        b-=n;//used n already

                        while(b>0){//O(bxn). From 1point 3acres bbs
                                Entry<Integer,Integer,Integer> e = pq.poll();
                                b--;
                                e.avgLoad=(e.avgLoad*e.numMachine)/(e.numMachine+1);
                                e.numMachine++;
                                pq.add(e);
                        }. 1point 3acres 璁哄潧
//prepare result
                        int distributions[] = new int[n];
                        for(Entry<Integer,Integer,Integer> e:pq){
                                distributions[e.cluster] =e.numMachine;
                        }
                        return distributions;
        }
回复 支持 反对

使用道具 举报

 楼主| 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-google 1point3acres
  2. {
  3. public:
  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;. 1point 3acres 璁哄潧
  6.         int avg_load;
  7.         int index;
  8.         int num_machine;
  9. };
  10. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  11. struct mycmp
  12. { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  13.         bool operator()(cluster& c1, cluster& c2) { return c1.avg_load < c2.avg_load; }
  14. };
  15. vector<int> loadBalance(vector<int>& loads, int b)
  16. {
  17.         vector<int> res(loads.size());
  18.         if (b < loads.size()) return res;
  19.         priority_queue < cluster, vector < cluster >, mycmp> pq;
  20.         for (int i = 0; i < loads.size(); ++i)
  21.                 pq.emplace(loads[i], loads[i], i, 1);. From 1point 3acres bbs
  22.         b -= loads.size();
  23.         while (b--)
  24.         {
  25.                 auto temp = pq.top();
  26.                 pq.pop();
  27.                 temp.num_machine++;
  28.                 temp.avg_load = temp.work_load / temp.num_machine;
  29.                 pq.push(temp);
  30.         }
  31.         while (!pq.empty())
  32.         {
  33.                 auto temp = pq.top();
  34.                 pq.pop();
  35.                 res[temp.index] = temp.num_machine;
  36.         }. from: 1point3acres.com/bbs
  37.         return res;.1point3acres缃
  38. }

  39. int main()
  40. {
  41.         vector<int> loads = { 200, 450 };
  42.         auto res = loadBalance(loads, 7);
  43.         printVector(res);
  44.         return 0;
  45. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 15:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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