一亩三分地论坛

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

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

Amazon intern面经

[复制链接] |试试Instant~ |关注本帖
djjkobe 发表于 2015-1-29 09:45:20 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 本科 实习@Amazon - 内推 - 技术电面 在线笔试 |Other

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

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

x
1月6号收到OA。。。上周五电面45分钟。。。面试官是个印度人

上来先让自我介绍一下,然后直接做题。。
第一题是给一个Integer数组,求maximum。。。直接回答先sort,然后得到答案,报runtimeO(nlgn)。。然后说这样慢了,可以O(n),就是one-pass,然后找到最大值。。面试官说好。。没让写代码。
follow-up:怎么得到Top k value。。。。我说还是可以先sort。。然后取前k个。。报runtimeO(nlgn)。。。然后说太慢了,可以维护一个size是k的min-heap解决。。让写code。。磨蹭了两下写完烙印觉得还行就说过了。。看下一题
第二题是同样一个Integer数组。。怎么得到max value和min value。。我也是醉了。。先说sort,慢,所以可以弄两个变量max和min,然后one-pass解决。。烙印说好,但是comparison是2n,问怎么改进。。当时一直没想出来,跟他讨论了半天,最后他提示说可以一次读2个数,然后终于想出来每次读取只需要比较3次就能得出max和min,这样total comparison是3n/2。。总算是符合了他的要求。。不过讨论和想花了挺多时间的,最后有些超时,随便问了个问题结束。。求过啊。。。. visit 1point3acres.com for more.


补充内容 (2015-2-3 04:19):
今天收到Congrat邮件。。

评分

1

查看全部评分

kurtwang 发表于 2015-1-29 10:27:16 | 显示全部楼层
follow up那个可以quick select做到O(n)
回复 支持 反对

使用道具 举报

LawranceH 发表于 2015-1-29 10:35:30 | 显示全部楼层
楼主,第二个问题,不就只要 先设置2个变量max 和min. 先初始化 max=MIN_VALUE. min = MAX_VALUE. 之后再for 循环 每个数读一遍. 然后 同时 比较max 和 min .不就好了吗? 这样复杂度就是O(n)?
assume A[] is input.
int max = Math.MIN_VALUE;. From 1point 3acres bbs
int min = Math.MAX_VALUE;

   for (int i = 0; i < A.length; i++) {
        max = Math.max(A[i],max);
        min =Math.in(A[i],min);
}
你的意思是这样每个数都要和max 还有min 比较一次 最后 总的是2n次比较?
之后改成
int max = A[0];
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷int min = A[0];

   for (int i = 1; i < A.length; ) {-google 1point3acres
        if (A[i-1]<A[i]) {. 鍥磋鎴戜滑@1point 3 acres
        max = Math.max(A[i],max);. 鍥磋鎴戜滑@1point 3 acres
        min =Math.in(A[i-1],min);
        } else { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        max = Math.max(A[i-1],max);
        min =Math.in(A[i],min);
        }-google 1point3acres
        i = i+2;
     }
     if(A.length % 2 !=0) {.1point3acres缃
        max = Math.max(A[A.length-1],max);
        min =Math.in(A[A.length-1],min);
       }
return max,min.
这样每2个数只比较3次. 就3n/2?
回复 支持 反对

使用道具 举报

LawranceH 发表于 2015-1-29 10:36:33 | 显示全部楼层
楼主,第二个问题,不就只要 先设置2个变量max 和min. 先初始化 max=MIN_VALUE. min = MAX_VALUE. 之后再for 循环 每个数读一遍. 然后 同时 比较max 和 min .不就好了吗? 这样复杂度就是O(n)?
assume A[] is input.
int max = Math.MIN_VALUE;
int min = Math.MAX_VALUE;
.1point3acres缃
   for (int i = 0; i < A.length; i++) {
        max = Math.max(A[i],max);
        min =Math.in(A[i],min);
}
你的意思是这样每个数都要和max 还有min 比较一次 最后 总的是2n次比较?
之后改成
int max = A[0];
int min = A[0];

   for (int i = 1; i < A.length; ) {
        if (A[i-1]<A[i]) {
        max = Math.max(A[i],max);
        min =Math.in(A[i-1],min);
        } else {
        max = Math.max(A[i-1],max);
        min =Math.in(A[i],min);
        }
        i = i+2;
     }
     if(A.length % 2 !=0) {
.1point3acres缃        max = Math.max(A[A.length-1],max);
        min =Math.in(A[A.length-1],min);
       }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
