推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 5593|回复: 14
收起左侧

亚麻onsite-已跪

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

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

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

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

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();
  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);
  8.         q.offer("");
  9.                 qT.offer(root);. more info on 1point3acres.com
  10.         HashMap<Character, String> map = new HashMap();
  11.         map.put('1', "");.鏈枃鍘熷垱鑷1point3acres璁哄潧
  12.         map.put('2', "abc");
  13.         map.put('3', "def");
  14.         map.put('4', "ghi");
  15.         map.put('5', "jkl");
  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();-google 1point3acres
  22.             char c = digits.charAt(i);
  23.             while(size > 0){
  24.                 String temp = q.poll();
  25.                                 Trie curr = qT.poll();. visit 1point3acres.com for more.
  26.                 for(int j = 0; j < map.get(c).length();j++){
  27.                                         int index = map.get(c).charAt(j) - 'a';
  28.                                         if(curr[index] != null){
  29.                                                 qT.offer(curr[index]);
  30.                                                 q.offer(temp+map.get(c).charAt(j));
  31.                                         }
  32.                                 }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  33.                 size--;. 1point 3acres 璁哄潧
  34.             }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  35.         }
  36.         while(q.size() > 0)
  37.             res.add(q.poll());. 鍥磋鎴戜滑@1point 3 acres
  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';
  45.                                 if(curr[c] == null)
  46.                                         curr[c] = new Trie();
  47.                                 curr = curr[c];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  48.                         }
  49.                         curr.word = w;
  50.                 }
  51.         }
  52.         class Trie{
  53.                 public Trie[] child;
  54.                 public String word;
  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 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
也不让吃顿饭,歇歇吗?lz回答的够可以的了,只是onsite的运气不够好吧。
回复 支持 反对

使用道具 举报

chs5003 发表于 2016-7-29 22:47:54 | 显示全部楼层
关注一亩三分地微博:
Warald
I can see you have pretty good coding skills from your code, you will succeed sooner or later.. 鍥磋鎴戜滑@1point 3 acres

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.. 鍥磋鎴戜滑@1point 3 acres

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
最后一题为什么不是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
. visit 1point3acres.com for more.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.鏈枃鍘熷垱鑷1point3acres璁哄潧
com.amazon.www  key 5 - > value 8. more info on 1point3acres.com
us.com.amazon.www key 5-> 6. 1point3acres.com/bbs
toy.us.com.amazon.www (这一级没有存key5). From 1point 3acres bbs
boy.toy.us.com.amazon.www key 5 -> 2.
.1point3acres缃
楼主能举个例子吗? 没看懂这个key在里面啥作用。 谢谢
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-29 03:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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