一亩三分地论坛

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

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

Amazon Seattle 面经 10/28

[复制链接] |试试Instant~ |关注本帖
feichangh 发表于 2016-11-2 04:37:53 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Amazon - 猎头 - Onsite |Other在职跳槽

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

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

x
今年第四面,前三个面经请看这里 谷歌 微软 TwoSigma
亚麻西雅图office,面的职位是SDE II,总共4轮。 亚麻对他们leadership principle考的还真是多,每轮起码问15分钟behavior question。

(1)两个白人小哥,上来先一道word break没难度不说了,楼主写完后空了很长时间面试官也没有说接下来做什么,就是低头看电脑,楼主只好再没话找话跑了1个例子,并仔细说了每个过程的优劣比如开dp数组开length + 1长度 vs 开length长度,dict用set vs 用trie之类的。结果还剩十分钟时候小哥抱着电脑走到白板说咱们做第二题吧,楼主看了下电脑屏幕明显他刚才在google第二个该出什么题=。= 题目是给整数N,每个整数用两次,问能不能生成一个2N的数组,使每两个相同的数字num之间相隔num个不同的数,比如n = 3,可用数字就是112233,结果就是312132, 两个1之间间隔1个数,两个2之间间隔2个数,两个3之间间隔3个数。楼主开始贪婪写了一遍,就是先放间隔最大的,在依次放之后的数,看最后能不能放满,结果发现行不通。换了个方法暴力用dfs生成2n所有的排列,递归过程中遇到不符合的就剪掉这个枝不继续。按这个思路写了一半没有时间了,小哥说可以了,我只care这个题的algorithm不care具体code。如果能早点出题的话楼主应该是可以写完,不过给出的这个算法是指数级复杂度,不太清楚还有什么算法可以更优?. 1point3acres.com/bbs

(2)白人大叔,估计是bar raiser。题目是给一个excel sheet,每个格子有数字或者公式,公式就是比如A1格子数值等于B2格子的数加4,让把整个表格计算出来。这个题本质上就是有向图遍历,dfs解之,注意一点是遍历时候要判断有没有环,比如A1引用B2,B2引用A1,这个就无解。写完以后大叔就没有问题,聊下天结束. more info on 1point3acres.com
.1point3acres缃

(3)印度小哥,系统设计题,设计预测系统,当用户浏览一个商品时判断他会不会买,判断会买的时候pre fetch购物车页面。先分析什么因素判断用户买不买这个商品,浏览记录,购买记录,在页面停留时间,浏览这类商品的次数,现在火的top 100商品等等。然后分析架构,楼主给的答案是首先master slave避免single point failure,用户点击商品后先通过dymanic dns look up找到距离最近的CDN,然后http request传过来给那个cluster的master server, mater本身有cache看看这个请求的结果是不是已经cache过了有的话直接返回(这里cache的是这个请求对应的购物车html页面),没有的话master做负载均衡下传给空闲slave server(rmi call), slave有自己的local cache因为对这个预测结果每个slave cache可以不consistent, 可以不用时刻recon每个不同的server cache。所有的数据存储都用in memory database并设置time to live, 因为这个是一个读取大于写的系统数据也不需要持久化不用支持transaction, scale也更容易。master如果挂了重启就可以,因为都是预测数据丢失了也无所谓。如果要更优化可以在浏览器端也做一层cache,如果用户反复点击同样的商品,就不用每次都make http call了。

.鏈枃鍘熷垱鑷1point3acres璁哄潧
(4)亚裔小哥加白人大哥, word ladder II的变形,原题是每次更换一个字母,这里是每次去掉一个字母,bfs解之。

有消息楼主会更新此贴。


评分

2

查看全部评分

本帖被以下淘专辑推荐:

catinclay 发表于 2016-11-2 05:46:30 | 显示全部楼层
第一题是问可不可以生成吗? 如果是的话
除了 n = 3的情况 312132
n = 4 时就 43121324
n = 5 就 5431213245 (每次都把新的n放在两边) 不就可以了?
回复 支持 1 反对 0

使用道具 举报

 楼主| feichangh 发表于 2016-11-2 06:54:47 | 显示全部楼层
catinclay 发表于 2016-11-2 05:46
第一题是问可不可以生成吗? 如果是的话. from: 1point3acres.com/bbs
除了 n = 3的情况 312132. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
n = 4 时就 43121324

是问可不可以生成,但是两个4之间要正好距离4个别的数,比如41312432
回复 支持 反对

使用道具 举报

caiqi8877 发表于 2016-11-2 07:05:05 | 显示全部楼层
请问下楼主面的是什么组呢?
回复 支持 反对

使用道具 举报

 楼主| feichangh 发表于 2016-11-2 07:12:51 | 显示全部楼层
caiqi8877 发表于 2016-11-2 07:05. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
请问下楼主面的是什么组呢?

checkout组
回复 支持 反对

使用道具 举报

