一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 1788|回复: 16
收起左侧

Indeed OA #17

[复制链接] |试试Instant~ |关注本帖
eamon_felix4213 发表于 2015-11-11 10:37:57 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Indeed - 网上海投 - 在线笔试 |Otherfresh grad应届毕业生

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

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

x
刚做完OA,题目还是 calculating quantiles,具体参考地里都有截图。有的人跑到了10个test case,小白只跑到了7个,并且两个test case没有过,这次OA应该是挂了。输出都被隐藏起来了所以完全不知道到底问题在哪。准备的过程中看了很多面经,看到还是有很多人全跑过的。所以在这里贴上自己的代码,好奇心太重,实在想知道到底哪出了问题。基本方法用的还是pair存加二分查找。. 1point 3acres 璁哄潧
  1. public class CalQuantiles {.1point3acres缃

  2.         public static void main(String[] args) {.1point3acres缃
  3.                 Scanner in = new Scanner(System.in);. 鍥磋鎴戜滑@1point 3 acres
  4.                
  5.                 int Q = in.nextInt();.鐣欏璁哄潧-涓浜-涓夊垎鍦
  6.                 int M = in.nextInt();
  7.                
  8.                 int v, c; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  9.                 int N = 0; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  10.                 Pairs[] list = new Pairs[M];
  11.                 for (int i = 0; i < M; i++) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  12.                         v = in.nextInt();
  13.                         c = in.nextInt();
  14.                         N = N + c;
  15.                         Pairs pair = new Pairs(v, c);
  16.                         list[i] = pair;
  17.                 }
  18.                
  19.                 System.out.println(Arrays.toString(solve(list, Q, M, N)));.鐣欏璁哄潧-涓浜-涓夊垎鍦
  20. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  21.         }
  22.         
  23.         public static class Pairs implements Comparable<Pairs> {
  24.                 int value;
  25.                 int count; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  26.                 int index;
  27.                
  28.                 Pairs(int v, int c) {
  29.                         value = v;
  30.                         count = c;. 1point 3acres 璁哄潧
  31.                 }
  32.         
  33.                 public int getValue() {. From 1point 3acres bbs
  34.                         return value;
  35.                 }
  36. -google 1point3acres
  37.                 public void setValue(int value) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  38.                         this.value = value;
  39.                 }

  40.                 public int getCount() {-google 1point3acres
  41.                         return count;
    . from: 1point3acres.com/bbs
  42.                 }

  43. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  44.                 public void setCount(int count) {
  45.                         this.count = count;. 鍥磋鎴戜滑@1point 3 acres
  46.                 }
  47.                 . 鍥磋鎴戜滑@1point 3 acres
  48.                 public int getIndex() {.1point3acres缃
  49.                         return index;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  50.                 }
  51.                 -google 1point3acres
  52.                 public void setIndex(int index) {
  53.                         this.index = index;
  54.                 }

  55.                 @Override
  56.                 public int compareTo(Pairs o) {
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  57.                         // TODO Auto-generated method stub. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  58.                         return this.value - o.value;
  59.                 }
  60.         }
  61.         
  62.         public static int[] solve(Pairs[] list, int Q, int M, int N) {
  63.                 int[] pos = new int[Q - 1];
  64.                 int[] rst = new int[Q - 1];
  65.                
  66.                 ArrayList<Integer> nums = new ArrayList<Integer>();
  67.                
  68.                 Arrays.sort(list);
  69.                
  70.                 for (int i = 0; i < Q - 1; i++) {
  71.                         int idx = (int) Math.ceil((double)N * (i + 1) / (double)Q);
  72.                         pos[i] = idx;
  73.                 }
  74.                 . 鍥磋鎴戜滑@1point 3 acres
  75.                 int count = 0;
  76.                
  77.                 for (Pairs p : list) {
  78.                         count = p.getCount() + count;
  79.                         p.setIndex(count);. 1point3acres.com/bbs
  80.                 }

  81.                
    . 1point 3acres 璁哄潧
  82.                 for (int n = 0; n < Q - 1; n++) {
  83.                         int x = search(list, pos[n]);
  84.                         if (x > 0) {
  85.                                 rst[n] = x; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  86.                         } else if (x < 0) {
  87.                                 System.out.print("wrong");
  88.                         }
  89.                 }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  90.                 return rst;
  91.         }
  92.         
  93.         public static int search(Pairs[] list, int target) {
  94.                 if (list.length == 0) {
  95.                         return -1;
  96.                 }
  97.                
  98.                 int start = 0;. 1point 3acres 璁哄潧
  99.                 int end = list.length - 1;
  100.                 int mid;. from: 1point3acres.com/bbs
  101.                 while (start + 1 < end) {
  102.                         mid = start + (end - start) / 2;
  103.                         if (list[mid].index == target) {
  104.                                 end = mid;. From 1point 3acres bbs
  105.                         } else if (list[mid].index > target) {
  106.                                 end = mid;
  107.                         } else if (list[mid].index < target) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  108.                                 start = mid;
  109.                         }
  110.                 }
  111.                
  112.                 if (list[end].index == target) {. From 1point 3acres bbs
  113.                         return list[end].value;
  114.                 } else if (list[start].index == target) {-google 1point3acres
  115.                         return list[start].value;
  116.                 } else if (list[start].index < target && target < list[end].index) {-google 1point3acres
  117.                         return list[end].value;
  118.                 }
  119.                 return -1;
  120.         }
  121. }
复制代码
感谢。




补充内容 (2015-11-18 14:19):
更新一下状态,刚刚通知店面

评分

1

