一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 1599|回复: 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 {.鐣欏璁哄潧-涓浜-涓夊垎鍦

  2.         public static void main(String[] args) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  3.                 Scanner in = new Scanner(System.in);
  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.         public static class Pairs implements Comparable<Pairs> {. 1point3acres.com/bbs
  23.                 int value;
  24.                 int count;
  25.                 int index;
  26.                
  27.                 Pairs(int v, int c) {
  28.                         value = v;
  29.                         count = c;
  30.                 }
  31.         
  32.                 public int getValue() {
  33.                         return value;
  34.                 }

  35.                 public void setValue(int value) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  36.                         this.value = value;
  37.                 }

  38.                 public int getCount() {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  39.                         return count;
  40.                 }

  41.                 public void setCount(int count) {
  42.                         this.count = count;
  43.                 }
  44.                 . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  45.                 public int getIndex() {
  46.                         return index;. 鍥磋鎴戜滑@1point 3 acres
  47.                 }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  48.                
  49.                 public void setIndex(int index) {-google 1point3acres
  50.                         this.index = index;
  51.                 }
  52. . Waral 鍗氬鏈夋洿澶氭枃绔,
  53.                 @Override
  54.                 public int compareTo(Pairs o) {
  55.                         // TODO Auto-generated method stub
  56.                         return this.value - o.value;
  57.                 }
  58.         }.1point3acres缃
  59.         
  60.         public static int[] solve(Pairs[] list, int Q, int M, int N) {
  61.                 int[] pos = new int[Q - 1];
  62.                 int[] rst = new int[Q - 1];
  63.                 -google 1point3acres
  64.                 ArrayList<Integer> nums = new ArrayList<Integer>();
  65.                
  66.                 Arrays.sort(list);
  67.                
  68.                 for (int i = 0; i < Q - 1; i++) {
  69.                         int idx = (int) Math.ceil((double)N * (i + 1) / (double)Q);
  70.                         pos[i] = idx;
  71.                 }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  72.                
  73.                 int count = 0;
  74.                
  75.                 for (Pairs p : list) {
  76.                         count = p.getCount() + count;
  77.                         p.setIndex(count);
  78.                 }
  79. . more info on 1point3acres.com
  80.                
  81.                 for (int n = 0; n < Q - 1; n++) {
  82.                         int x = search(list, pos[n]);
  83.                         if (x > 0) {. 1point 3acres 璁哄潧
  84.                                 rst[n] = x;
  85.                         } else if (x < 0) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  86.                                 System.out.print("wrong");
    . 1point3acres.com/bbs
  87.                         }
  88.                 }
  89. . more info on 1point3acres.com
  90.                 return rst;. visit 1point3acres.com for more.
  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;
  99.                 int end = list.length - 1;
  100.                 int mid;
  101.                 while (start + 1 < end) {
  102.                         mid = start + (end - start) / 2;. 1point3acres.com/bbs
  103.                         if (list[mid].index == target) {
  104.                                 end = mid;
  105.                         } else if (list[mid].index > target) {
  106.                                 end = mid;
  107.                         } else if (list[mid].index < target) {
  108.                                 start = mid;
  109.                         }. 1point 3acres 璁哄潧
  110.                 }
  111.                
  112.                 if (list[end].index == target) {
  113.                         return list[end].value;. 1point3acres.com/bbs
  114.                 } else if (list[start].index == target) {
  115.                         return list[start].value;
  116.                 } else if (list[start].index < target && target < list[end].index) {
  117.                         return list[end].value;
  118.                 }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  119.                 return -1;
  120.         }
  121. }
复制代码
感谢。



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

评分

1

查看全部评分

nycok 发表于 2015-11-21 08:18:28 | 显示全部楼层
楼主请问下最后找到代码的问题了不?
回复 支持 1 反对 0

使用道具 举报

zZ-IT 发表于 2015-11-15 14:23:48 | 显示全部楼层
求问楼主,你说的截图在哪里 没有找到,楼主可以给个链接 或者 发到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没过 就是挂了吗
回复 支持 反对

使用道具 举报

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% ...
. 1point3acres.com/bbs
谢谢楼主!!
回复 支持 反对

使用道具 举报

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行左 ...
. 1point3acres.com/bbs
回复 支持 反对

使用道具 举报

 楼主| 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:
http://www.1point3acres.com/bbs/thread-147277-1-1.html.1point3acres缃
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是相同的,注意判断。. Waral 鍗氬鏈夋洿澶氭枃绔,

补充内容 (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璁哄潧
@Kidsplay 你看是不是这个意思:
https://gist.github.com/xun-gong/ed02769927c879f91782

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 23:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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