📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
回复: 54
跳转到指定楼层
上一主题 下一主题
收起左侧

重发LiveRamp的OA,有原题截图,free response好坑//非故意重发,只是想大家看到原题

全局:

2016(4-6月) 码农类General 本科 全职@ - 网上海投 - 在线笔试  | | Other | 应届毕业生
首先我昨天发过这份面经,但是因为其中一道题可能我的叙述不够完美,所以重新截了图发上来。我刚发现我投了LiveRamp几个职位,然后拿到两个OA的链接,抱着好奇的心态打开了第二个,发现和我昨天做的题目一样,就给你们截了个图。在这里还要说,LiveRamp真是给OA给的好快,感觉像是系统自动反应似的,不过我也不确定,因为投了三四个只收到两个OA。不过听说他家很少招全职,大都是return offer回去的,所以就做着玩儿呗。首先来介绍一下题目,两道题,
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
面的时间,出现靠前位置的叶子(也就是没有帮助)
3. 每一秒掉下来的新叶子都有可能对全局进行影响,这个可以尝试画个图,就容易发现自己误解的地方
  1.         public static int frogJump(int[] arr, int X, int D) {
  2.                 if (arr == null || arr.length == 0 || X <= D)
  3.                         return 0;

  4.                 int[] rst = new int[X + 1];
  5.                 Arrays.fill(rst, Integer.MAX_VALUE);
  6.                 rst[0] = 0;
  7.                 // position of leaf *AND* the earliest time reach this position
  8.                 Map<Integer, Integer> leaf = new HashMap<>();
  9.                 leaf.put(0, 0);
  10.                 leaf.put(X, 0);
  11.                
  12.                 for (int i = 0; i < arr.length; i++) {
  13.                         if (!leaf.containsKey(arr[i]))
  14.                                 // the earliest time reach *position* arr[i] is *time* i
  15.                                 leaf.put(arr[i], i);
  16.                 }
  17.                
  18.                 for (int pos = 1; pos <= X; pos++) {
  19.                         if (leaf.containsKey(pos)) {
  20.                                 if (pos <= D) {
  21.                                         rst[pos] = leaf.get(pos);
  22.                                 } else {
  23.                                         for (int step = 1; step <= D; step++) {
  24.                                                 if (leaf.get(pos) < rst[pos - step]) {
  25.                                                         rst[pos] = Math.min(rst[pos], rst[pos - step]);
  26.                                                 } else {
  27.                                                         rst[pos] = Math.min(rst[pos], leaf.get(pos));
  28.                                                 }
  29.                                         }
  30.                                 }
  31.                         }
  32.                 }
  33.                
  34.                 return rst[X] == Integer.MAX_VALUE ? -1 : rst[X];
  35.         }
复制代码

补充内容 (2015-10-1 03:22):
青蛙题目也放到云盘了,好多人说有权限看不到!希望有帮助!!!

本帖子中包含更多资源

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x

评分

参与人数 3大米 +9 收起 理由
lerena + 5 感谢分享!
haomin_zz + 3 感谢分享!
attt + 1 感谢分享!

查看全部评分


上一篇:Amazon hackerrank OA, 60 min,一道题,没见过的。
下一篇:Indeed 電面
推荐
rhett.lhy 2015-10-2 07:54:33 | 只看该作者
全局:
稍微改了下处理重复叶子的问题。现在应该是O(N logK log*K)了,K = min{X, N}
  1.    
  2. public static int frogJump(int[] arr, int X, int D) {

  3.         class DisjointSet {

  4.             private java.util.concurrent.ConcurrentSkipListMap<Integer, Integer> parent;

  5.             public DisjointSet() {
  6.                 parent = new java.util.concurrent.ConcurrentSkipListMap<>();
  7.             }

  8.             public boolean check(int x, int y) {
  9.                 return findRoot(x) != -1 && findRoot(x) == findRoot(y);
  10.             }

  11.             public boolean addLeaf(int x) {
  12.                 if (parent.containsKey(x)) {
  13.                     return false;
  14.                 }
  15.                 parent.put(x, x);
  16.                 if (0 < x && x < X) {
  17.                     int other = parent.lowerKey(x);
  18.                     if (x - other <= D) {
  19.                         merge(x, other);
  20.                     }
  21.                     other = parent.higherKey(x);
  22.                     if (other - x <= D) {
  23.                         merge(x, other);
  24.                     }
  25.                 }
  26.                 return true;
  27.             }

  28.             public int findRoot(int x) {
  29.                 if (parent.get(x) == null) {
  30.                     return -1;
  31.                 }
  32.                 if (parent.get(x) == x) {
  33.                     return x;
  34.                 }
  35.                 int ans = findRoot(parent.get(x));
  36.                 parent.put(x, ans);
  37.                 return ans;
  38.             }

  39.             public void merge(int x, int y) {
  40.                 int rx = findRoot(x);
  41.                 int ry = findRoot(y);
  42.                 parent.put(ry, rx);
  43.             }
  44.         }
  45.         // end of disjoint set definition

  46.         if (X <= D) {
  47.             return 0;
  48.         }

  49.         DisjointSet ds = new DisjointSet();
  50.         ds.addLeaf(0);
  51.         ds.addLeaf(X);

  52.         for (int i=0; i<arr.length; i++) {
  53.             if (ds.addLeaf(arr[i]) && ds.check(0, X)) {
  54.                 return i;
  55.             }
  56.         }
  57.         return -1;
  58.     }
