楼主: wobujupa
跳转到指定楼层
上一主题 下一主题
收起左侧

Amazon家新鲜OA,HackRanker 90min

🔗
 楼主| wobujupa 2016-7-5 22:25:27 | 只看该作者
全局:
maimaihu 发表于 2016-7-2 10:31
==, 你这题要求不是要输出从0 到某个数的一个结果吗?
anyway, 算n的时候,n-1和n/2对应的结果都已 ...

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

使用道具 举报

🔗
小魏Stenica 2016-7-25 08:59:24 | 只看该作者
全局:
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:57 | 只看该作者
全局:
祝楼主顺利过关。
回复

使用道具 举报

🔗
 楼主| wobujupa 2016-8-10 22:13:40 | 只看该作者
全局:
beyondhzm 发表于 2016-8-10 17:59
祝楼主顺利过关。

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

使用道具 举报

🔗
小魏Stenica 2016-8-12 06:27:08 | 只看该作者
全局:
wobujupa 发表于 2016-8-10 07:13
不晓得什么情况,做完了OA, 给HR去了封邮件,她问我做的是4月的还是7月的,然后就没信了,一周一封邮件 ...

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

使用道具 举报

🔗
 楼主| wobujupa 2016-8-14 00:17:06 | 只看该作者
全局:
小魏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.         for (int i = 0; i < lockerXCoordinates.length; i++) {
  4.             res[lockerXCoordinates[i]][lockerYCoordinates[i]] = 0;
  5.             Locker locker = new Locker(lockerXCoordinates[i], lockerYCoordinates[i]);
  6.             BFS(res, locker);
  7.         }

  8.         return res;
  9.     }

  10.     private void BFS(int[][] res, Locker locker) {
  11.         int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

  12.         Queue<Locker> q = new LinkedList<>();
  13.         q.add(locker);
  14.         while (!q.isEmpty()) {
  15.             Locker cur = q.poll();

  16.             for (int[] direction : directions) {
  17.                 int x = direction[0] + cur.x;
  18.                 int y = direction[1] + cur.y;
  19.                 int distance = Math.abs(locker.x - x) + Math.abs(locker.y - y);

  20.                 if (x < res.length && x >=0 && y < res[0].length && y >= 0 && (x != locker.x || y != locker.y)) {
  21.                     if (res[x][y] != 0 && res[x][y] <= distance) continue;

  22.                     res[x][y] = distance;

  23.                     Locker lockerNext = new Locker(x, y);
  24.                     q.offer(lockerNext);
  25.                 }
  26.             }
  27.         }
  28.     }

  29.     class Locker {
  30.         int x = 0;
  31.         int y = 0;
  32.         public Locker(int x, int y) {
  33.             this.x = x;
  34.             this.y = y;
  35.         }
  36.     }
复制代码
楼的思想自己写了一个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.         for (int i = 0 ; i < lockerXCoordinates.length; i++) {
  7.             visited[lockerXCoordinates[i]][lockerYCoordinates[i]] = true;
  8.             q.offer(new int[]{lockerXCoordinates[i], lockerYCoordinates[i]});
  9.         }

  10.         while (!q.isEmpty()) {
  11.             int[] cur = q.poll();

  12.             for (int[] direction : directions) {
  13.                 int next_x = cur[0] + direction[0];
  14.                 int next_y = cur[1] + direction[1];

  15.                 if (next_x < cityLength && next_x >= 0 && next_y < cityWidth && next_y >= 0 && !visited[next_x][next_y]) {
  16.                     visited[next_x][next_y] = true;
  17.                     res[next_x][next_y] = res[cur[0]][cur[1]] + 1;
  18.                     q.offer(new int[]{next_x, next_y});
  19.                 }
  20.             }
  21.         }

  22.         return res;
  23.     }
复制代码
回复

使用道具 举报

🔗
小魏Stenica 2016-8-14 13:23:01 | 只看该作者
全局:

好吧,我的不是,应该是个印度人,叫Vinny
Anyway!祝楼主早日拿到onsite
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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