一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1861|回复: 17
收起左侧

LiveRamp OA秒过,求问有人跟Tenzing Shaw面过吗?

[复制链接] |试试Instant~ |关注本帖
ZionHill 发表于 2015-10-3 04:14:32 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 实习@LiveRamp - 网上海投 - 在线笔试 |Passfresh grad应届毕业生

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

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

x

题目就是大家都很熟悉的青蛙过河,差不多medium难度吧,跟LeetCode的Jump Game类似,用一个boolean array做就好了,O(N) time,O(X) space。不过写的有点磕磕绊绊的,用了将近一个小时才做完,后面两道Behaviour Question答得比较水。特别是“Why us”这个问题就写了四五行。。。
面完大约半小时收到邮件通知,要跟Tenzing Shaw约时间面试,请问各位有跟他面试过的吗?求分享经验。。. From 1point 3acres bbs
rhett.lhy 发表于 2015-10-3 04:28:40 | 显示全部楼层
楼主能否请教一下O(N) time O(X) space的算法是咋写的?建一个大数组然后染色吗?那样的话不应该是O(ND)的时间复杂度么
回复 支持 反对

使用道具 举报

 楼主| ZionHill 发表于 2015-10-3 04:34:28 | 显示全部楼层
rhett.lhy 发表于 2015-10-3 04:28. 鍥磋鎴戜滑@1point 3 acres
楼主能否请教一下O(N) time O(X) space的算法是咋写的?建一个大数组然后染色吗?那样的话不应该是O(ND)的 ...

哦对对,应该是O(ND)time。。不好意思
回复 支持 反对

使用道具 举报

rhett.lhy 发表于 2015-10-3 05:08:57 | 显示全部楼层
ZionHill 发表于 2015-10-3 04:34
哦对对,应该是O(ND)time。。不好意思

好吧看来不能写太快……我用并查集写了个O(NlogK) 时间 O(K) 空间的 (K = min{X, K}),被秒拒了……

补充内容 (2015-10-3 05:09):
typo: K=min{X, N}
回复 支持 反对

使用道具 举报

面假空虚 发表于 2015-10-21 06:15:41 | 显示全部楼层
ZionHill 发表于 2015-10-3 04:34
哦对对,应该是O(ND)time。。不好意思
.鐣欏璁哄潧-涓浜-涓夊垎鍦
染色的话我觉得这题是O(N)或者O(X)吧,看N和X哪个大了,用一个tail指针标记了已经染色的区域的末尾的话,每次从末尾向后开始染色,可以和D没有关系的哈~
回复 支持 反对

使用道具 举报

rhett.lhy 发表于 2015-10-21 06:27:30 | 显示全部楼层
面假空虚 发表于 2015-10-21 06:15
染色的话我觉得这题是O(N)或者O(X)吧,看N和X哪个大了,用一个tail指针标记了已经染色的区域的末尾的话, ...

但是你要分析出来一共需要maintain多少个tail指针,这些指针你怎么存储(比如是不是要保证有序)?这样分析下去你的做法就和并查集合并interval的思路类似了。
回复 支持 反对

使用道具 举报

面假空虚 发表于 2015-10-21 07:19:46 | 显示全部楼层
rhett.lhy 发表于 2015-10-21 06:27
但是你要分析出来一共需要maintain多少个tail指针,这些指针你怎么存储(比如是不是要保证有序)?这样分 ...

额,可能我们说的染色的意思不一样?我是只连续向后染的,染色了的区域是指我当前这个时间点能跳到的区域,一旦染到了河对岸,就结束了。比如我当前能跳刀位置为8, 河对岸的坐标是15,这时刻在位置10落下片叶子,我是不染色的,只记录一下10这里有了片叶子为以后染色提供信息。

补充内容 (2015-10-21 07:22):
只有当落下的叶子在已经染色了的区域(当前时间点已经可达),我才继续向后染色,新染色的区域上如果已经有之前落下来的叶子,用它继续往更远处染色。每一步都染色到可达的最远端。
回复 支持 反对

使用道具 举报

rhett.lhy 发表于 2015-10-21 08:54:38 | 显示全部楼层
面假空虚 发表于 2015-10-21 07:19
额,可能我们说的染色的意思不一样?我是只连续向后染的,染色了的区域是指我当前这个时间点能跳到的区域 ...

“...新染色的区域上如果已经有之前落下来的叶子,用它继续往更远处染色...”

这一步不就和D有关系了么,如果位置x落下一个叶子,你就要检查[x,x+D)之内有没有你之前标记过但是没染色的叶子,对吧?所以你的时间复杂度还是O(ND)的啊

回复 支持 反对

使用道具 举报

面假空虚 发表于 2015-10-21 09:33:02 | 显示全部楼层
rhett.lhy 发表于 2015-10-21 08:54
“...新染色的区域上如果已经有之前落下来的叶子,用它继续往更远处染色...”

这一步不就和D有关系了 ...

