一亩三分地论坛

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

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

6.22amazon onsite面经

[复制链接] |试试Instant~ |关注本帖
zhouyuzhe 发表于 2016-7-5 23:02:26 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Amazon - 网上海投 - Onsite |Passfresh grad应届毕业生

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

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

x
6月22日amazon onsite面经:
第一轮:
1a.给两个use_id的file,找出repeat user,即同时出现在file1和file2的user
1b.对于repeat user,找出它们的访问次数交集的最大值。
2.给一个array,找出balance point,即该点左边sum和右边sum的差值最小。O(n)

第二轮:
给一个数组,找最长增长区间。
1,4,2,6.   length[0]=1,length[1]=2,length[2]=1, length[3]=4, max=length[3]=4. 区间内的数不用连续增长,其实是对每一个位置,向前找到不大于该位置的最长序列,然后求最大值。
用stack做,类似leetcode84。O(n)

第三轮:
1.rat in a maze
2.two sum. 写test case

第四轮:. from: 1point3acres.com/bbs
有一个音乐视频电子书的分享平台,设计用户的搜索功能

评分

2

查看全部评分

laonong15 发表于 2016-7-6 09:14:37 | 显示全部楼层
对 dp不行  从后向前走是不是可以不用stack ?:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

public int maxSegment(int[] nums) {
    if(nums == null || nums.length == 0) {
        return 0;. From 1point 3acres bbs
    }
    int  max =1;
    int  len = nums.length;
    int index = len -2;
    int current = nums[len - 1] ;
    int count = 1;
    while( index >= 0) {
        if(current >= nums[i]) {
            count++;
        } else {
            max = Math.max(max,count);.鐣欏璁哄潧-涓浜-涓夊垎鍦
            count = 1;
            current = nums[i];
        }
       index--;
    }
    return max;
}
回复 支持 0 反对 2

使用道具 举报

sevenyunan 发表于 2016-7-6 01:38:22 | 显示全部楼层
Is this sde1 or sde2?
回复 支持 反对

使用道具 举报

 楼主| zhouyuzhe 发表于 2016-7-6 01:39:26 | 显示全部楼层
sevenyunan 发表于 2016-7-6 01:38.1point3acres缃
Is this sde1 or sde2?

sde1 new grad
回复 支持 反对

使用道具 举报

谎言之躯 发表于 2016-7-6 02:26:30 | 显示全部楼层
第二轮的题目要求还是没看懂,楼主能不能再具体说一下?
回复 支持 反对

使用道具 举报

laonong15 发表于 2016-7-6 03:11:50 | 显示全部楼层
A家画风变了?
回复 支持 反对

使用道具 举报

liu298871369 发表于 2016-7-6 03:47:35 | 显示全部楼层
第一题是给出了两个file自己要写i/o部分吗,需要自己设计全部code, 还是在solution里面有写好的class 以及method 像leetcode那种直接实现就好了 。以及求解法。。
回复 支持 反对

使用道具 举报

 楼主| zhouyuzhe 发表于 2016-7-6 04:35:35 | 显示全部楼层
liu298871369 发表于 2016-7-6 03:47
第一题是给出了两个file自己要写i/o部分吗,需要自己设计全部code, 还是在solution里面有写好的class 以及 ...

有让讲一下怎么从file里面读取id,代码部分写input是string list的就行了。做法用hashmap存分别存两个listid和出现次数,然后对每个id求交集
回复 支持 反对

使用道具 举报

 楼主| zhouyuzhe 发表于 2016-7-6 04:43:22 | 显示全部楼层
谎言之躯 发表于 2016-7-6 02:26
第二轮的题目要求还是没看懂,楼主能不能再具体说一下?
. 1point3acres.com/bbs
以1,4,2,6这个list为例,length看作是截止到i位置的最长增长区间。length[0]=1,因为前面没有数,所以长度就是本身。leng[1]=2,区间是1,4。length[2]=1,因为2前面的第一个数4就大于2。length[3]=4,因为前面的所有数都小于6,区间就是1,4,2,6。 brute force 就是对每个位置向前遍历,遇到大于当前数就停下,然后求最大值,是O(n^2)。用stack的话可以O(n)
回复 支持 反对

使用道具 举报

laonong15 发表于 2016-7-6 05:42:47 | 显示全部楼层
dp 一下:
dp(i) : max of increasing end with   index i
dp(i) = 1 if(nuts[i] < num[i-1])   dp(i) = dp(i-1) + 1   (otherwise)
. 1point 3acres 璁哄潧
return max(dp[i])

int max = 1;
int prev = 1

for( int i = 1; i < nums.length; i++){
       if(nums[i] < nums[i-1]) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
            prev =1;}
   else  pre ++;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
   max = math.max(max,prev);
}-google 1point3acres
return max;
回复 支持 反对

使用道具 举报

 楼主| zhouyuzhe 发表于 2016-7-6 05:58:27 | 显示全部楼层
laonong15 发表于 2016-7-6 05:42
dp 一下:
dp(i) : max of increasing end with   index i
dp(i) = 1 if(nuts < num)   dp(i) = dp(i- ...

我觉得好像不太对,这个题跟longest increasing sequence不一样。1,4,2,6最后一个位置的区间长度不是2而应该是4,因为前面的数都小于6,不需要是持续递增的
回复 支持 反对

使用道具 举报

bonnachoven 发表于 2016-7-6 06:51:37 | 显示全部楼层
zhouyuzhe 发表于 2016-7-6 04:43
以1,4,2,6这个list为例,length看作是截止到i位置的最长增长区间。length[0]=1,因为前面没有数,所以 ...

lz能说下用stack的做法么?多谢~
回复 支持 反对

使用道具 举报

 楼主| zhouyuzhe 发表于 2016-7-6 10:26:21 | 显示全部楼层
laonong15 发表于 2016-7-6 09:14
对 dp不行  从后向前走是不是可以不用stack ?:

public int maxSegment(int[] nums) {

应该是的,棒!
回复 支持 反对

使用道具 举报

zhangyf76 发表于 2016-7-7 00:29:23 | 显示全部楼层
max slide window 的变种吧
回复 支持 反对

使用道具 举报

ninacc 发表于 2016-7-7 01:11:20 | 显示全部楼层
楼主您好,恭喜offer! 请问能提供下海投的链接吗,谢谢!!!
回复 支持 反对

使用道具 举报

 楼主| zhouyuzhe 发表于 2016-7-7 04:55:41 | 显示全部楼层
ninacc 发表于 2016-7-7 01:11
楼主您好,恭喜offer! 请问能提供下海投的链接吗,谢谢!!!

我投了好几个,Job: 334960 不太确定是不是这个中的
回复 支持 反对

使用道具 举报

laonong15 发表于 2016-7-7 05:04:13 | 显示全部楼层
恭喜offer  多长时间知道offer的
回复 支持 反对

使用道具 举报

 楼主| zhouyuzhe 发表于 2016-7-7 06:10:38 | 显示全部楼层
laonong15 发表于 2016-7-7 05:04
恭喜offer  多长时间知道offer的
. 1point3acres.com/bbs
面完差不多一周
回复 支持 反对

使用道具 举报

laonong15 发表于 2016-7-7 12:27:43 | 显示全部楼层
能说说你第四题咋做地嘛
回复 支持 反对

使用道具 举报

月球那半边 发表于 2016-7-18 11:24:41 | 显示全部楼层
请问楼主什么时候海投的,多久拿到oa?谢谢!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 19:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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