一亩三分地论坛

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

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

Amazon OA1 12.7 Due | 注意,coding题目微调

[复制链接] |试试Instant~ |关注本帖
阿色 发表于 2015-12-4 13:38:53 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 博士 全职@Amazon - 内推 - 在线笔试 |Otherfresh grad应届毕业生

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

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

x
Debug题和逻辑题地里都有了,这部分看看就没太大问题了。
逻辑题注意时间把握,前面做得太慢的话,后面大段的推理就比较仓促了。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
另外,我抽到的coding题不是地里常出现的老三道(Window Sum/Rectangle Area/K Points),而是Window Minimum。具体题目如下:
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
给了一个ArrayList:4, 2, 12, 11, -5,窗口size为2,返回的ArrayList为:2, 2, 11, -5。这里窗口size是一个参数。

楼主想效仿Window Sum写一个O(n)的方法,但是最后没想出来。老老实实写了两重循环,过了5个test case。有没有同学指点一下好的解法?

最后,本来想按截屏键截个图给大家,结果刚按下就被系统警告了,说再违规就会disable test。有没人知道这个对结果有无影响啊?有的话实在亏大了……求保佑!

评分

4

查看全部评分

本帖被以下淘专辑推荐:

dengke 发表于 2015-12-4 14:10:55 | 显示全部楼层
谢谢题主的分享!

