當了一年的 Facebook Rotational Software Engineer 心得分享

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 1747|回复: 0
收起左侧

indeed OA#15 代码分享

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

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

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

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

x
上一个帖子(传送门)说到楼主用了一个非二分法做indeed的OA#15,时间复杂度O(m+n),今天收到通过的邮件,把代码贴出来大家参考参考。求版主赏点大米
  1.     static class Pair{
  2.         int val;. more info on 1point3acres
  3.         int count;
  4.         public Pair(int val, int count){
  5.             this.val = val;
  6.             this.count = count;
  7.         }
  8.     }

  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;. 1point3acres
  12.         long idx = (long)Math.ceil((double)N * k / Q);
  13. . 留学申请论坛-一亩三分地
  14.         for(int i = 0; i < M; i++){
  15.             sum += pairs[i].count;
  16.             while(k <= Q - 1 && idx <= sum){. from: 1point3acres
  17.                 //System.out.print(idx + " ");
  18.                 result.add(pairs[i].val);
  19.                 idx = (long)Math.ceil((double)N * ++k / Q);
  20.             }. 牛人云集,一亩三分地
  21.             if(k == Q) break;
  22.         }
  23.         return result;
  24.     }

  25.     public static void main(String[] args) {
  26.         Scanner sc = new Scanner(System.in);
  27.         long Q = sc.nextInt();. from: 1point3acres
  28.         int M = sc.nextInt();
  29.         long N = 0;
  30.         Pair[] pairs = new Pair[M];

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

  35.         Arrays.sort(pairs, new Comparator<Pair>(){
  36.             @Override
  37.             public int compare(Pair p1, Pair p2){
  38.                 return p1.val - p2. val;
  39.             }. 牛人云集,一亩三分地
  40.         });

  41.         List<Integer> result = findQuantiles(N, Q, M, pairs);
  42.         //System.out.println();
  43.         for(int res: result) System.out.print(res + " "); 来源一亩.三分地论坛.

  44.         sc.close();
  45.     }
复制代码

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

评分

3

查看全部评分

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-20 20:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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