不是呀,因为记录了染过色的tail,从tail后开始判断,所以每个位置只会被染色一次的,也就和D没有关系啦。比如说我已经染到了8,之前10的位置有一片叶子,D是能跳5步,这时候6的位置落了片叶子,那我只从9开始往后染,能染到11,但是中间会check到10也有叶子,继续染到15,这时候tail就成了15了,下次有叶子来是从16开始判断。也就是说 x + D > tail 的话才染色,每一个时间点可能染 <D 个位置,也可能染特别多位置,但是最终每个位置只染一次,是个amortized 线性
回复 支持 反对

使用道具 举报

rhett.lhy 发表于 2015-10-21 22:01:42 | 显示全部楼层
面假空虚 发表于 2015-10-21 09:33
不是呀,因为记录了染过色的tail,从tail后开始判断,所以每个位置只会被染色一次的,也就和D没有关系啦 ...

啊对对对,是O(N)的~
回复 支持 反对

使用道具 举报

面假空虚 发表于 2015-10-22 03:50:47 | 显示全部楼层
rhett.lhy 发表于 2015-10-21 22:01
啊对对对,是O(N)的~

额,因为N和X的大小不确定,是O(N+X), 最坏情况遍历所有时间点,染整个河道的色。
回复 支持 反对

使用道具 举报

lovexinxu 发表于 2015-10-22 05:03:26 | 显示全部楼层
我就是Tenzing Shaw给面的,问算法复杂度的时候会问的超级细,让我解释quickselect的复杂度来着。
题目就是面经题,没啥别的。

祝好运!
回复 支持 反对

使用道具 举报

phil 发表于 2015-10-22 07:09:24 | 显示全部楼层
jump game用dp是O(N^2)复杂度的,拜问楼主以及楼上各位大神这一题是用dp的吗?
回复 支持 反对

使用道具 举报

面假空虚 发表于 2015-10-22 07:16:54 | 显示全部楼层
phil 发表于 2015-10-22 07:09
jump game用dp是O(N^2)复杂度的,拜问楼主以及楼上各位大神这一题是用dp的吗?

用greedy可以达到线性,参加我上面的回复。
回复 支持 反对

使用道具 举报

 楼主| ZionHill 发表于 2015-10-22 07:22:47 | 显示全部楼层
lovexinxu 发表于 2015-10-22 05:03
我就是Tenzing Shaw给面的,问算法复杂度的时候会问的超级细,让我解释quickselect的复杂度来着。
题目就 ...
. visit 1point3acres.com for more.
LZ早就面完了,已挂,被问了一道非常难的题,面经见:
http://www.1point3acres.com/bbs/thread-143669-1-1.html
回复 支持 反对

使用道具 举报

phil 发表于 2015-10-22 07:47:18 | 显示全部楼层
phil 发表于 2015-10-22 07:09
jump game用dp是O(N^2)复杂度的,拜问楼主以及楼上各位大神这一题是用dp的吗?

突然想起jump game 的greedy 了, 但又不会迁移到这道题上了尼玛,我再好好想想吧,真是憋死我了
回复 支持 反对

使用道具 举报

u-r-the-one 发表于 2016-2-21 11:11:44 | 显示全部楼层
面假空虚 发表于 2015-10-21 14:50
额,因为N和X的大小不确定,是O(N+X), 最坏情况遍历所有时间点,染整个河道的色。
. from: 1point3acres.com/bbs
能仔细讲讲吗 我只知道O(DN)的做法 没看懂这个O(N+X)的 谢谢啦
回复 支持 反对

使用道具 举报

面假空虚 发表于 2016-2-23 23:10:09 | 显示全部楼层
u-r-the-one 发表于 2016-2-21 11:11
能仔细讲讲吗 我只知道O(DN)的做法 没看懂这个O(N+X)的 谢谢啦
  1. class Solution {
  2.     public int solution(int[] A, int X, int D) {
  3.         // write your code in Java SE 8
  4.         if(D >= X) return 0;
  5.         else if(A == null || A.length == 0) return -1;
  6.         boolean[] hasLeave = new boolean[X]; //leave hasLeave[0] idle for convinence to express
  7.         boolean[] ableJumpTo = new boolean[X];
  8.         int tail = 0;
  9.         for( ; tail <= D; tail++) ableJumpTo[tail] = true; //deal with initial case.
  10.         for(int i = 0; i < A.length; i++) {
  11.             int curr = A[i];
  12.             hasLeave[curr] = true;         
  13.             while(hasLeave[curr] == true && ableJumpTo[curr] == true && curr + D >= tail) {
  14.                 int expandEnd = curr + D;
  15.                 curr++; //to avoid infinite while loop. visit 1point3acres.com for more.
  16.                 for( ; tail <= expandEnd; tail++) {
  17.                     if(tail == X) return i; //reach the bank, return current time.
  18.                     ableJumpTo[tail] = true;
  19.                     if(hasLeave[tail] == true) curr = tail;
  20.                 }               
  21.             }           
  22.         }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  23.         return -1;
  24.     }
  25. }
复制代码
你可以看下代码先想下,主要是while循环那块
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 13:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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