一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
Airbnb 数据科学职位
in analytics and inference
游戏初创公司
招聘工程师、Designer和游戏策划
游戏初创公司DreamCraft招聘工程师、UIUX Designer和游戏策划
电商初创公司Good Days
招聘SDE/UI/TPM实习生
把贵司招聘信息放这里
查看: 1048|回复: 9
收起左侧

POCKET GEMS Challenge OA4 经验

[复制链接] |试试Instant~ |关注本帖
630904334 发表于 2017-10-29 09:37:43 | 显示全部楼层 |阅读模式

2018(7-9月) 码农类 本科 全职@PoketGem - 校园招聘会 - 校园招聘会 在线笔试 |Otherfresh grad应届毕业生

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

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

x
拖了一个星期才做完的OA,看了不少地里的OA经验,我也在这里写一下吧。
题目是这两个题目,https://instant.1point3acres.com/thread/285075,感谢greenmania。第一题很简单,地里有答案可能?我贴出来我看到的吧,希望原作者看到后告诉我,我会修改的。
  1. static String canReach(int x1, int y1, int x2, int y2) {
  2.         return helper(x1, y1, x2, y2) ? "Yes" : "No";
  3.     }
  4.     private static boolean helper(int x1, int y1, int x2, int y2) {. more info on 1point3acres.com
  5.         if (x1 > x2 || y1 > y2) { return false; }-google 1point3acres
  6.         if (x1 == x2 && y1 == y2) { return true; }
  7.         return helper(x1 + y1, y1, x2, y2) || helper(x1, x1 + y1, x2, y2);
  8.     }
复制代码
我重点描述一下第二题吧(有点可惜,最终由两个case超时了,用weighted union find可能会好一些)
hackerrank中给的输入是,(int n, String[] queryType, int[] students1, int[]students2),n是指总共有n个学生,queryType中要么是"Friend"要么是“Total”,“Friend"操作内容是把学生 i 和学生 j 连接起来,对应union find里的union操作,"Total"是内容计算出学生 i 和学生 j 总共的朋友圈个数, students1里是q个学生(可以理解为操作中的 i 学生)students2里是q个学生(可以理解为操作中的 j 学生)。要求的返回值居然是个int[],这个数组里存着每一次"Total"操作的结果。
我按照印象把代码贴出来吧,写的有些地方不严谨,还望指正。
  1. static int[] friendcircle(int n, String[] queryType, int[] students1, int[] students2) {
  2.                 List<Integer> res = new ArrayList<Integer>();
  3.                 int length = queryType.length;
  4.                 int[] students = new int[n+1];
  5.                 for(int i = 0; i<n; i++){
  6.                         students[i] = i+1;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  7.                 } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

  8.                 for(int i = 0; i<length; i++){
  9.                         if(queryType[i].equals("Friend")){. visit 1point3acres.com for more.
  10.                                 union(students, students1[i], students2[i]);
  11.                         }
  12.                         if(queryType[i].equals("Total")){
  13.                                 res.add(getSize(students, students1[i], students2[i]));
  14.                         }
  15.                 }

  16.                 int k = res.size();
  17.                 int[] realres = new int[k];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  18.                 for(int i = 0; i<k; i++){
  19.                         realres[i] = res.get(i);
  20.                 }
  21.                 return realres;
  22.         }
  23.        
  24.         public static int getSize(int[] students, int i, int j) {
  25.                 int root_i = findRoot(students, i);
  26.                 int root_j = findRoot(students, j);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  27.                 int size = 0;
  28.                 for (int k = 1; k < students.length; k++) {
  29.                         if (findRoot(students, k) == root_i || findRoot(students, k) == root_j) { size++; }
  30.                 }
  31.                 return size;. from: 1point3acres.com/bbs
  32.         }
  33.        
  34.         public static void union(int[] students, int i, int j) {. 鍥磋鎴戜滑@1point 3 acres
  35.                 int i_root = findRoot(students, i);
  36.                 int j_root = findRoot(students, j);
  37.                 if (i_root != j_root) {
  38.                         students[i_root-1] = j_root;
  39.                 }
  40.         }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴


  41.         private static int findRoot(int[] students, int x) {
  42.                 int root = x, cur = x, temp = -1;
  43.                 while (students[root-1] != root) { root = students[root-1]; }. visit 1point3acres.com for more.
  44.                 while (students[cur-1] != cur) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  45.                         temp = students[cur-1];
  46.                         students[cur] = root;
  47.                         cur = temp;
  48.                 }
  49.                 return root;       
  50.         }