return max,min.. 1point 3acres 璁哄潧
这样每2个数只比较3次. 就3n/2?
回复 支持 反对

使用道具 举报

 楼主| djjkobe 发表于 2015-1-29 10:41:59 | 显示全部楼层
LawranceH 发表于 2015-1-29 10:35
楼主,第二个问题,不就只要 先设置2个变量max 和min. 先初始化 max=MIN_VALUE. min = MAX_VALUE. 之后再for  ...

对对对。。。完全正确!
回复 支持 反对

使用道具 举报

 楼主| djjkobe 发表于 2015-1-29 10:43:02 | 显示全部楼层
LawranceH 发表于 2015-1-29 10:35
楼主,第二个问题,不就只要 先设置2个变量max 和min. 先初始化 max=MIN_VALUE. min = MAX_VALUE. 之后再for  ...

对对对。。。完全正确!
回复 支持 反对

使用道具 举报

lenss 发表于 2015-1-30 06:48:55 | 显示全部楼层
楼主收到信儿了么?
回复 支持 反对

使用道具 举报

 楼主| djjkobe 发表于 2015-1-30 07:00:38 | 显示全部楼层
lenss 发表于 2015-1-30 06:48. 1point3acres.com/bbs
楼主收到信儿了么?

没有。。。感觉是默剧的节奏
回复 支持 反对

使用道具 举报

lenss 发表于 2015-1-30 07:46:33 | 显示全部楼层
djjkobe 发表于 2015-1-30 07:00
没有。。。感觉是默剧的节奏
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
不会的,offer 会来的。我周二面的。
回复 支持 反对

使用道具 举报

 楼主| djjkobe 发表于 2015-1-30 07:52:57 | 显示全部楼层
lenss 发表于 2015-1-30 07:46
不会的,offer 会来的。我周二面的。

这周二吗。。已经出结果了?。。发点面经吧
回复 支持 反对

使用道具 举报

lenss 发表于 2015-1-30 07:58:10 | 显示全部楼层
djjkobe 发表于 2015-1-30 07:52
这周二吗。。已经出结果了?。。发点面经吧
. From 1point 3acres bbs
嗯,我没有出结果。不过感觉不太良好,烙印面的。我下周抽时间发个面经。
回复 支持 反对

使用道具 举报

dchen0215 发表于 2015-1-31 13:54:30 | 显示全部楼层
感谢lz分享,下周五店面。。。最好不要三哥啊!
回复 支持 反对

使用道具 举报

bjik 发表于 2015-2-1 00:16:33 | 显示全部楼层
lenss 发表于 2015-1-30 07:58
嗯,我没有出结果。不过感觉不太良好,烙印面的。我下周抽时间发个面经。

求share面经~~
回复 支持 反对

使用道具 举报

kurtwang 发表于 2015-2-1 00:26:44 | 显示全部楼层
dchen0215 发表于 2015-1-31 13:54
感谢lz分享,下周五店面。。。最好不要三哥啊!

搭车同求
回复 支持 反对

使用道具 举报

lenss 发表于 2015-2-1 02:00:22 | 显示全部楼层
bjik 发表于 2015-2-1 00:16. Waral 鍗氬鏈夋洿澶氭枃绔,
求share面经~~

我已经发了,你到版上搜一下吧
回复 支持 反对

使用道具 举报

bjik 发表于 2015-2-1 05:44:58 | 显示全部楼层
lenss 发表于 2015-2-1 02:00
我已经发了,你到版上搜一下吧

看到了 谢了~
回复 支持 反对

使用道具 举报

LawranceH 发表于 2015-2-3 08:27:10 | 显示全部楼层
lenss 发表于 2015-1-30 07:58
嗯,我没有出结果。不过感觉不太良好,烙印面的。我下周抽时间发个面经。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
求面经~~~~~~~~~~~~~
回复 支持 反对

使用道具 举报

lenss 发表于 2015-2-3 08:30:39 | 显示全部楼层
LawranceH 发表于 2015-2-3 08:27
求面经~~~~~~~~~~~~~
. 1point 3acres 璁哄潧
已发,你到版上搜一下,祝拿offer
回复 支持 反对

使用道具 举报

yihongzhang0417 发表于 2015-2-3 08:42:30 | 显示全部楼层
求问楼主做完OA大概多久收到的面试通知?
回复 支持 反对

使用道具 举报

 楼主| djjkobe 发表于 2015-2-3 08:50:12 | 显示全部楼层
yihongzhang0417 发表于 2015-2-3 08:42
求问楼主做完OA大概多久收到的面试通知?

10天吧。。是有点慢
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 21:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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