一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 1925|回复: 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存加二分查找。
  1. public class CalQuantiles {. 鍥磋鎴戜滑@1point 3 acres

  2.         public static void main(String[] args) {
  3.                 Scanner in = new Scanner(System.in);
  4.                
  5.                 int Q = in.nextInt();. from: 1point3acres.com/bbs
  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++) {. From 1point 3acres bbs
  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. .1point3acres缃
  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 3 acres
  31.                 }
  32.         
  33.                 public int getValue() {
  34.                         return value;
  35.                 }
  36. . from: 1point3acres.com/bbs
  37.                 public void setValue(int value) {
  38.                         this.value = value;
  39.                 }. 鍥磋鎴戜滑@1point 3 acres

  40.                 public int getCount() {
  41.                         return count;
  42.                 }

  43.                 public void setCount(int count) {
  44.                         this.count = count;. 鍥磋鎴戜滑@1point 3 acres
  45.                 }
  46.                 -google 1point3acres
  47.                 public int getIndex() {
  48.                         return index; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  49.                 }
  50.                 -google 1point3acres
  51.                 public void setIndex(int index) {. from: 1point3acres.com/bbs
  52.                         this.index = index;
  53.                 }

  54.                 @Override
  55.                 public int compareTo(Pairs o) {
  56.                         // TODO Auto-generated method stub
  57.                         return this.value - o.value;
  58.                 }
  59.         }
  60.         
  61.         public static int[] solve(Pairs[] list, int Q, int M, int N) {.1point3acres缃
  62.                 int[] pos = new int[Q - 1];. from: 1point3acres.com/bbs
  63.                 int[] rst = new int[Q - 1];
  64.                
  65.                 ArrayList<Integer> nums = new ArrayList<Integer>();. more info on 1point3acres.com
  66.                 . 1point 3acres 璁哄潧
  67.                 Arrays.sort(list);
  68.                
  69.                 for (int i = 0; i < Q - 1; i++) {
  70.                         int idx = (int) Math.ceil((double)N * (i + 1) / (double)Q);. 鍥磋鎴戜滑@1point 3 acres
  71.                         pos[i] = idx;
  72.                 }
  73.                
  74.                 int count = 0;
  75.                
  76.                 for (Pairs p : list) {
  77.                         count = p.getCount() + count;
  78.                         p.setIndex(count);
  79.                 }.鏈枃鍘熷垱鑷1point3acres璁哄潧

  80.                
  81.                 for (int n = 0; n < Q - 1; n++) {
  82.                         int x = search(list, pos[n]);-google 1point3acres
  83.                         if (x > 0) {. 鍥磋鎴戜滑@1point 3 acres
  84.                                 rst[n] = x;
  85.                         } else if (x < 0) {
  86.                                 System.out.print("wrong");
  87.                         }
  88.                 }

  89.                 return rst;
  90.         }
  91.         
  92.         public static int search(Pairs[] list, int target) {
  93.                 if (list.length == 0) {
  94.                         return -1;
  95.                 }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  96.                
  97.                 int start = 0;
  98.                 int end = list.length - 1;. From 1point 3acres bbs
  99.                 int mid;
  100.                 while (start + 1 < end) {
  101.                         mid = start + (end - start) / 2;
  102.                         if (list[mid].index == target) {
  103.                                 end = mid;
  104.                         } else if (list[mid].index > target) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  105.                                 end = mid;
  106.                         } else if (list[mid].index < target) {
  107.                                 start = mid;
  108.                         }
  109.                 }
  110.                 .鏈枃鍘熷垱鑷1point3acres璁哄潧
  111.                 if (list[end].index == target) {-google 1point3acres
  112.                         return list[end].value;
  113.                 } else if (list[start].index == target) {
  114.                         return list[start].value;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  115.                 } else if (list[start].index < target && target < list[end].index) {
  116.                         return list[end].value;
  117.                 }
  118.                 return -1;
  119.         }
  120. }
复制代码
感谢。



. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (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
已发邮件,链接也有 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. 1point3acres.com/bbs
楼主写的太复杂了。。。我的core code就十行。。。。

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

使用道具 举报

rosalind324 发表于 2015-11-20 00:11:22 | 显示全部楼层
check these two posts: . 鍥磋鎴戜滑@1point 3 acres
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是相同的,注意判断。

补充内容 (2015-12-27 23:27):
. Waral 鍗氬鏈夋洿澶氭枃绔,我的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
@Kidsplay 你看是不是这个意思: . visit 1point3acres.com for more.
https://gist.github.com/xun-gong/ed02769927c879f91782

抱歉。。太久以前的帖子了 忘了我是怎么做的了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-3-28 14:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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