一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 1199|回复: 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. more info on 1point3acres.com

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){
//define distribution array and initialize it with 1 distribution, which is minimum num of distr
//also maximum of load               
                int[] distributions = new int[n];. from: 1point3acres.com/bbs
                for(int i=0;i<n;i++){//O(n)
. more info on 1point3acres.com                        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. 1point3acres.com/bbs
                                if(a/(distributions+1)>leastMax){
                                        leastMax = a/(distributions+1);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                                        j=i;
                                }
                        }-google 1point3acres
                        b--;
                        distributions[j]++;
                }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                return distributions;
        }
       

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

使用道具 举报

 楼主| andrewmasj 发表于 2016-6-18 08:22:11 | 显示全部楼层
关注一亩三分地微博:
Warald
first to make it work, then to make it tuned. most important thing is to understand it.

here's heap solution.. visit 1point3acres.com for more.

        static int[] distributeMachineToClustersPQ(int b,int n,int[] a){
                class Entry<K,V,N> {
                        K cluster;.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        V avgLoad;
                        N numMachine;
                        public Entry(K k,V v,N c){
                                cluster=k;
                                avgLoad = v;.1point3acres缃
                                numMachine = c;. from: 1point3acres.com/bbs
                        }
                } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                //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>>() {
                                        @Override
                                        public int compare(Entry<Integer, Integer, Integer> o1,. From 1point 3acres bbs
                                                        Entry<Integer, Integer, Integer> o2) {
                                                return o2.avgLoad-o1.avgLoad;
                                        }
                        }
                        );

                        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);
                        }.鐣欏璁哄潧-涓浜-涓夊垎鍦
                        b-=n;//used n already

                        while(b>0){//O(bxn)
                                Entry<Integer,Integer,Integer> e = pq.poll();
                                b--; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                                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;
        }
回复 支持 反对

使用道具 举报

 楼主| 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:
  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;
  6.         int avg_load;. 鍥磋鎴戜滑@1point 3 acres
  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)
  20.                 pq.emplace(loads[i], loads[i], i, 1);. 鍥磋鎴戜滑@1point 3 acres
  21.         b -= loads.size(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  22.         while (b--)
  23.         {
  24.                 auto temp = pq.top();
  25.                 pq.pop();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  26.                 temp.num_machine++;
  27.                 temp.avg_load = temp.work_load / temp.num_machine;
  28.                 pq.push(temp);
  29.         }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  30.         while (!pq.empty())
  31.         {. more info on 1point3acres.com
  32.                 auto temp = pq.top();
  33.                 pq.pop();
  34.                 res[temp.index] = temp.num_machine;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  35.         }
  36.         return res;
  37. }

  38. int main(). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  39. {
  40.         vector<int> loads = { 200, 450 };
  41.         auto res = loadBalance(loads, 7);
  42.         printVector(res);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  43.         return 0;
  44. }
复制代码
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-3-26 13:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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