买房小白任秀坡在湾区买房经历(一)

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
[Google级团队]:实时大数据分析领域践行者
北京/深圳-大数据/搜索/机器学习职位
日志易机器大数据行业践行者Web/大数据/机器学习等职位-北京or深圳
把贵司招聘信息放这里
查看: 6497|回复: 13
收起左侧

讨论一下liveramp的过河问题

[复制链接] |试试Instant~ |关注本帖
gaohannk 发表于 2016-5-30 07:33:04 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@LiveRamp - 网上海投 - 在线笔试  | Other | fresh grad应届毕业生

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

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

x
liveramp的OA里面有道过河问题,这个过河问题还有两个版本,一个是青蛙,一个是猴子。
题目看连接 . Waral 鍗氬鏈夋洿澶氭枃绔,
http://www.1point3acres.com/bbs/ ... ;highlight=liveramp
http://www.1point3acres.com/bbs/ ... ;highlight=liveramp

首先说一下两个题目不同点就是A[k]的表示,
青蛙的是 A[k] represent the position where a leaf will fall at time k.
猴子的是 A[k] represent a time when the stone at position k will be out of water.
基本上就是反的,猴子的可以 A[k]=-1 表示 k 不会有stone, 对应的青蛙就应该是数组A里面没有值为K的元素
另外 根据猴子的那个图示,初始position是-1对岸是A.length, 而青蛙的似乎初始是在position 0 对岸是 X,
后面的代码是根据猴子的写的。
我想到了两种解法:第一种native 每一秒钟查看stone 和leaf 是不是可以保证过河,至少 需要A.length/D 多个stone, 也就是A.length.D 秒。 time O(max(A)*N). From 1point 3acres bbs
第二种DP, B represent 跳到position i 最少需要的时间。
B = max(min(B[i-1],B[i-2], ... , B[i-D]),A)  if B[i-1]!=-1or B[i-2]!=-1, ... , B[i-D] !=-1
      =  -1 if A= -1 or B[i-1] until B[i-D] = -1


代码如下:
  1.         public static int solution(int[] A, int D) {
  2.       if (A == null || A.length == 0). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  3.            return -1;. from: 1point3acres.com/bbs
  4.                 if (D > A.length). From 1point 3acres bbs
  5.                         return 0;
  6.                 int B[] = new int[A.length + 1];
  7.                 for (int i = 0; i < D; i++) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  8.                         B[i] = A[i];
  9.                 }
  10.                 for (int i = D; i < A.length; i++) {
  11.                         if (A[i] == -1) {
  12.                                 B[i] = -1;. Waral 鍗氬鏈夋洿澶氭枃绔,
  13.                         } else {
  14.                                 int temp = Integer.MAX_VALUE;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  15.                                 int count = 0;
  16.                                 for (int j = 1; j <= D; j++) {-google 1point3acres
  17.                                         if (B[i - j] == -1) {
  18.                                                 count++;
  19.                                                 continue;
  20.                                         }. more info on 1point3acres.com
  21.                                         temp = Math.min(temp, B[i - j]);
  22.                                 }. from: 1point3acres.com/bbs
  23.                                 B[i] = count == D ? -1 : Math.max(temp, A[i]);
  24.                         }
  25.                 }
  26.                 int res = Integer.MAX_VALUE;
  27.                 int count = 0;
  28.                 for (int j = 1; j <= D; j++) {
  29.                         if (B[A.length - j] == -1) {-google 1point3acres
  30.                                 count++;
  31.                                 continue;
  32.                         }.1point3acres缃
  33.                         res = Math.min(res, B[A.length - j]);
  34. }
  35.                 return res = count == D ? -1 : res;.1point3acres缃
  36.         }
复制代码

评分

3

查看全部评分

本帖被以下淘专辑推荐:

头像被屏蔽
garygao1993 发表于 2016-9-29 05:59:46 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 1 反对 0

使用道具 举报

 楼主| gaohannk 发表于 2016-5-30 07:33:45 | 显示全部楼层
time O(D*N)

补充内容 (2016-5-30 07:35):. more info on 1point3acres.com
B = max(min(B[i-1],B[i-2], ... , B[i-D]),A)  if B[i-1]!=-1 or B[i-2]!=-1, ... ,or B[i-D] !=-1
      =  -1 if A= -1 or B[i-1] until B[i-D] = -1
回复 支持 反对

使用道具 举报

 楼主| gaohannk 发表于 2016-5-30 07:35:38 | 显示全部楼层
