一亩三分地论坛

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

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

Amazon家新鲜OA,HackRanker 90min

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

2016(4-6月) 码农类 本科 全职@Amazon - 猎头 - HR筛选 |Other在职跳槽

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

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

x
昨天刚刚做的OA,是Marketplace的Interview Event,但是不晓得为什么写着是April的,我要参加的应该是七月份的。之前网上找面经,找到这个http://www.1point3acres.com/bbs/thread-169516-1-1.html
题目除了第一题是一样的,剩下两个都是新题(没做太多准备工作,也可能有人分享了我没看到). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

第一题: 找第一个重复出现的字符串,字符串可能由多个空格/分号/冒号/逗号/句号/减号 分隔开。
思路就是用regex split就好。代码如下:
  1. static String firstRepeatedWord(String s) {
  2.         if(s == null || s.length() == 0) return "";
  3.         String[] arr = s.split("\\s+|,+|\\.+|:+|;+|-+");
  4.         Set<String> set = new HashSet<String>();
  5.         for(String str : arr){
  6.             if(!set.add(str)){
  7.                 return str;
  8.             }
  9.         }
  10.         return "";
  11.     }
复制代码
第二题: Two Operations,题意是从零开始,只有两种操作可供选择,+ 1 和 × 2,求到某个数字的最小的操作次数.  . From 1point 3acres bbs
比如(从左向右计算,我就不加括号了)
. 1point 3acres 璁哄潧       3 = 0 +1+1+1 (3) / 0 + 1 * 2 + 1(3)  
       5 = 0 + 1 * 2 * 2 + 1(4)
上来想复杂了,还考虑用DP去做,后来发现有几个case超时。后来发现,* 2 操作一定比 + 1操作快,然后就改了下,然后就pass了test case。因为输入项里说明n <= pow(10, 16), 所以这里用Integet.parseInt(S)会报异常,所以用Long去接收。最后加了个cache优化一下。
代码如下:
  1. static Map<Long, Integer> cache = new HashMap<>();
  2.    
  3.     static int[] MinOperations(String[] nvalues) {
  4.         if(nvalues == null || nvalues.length == 0) return new int[0];
  5.         int len = nvalues.length;
  6.         int[] res = new int[len];
  7.         for(int i = 0; i < len; i++){
  8.             res[i] = helper(Long.parseLong(nvalues[i]));
  9.         }
  10.         return res;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  11.     }. 1point 3acres 璁哄潧

  12.     public static int helper(long num){
  13.         if(num == 0) return 0;
  14.         int res = 0;
  15.         while(num > 1){
    .1point3acres缃
  16.             if(cache.containsKey(num)){
  17.                 return cache.get(num) + 1;
  18.             }
  19.             if(num % 2 == 0){
  20.                 num /= 2;
  21.                 res++;
  22.             }else{. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  23.                 num--;
  24.                 res++;
  25.             }. from: 1point3acres.com/bbs
  26.         }
  27.         cache.put(num, res + 1);
  28.         return res + 1;
  29.     }
复制代码
第三题: Amazon Locker Location 神马神马的。题目的介绍特别长,看着高大上,但是题意其实挺简单。
.鏈枃鍘熷垱鑷1point3acres璁哄潧input是这样: static int[][] getLockerDistanceGrid(int cityLength, int cityWidth, int[] lockerXCoordinates, int[] lockerYCoordinates)
cityLength/cityWidth 代表的是一个city组成的block的长与宽,每个坐标代表一个城市,lockerXCoordinates代表的是locker位置的x坐标,lockerYCoordinates代表的是locker位置的纵坐标。. 1point3acres.com/bbs
output是: 求每一个城市对应的最近的locker的distance。distance是两个坐标的x与y的差值(绝对值)加和。
我的做法是便利二维数组,每个点和所有locker求距离,取最小值。如果长宽分别是m n,有k个locker的话,复杂度是O(mnk)。结果也顺利的pass了所有的test case。 代码如下
  1. static int[][] getLockerDistanceGrid(int cityLength, int cityWidth, int[] lockerXCoordinates, int[] lockerYCoordinates) {
  2.         int[][] res = new int[cityLength][cityWidth];
  3.         for(int i = 0; i < cityLength; i++){
  4.             for(int j = 0; j < cityWidth; j++){
  5.                 res[i][j] = Integer.MAX_VALUE;
  6.                 for(int m = 0; m < lockerXCoordinates.length; m++){. 1point 3acres 璁哄潧
  7.                     res[i][j] = Math.min(res[i][j], Math.abs(lockerXCoordinates[m] - i - 1) + Math.abs(lockerYCoordinates[m] - j - 1));
  8.                 }
  9.             }
  10.         }
  11.         return res;
  12.     }. From 1point 3acres bbs
