推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 4799|回复: 7
收起左侧

liveramp oa 面经

[复制链接] |试试Instant~ |关注本帖
zwcelesta 发表于 2015-9-13 11:36:28 | 显示全部楼层 |阅读模式

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

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

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

x
Liveramp codlity OA
一道算法题,一个问为什么感兴趣我们公司-google 1point3acres

算法题:青蛙过河。

输入一个Array, X,D,最早可以跳过X的时刻。

1 有只青蛙要过河,起始位置position 0,一路跳到 X,每次跳得距离 在1 ~ D,一秒可以跳很多次的样子只要有叶子可以停。。。
2 每秒都会落下一片叶子,青蛙可以停在上面(叶子不会消失) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
3 给了一个Array, Array[k] 表示,k秒落下叶子的位置

详细得跟这个帖子一样:http://www.meetqun.com/thread-10851-1-1.html

思路:* y, B$ w7 Z- u) W; ?1 I. G- _
一个hashtable 1个记录叶子的位置跟最早掉下时间。然后dp的思路。
. Waral 鍗氬鏈夋洿澶氭枃绔,
int solution(vector<int> &A, int X, int D) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
    if(X<=D) return 0;. from: 1point3acres.com/bbs
    vector<int> res(X+1,100000);
    map<int,int> leaf;
    res[0]=0;
    leaf[0]=0;
    leaf[X]=0;
    for(int i=0;i<A.size();++i){
        if(leaf.count(A)) continue;
        else leaf[A]=i;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    }
    for(int i=1;i<=X;++i){
        if(!leaf.count(i)) continue;
        if(i<=D){
            if(leaf.count(i)) res=leaf;
        }. visit 1point3acres.com for more.
        else{
            for(int k=D;k>0;--k){
                if(leaf<=res[i-k]) res=min(res,res[i-k]);
                else res=min(res,leaf);
            }
. 鍥磋鎴戜滑@1point 3 acres        }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    } . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    return res[X];
}

评分

1

查看全部评分

Laurinda93 发表于 2015-9-18 14:27:54 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
个人觉得这个解法应该是没问题的,并且要简单很多;也麻烦lz和大家一起看看思路就是在每次做D步更新,然后这这个范围内不断更新最大范围,并判断是否能在当前位置跳到;如果可以就返回当前位置,否则更新当前能到达的最大范围





  1. -google 1point3acres
  2. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  3. <p class="p1"><span class="Apple-tab-span">        </span><span class="s1">public</span> <span class="s1">static</span> <span class="s1">int</span> frogJump(<span class="s1">int</span>[] <span class="s2">arr</span>, <span class="s1">int</span> <span class="s2">X</span>, <span class="s1">int</span> <span class="s2">D</span>) {</p><p class="p1"><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="s1">if</span> (<span class="s2">arr</span> == <span class="s1">null</span> || <span class="s2">arr</span>.<span class="s3">length</span> == 0 || <span class="s2">X</span> <= <span class="s2">D</span>)</p><p class="p1"><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="s1">return</span> 0;</p><p class="p2">
  4. </p><p class="p1"><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="s1">int</span> <span class="s2">left</span> = 0;</p><p class="p1"><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="s1">int</span> <span class="s2">right</span> = <span class="s2">D</span>;</p><p class="p1"><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="s1">int</span> <span class="s2">maxRange</span> = 0;</p><p class="p2">
  5. </p><p class="p1"><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="s1">while</span> (<span class="s2">left</span> < <span class="s2">right</span>) {</p><p class="p1"><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="s2">maxRange</span> = Math.max(<span class="s2">maxRange</span>, <span class="s2">arr</span>[<span class="s2">left</span>] + <span class="s2">D</span>);</p><p class="p1"><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="s1">if</span> (<span class="s2">maxRange</span> >= <span class="s2">X</span>)</p><p class="p1"><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="s1">return</span> <span class="s2">left</span>;</p><p class="p1"><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="s2">left</span>++;</p><p class="p3"><span class="s4"><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span></span>right<span class="s4"> = </span>maxRange<span class="s4">;</span></p><p class="p1"><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span>}</p><p class="p1"><span class="Apple-tab-span">        </span><span class="Apple-tab-span">        </span><span class="s1">return</span> Integer.<span class="s3">MAX_VALUE</span>;</p><p class="p1">





  6. -google 1point3acres
  7. -google 1point3acres




  8. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  9. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴











  10. </p><p class="p1"><span class="Apple-tab-span">        </span>}</p>
复制代码
回复 支持 反对

使用道具 举报

Laurinda93 发表于 2015-9-18 14:28:50 | 显示全部楼层
关注一亩三分地微博:
Warald
Laurinda93 发表于 2015-9-18 14:27
个人觉得这个解法应该是没问题的,并且要简单很多;也麻烦lz和大家一起看看思路就是在每次做D步更新,然后 ...

不知道为什么上一条乱码
  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 left = 0;
  5.                 int right = D;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  6.                 int maxRange = 0;. from: 1point3acres.com/bbs

  7.                 while (left < right) {
  8.                         maxRange = Math.max(maxRange, arr[left] + D);
  9.                         if (maxRange >= X)
  10.                                 return left;
  11.                         left++;

  12.                         right = maxRange;
  13.                 }
  14.                 return Integer.MAX_VALUE;
  15.         }
复制代码
回复 支持 反对

使用道具 举报

QawsQAER 发表于 2015-9-19 01:37:38 | 显示全部楼层
Laurinda93 发表于 2015-9-18 14:28
不知道为什么上一条乱码

是不是读错题了?
根据我的理解,你的代码似乎是把arr[k]当成在可以跳到位置为arr[k]的树叶上(类似leetcode Jump Game那道题?)。. 鍥磋鎴戜滑@1point 3 acres
但是根据题意,arr[k]是指在第k秒会多增一个位置为arr[k]的树叶。

例如test case
arr[] = {5,1,0,0,2}, x = 5, d = 2,
根据你的解法,一上来这个青蛙就能达到目的地了,返回0.
然而根据题意,应该是在第0秒的时候,position 5 有一片树叶, 但是青蛙最多能跳的距离只为2, 所以不可能以上来就调到position 5 呀?
回复 支持 反对

使用道具 举报

Laurinda93 发表于 2015-9-19 07:08:35 | 显示全部楼层
QawsQAER 发表于 2015-9-19 01:37
是不是读错题了?
根据我的理解,你的代码似乎是把arr[k]当成在可以跳到位置为arr[k]的树叶上(类似leet ...

ok~~~谢谢啦 我觉得是我理解错了呢哭
再去研究一下嘿嘿~~~
回复 支持 反对

使用道具 举报

yangmyfly 发表于 2016-9-20 21:09:14 来自手机 | 显示全部楼层
但是贪心就可以吧,每次跳到能跳的最远的位置?
回复 支持 反对

使用道具 举报

yangmyfly 发表于 2016-9-20 21:11:47 来自手机 | 显示全部楼层
如果求所需最少踩的叶子才需要dp吧?
回复 支持 反对

使用道具 举报

gengyige 发表于 2016-12-11 09:20:59 | 显示全部楼层
Laurinda93 发表于 2015-9-19 07:08
ok~~~谢谢啦 我觉得是我理解错了呢哭
再去研究一下嘿嘿~~~

我觉得算每秒最多能到哪可以吧,不懂为何偏要用hashamp呢,明明一个extra O(1)不可以解决吗?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-28 00:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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