传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 1512|回复: 0
收起左侧

indeed OA#15 代码分享

[复制链接] |试试Instant~ |关注本帖
一岁上山采药 发表于 2016-2-17 03:27:40 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Indeed - 网上海投 - 在线笔试 |Passfresh grad应届毕业生

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

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

x
上一个帖子(传送门)说到楼主用了一个非二分法做indeed的OA#15,时间复杂度O(m+n),今天收到通过的邮件,把代码贴出来大家参考参考。求版主赏点大米
  1.     static class Pair{
  2.         int val;
  3.         int count;
  4.         public Pair(int val, int count){
  5.             this.val = val;
  6.             this.count = count;
  7.         }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  8.     }. 鍥磋鎴戜滑@1point 3 acres

  9.     private static List<Integer> findQuantiles(long N, long Q, int M, Pair[] pairs){
  10.         List<Integer> result = new LinkedList<Integer>();
  11.         long sum = 0, k = 1;. Waral 鍗氬鏈夋洿澶氭枃绔,
  12.         long idx = (long)Math.ceil((double)N * k / Q);

  13.         for(int i = 0; i < M; i++){
  14.             sum += pairs[i].count;
  15.             while(k <= Q - 1 && idx <= sum){
  16.                 //System.out.print(idx + " ");
    -google 1point3acres
  17.                 result.add(pairs[i].val);
  18.                 idx = (long)Math.ceil((double)N * ++k / Q);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  19.             }
  20.             if(k == Q) break;
  21.         }
  22.         return result;
  23.     }

  24.     public static void main(String[] args) {
  25.         Scanner sc = new Scanner(System.in);
  26.         long Q = sc.nextInt();
  27.         int M = sc.nextInt();
  28.         long N = 0;
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  29.         Pair[] pairs = new Pair[M];. more info on 1point3acres.com

  30.         for(int i = 0; i < M; i++){-google 1point3acres
  31.             pairs[i] = new Pair(sc.nextInt(), sc.nextInt());
  32.             N += pairs[i].count;
  33.         }

  34.         Arrays.sort(pairs, new Comparator<Pair>(){
  35.             @Override
  36.             public int compare(Pair p1, Pair p2){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  37.                 return p1.val - p2. val;
  38.             }
  39.         });

  40.         List<Integer> result = findQuantiles(N, Q, M, pairs);
  41.         //System.out.println();
  42.         for(int res: result) System.out.print(res + " ");. from: 1point3acres.com/bbs
  43. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  44.         sc.close();
  45.     }
复制代码

补充内容 (2016-2-17 03:29):. from: 1point3acres.com/bbs
时间复杂度忘记考虑sort了,说错了,抱歉

评分

2

查看全部评分

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-25 10:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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