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


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 2529|回复: 16
收起左侧

Indeed OA #17

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

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

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

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

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

  2.         public static void main(String[] args) {
  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. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  21.         }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  22.         . from: 1point3acres.com/bbs
  23.         public static class Pairs implements Comparable<Pairs> {
  24.                 int value;
  25.                 int count;
  26.                 int index;
  27.                
  28.                 Pairs(int v, int c) {. 1point 3acres 璁哄潧
  29.                         value = v;
  30.                         count = c;
  31.                 }
  32.         
  33.                 public int getValue() {
  34.                         return value;
  35.                 }. 鍥磋鎴戜滑@1point 3 acres

  36.                 public void setValue(int value) {. from: 1point3acres.com/bbs
  37.                         this.value = value;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  38.                 }

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

  42.                 public void setCount(int count) {
  43.                         this.count = count;
  44.                 }
  45.                
  46.                 public int getIndex() {
  47.                         return index;
  48.                 }
  49.                
  50.                 public void setIndex(int index) {
  51.                         this.index = index;
  52.                 }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  53.                 @Override
  54.                 public int compareTo(Pairs o) {
  55.                         // TODO Auto-generated method stub
  56.                         return this.value - o.value;
  57.                 }
  58.         }
  59.         
  60.         public static int[] solve(Pairs[] list, int Q, int M, int N) {
  61.                 int[] pos = new int[Q - 1];. Waral 鍗氬鏈夋洿澶氭枃绔,
  62.                 int[] rst = new int[Q - 1];.鏈枃鍘熷垱鑷1point3acres璁哄潧
  63.                
  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;. from: 1point3acres.com/bbs
  74.                 . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  75.                 for (Pairs p : list) {
  76.                         count = p.getCount() + count;
  77.                         p.setIndex(count);
  78.                 }

  79.                
  80.                 for (int n = 0; n < Q - 1; n++) {
  81.                         int x = search(list, pos[n]);
  82.                         if (x > 0) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  83.                                 rst[n] = x;
  84.                         } else if (x < 0) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  85.                                 System.out.print("wrong");
  86.                         }
  87.                 }

  88.                 return rst;
  89.         }
  90.         
  91.         public static int search(Pairs[] list, int target) {
  92.                 if (list.length == 0) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  93.                         return -1;
  94.                 }
  95.                
  96.                 int start = 0;
  97.                 int end = list.length - 1;-google 1point3acres
  98.                 int mid;
  99.                 while (start + 1 < end) {
  100.                         mid = start + (end - start) / 2;
  101.                         if (list[mid].index == target) {. 鍥磋鎴戜滑@1point 3 acres
  102.                                 end = mid;. Waral 鍗氬鏈夋洿澶氭枃绔,
  103.                         } else if (list[mid].index > target) {
  104.                                 end = mid;
  105.                         } else if (list[mid].index < target) {
    . more info on 1point3acres.com
  106.                                 start = mid;
  107.                         }
  108.                 }
  109.                 .鏈枃鍘熷垱鑷1point3acres璁哄潧
  110.                 if (list[end].index == target) {
  111.                         return list[end].value;
  112.                 } else if (list[start].index == target) {
  113.                         return list[start].value;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  114.                 } else if (list[start].index < target && target < list[end].index) {
  115.                         return list[end].value;
  116.                 }
  117.                 return -1;
  118.         }
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  119. }
复制代码
感谢。. From 1point 3acres bbs


.鐣欏璁哄潧-涓浜-涓夊垎鍦

补充内容 (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 这里嘛 这是谢谢楼主 ...

. 鍥磋鎴戜滑@1point 3 acres已发邮件,链接也有 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% ...

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

使用道具 举报

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. from: 1point3acres.com/bbs
一个月前做的。 我记得不用二分查找, 好像没用到什么算法,直接按公式算就行。 处理输入的代码用了10行左 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
回复 支持 反对

使用道具 举报

 楼主| eamon_felix4213 发表于 2015-11-19 22:00:10 | 显示全部楼层
sue0927 发表于 2015-11-18 23:41. Waral 鍗氬鏈夋洿澶氭枃绔,
楼主写的太复杂了。。。我的core code就十行。。。。

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

使用道具 举报

rosalind324 发表于 2015-11-20 00:11:22 | 显示全部楼层
check these two posts:
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. more info on 1point3acres.com
楼主和楼上, 在二分的时候 应该还要判断 list[start].index > target 的情况 , 然后 那个 因为总个数有可 ...

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

使用道具 举报

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

使用道具 举报

Kidsplay 发表于 2015-12-28 12:26:28 | 显示全部楼层
写太复杂了。我的做法是建立最小堆保存所有的input pair,然后计算出Q-1个index,然后依次从堆往外取就好了。Q>N的情况有可能会导致两次的index是相同的,注意判断。

补充内容 (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
. From 1point 3acres bbs
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 你看是不是这个意思:
https://gist.github.com/xun-gong/ed02769927c879f91782
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
抱歉。。太久以前的帖子了 忘了我是怎么做的了
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-22 02:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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