复制代码
如果有其他参加这次interview event的小伙伴欢迎热烈讨论,代码如果有什么好的优化意见的话也洗耳恭听,望不吝赐教。求onsite,求offer。

评分

4

查看全部评分

readman 发表于 2016-6-28 23:44:31 | 显示全部楼层
第二题是某家的onsite题, x2就是二进制的往左移位, +1 就是后位补1. 所以o(k) 应该就能算出来, k是补1的时候的扫描1个数
回复 支持 2 反对 0

使用道具 举报

会踢球的哈士奇 发表于 2016-8-14 04:43:59 | 显示全部楼层
马上就amazon oa 120mins 看看楼主的经验。
对于第二题 我自己写了一个算法, 不知道对不对 请楼主和大家指导一下

public int minOpertion(int n) {
        int steps = 0;

        while (n != 0) {
            if (n % 2 == 0) {
                n = n >> 1;
            } else {
                n--;
            }
            steps++;
        }
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        return steps;
    }
回复 支持 1 反对 0

使用道具 举报

肥娇娇 发表于 2016-6-27 22:16:14 | 显示全部楼层
O(∩_∩)O谢谢楼主!!祝你得onsite, 拿offer!
回复 支持 反对

使用道具 举报

陈润鹏 发表于 2016-6-28 02:55:40 | 显示全部楼层
第三题有没有更好的方法呀 这是brute force呀
回复 支持 反对

使用道具 举报

 楼主| wobujupa 发表于 2016-6-28 03:12:45 | 显示全部楼层
陈润鹏 发表于 2016-6-28 02:55
第三题有没有更好的方法呀 这是brute force呀

恩,这个确实是brute force,当时是考虑有没有优化的可能性。random给一个点的话,也是需要把所有的locker比较一遍才能知道哪个是最近的。另外的一个方向是,有没有可能从这几个locker的坐标开始向周围发散,但是考虑到发散的同时也要考虑是不是其他的locker距离已经比当前locker的距离近了,最后的复杂度还是O(mnk)。最最主要的是test case全都跑通了,我也就没有多想,就提交了。我觉的应该会有优化的方式,不过暂时还是没有idea。
回复 支持 反对

使用道具 举报

陈润鹏 发表于 2016-6-28 03:32:36 | 显示全部楼层
wobujupa 发表于 2016-6-28 03:12
恩,这个确实是brute force,当时是考虑有没有优化的可能性。random给一个点的话,也是需要把所有的locker ...

只是进行头脑风暴 不是judge, 好像也只能O(mnk)了
回复 支持 反对

使用道具 举报

maimaihu 发表于 2016-6-28 07:00:29 | 显示全部楼层
dp 也比较简单的。
        public int  minOperation(int n) {
                if(n == 1 ) return 1;
                if(n == 2)  return 2;
                int[] res = new int[n+1];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                res[1] = 1;
                res[2] = 2;
                for(int i = 3; i <= n; i++){
                        if(i%2 == 0){
                                res[i] = Math.min(res[i/2] + 1, res[i-1] +1);
                        }else{ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                                res[i] = res[i-1] + 1;
                        }
                }
                return res[n];
        }
回复 支持 反对

使用道具 举报

 楼主| wobujupa 发表于 2016-6-28 09:37:17 | 显示全部楼层
