亚麻onsite-已跪

Amazon Prime，5轮+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[i] =1+min(dp[i-1], dp[i-2], dp[i-3])，然后他问还有什么solution。经他提醒，貌似可以用三叉树，每一个node存index，每一分支代表步长。然后用BFS找到最多路经。他说这样可以，让我选一个方式，我当然选dp了。

3.     午饭

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

他更好的办法）。

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);
   
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");
    
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';
    
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.         }
    
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';
    
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。不太确定是什么意思

还有一个问题是，多级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.

楼主能举个例子吗？ 没看懂这个key在里面啥作用。 谢谢

關於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

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?

楼主面的哪个组？

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 ...

我又补充了一下

mtler 发表于 2016-7-30 01:42
楼主面的哪个组？

第一句就是 Amazon Prime。。

最后一题为什么不是trie＋dfs呢？在没有重复节点的情况下剪枝遍历对于bfs和dfs不是应该同样的时间复杂度吗？dfs还少了很多的空间复杂度

MapReduce 发表于 2016-8-9 13:34
最后一题为什么不是trie＋dfs呢？在没有重复节点的情况下剪枝遍历对于bfs和dfs不是应该同样的时间复杂度吗 ...

DFS不会减少空间复杂度，recursion也需要stack memory