我觉得这道题是LeetCode里面Windows Maximum的变体啊,用deque做可以实现O(n).

  1. public class Solution {
  2.     public int[] maxSlidingWindow(int[] nums, int k) {
  3.         . Waral 鍗氬鏈夋洿澶氭枃绔,
  4.         if (nums == null || k <= 0) {
  5.             return new int[0];
  6.         }
  7.         int n = nums.length;
  8.         int[] r = new int[n-k+1];
  9.         int ri = 0;
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  10.         // store index
  11.         Deque<Integer> q = new ArrayDeque<>(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  12.         for (int i = 0; i < nums.length; i++) {
  13.             // remove numbers out of range k
  14.             while (!q.isEmpty() && q.peek() < i - k + 1) {.1point3acres缃
  15.                 q.poll();
  16.             }
  17.             // remove larger numbers in k range as they are useless
  18.             while (!q.isEmpty() && nums[q.peekLast()] > nums[i]) {
  19.                 q.pollLast();
  20.             }
  21.             // q contains index... r contains content
  22.             q.offer(i);
  23.             if (i >= k - 1) {
  24.                 r[ri++] = nums[q.peek()];
  25.             }
  26.         }
  27.         return r;
  28.         
  29.     }
  30. }
复制代码


请问题主除了这道题,另一道coding是什么题啊?
回复 支持 1 反对 0

使用道具 举报

 楼主| 阿色 发表于 2015-12-4 14:18:43 | 显示全部楼层
dengke 发表于 2015-12-4 14:10
谢谢题主的分享!

我觉得这道题是LeetCode里面Windows Maximum的变体啊,用deque做可以实现O(n).

长见识了。
. 1point 3acres 璁哄潧
OA1就一道coding。
回复 支持 反对

使用道具 举报

aloncgo 发表于 2015-12-4 14:25:13 | 显示全部楼层
dengke 发表于 2015-12-4 14:10
谢谢题主的分享!

我觉得这道题是LeetCode里面Windows Maximum的变体啊,用deque做可以实现O(n).

OA1 这种难度也太难了吧。。。    (比起之前的那几道
回复 支持 反对

使用道具 举报

zws0818 发表于 2015-12-4 15:10:44 | 显示全部楼层
这道题不是类似LeetCode里面Sliding Window Maximum吗,方法应该一样啊,只不过是求最大变成最小,deque就实现了,虽说是新题,但是刷了leetcode应该不是啥问题啊,但是OA1出这么难的题,也是够了
回复 支持 反对

使用道具 举报

 楼主| 阿色 发表于 2015-12-4 15:22:57 | 显示全部楼层
zws0818 发表于 2015-12-4 15:10
这道题不是类似LeetCode里面Sliding Window Maximum吗,方法应该一样啊,只不过是求最大变成最小,deque就 ...

对啊,就是不知道暴力的让不让过。题目没有给复杂度要求。

补充内容 (2015-12-4 15:23):
一共就5个test case,暴力的能过所有5个。
回复 支持 反对

使用道具 举报

510kg 发表于 2015-12-4 15:25:00 | 显示全部楼层
多谢!救了命了!
回复 支持 反对

使用道具 举报

zws0818 发表于 2015-12-4 15:26:26 | 显示全部楼层
阿色 发表于 2015-12-4 15:22
对啊,就是不知道暴力的让不让过。题目没有给复杂度要求。
. more info on 1point3acres.com
补充内容 (2015-12-4 15:23):

如果暴力能过应该没事吧,毕竟没人审OA1的代码
回复 支持 反对

使用道具 举报

eamon_felix4213 发表于 2015-12-4 23:23:44 | 显示全部楼层
感谢楼主,很有用的信息,不知道OA2的题库有米有变
回复 支持 反对

使用道具 举报

wade123 发表于 2015-12-5 00:27:39 | 显示全部楼层
eamon_felix4213 发表于 2015-12-4 09:23
感谢楼主,很有用的信息,不知道OA2的题库有米有变

感觉会一起变。。。
回复 支持 反对

使用道具 举报

eamon_felix4213 发表于 2015-12-5 00:39:40 | 显示全部楼层
wade123 发表于 2015-12-4 11:27. 1point 3acres 璁哄潧
感觉会一起变。。。

回复 支持 反对

使用道具 举报

leonidas1573 发表于 2015-12-5 03:45:56 | 显示全部楼层
非常感谢分享! 新题对大家都是帮助. . from: 1point3acres.com/bbs
  1. int* minslidingwindow(int* inputarray, int inputlen, int windowsize) {
  2.         if (windowsize == 0) return NULL;
  3.         list<int> minheap;
  4.         for (int i = 0; i < inputlen && i < windowsize; ++i) {
  5.                 while (minheap.size() && minheap.back() > inputarray[i]). From 1point 3acres bbs
  6.                         minheap.pop_back();
  7.                 minheap.push_back(inputarray[i]);
  8.         }
  9.         vector<int> ret;
  10.         ret.push_back(minheap.front());
  11.         for (int slow = 0, fast = windowsize; fast < inputlen; ++fast, ++slow) {
  12.                 if (inputarray[slow] == minheap.front()) {
  13.                         minheap.pop_front();
  14.                 }. 1point3acres.com/bbs
  15.                 while (minheap.size() && minheap.back() > inputarray[fast])
  16.                         minheap.pop_back();
  17.                 minheap.push_back(inputarray[fast]);
  18.                 ret.push_back(minheap.front());.鐣欏璁哄潧-涓浜-涓夊垎鍦
  19.         }

  20.         // output. 1point3acres.com/bbs
  21.         int* pointerret = new int[ret.size()]();
  22.         for (int i = 0; i < ret.size(); ++i). from: 1point3acres.com/bbs
  23.                 pointerret[i] = ret[i];
  24.         return pointerret;
  25. }
复制代码
回复 支持 反对

使用道具 举报

ron1990 发表于 2015-12-5 05:47:26 | 显示全部楼层
能不能用treeset做?
回复 支持 反对

使用道具 举报

wade123 发表于 2015-12-5 06:07:07 | 显示全部楼层
ron1990 发表于 2015-12-4 15:47
能不能用treeset做?

不行吧,因为有重复元素。复杂度是n*logk,比用deque的O(n)高
回复 支持 反对

使用道具 举报

YuxuanHe 发表于 2015-12-5 08:06:58 | 显示全部楼层
我刚打算做, 就出新题,我去。 这题是leetcode里面的变形吧, 日了狗
回复 支持 反对

使用道具 举报

基督山伯伯 发表于 2015-12-5 12:03:02 | 显示全部楼层
OA1居然出LEETCODE 里HARD的题。。也真是够了
回复 支持 反对

使用道具 举报

 楼主| 阿色 发表于 2015-12-5 13:33:55 | 显示全部楼层
楼主刚收到OA2的link。说明这题用两重循环的naive暴力解是不会有任何问题的,请大家放宽心。
回复 支持 反对

使用道具 举报

fuqiang_1984 发表于 2015-12-5 16:51:26 | 显示全部楼层
这个online考试,有监控么?
回复 支持 反对

使用道具 举报

 楼主| 阿色 发表于 2015-12-5 23:45:07 | 显示全部楼层
fuqiang_1984 发表于 2015-12-5 16:51. more info on 1point3acres.com
这个online考试,有监控么?
. Waral 鍗氬鏈夋洿澶氭枃绔,
全程视频监控。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 08:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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