Amazon家新鲜OA，HackRanker 90min

昨天刚刚做的OA，是Marketplace的Interview Event，但是不晓得为什么写着是April的，我要参加的应该是七月份的。之前网上找面经，找到这个。
题目除了第一题是一样的，剩下两个都是新题(没做太多准备工作，也可能有人分享了我没看到)

第一题： 找第一个重复出现的字符串，字符串可能由多个空格/分号/冒号/逗号/句号/减号 分隔开。
思路就是用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

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

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

cker求距离，取最小值。如果长宽分别是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++){
   
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.     }
    

复制代码

如果有其他参加这次interview event的小伙伴欢迎热烈讨论，代码如果有什么好的优化意见的话也洗耳恭听，望不吝赐教。求onsite，求offer。

马上就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;
    }

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

第三道题我按照12楼的思想自己写了java的代码 代码感觉写的不是很规整 应该可以精简， 求大家指点。

1. public int[][] getLockerDistanceGrid(int cityLength, int cityWidth, int[] lockerXCoordinates, int[] lockerYCoordinates) {
   
2.         int[][] res = new int[cityLength][cityWidth];
   
3. 
   
4.         for (int i = 0; i < lockerXCoordinates.length; i++) {
   
5.             res[lockerXCoordinates[i]][lockerYCoordinates[i]] = 0;
   
6.             Locker locker = new Locker(lockerXCoordinates[i], lockerYCoordinates[i]);
   
7.             BFS(res, locker);
   
8.         }
   
9. 
   
10.         return res;
    
11.     }
    
12. 
    
13.     private void BFS(int[][] res, Locker locker) {
    
14.         int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
15. 
    
16.         Queue<Locker> q = new LinkedList<>();
    
17.         q.add(locker);
    
18.         while (!q.isEmpty()) {
    
19.             Locker cur = q.poll();
    
20. 
    
21.             for (int[] direction : directions) {
    
22.                 int x = direction[0] + cur.x;
    
23.                 int y = direction[1] + cur.y;
    
24.                 int distance = Math.abs(locker.x - x) + Math.abs(locker.y - y);
    
25. 
    
26.                 if (x < res.length && x >=0 && y < res[0].length && y >= 0 && (x != locker.x || y != locker.y)) {
    
27.                     if (res[x][y] != 0 && res[x][y] <= distance) continue;
    
28. 
    
29.                     res[x][y] = distance;
    
30. 
    
31.                     Locker lockerNext = new Locker(x, y);
    
32.                     q.offer(lockerNext);
    
33.                 }
    
34.             }
    
35.         }
    
36.     }
    
37. 
    
38.     class Locker {
    
39.         int x = 0;
    
40.         int y = 0;
    
41.         public Locker(int x, int y) {
    
42.             this.x = x;
    
43.             this.y = y;
    
44.         }
    
45.     }

复制代码

楼的思想自己写了一个java版本的 感觉代码量有点大 求指点：



补充内容 (2016-8-14 12:44):
算法写的不是很好， 我在29 楼更新了一下我的算法

O(∩_∩)O谢谢楼主！！祝你得onsite, 拿offer！

第三题有没有更好的方法呀 这是brute force呀

陈润鹏 发表于 2016-6-28 02:55
第三题有没有更好的方法呀 这是brute force呀

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

wobujupa 发表于 2016-6-28 03:12
恩，这个确实是brute force,当时是考虑有没有优化的可能性。random给一个点的话，也是需要把所有的locker ...

只是进行头脑风暴 不是judge， 好像也只能O（mnk）了

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];
        }

maimaihu 发表于 2016-6-28 07:00
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是没有必要去进行计算的必要，因为他不出现在最短操作的这个路径中。
如果输入项是2的n次方，那我的时间是n，你的dp操作的时间是2的n次方。这样就很容易看出来时间的差别了。

第三题分析请见我这个帖子面经/LintCode/LeetCode题目想法和代码分享第29楼

dg7743 发表于 2016-6-28 10:45
第三题分析请见我这个帖子面经/LintCode/LeetCode题目想法和代码分享第29楼

这题是不是求locker到城市边缘的距离呀？ 如果是的话你的BFS做反了， 第二 如果不是的话,必须每一个都比对  O（mnk）是对的了

第二题如果num在cache里面，应该返回的貌似是 cache.get(num)+res?