一亩三分地论坛

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

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

Liveramp OA

[复制链接] |试试Instant~ |关注本帖
sheepmiemies 发表于 2016-6-10 01:59:35 | 显示全部楼层 |阅读模式

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

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

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

x
网上opening position还是有new grad,然后投了确实还有自动的OA,但是地里最近没消息,所以他家也许不招了么?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
题目还是:(1)猴子过河(2)解释你的算法给同事听(3)为啥liveramp

原题就不发啦,大家自行搜索,地里发过好几次。这里贴几个问题讨论的帖子吧,尤其第一个大神解释答题思路,感觉很有帮助。

答题思路: http://www.1point3acres.com/bbs/thread-142307-1-1.html. 1point3acres.com/bbs
猴子问题: http://www.1point3acres.com/bbs/ ... adio%26sortid%3D311. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
sequence:http://www.1point3acres.com/bbs/ ... adio%26sortid%3D311

地里出现过的OA问题如下:.1point3acres缃
1.青蛙过河;2.猴子过河;这两个问题其实可以说完全一样,稍后讨论思路。
3.sequence
4.M cities
5.six - degre
6.选择题,在第上面第一个链接里有分享. more info on 1point3acres.com
7.behavior问题,即解释你写的算法  +  为什么选liveramp

思路:-google 1point3acres
1.青蛙过河。感谢地里大家分享的解法,这里提供一个自己的另一个思路吧。这道题最tricky的地方应该就是,原先落下的叶子够不到,但是在更新的过程中,突然又能够到了,怎么样有效更新当前的状态呢?我用了下几个变量/结构来保存/更新状态:

*一个hashset,暂且叫做reachable, 用于保存当前能够到达的所有position,空间复杂度是O(N + D)。更新过程是顺序增长,即1,2,3,4,5,6,不会出现1,2,5,6的情况(下面会解释),则一旦它的长度大于等于我们的距离X,则表示能够到达对岸。
*第二个hashset,暂且叫做unused,用于保存当前已经存在却无法够到的所有叶子,空间复杂度O(N)。. 1point 3acres 璁哄潧
*一个边界,在此边界前的所有叶子都没有价值,或者说通过那些叶子不能帮助青蛙跳得更远,暂且叫做usefulBound。

(1)base case。根据我们上述的定义,(i)如果 reachable已经覆盖了X,我们返回当前时间;(ii)如果遍历了所有可用的叶子依然不能到达X,返回-1
(2)更新过程,一共会有三种情况:
(i)case 1:如果叶子的位置在usefulBound之前,我们直接跳过。
(ii)case 2:如果叶子的位置不在reachable里,表示目前无法够到,我们把这个叶子存入unused里。
(iii)case 3:除去前两种情况,我们可以用当前的叶子更新我们的状态。假设当前时间是 i,叶子位置是 s,reachable的size是k(则表示1 - k都可达),青蛙踩在 s 上能够到达最远的地方则是 s + D,我们需要插入reachable的位置就只有 pos = [k + 1, s + D]。我们挨个插入保证了reachable的范围是无缝的,并且每个position最多插入一次。这时候我们需要再做另一件事,每当我们插入一个新的pos到reachable,我们检查pos是否存在unused里,如果存在,我们只需要把更新的范围从s + D延长到 pos +D。由于pos是单调递增的,我们保证了每个叶子最多只被检查了一次。
(3)更新结束后做两件事,(i)更新usefulBound = reachable.size() - D + 1,比如当前能覆盖1 - 6, D = 3,那新叶子至少必须在4及其以后才会有用。(2)判断reachable是否覆盖目的地X,如果覆盖,返回当前时间 i 。

