一亩三分地论坛

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

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

亚麻onsite-已跪

[复制链接] |试试Instant~ |关注本帖
lfzh123 发表于 2016-7-29 21:52:21 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Amazon - 网上海投 - Onsite |Fail在职跳槽

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

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

x

Amazon Prime5+1轮午饭,一共见了7个人,三个manager,两个senior,一个SDEII,每一轮都是1个小时!没有休息时间,到最后脑子都不太转了
1.     烙印Manager。Behavior Questions, divedeeply into resume, 问了最近的一些project的实现,都需要非常详细的讲给面试官。
2.     Senior白人,20分钟的behavior questions,jumpgame。不一样的是,每一步步长最多是3,要求输出最短路径的index。问都有什么solution,我先想到的是dp(dp =1+min(dp[i-1], dp[i-2], dp[i-3]),然后他问还有什么solution。经他提醒,貌似可以用三叉树,每一个node存index,每一分支代表步长。然后用BFS找到最多路经。他说这样可以,让我选一个方式,我当然选dp了。
3.     午饭
4.     烙印manager。System design. 1 billionrequest, 1 million servers. Request分为多种type, 有些type是heavy duty,like playing movie,有些是简单的,如何设计可以保证loadbalance。如果有一些server一直没有heavyduty,如果能让这些server保证得到heavyduty。如果有些serverdown了,怎么办?还有如果server。
还有一个问题是,多级domain,每一级都存key-value,输入(rootdomain, int key)要求找到最低一级domain的value。每一级都可能有key,但是value不一样。这样用什么结构存比较好,我说用tree型结构,searchfrom bottom up
com.amazon.www  key 5 - > value 8
us.com.amazon.www key 5-> 6
toy.us.com.amazon.www (这一级没有存key5)
boy.toy.us.com.amazon.www key 5 -> 2.
然后不知道怎么说到了trie,让我写了下implement,这个比较简单。
5.     hiring team colleague,说manager没有来。问了一下amazon locker的设计,要求是bag分为small,medium,largesize,locker也是,bag不能放入size小的locker。写了下bag和lockerclass,然后有一个lockermanager,查看有没有available的locker,存包和取包。小哥没有太challenge我所说的,就是问问为什么这么设计什么的。
6.     白人manager+白人shadow。还是问了20分钟behavior question。LCphone number combination那道题的变种,因为还有一个dictionary,只返回在dictionary里的words,这个条件没有听清,直接写了DFS+backtracking。然后问我如何剔除不在dictionary里的combination,我说可以用trie或者hashset,讲了一下tradeoff。如果用hashset的话,其实timecomplexity没有变化O(2^N).
最后明白了,如果用trie+BFS的话,比较好,因为不在trie的brach就不用走下去了.我就大概写了BFS主要的部分,就没有时间了.
面试完之后的感悟一定要写最优解,尽量用iterative way和BFS,避免DFS(除非没有其他更好的办法)。

  1.     public List<String> letterCombinations(String digits, HashSet<String> words) {
  2.         List<String> res = new ArrayList();. 鍥磋鎴戜滑@1point 3 acres
  3.         if(digits.length() == 0) return res;
  4.         Queue<String> q = new LinkedList();
  5.                 Queue<Trie> qT = new LinkedList();
  6.                 Trie root = new Trie();
  7.                 buildTrie(root, words);. 鍥磋鎴戜滑@1point 3 acres
  8.         q.offer("");
  9.                 qT.offer(root);
  10.         HashMap<Character, String> map = new HashMap();
  11.         map.put('1', "");.鐣欏璁哄潧-涓浜-涓夊垎鍦
  12.         map.put('2', "abc");
  13.         map.put('3', "def");
  14.         map.put('4', "ghi");
  15.         map.put('5', "jkl");. 1point3acres.com/bbs
  16.         map.put('6', "mno");
  17.         map.put('7', "pqrs");
  18.         map.put('8', "tuv");
  19.         map.put('9', "wxyz");
  20.         for(int i = 0; i < digits.length();i++){
  21.             int size = q.size();
  22.             char c = digits.charAt(i);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  23.             while(size > 0){
  24.                 String temp = q.poll();
  25.                                 Trie curr = qT.poll();
  26.                 for(int j = 0; j < map.get(c).length();j++){
  27.                                         int index = map.get(c).charAt(j) - 'a';. from: 1point3acres.com/bbs
  28.                                         if(curr[index] != null){
  29.                                                 qT.offer(curr[index]);
  30.                                                 q.offer(temp+map.get(c).charAt(j));
  31.                                         }
  32.                                 }
  33.                 size--;
  34.             }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  35.         }. 1point 3acres 璁哄潧
  36.         while(q.size() > 0)
  37.             res.add(q.poll());
  38.         return res;
  39.     }
  40.         public void buildTrie(Trie root, HashSet<String> words){
  41.                 for(String w: words){
  42.                         Trie curr = root;
  43.                         for(int i = 0; i < w.length();i++){
  44.                                 int c = w.charAt(i) - 'a';.鏈枃鍘熷垱鑷1point3acres璁哄潧
  45.                                 if(curr[c] == null). 鍥磋鎴戜滑@1point 3 acres
  46.                                         curr[c] = new Trie();
  47.                                 curr = curr[c];. 1point3acres.com/bbs
  48.                         }
  49.                         curr.word = w;
  50.                 }
  51.         }
  52.         class Trie{. From 1point 3acres bbs
  53.                 public Trie[] child;. more info on 1point3acres.com
  54.                 public String word;. Waral 鍗氬鏈夋洿澶氭枃绔,
  55.                 public Trie(){
  56.                         child = new Trie[26];
  57.                         word = "";
  58.                 }
  59.         }
复制代码
最后HR没有给detailed feedback due to policy。也不知道问题在哪儿,我猜是design那一轮,而且最后一轮没有写完。但是HR说不会freeze我,我可以接着再申请,所以我猜最后结果比较close吧。




补充内容 (2016-7-30 07:11):
第4个问题没有type完,如果server的IP改变了怎么办,我说让server通知master去update啊,三哥说如果server也不知道呢。。我就不太明白了,然后问我知道不知道 如果知道了IP,怎么访问这个server。不太确定是什么意思

评分

1

查看全部评分

z165153 发表于 2016-7-29 22:33:51 | 显示全部楼层
也不让吃顿饭,歇歇吗?lz回答的够可以的了,只是onsite的运气不够好吧。
回复 支持 反对

使用道具 举报

chs5003 发表于 2016-7-29 22:47:54 | 显示全部楼层
I can see you have pretty good coding skills from your code, you will succeed sooner or later.

The problem description seems to be incomplete for Problem 4?
回复 支持 反对

使用道具 举报

mtler 发表于 2016-7-30 01:42:27 | 显示全部楼层
楼主面的哪个组?
回复 支持 反对

使用道具 举报

 楼主| lfzh123 发表于 2016-7-30 07:09:07 | 显示全部楼层
z165153 发表于 2016-7-29 22:33
也不让吃顿饭,歇歇吗?lz回答的够可以的了,只是onsite的运气不够好吧。

午饭肯定有了,就是每轮之间没有休息
回复 支持 反对

使用道具 举报

 楼主| lfzh123 发表于 2016-7-30 07:11:50 | 显示全部楼层
chs5003 发表于 2016-7-29 22:47
I can see you have pretty good coding skills from your code, you will succeed sooner or later.

Th ...

我又补充了一下
回复 支持 反对

使用道具 举报

 楼主| lfzh123 发表于 2016-7-30 07:12:05 | 显示全部楼层
mtler 发表于 2016-7-30 01:42
楼主面的哪个组?

第一句就是 Amazon Prime。。
回复 支持 反对

使用道具 举报

MapReduce 发表于 2016-8-9 13:34:02 | 显示全部楼层
最后一题为什么不是trie+dfs呢?在没有重复节点的情况下剪枝遍历对于bfs和dfs不是应该同样的时间复杂度吗?dfs还少了很多的空间复杂度
回复 支持 反对

使用道具 举报

 楼主| lfzh123 发表于 2016-8-12 00:29:19 | 显示全部楼层
MapReduce 发表于 2016-8-9 13:34. Waral 鍗氬鏈夋洿澶氭枃绔,
最后一题为什么不是trie+dfs呢?在没有重复节点的情况下剪枝遍历对于bfs和dfs不是应该同样的时间复杂度吗 ...

DFS不会减少空间复杂度,recursion也需要stack memory
回复 支持 反对

使用道具 举报

dianek 发表于 2016-8-12 02:53:56 | 显示全部楼层
關於IP改變問題的解決,有幾個方法不知道可不可以提:
鏈路層,L2TP + 鏈路層Handover (3GPP internal protocols)
transport層,用SCTP: multihome + multistream  + heartbeat
ip層,用mobile ip:home agent + foreign agent + care-of address
應用層,用SIP,subscribe new address from user agent after detecting IP change
回复 支持 反对

使用道具 举报

dianek 发表于 2016-8-12 03:00:48 | 显示全部楼层
關於知道IP如何訪問server的問題,這是在考你ARP和RARP協議:
一部分server的active-standby是用ARP實現的,就是兩個server共享一個Public IP,然後它們各自有自己的Private IP,standby定期ARP ping Public IP,如果down了,馬上用public IP廣播若干ARP來替換public IP server,這樣就實現切換了。粒度大概600ms
回复 支持 反对

使用道具 举报

wuyufeng 发表于 2016-8-28 01:00:59 | 显示全部楼层
那个trie里面的变量为啥都用public。。。。。。
回复 支持 反对

使用道具 举报

超分 发表于 2016-9-3 11:48:29 | 显示全部楼层
楼主是面SDE2?
回复 支持 反对

使用道具 举报

stefan0428 发表于 2016-9-14 10:27:01 | 显示全部楼层
还有一个问题是,多级domain,每一级都存key-value,输入(rootdomain, int key)要求找到最低一级domain的value。每一级都可能有key,但是value不一样。这样用什么结构存比较好,我说用tree型结构,searchfrom bottom up
com.amazon.www  key 5 - > value 8
us.com.amazon.www key 5-> 6.1point3acres缃
toy.us.com.amazon.www (这一级没有存key5).鏈枃鍘熷垱鑷1point3acres璁哄潧
boy.toy.us.com.amazon.www key 5 -> 2.
. 鍥磋鎴戜滑@1point 3 acres
楼主能举个例子吗? 没看懂这个key在里面啥作用。 谢谢
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-10-28 04:25:22 | 显示全部楼层
求问第四题那个多级DOMAIN具体是什么,没太看懂那个KEY VALUE PAIR
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 03:31

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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