Amazon家新鲜OA，HackRanker 90min

maimaihu 发表于 2016-7-2 10:31
＝＝， 你这题要求不是要输出从0 到某个数的一个结果吗？
anyway， 算n的时候，n-1和n/2对应的结果都已 ...

上面的这个dp的写法里边，你可以看到它是从小到大开始便利的，所以上来先找的不是n-1 n/2，而是从3开始，所以会有很多无用的遍历，即使已经把n之前需要用的数都放到缓存里了，那依然还是需要去走一遍，取一遍，这样就超时了。

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

弱弱的问一句。。。请问一下这道题用BFS这样的方法做time complexity 和 space complexity是多少啊，对big O各种没搞清楚。。。
而且我用Java写的话，一开始初始化这个2D的数组都为-1的话，我得写两个for循环(nested)的这种，通常来说这种时间复杂度一定就是O(n^2)了呀
各种没想通。。。
谢谢！

祝楼主顺利过关。

beyondhzm 发表于 2016-8-10 17:59
祝楼主顺利过关。

不晓得什么情况，做完了OA， 给HR去了封邮件，她问我做的是4月的还是7月的，然后就没信了，一周一封邮件，结果七月结束了也没有回复。不太明白什么情况

wobujupa 发表于 2016-8-10 07:13
不晓得什么情况，做完了OA， 给HR去了封邮件，她问我做的是4月的还是7月的，然后就没信了，一周一封邮件 ...

楼主我看你写的你是marketplace的interview event，我的也是marketplace的(不过不是interview event)，做了OA两周了，也发了邮件，hr不理人，请问一下楼主方便说一下联系你的hr是谁吗

小魏Stenica 发表于 2016-8-12 06:27
楼主我看你写的你是marketplace的interview event，我的也是marketplace的(不过不是interview event)，做 ...

是Christina

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

第三道题我按照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 楼更新了一下我的算法

update了一下28自己写的算法。

1. public int[][] getLockerDistanceGrid(int cityLength, int cityWidth, int[] lockerXCoordinates, int[] lockerYCoordinates) {
   
2.         int[][] res = new int[cityLength][cityWidth];
   
3.         boolean[][] visited = new boolean[cityLength][cityWidth];
   
4.         int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
   
5.         Queue<int[]> q = new LinkedList<int[]>();
   
6. 
   
7.         for (int i = 0 ; i < lockerXCoordinates.length; i++) {
   
8.             visited[lockerXCoordinates[i]][lockerYCoordinates[i]] = true;
   
9.             q.offer(new int[]{lockerXCoordinates[i], lockerYCoordinates[i]});
   
10.         }
    
11. 
    
12.         while (!q.isEmpty()) {
    
13.             int[] cur = q.poll();
    
14. 
    
15.             for (int[] direction : directions) {
    
16.                 int next_x = cur[0] + direction[0];
    
17.                 int next_y = cur[1] + direction[1];
    
18. 
    
19.                 if (next_x < cityLength && next_x >= 0 && next_y < cityWidth && next_y >= 0 && !visited[next_x][next_y]) {
    
20.                     visited[next_x][next_y] = true;
    
21.                     res[next_x][next_y] = res[cur[0]][cur[1]] + 1;
    
22.                     q.offer(new int[]{next_x, next_y});
    
23.                 }
    
24.             }
    
25.         }
    
26. 
    
27.         return res;
    
28.     }

复制代码

wobujupa 发表于 2016-8-13 09:17
是Christina

好吧，我的不是，应该是个印度人，叫Vinny
Anyway！祝楼主早日拿到onsite