Liveramp OA

网上opening position还是有new grad，然后投了确实还有自动的OA，但是地里最近没消息，所以他家也许不招了么？

题目还是：（1）猴子过河（2）解释你的算法给同事听（3）为啥liveramp

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

答题思路：
猴子问题：
sequence：

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

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

*一个hashset，暂且叫做reachable， 用于保存当前能够到达的所有position，空间复杂度是O(N + D)。更新过程是顺序增长，即1,2,3,4,5,6，不会出现1,2,5,6的情况（下面会解释），则一旦它的长度大于等于我们的距离X，则表示能够到达对岸。
*第二个hashset，暂且叫做unused，用于保存当前已经存在却无法够到的所有叶子，空间复杂度O(N)。

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

度和（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看我分享的第一个链接吧，那个大神描述的很详细了。

估计现在还是有不少和我一样当初太过自信导致如今毕业了仍然待业的筒子们，当初一步慢，步步慢啊。。。。不过没关系，大家一起努力坚持，一定会有好结果！

49502292 发表于 2016-6-11 09:55
赞LZ的心态， 同跪了很多。。。

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

赞LZ的心态， 同跪了很多。。。

鹏鹏加油！

这家自动 OA 嘛，我收到拒信了，简历拒了。。

dajiang 发表于 2016-7-9 09:39
这家自动 OA 嘛，我收到拒信了，简历拒了。。

不知道诶这个。。。

感觉青蛙那道题有点问题题啊
hashset是不能排序的，所以reachable应该是一个list类型，这样的话就应该考虑维护有序list的代价即插入操作，插入操作应该是Oi的。
所以我觉得是不是再用一个max变量记录目前到达的最远距离，这样就不要维护有序list了

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

其实解法可以是On2，也可以是Ond，只需要修改一下inner for循环即可，是按照步数遍历还是set遍历。