复制代码
回复

使用道具 举报

推荐
rhett.lhy 2015-10-2 07:46:17 | 只看该作者
全局:
O(N logN log*N) implementation
  1.    
  2. public static int frogJump(int[] arr, int X, int D) {

  3.         class DisjointSet {

  4.             private java.util.concurrent.ConcurrentSkipListMap<Integer, Integer> parent;

  5.             public DisjointSet() {
  6.                 parent = new java.util.concurrent.ConcurrentSkipListMap<>();
  7.             }

  8.             public boolean check(int x, int y) {
  9.                 return findRoot(x) != -1 && findRoot(x) == findRoot(y);
  10.             }

  11.             public void addLeaf(int x) {
  12.                 parent.put(x, x);
  13.                 if (0 < x && x < X) {
  14.                     int other = parent.lowerKey(x);
  15.                     if (x - other <= D) {
  16.                         merge(x, other);
  17.                     }
  18.                     other = parent.higherKey(x);
  19.                     if (other - x <= D) {
  20.                         merge(x, other);
  21.                     }
  22.                 }
  23.             }

  24.             public int findRoot(int x) {
  25.                 if (parent.get(x) == null) {
  26.                     return -1;
  27.                 }
  28.                 if (parent.get(x) == x) {
  29.                     return x;
  30.                 }
  31.                 int ans = findRoot(parent.get(x));
  32.                 parent.put(x, ans);
  33.                 return ans;
  34.             }

  35.             public void merge(int x, int y) {
  36.                 int rx = findRoot(x);
  37.                 int ry = findRoot(y);
  38.                 parent.put(ry, rx);
  39.             }
  40.         }
  41.         // end of disjoint set definition

  42.         if (X <= D) {
  43.             return 0;
  44.         }

  45.         DisjointSet ds = new DisjointSet();
  46.         ds.addLeaf(0);
  47.         ds.addLeaf(X);

  48.         for (int i=0; i<arr.length; i++) {
  49.             ds.addLeaf(arr[i]);
  50.             if (ds.check(0, X)) {
  51.                 return i;
  52.             }
  53.         }
  54.         return -1;
  55.     }
复制代码

补充内容 (2015-10-2 07:50):
再稍微优化一下,不处理重复的leaf的话,就是O(N logK log*K)了,K = min{X, N}
回复

使用道具 举报

🔗
oio14644 2015-9-23 08:57:39 | 只看该作者
全局:
题里面不是给了四个参数吗(int[] A, int N, int X, int D),为什么你写的只有三个参数?
回复

使用道具 举报

🔗
likita1002 2015-9-23 09:25:07 | 只看该作者
全局:
现在OA都是青蛙过河的 没有city那个了么?
回复

使用道具 举报

🔗
LawranceH 2015-9-23 09:59:00 | 只看该作者
全局:
楼主拿到店面了吗?
回复

使用道具 举报

🔗
 楼主| 嘟嘟要一直努力 2015-9-23 13:34:20 | 只看该作者
全局:
oio14644 发表于 2015-9-23 08:57
题里面不是给了四个参数吗(int[] A, int N, int X, int D),为什么你写的只有三个参数?

因为截图截得C语言,我写的Java,Java就是三个
回复

使用道具 举报

无效楼层,该帖已经被删除
🔗
 楼主| 嘟嘟要一直努力 2015-9-26 10:03:52 | 只看该作者
全局:
LawranceH 发表于 2015-9-23 09:59
楼主拿到店面了吗?

嗯嗯呐已经拿到店面了,前两天通知的,约的下周
回复

使用道具 举报

无效楼层,该帖已经被删除
无效楼层,该帖已经被删除
您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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