查看全部评分

nycok 发表于 2015-11-21 08:18:28 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
楼主请问下最后找到代码的问题了不?
回复 支持 1 反对 0

使用道具 举报

zZ-IT 发表于 2015-11-15 14:23:48 | 显示全部楼层
关注一亩三分地微博:
Warald
求问楼主,你说的截图在哪里 没有找到,楼主可以给个链接 或者 发到416736479@qq.com 这里嘛 这是谢谢楼主了~~
回复 支持 反对

使用道具 举报

 楼主| eamon_felix4213 发表于 2015-11-16 00:33:56 | 显示全部楼层
zZ-IT 发表于 2015-11-15 01:23
求问楼主,你说的截图在哪里 没有找到,楼主可以给个链接 或者 发到416736479@qq.com 这里嘛 这是谢谢楼主 ...

已发邮件,链接也有 http://www.1point3acres.com/bbs/ ... adio%26sortid%3D311 收好不谢
回复 支持 反对

使用道具 举报

鬼刃道 发表于 2015-11-16 02:59:19 | 显示全部楼层
请问一下 oa只要有test没过 就是挂了吗
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

zZ-IT 发表于 2015-11-16 06:20:08 | 显示全部楼层
eamon_felix4213 发表于 2015-11-16 00:33
. Waral 鍗氬鏈夋洿澶氭枃绔,已发邮件,链接也有 http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=145192&extra=page% ...

谢谢楼主!!
回复 支持 反对

使用道具 举报

sue0927 发表于 2015-11-19 12:41:13 | 显示全部楼层
楼主写的太复杂了。。。我的core code就十行。。。。
回复 支持 反对

使用道具 举报

EverestCamp 发表于 2015-11-19 13:34:19 | 显示全部楼层
一个月前做的。 我记得不用二分查找, 好像没用到什么算法,直接按公式算就行。 处理输入的代码用了10行左右,核心代码也是10行左右
回复 支持 反对

使用道具 举报

 楼主| eamon_felix4213 发表于 2015-11-19 21:59:06 | 显示全部楼层
EverestCamp 发表于 2015-11-19 00:34
一个月前做的。 我记得不用二分查找, 好像没用到什么算法,直接按公式算就行。 处理输入的代码用了10行左 ...

回复 支持 反对

使用道具 举报

 楼主| eamon_felix4213 发表于 2015-11-19 22:00:10 | 显示全部楼层
sue0927 发表于 2015-11-18 23:41
楼主写的太复杂了。。。我的core code就十行。。。。

还是不知道问题在哪
回复 支持 反对

使用道具 举报

rosalind324 发表于 2015-11-20 00:11:22 | 显示全部楼层
check these two posts: . from: 1point3acres.com/bbs
http://www.1point3acres.com/bbs/thread-147277-1-1.html
http://www.1point3acres.com/bbs/thread-147068-1-1.html
回复 支持 反对

使用道具 举报

zZ-IT 发表于 2015-11-22 04:11:04 | 显示全部楼层
楼主和楼上, 在二分的时候 应该还要判断 list[start].index > target 的情况 , 然后 那个 因为总个数有可能超过int的最大值,所以最好还用long来存
回复 支持 反对

使用道具 举报

 楼主| eamon_felix4213 发表于 2015-11-22 11:54:47 | 显示全部楼层
zZ-IT 发表于 2015-11-21 15:11
楼主和楼上, 在二分的时候 应该还要判断 list[start].index > target 的情况 , 然后 那个 因为总个数有可 ...

首先谢谢 @zZ-IT,说的很详细,嗯,第一考虑过 start > target 的情况,但是当时不知道怎么搞的,想出来的case最后总感觉是一个伪条件,一直很混乱,第二个关于 long 的问题,肯定是需要的,但是 debug 的时候,也加上修改过,但是还是没有改善,可能是时间不够没有仔细去想,具体是哪几个变量需要改成 long
回复 支持 反对

使用道具 举报

haoxuango 发表于 2015-12-15 11:45:28 | 显示全部楼层
一共就7个吧。。。
楼主你的index -1 了吗? 就是是从0 开始的吗
回复 支持 反对

使用道具 举报

Kidsplay 发表于 2015-12-28 12:26:28 | 显示全部楼层
写太复杂了。我的做法是建立最小堆保存所有的input pair,然后计算出Q-1个index,然后依次从堆往外取就好了。Q>N的情况有可能会导致两次的index是相同的,注意判断。
-google 1point3acres
补充内容 (2015-12-27 23:27):
我的test是有7个test case,两个隐藏了,都过了。
回复 支持 反对

使用道具 举报

tonygxxx1212 发表于 2016-2-1 07:25:34 | 显示全部楼层
Kidsplay 发表于 2015-12-28 12:26. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
写太复杂了。我的做法是建立最小堆保存所有的input pair,然后计算出Q-1个index,然后依次从堆往外取就好了 ...

@Kidsplay 你看是不是这个意思:
https://gist.github.com/xun-gong/ed02769927c879f91782

Q > N 没太懂, 我试了 Q = 3, N = 3, For {1, 2, 3}  print 出来 1, 2
回复 支持 反对

使用道具 举报

Kidsplay 发表于 2016-2-18 12:39:39 | 显示全部楼层
tonygxxx1212 发表于 2016-1-31 18:25. 1point3acres.com/bbs
@Kidsplay 你看是不是这个意思:
https://gist.github.com/xun-gong/ed02769927c879f91782
. visit 1point3acres.com for more.
抱歉。。太久以前的帖子了 忘了我是怎么做的了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-2-25 22:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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