10月28,K神开讲数据科学:AB Test/实验设计


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 2848|回复: 24
收起左侧

Amazon intern面经

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

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

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

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

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。。总算是符合了他的要求。。不过讨论和想花了挺多时间的,最后有些超时,随便问了个问题结束。。求过啊。。。


补充内容 (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;
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次比较?. Waral 鍗氬鏈夋洿澶氭枃绔,
之后改成 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
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);.1point3acres缃
        } else {. From 1point 3acres bbs
        max = Math.max(A[i-1],max);
        min =Math.in(A[i],min);
        }
        i = i+2;
     }
     if(A.length % 2 !=0) {
        max = Math.max(A[A.length-1],max);. Waral 鍗氬鏈夋洿澶氭枃绔,
        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;

   for (int i = 0; i < A.length; i++) {.1point3acres缃
        max = Math.max(A[i],max);
        min =Math.in(A[i],min);
}
你的意思是这样每个数都要和max 还有min 比较一次 最后 总的是2n次比较?
之后改成 . 鍥磋鎴戜滑@1point 3 acres
int max = A[0];
int min = A[0];. from: 1point3acres.com/bbs

   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 {-google 1point3acres
        max = Math.max(A[i-1],max);
        min =Math.in(A[i],min);
. From 1point 3acres bbs        }
        i = i+2;
     }
     if(A.length % 2 !=0) {
        max = Math.max(A[A.length-1],max);
        min =Math.in(A[A.length-1],min);
       }
return max,min..1point3acres缃
这样每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
楼主收到信儿了么?
. Waral 鍗氬鏈夋洿澶氭枃绔,
没有。。。感觉是默剧的节奏
回复 支持 反对

使用道具 举报

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
这周二吗。。已经出结果了?。。发点面经吧
. visit 1point3acres.com for more.
嗯,我没有出结果。不过感觉不太良好,烙印面的。我下周抽时间发个面经。
回复 支持 反对

使用道具 举报

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-google 1point3acres
感谢lz分享,下周五店面。。。最好不要三哥啊!

. 1point3acres.com/bbs搭车同求
回复 支持 反对

使用道具 举报

lenss 发表于 2015-2-1 02:00:22 | 显示全部楼层
bjik 发表于 2015-2-1 00:16. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
求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
求面经~~~~~~~~~~~~~

已发,你到版上搜一下,祝拿offer
回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| djjkobe 发表于 2015-2-3 08:50:12 | 显示全部楼层
yihongzhang0417 发表于 2015-2-3 08:42. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
求问楼主做完OA大概多久收到的面试通知?
.鐣欏璁哄潧-涓浜-涓夊垎鍦
10天吧。。是有点慢
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-10-19 02:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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