一亩三分地论坛

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

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

LiveRamp OA+第一轮电面

[复制链接] |试试Instant~ |关注本帖
独孤辰涛 发表于 2015-9-30 07:03:03 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 实习@LiveRamp - 网上海投 - 技术电面 在线笔试 |Otherfresh grad应届毕业生

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

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

x
刚刚面完第一轮电面,估计要跪,这面经相当热乎~一开始就是随便聊聊学校怎么样啊,最喜欢的课和project是什么,没聊多久就开始问题了Tenzing小哥换题了!看了地里的童鞋被他面的是find kth largest element in array,白准备了半天,也许我申的是intern,和full-time问的不一样吧
. From 1point 3acres bbs今天被问的是word ladder II,leetcode上有,大家自行练习,这还是他最后告我的,唯一的区别是返回任意一个最短的sequence path,可惜楼主没刷过这道题啊啊啊,连题目都让举了俩例子才懂,最后勉强地说了个backtracking,不知还有啥别的办法. 鍥磋鎴戜滑@1point 3 acres
但他说时间差不多了,就觉得完了,啥也不说了,继续刷提去~
我的OA也是青蛙过河,面经太多了,网上都能搜到一模一样的原题,我就不赘述了,十分感谢面经~ 我用的方法是用一个长度为X的bool array来存是否可到达,每次更新[A[i], A[i] +d)的范围为true,还有一个var更新可到达的最远位置,直到它等于X。time:O(dn), space: O(X)
求攒人品啊!. 1point 3acres 璁哄潧



. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

评分

1

查看全部评分

小A要当码农 发表于 2015-10-11 00:18:44 | 显示全部楼层
求问楼主,我马上做Intern的OA,最近是否都是青蛙过河这么一道题呢?谢谢,只准备了这个,而且貌似没找到其他的题。。。
回复 支持 反对

使用道具 举报

sanguine 发表于 2015-10-11 05:40:10 | 显示全部楼层
没懂LZ这个青蛙过河的思路

如果有5, 1,1 ,1 ,2, D = 3, X = 8
一开始0秒,1, 2, 3为true, var = 3. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
1秒,5位置,这样1, 2, 3, 5, 6, 7,8为true, var还是只能为3
2秒,1位置,这样1, 2, 3, 4, 5, 6, 7, 8都是true, var更新到4,但是这有时候还是不能跳到终点,因为1只能跳到4, 但是只有5的位置可以给青蛙跳对吧
3秒,1位置,这时候我要怎么判断var的位置了呢……整个数据都已经是TRUE了……
回复 支持 反对

使用道具 举报

 楼主| 独孤辰涛 发表于 2015-10-13 05:57:17 | 显示全部楼层
sanguine 发表于 2015-10-11 05:40
没懂LZ这个青蛙过河的思路

如果有5, 1,1 ,1 ,2, D = 3, X = 8

这里有个小trick,不知你注意到没有我那个更新的范围是[A, A[1]+d),右边是开括号,也就是不能更新A+d为true,这样的话你那个例子,第4个位置就是false,必须等到第4位置或2、3落下来叶子才能跳过去,设想就算你能跳到4,但4没有叶子,你也没法跳到4是吧
按你的例子,0为起点,8为终点,用x表示true,o表示false,刚开始设终点为true,等到全部x连起来就可以达到终点了
         012345678  var
第0秒 xxxooooox  2
第1秒 xxxooxxxx  2. 1point 3acres 璁哄潧
第2秒 xxxxoxxxx  3


回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 12:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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