gaohannk 发表于 2016-5-30 07:33
time O(D*N)
.鏈枃鍘熷垱鑷1point3acres璁哄潧
补充内容 (2016-5-30 07:35):

被什么老师丢字符呢? 算了大家自己体会一下吧。
回复 支持 反对

使用道具 举报

whitney94 发表于 2016-9-14 06:24:19 | 显示全部楼层
能问一下楼主为什么这行是取B和A的max嘛?谢谢!B = max(min(B[i-1],B[i-2], ... , B[i-D]),A)
回复 支持 反对

使用道具 举报

头像被屏蔽
garygao1993 发表于 2016-9-20 16:00:22 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

startuptech11 发表于 2016-9-29 04:44:55 | 显示全部楼层
garygao1993 发表于 2016-9-20 16:00
不知道我这个解法有没有问题?

补充内容 (2016-9-20 16:07):
. visit 1point3acres.com for more.
该代码似乎并没有工作。
回复 支持 反对

使用道具 举报

仲夏夜 发表于 2016-10-2 14:46:21 | 显示全部楼层
garygao1993 发表于 2016-9-29 05:59
楼上是烙印?...惊了...『似乎并没有工作』... seems not working?

输入为A=[-1], D=1,会报错了,楼考虑了D=N?
回复 支持 反对

使用道具 举报

头像被屏蔽
garygao1993 发表于 2016-10-2 15:52:47 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

Mimilu 发表于 2016-10-4 12:16:05 | 显示全部楼层
garygao1993 发表于 2016-9-29 05:59
楼上是烙印?...惊了...『似乎并没有工作』... seems not working?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
呼叫管理员
回复 支持 反对

使用道具 举报

SuperMe 发表于 2016-10-7 06:18:04 | 显示全部楼层
garygao1993 发表于 2016-9-29 05:59
楼上是烙印?...惊了...『似乎并没有工作』... seems not working?

烙印是什么意思??
回复 支持 反对

使用道具 举报

freeaccount 发表于 2016-11-15 06:24:11 | 显示全部楼层
SuperMe 发表于 2016-10-6 17:18
烙印是什么意思??
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
来挖坟。。。老印,就是印度人。据说是本论坛太有名所以会有印度人用google translate来访问。。。
回复 支持 反对

使用道具 举报

zhaoty0906 发表于 2016-11-29 09:50:46 | 显示全部楼层
请问下楼主,这道题可不可以用priorityqueue储存数组A里面的元素,然后dp储存当前时间所能到达的最远距离,每次只要看priorityqueue里面的最小值是不是等于当前时间,等于就说明对应的位置可以时候,更新最远距离,最远距离超过岸边值,就说明能够到达. Waral 鍗氬鏈夋洿澶氭枃绔,

补充内容 (2016-11-29 10:07):. 1point 3acres 璁哄潧
发现问题了
回复 支持 反对

使用道具 举报

miracle2138 发表于 2017-2-19 00:50:06 | 显示全部楼层
public int monkeyCross(int D, int[] A, int N){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                if(-1 + D >= N) return 0;. visit 1point3acres.com for more.
                if(A == null || A.length == 0) return -1;
                int size = 0;
                for(int i : A){
                        size = Math.max(size, i);
                }
                int[] time = new int[size + 1];
                Arrays.fill(time, -1);
                for(int i = 0; i < A.length; i++){
                        if(A[i] == -1) continue;
                        time[A[i]] = i;
                }
                Set<Integer> reach = new HashSet<>();
                reach.add(-1);
                Set<Integer> unreach = new HashSet<>();
                int max_sofar = -1;
.鐣欏璁哄潧-涓浜-涓夊垎鍦                for(int i = 0; i < time.length; i++){. from: 1point3acres.com/bbs
                        if(time[i] != -1 && !reach.contains(time[i]) && !unreach.contains(time[i])){
                                if(max_sofar + D >= time[i]){
                                        reach.add(time[i]);
                                        max_sofar = time[i];. from: 1point3acres.com/bbs
                                        for(int j = 1; j <= D; j++){
                                                int pos = j + time[i];
                                                if(unreach.contains(pos)){
                                                        max_sofar = Math.max(max_sofar, pos);
                                                        unreach.remove(pos);
                                                        reach.add(pos);
                                                }-google 1point3acres
                                        }
                                        if(max_sofar + D >= N)
                                                return i;
                                }else{. visit 1point3acres.com for more.
                                        unreach.add(time[i]);
                                }
                        }
                }
                return -1;
        }

我的解法,猴子过河。空间应该是O(N+MAX(A))时间是O(MAX(A)*D)
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-388663-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-4-20 15:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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