狗家 昂赛面经

周二在西雅进行的昂赛，周五收到邮件说过了，在准备hc。来发面经回馈地里！

一共5轮，4轮coding加1轮behavior。

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

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

每个题写完后都跟面试官讨论了各种follow-up，各种变换后的时间空间复杂度等等。整个experience非常好，感觉学到很多东西，面试官也愿意跟你分享他的想法，互动很多。

求大米！！


补充内容 (2019-4-14 14:36):
补充一下第2轮，出题的时候面试官还提供了一个list，里面是所有词出现过的char，例如{c, a, t, d, o, g}。他说有的人用得着这个list，也可以不用。我的算法没用它。补充这个题目供大家参考。

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

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

jdlimiao 发表于 2019-4-14 14:33
我的做法跟楼下umialpha@的dfs一样，就是把一个词不断的删字母，然后跟原set里的词比较，直到删没，或者 ...

请问删字母规定是从头至尾删嘛，cat -> ct 考虑吗？ 不然的话岂不是word break?

第一题是用bfs的吗？大概就是先处理k=i的情况，然后k=i+1时在之前的所有list的结尾append上list.end()或list.end()+1，然后再做下层循环，直到k==n

1.     public List<List<Integer>> getPattern(int n) {
   
2.         List<List<Integer>> result = new LinkedList<>();
   
3.         //dfs(result, n, new LinkedList<>(), 1);
   
4.         bfs(result, n);
   
5.         return result;
   
6.     }
   
7. 
   
8.     private void bfs(List<List<Integer>> result, int n) {
   
9.         Queue<List<Integer>> queue = new LinkedList<>();
   
10.         List<Integer> start = new LinkedList<>();
    
11.         start.add(1);
    
12.         int len = 1;
    
13.         queue.offer(start);
    
14.         while (!queue.isEmpty()) {
    
15.             if (len == n) break;
    
16.             int size = queue.size();
    
17.             while (size-- > 0) {
    
18.                 List<Integer> curr = queue.poll();
    
19.                 for (int i = 1; i <= curr.get(curr.size() - 1) +1; ++i) {
    
20.                     curr.add(i);
    
21.                     queue.offer(new LinkedList<>(curr));
    
22.                     curr.remove(curr.size() - 1);
    
23.                 }
    
24.             }
    
25.             len++;
    
26.         }
    
27.         while (!queue.isEmpty()) {
    
28.             result.add(queue.poll());
    
29.         }
    
30.     }

复制代码

第二轮LZ怎么做的？
我能想到的就是建一个prefix tree和一个postfix tree

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

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

修正代码中的一处笔误

1. def can_be_deleted(dictionary):
   
2. 
   
3.     memo = {}
   
4.     def dfs(s):
   
5.         if not s:
   
6.             return True
   
7.         if s not in dictionary:
   
8.             return False
   
9.         if s in memo:
   
10.             return memo[s]
    
11. 
    
12.         memo[s] = any(dfs(s[:i] + s[i + 1:]) for i in range(len(s)))
    
13.         return memo[s]
    
14. 
    
15.     return list(s for s in dictionary if dfs(s))

复制代码

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

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

可以问下楼主behavior问了什么吗？

天街小雨tjy 发表于 2019-4-15 00:11
第一题是用bfs的吗？大概就是先处理k=i的情况，然后k=i+1时在之前的所有list的结尾append上list.end()或lis ...

我觉得是对的