Amazon家新鲜OA，HackRanker 90min

papayachips 发表于 2016-6-28 23:28
第二题如果num在cache里面，应该返回的貌似是 cache.get(num)+res?

好像是这么个情况呢，神奇的是这个也跑通了所有的case，估计是case不够多，没有cover到所有的情况。

最后一个其实是g家面试的一个改版. 可以从每个locker出发, 访问附近的cell, 如果cell是0(没有访问过), 设置成当前的距离, 如果不为0, 看看当前距离是不是小于cell的距离. 如果yes, 更新, 继续, 如果no..这个方向就停止了..cell的表示和楼主一样, worst case 是n^2,

第二题是某家的onsite题, x2就是二进制的往左移位, +1 就是后位补1. 所以o(k) 应该就能算出来, k是补1的时候的扫描1个数

readman 发表于 2016-6-28 23:40
最后一个其实是g家面试的一个改版. 可以从每个locker出发, 访问附近的cell, 如果cell是0(没有访问过), 设置 ...

嗯嗯，这个思路行得通，赞一个。等下我重新优化下代码。

readman 发表于 2016-6-28 23:44
第二题是某家的onsite题, x2就是二进制的往左移位, +1 就是后位补1. 所以o(k) 应该就能算出来, k是补1的时 ...

赞赞赞赞赞，当时怎么也没发现这个规律呢。这个解法犀利，学习了。

陈润鹏 发表于 2016-6-28 22:16
这题是不是求locker到城市边缘的距离呀？ 如果是的话你的BFS做反了， 第二 如果不是的话,必须每一个都比 ...

要求的是这个matrix中每个点到最近locker的距离。跟readman的思路是差不多的的。只不过我们不用检查附近的cell的距离，只要走过了，它所存的距离就一定是最短的。你可以想象我们有n个robots从每个locker向上下左右四个方向同时出发，同一时刻它们都前进一格。如果某个格已经被走过了，证明已经被从更近的locker出发的robots走过了，就不用再走了。

dg7743 发表于 2016-6-29 03:11
要求的是这个matrix中每个点到最近locker的距离。跟readman的思路是差不多的的。只不过我们不用检查附近 ...

明白了 谢谢

wobujupa 发表于 2016-6-28 09:37
我最开始的dp代码就是这样写的，这样会超时，而且空间复杂度也略高。只要是可以被2整除，那就没有比较减1 ...

I see. 谢谢你的解释

wobujupa 发表于 2016-6-28 09:37
我最开始的dp代码就是这样写的，这样会超时，而且空间复杂度也略高。只要是可以被2整除，那就没有比较减1 ...

＝＝， 你这题要求不是要输出从0 到某个数的一个结果吗？
anyway， 算n的时候，n-1和n/2对应的结果都已经算出来了，为什么还会超时？

readman 发表于 2016-6-28 23:40
最后一个其实是g家面试的一个改版. 可以从每个locker出发, 访问附近的cell, 如果cell是0(没有访问过), 设置 ...

BFS从所有的locker出发（先把所有locker加入queue）访问每个点，如果没访问过，设置当前距离，并把该点加入queue；如果已经访问过，直接忽略，并且这个方向停止（该点不加入队列）。因为BFS是从左右locker出发的，所以第一次访问某个点一定是该点到其中一个locker的最短距离；第二次访问某个点的时候一定不是最短距离。