复制代码
祝大家offer满满。
别像我一样做个拖拉机....
. visit 1point3acres.com for more.求点赞TAT,求各种,好多帖子都看不了,心好痛TAT....




补充内容 (2017-11-22 02:29):
昨天突然收到这家约电话面试,都过去一个月了,我以为OA没做好然后直接默拒了...可能只是电面着玩玩?

评分

9

查看全部评分

asd101200 发表于 2017-11-1 05:41:12 | 显示全部楼层
我感觉第一题的代码有问题,if (x1 > x2 || y1 > y2) { return false; } 这里不对吧,因为即使x1 > x2, 但还有可能x1 + y1 == x2, 因为y1可正可负,同理y1,y2. 除非题里明确说x1,y1,x2,y2,都大于0. (-1,-1,-1,-2)这个test case你的代码过不了。
回复 支持 反对

使用道具 举报

 楼主| 630904334 发表于 2017-11-1 07:24:01 | 显示全部楼层
asd101200 发表于 2017-11-1 05:41
我感觉第一题的代码有问题,if (x1 > x2 || y1 > y2) { return false; } 这里不对吧,因为即使x1 > x2, 但 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
不好意思,我贴的是我参考的代代码,现在是我自己写在OA里的代码
回复 支持 反对

使用道具 举报

 楼主| 630904334 发表于 2017-11-1 07:24:24 | 显示全部楼层
  1. public class canReach {
  2.     public static void main(String[] args) {
  3.         int x1 = 1;
  4.         int y1 = 4; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  5.         int x2 = 5;
  6.         int y2 = 9;

  7.         String res = canarrive(x1,y1,x2,y2);. from: 1point3acres.com/bbs

  8.         System.out.println(res);
  9.     }

  10.     public static String canarrive(int x1, int y1, int x2, int y2){
  11.         if(x1 == x2 && y1 == y2){
  12.             return "Yes";
  13.         }
  14.         if(x1 > x2 || y1 > y2){
  15.             return "No";
  16.         }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  17.         return (canarrive(x1 + y1, y1,x2,y2).equals("Yes") || canarrive(x1, y1 + x1, x2,y2).equals("Yes")) ? "Yes":"No";
  18.     }-google 1point3acres
  19. }
复制代码

补充内容 (2017-11-1 08:37):
额,这是我测试的时候用的,OA里只需要"canarrive"那个function就可以了
回复 支持 反对

使用道具 举报

shanL 发表于 2017-11-1 08:27:15 | 显示全部楼层
感谢楼主分享!
回复 支持 反对

使用道具 举报

小师妹 发表于 2017-11-4 12:24:47 | 显示全部楼层
用了weighted union find还是两个test case超时,不懂
回复 支持 反对

使用道具 举报

 楼主| 630904334 发表于 2017-11-4 13:31:33 | 显示全部楼层
小师妹 发表于 2017-11-4 12:24
用了weighted union find还是两个test case超时,不懂
. from: 1point3acres.com/bbs
patpat把重心放在其他公司吧
回复 支持 反对

使用道具 举报

SXY123 发表于 2017-11-5 12:38:43 | 显示全部楼层
630904334 发表于 2017-11-1 07:24
补充内容 (2017-11-1 08:37):
额,这是我测试的时候用的,OA里只需要"canarrive"那个function就可以了

. Waral 鍗氬鏈夋洿澶氭枃绔,为什么我觉得第二个if语句应该是大于等于,x, y都是正数,应该不存在0的情况
回复 支持 反对

使用道具 举报

AryaStark 发表于 2017-11-20 12:53:36 | 显示全部楼层
第二个问题,我第五个第九个和最后三个test都是wrong answer。。。请问楼主遇到什么一开始没过的地方后来调过了吗。。醉了,提前15分钟写完死活找不错误来。。
回复 支持 反对

使用道具 举报

rickliang 发表于 2017-12-4 04:00:41 | 显示全部楼层
请问楼主 角标 root - 1 是什么意思啊?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2018-1-20 09:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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