mayo 发表于 2016-11-2 09:36:19 | 显示全部楼层
楼主是10-27,10-28面的event吗?
回复 支持 反对

使用道具 举报

catinclay 发表于 2016-11-2 09:51:33 | 显示全部楼层
feichangh 发表于 2016-11-2 06:54. From 1point 3acres bbs
是问可不可以生成,但是两个4之间要正好距离4个别的数,比如41312432

原來是要剛好!我再想想
回复 支持 反对

使用道具 举报

mayo 发表于 2016-11-2 10:49:02 | 显示全部楼层
catinclay 发表于 2016-11-2 09:51. 鍥磋鎴戜滑@1point 3 acres
原來是要剛好!我再想想

    public List<String> generate(int n){
        List<String> result = new ArrayList<>();. Waral 鍗氬鏈夋洿澶氭枃绔,
        dfs(result, new int[n*2], n, 1);
        return result;. 1point 3acres 璁哄潧
    }   
    public void dfs(List<String> result, int[] arr, int n, int index){
        boolean allFilled = true;
        int[] counts = new int[n];
        for(int x : arr){
            if(x == 0){             //checking unfilled element
                allFilled = false;
                break;
            }
            counts[x-1]++;.鐣欏璁哄潧-涓浜-涓夊垎鍦
        }
        for(int count : counts){    //checking number match count 2
            if(count != 2){
                allFilled = false;
                break;
            }
        }        
        if(allFilled){              //base case
            StringBuilder sb = new StringBuilder();
            for(int x : arr){
                sb.append(x);
            }
            result.add(sb.toString());
            return;
        }

        for(int i=index; i<=n ;i++){. more info on 1point3acres.com
            for(int j=0; j<arr.length; j++){
                int start = j;. visit 1point3acres.com for more.
                int end = j+i+1;                . 1point3acres.com/bbs

                if(isValid(arr, start, end)){
                    arr[start]=i;
                    arr[end]=i;                    
                    dfs(result, arr, n, index+1);                    
                    arr[start]=0;
                    arr[end]=0;               
                }
            }.鏈枃鍘熷垱鑷1point3acres璁哄潧
        }
    }   
    public boolean isValid(int[] nums, int i, int j){
        if(i<0 || i>=nums.length) return false;.鏈枃鍘熷垱鑷1point3acres璁哄潧
        if(j<0 || j>=nums.length) return false;-google 1point3acres
        return nums == 0 && nums[j] == 0;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
. 1point3acres.com/bbs
按照楼主的思路码出来的代码, 前提条件是n<10吧

回复 支持 反对

使用道具 举报

Owenli20 发表于 2016-11-2 12:32:50 | 显示全部楼层
楼主能分享一下background吗 比如在哪工作几年?
回复 支持 反对

使用道具 举报

 楼主| feichangh 发表于 2016-11-2 22:48:51 | 显示全部楼层
mayo 发表于 2016-11-2 09:36
楼主是10-27,10-28面的event吗?

不是哈,就是普通的onsite
回复 支持 反对

使用道具 举报

 楼主| feichangh 发表于 2016-11-2 22:51:52 | 显示全部楼层
Owenli20 发表于 2016-11-2 12:32
楼主能分享一下background吗 比如在哪工作几年?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
在一家金融科技公司sde,工作两年多快三年了
回复 支持 反对

使用道具 举报

 楼主| feichangh 发表于 2016-11-2 22:56:43 | 显示全部楼层
mayo 发表于 2016-11-2 10:49
public List generate(int n){
        List result = new ArrayList();
        dfs(result, new  ...

应该没有更优的做法了,后来上网搜了下这个题居然是个brain teaser, 这个帖子(http://que4u.blogspot.com/2013/0 ... -answers-brain.html)第十五题,怪不得他不要求写代码。。。。
回复 支持 反对

使用道具 举报

mayo 发表于 2016-11-3 07:56:28 | 显示全部楼层
feichangh 发表于 2016-11-2 22:56
应该没有更优的做法了,后来上网搜了下这个题居然是个brain teaser, 这个帖子(http://que4u.blogspot.co ...
. 鍥磋鎴戜滑@1point 3 acres
祝楼主能拿到offer 我 11/3日在纽约的amazon onsite sde ii,也不知道是不是很难。
回复 支持 反对

使用道具 举报

 楼主| feichangh 发表于 2016-11-4 11:58:35 | 显示全部楼层
mayo 发表于 2016-11-3 07:56
祝楼主能拿到offer 我 11/3日在纽约的amazon onsite sde ii,也不知道是不是很难。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
谢谢也祝你好运!已拿到offer,现在在和hr商量能不能转到aws去并继续面其他的。面试我感觉主要还是看bar在哪, 题目难不难是次要
回复 支持 反对

使用道具 举报

linspiration 发表于 2016-11-9 14:21:24 | 显示全部楼层
看了楼主四个贴子 真的很厉害 祝贺!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 08:34

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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