maimaihu 发表于 2016-6-28 07:00
. 1point 3acres 璁哄潧dp 也比较简单的。
        public int  minOperation(int n) {
                if(n == 1 ) return 1;

我最开始的dp代码就是这样写的,这样会超时,而且空间复杂度也略高。只要是可以被2整除,那就没有比较减1操作。
如果输入项是8,
按照我的操作过程就是 8 / 2 = 4 4 / 2 = 2 2 / 2 = 1
如果用你的dp操作 那是 3 4 5 6 7 8都要去进行运算,但是3 5 6 7是没有必要去进行计算的必要,因为他不出现在最短操作的这个路径中。. from: 1point3acres.com/bbs
如果输入项是2的n次方,那我的时间是n,你的dp操作的时间是2的n次方。这样就很容易看出来时间的差别了。
回复 支持 反对

使用道具 举报

dg7743 发表于 2016-6-28 10:45:34 | 显示全部楼层
第三题分析请见我这个帖子面经/LintCode/LeetCode题目想法和代码分享第29楼
回复 支持 反对

使用道具 举报

陈润鹏 发表于 2016-6-28 22:16:24 | 显示全部楼层
dg7743 发表于 2016-6-28 10:45
第三题分析请见我这个帖子面经/LintCode/LeetCode题目想法和代码分享第29楼

这题是不是求locker到城市边缘的距离呀? 如果是的话你的BFS做反了, 第二 如果不是的话,必须每一个都比对  O(mnk)是对的了
回复 支持 反对

使用道具 举报

papayachips 发表于 2016-6-28 23:28:58 | 显示全部楼层
第二题如果num在cache里面,应该返回的貌似是 cache.get(num)+res?
回复 支持 反对

使用道具 举报

 楼主| wobujupa 发表于 2016-6-28 23:34:09 | 显示全部楼层
papayachips 发表于 2016-6-28 23:28
第二题如果num在cache里面,应该返回的貌似是 cache.get(num)+res?

好像是这么个情况呢,神奇的是这个也跑通了所有的case,估计是case不够多,没有cover到所有的情况。
回复 支持 反对

使用道具 举报

readman 发表于 2016-6-28 23:40:42 | 显示全部楼层
最后一个其实是g家面试的一个改版. 可以从每个locker出发, 访问附近的cell, 如果cell是0(没有访问过), 设置成当前的距离, 如果不为0, 看看当前距离是不是小于cell的距离. 如果yes, 更新, 继续, 如果no..这个方向就停止了..cell的表示和楼主一样, worst case 是n^2,
回复 支持 反对

使用道具 举报

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

嗯嗯,这个思路行得通,赞一个。等下我重新优化下代码。
回复 支持 反对

使用道具 举报

 楼主| wobujupa 发表于 2016-6-28 23:51:05 | 显示全部楼层
readman 发表于 2016-6-28 23:44. 1point3acres.com/bbs
第二题是某家的onsite题, x2就是二进制的往左移位, +1 就是后位补1. 所以o(k) 应该就能算出来, k是补1的时 ...

赞赞赞赞赞,当时怎么也没发现这个规律呢。这个解法犀利,学习了。
回复 支持 反对

使用道具 举报

dg7743 发表于 2016-6-29 03:11:33 | 显示全部楼层
陈润鹏 发表于 2016-6-28 22:16
这题是不是求locker到城市边缘的距离呀? 如果是的话你的BFS做反了, 第二 如果不是的话,必须每一个都比 ...

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

使用道具 举报

陈润鹏 发表于 2016-6-29 09:56:56 | 显示全部楼层
dg7743 发表于 2016-6-29 03:11. Waral 鍗氬鏈夋洿澶氭枃绔,
要求的是这个matrix中每个点到最近locker的距离。跟readman的思路是差不多的的。只不过我们不用检查附近 ...

明白了 谢谢
回复 支持 反对

使用道具 举报

maimaihu 发表于 2016-7-2 10:25:07 | 显示全部楼层
wobujupa 发表于 2016-6-28 09:37
我最开始的dp代码就是这样写的,这样会超时,而且空间复杂度也略高。只要是可以被2整除,那就没有比较减1 ...

I see. 谢谢你的解释
回复 支持 反对

使用道具 举报

maimaihu 发表于 2016-7-2 10:31:17 | 显示全部楼层
wobujupa 发表于 2016-6-28 09:37
我最开始的dp代码就是这样写的,这样会超时,而且空间复杂度也略高。只要是可以被2整除,那就没有比较减1 ...

==, 你这题要求不是要输出从0 到某个数的一个结果吗?
anyway, 算n的时候,n-1和n/2对应的结果都已经算出来了,为什么还会超时?
回复 支持 反对

使用道具 举报

cuiyi 发表于 2016-7-3 02:44:42 | 显示全部楼层
readman 发表于 2016-6-28 23:40
最后一个其实是g家面试的一个改版. 可以从每个locker出发, 访问附近的cell, 如果cell是0(没有访问过), 设置 ...
. 鍥磋鎴戜滑@1point 3 acres
BFS从所有的locker出发(先把所有locker加入queue)访问每个点,如果没访问过,设置当前距离,并把该点加入queue;如果已经访问过,直接忽略,并且这个方向停止(该点不加入队列)。因为BFS是从左右locker出发的,所以第一次访问某个点一定是该点到其中一个locker的最短距离;第二次访问某个点的时候一定不是最短距离。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 16:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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