复杂度:空间是O(N+D)不用多说,关于时间,由于input给的叶子array长度是N,则叶子数量不会超过N,时间也不超过N;对于reachable,最远的可达范围是最后一片叶子+最后一跳,所以是N + D,并且这些位置最多只会被插入一次;对于每次检查当前时间的叶子,三种情况都只做了常数次操作,而且每个叶子也仍然最多被插入unused这个set里一次,并且由于reachable递增的特性,每个unused里的叶子也最多只被check一次。总的下来时间复杂度就是O(N + D),由于两者量级相同可以简化为O(N)。不知道分析有没有遗漏的地方。.1point3acres缃

2. 猴子过河。这道题其实换汤不换药,但是要注意两个地方:
(1)青蛙过河的初始位置是0,目的地位置是X;但是猴子过河初始是-1,到达的位置是河对岸,比如 [0,1,2,3,4,5],则需要到达6才算过河,一共需要跳7步以上。
(2)青蛙过河的input是 时间--->出现叶子的位置,猴子过河里变成了  石头位置--->出现时间。我们需要做的只是预处理把猴子过河里的input 转置一下,就和青蛙过河的input完全一样了。值得一提的是,题目说同一时间只会有一块石头出现,省得我们再想太多。
关于复杂度的问题,就是因为(ii)的预处理,导致我们需要首先判断 “最长的时间 t”,也就是数组A中的max,然后开辟一个数组长度为 t + 1来保存  时间--->石头位置,这样问题又退化到青蛙过河。但是这时候的时间长度可能会比原始数组A要长,所以最后的时空复杂度要求是O(N + max(A))。

3. sequence,其实是求最大subset,这个set满足里面的数最大的数和最小的数相差不超过1,比如[3,1,2,2,3,4],那么最长的是[3,2,2,3],返回4。有两种思路:
(1)用hashmap统计每个数的重复次数,得到k个不同的数,然后one-by-one scan这k个数,对每个数,计算count[k-1] + count[k] 和 count[k] + count[k+1]的数量,然后更新maxLen。时空复杂度都是O(N)
(2)sort and count,其实实现的难度和(1)一样,甚至逻辑没有那么清晰,需要考虑清楚index和off-by-one的问题。常数的空间复杂度+O(nlogn)的时间

4. M cities,找出离capital距离为1,2,3....M-1的城市数量。很典型的BFS,需要的是先建立一个adjacent list,然后用queue做BFS,注意更新和使用queue的长度。

5. six-degree,这道题看地里的意思应该就是描述算法优缺点然后做选择了?比较好描述的是DFS, BFS, Dijkstra,然后Bi-direction DFS/BFS/Dijkstra吧,很惭愧没有仔细看过A*算法。

6. 选择题和behavior看我分享的第一个链接吧,那个大神描述的很详细了。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
. from: 1point3acres.com/bbs
估计现在还是有不少和我一样当初太过自信导致如今毕业了仍然待业的筒子们,当初一步慢,步步慢啊。。。。不过没关系,大家一起努力坚持,一定会有好结果!

评分

4

查看全部评分

 楼主| sheepmiemies 发表于 2016-6-11 11:50:26 | 显示全部楼层
49502292 发表于 2016-6-11 09:55
赞LZ的心态, 同跪了很多。。。

嗨。。。当初就是太不紧张了,战术勤奋,战略懒惰。。。现在稍微绷着神经,保持心情继续努力吧,毕竟想太多也没有好处啊。。。
回复 支持 1 反对 0

使用道具 举报

49502292 发表于 2016-6-11 09:55:54 | 显示全部楼层
赞LZ的心态, 同跪了很多。。。
回复 支持 反对

使用道具 举报

dajiang 发表于 2016-7-9 09:39:28 | 显示全部楼层
这家自动 OA 嘛,我收到拒信了,简历拒了。。
回复 支持 反对

使用道具 举报

 楼主| sheepmiemies 发表于 2016-7-9 13:04:04 | 显示全部楼层
dajiang 发表于 2016-7-9 09:39
这家自动 OA 嘛,我收到拒信了,简历拒了。。

不知道诶这个。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 20:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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