一月三十一号狗家昂赛

1月31号的昂赛。自我感觉不错，今天也进HC了。发面筋求人品，求offer，求大米

我应该没签NDA（反正肯定没有真的签字或者电子签字。如果哪里犄角旮旯有类似保密要求我再考虑删帖吧），所以就细说题了。我会把第一轮两题和第三轮的解法会在后面几楼po出来。
第一轮：
白男。似乎是出了新题，起码我没见过。

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

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

而且最后都没有反应过来……不知道面我的人作何感想又会怎么评价……太糗了……这轮可能有小问题。
后来应该是时间太多不知道聊什么（我有没get到他的follow up），他又出了一道题，说不用写code。

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

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

第二轮：
白男。先是判断两个interval是否overlap的简单题。说我可能见过。我假装没见过思路严谨地尝试定义了interval，考虑是否inclusive的状况，他说只考虑两端都是inclusive的就好了。而后秒掉。
第二题他本来应该是想出 里口:依儿吧。我为了表示没见过，演了一下听不懂consecutive之类的一大堆定语，细问的时候他改了题目，改成了简单的longest subarray。这么简单秒掉……而且他应该是有心放水不想出太难，蛮友好的。
而后追加了求longest parent-to-child path in a tree。注意不是binary tree。应该算新题，不过肯定不能算难。recursive一下秒掉。剩下的时间随便聊了聊天。

第三轮：
中国妹子。面筋原题，大大地放水。：）给一个string和一个word dict。找dict里是给定string的sub sequence的最长的word。按部就班表演，先写正常解法。follow up string太长解法，follow up dictionary太大解法。均是表演过思考过程后秒掉。

第四轮：
白男，也是很友好，应该有放水。
第一题：

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

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

后来follow up没做，他觉得我肯定会所以换了 里口：散妖武。我演了一下没见过，说了naive做法。而后思索能不能装没做过。后来觉得当场发明BIT太假了，就老实说我见过，这是我学习BIT的例题。讲解了做法。他表示一般他期望人们能看出来最后一位总是0就比较满意了。我肯定above。
我的感觉是我表现其实一般（实在是累，第一场都没见过有点难，后来还一直扯）。而且两道题都见过。不过他似乎挺满意，因为我都是给出了完整分析和比较普遍的解法+背景知识。而不是“这道题刷过”。希望不是我的错觉……

第五轮：
中国汉子。很友好，肯定有放水。
也应该是面筋原题。给两个tree表示html body。自己定义tree，如何parse可以不管。写方法判断两个tree里的text一样不一样。正常recusive就能解决。follow up是text太大怎么办。用iterator就好。完了之后聊了不少time，mem complexity的问题，在而后就闲聊了。


补充内容 (2017-2-3 15:27):
楼主实在加州san bruno面的昂赛。youtube的地盘

给力の面经+完美的演出， 提前祝贺大OFFER

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

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

第三轮，java version

1. public class LongestSubsequenceInDict {
   
2. 
   
3.     public String longestSubsequenceWord(String s, Set<String> dict) {
   
4.         String res = "";
   
5.         for (String word : dict) {
   
6.             if (word.length() > res.length() && isSebsequence(s, word)) {
   
7.                 res = word;
   
8.             }
   
9.         }
   
10. 
    
11.         return res;
    
12.     }
    
13. 
    
14.     private boolean isSebsequence(String s, String word) {
    
15.         int i = 0;
    
16.         int j = 0;
    
17.         while (i < s.length() && j < word.length()) {
    
18.             if (s.charAt(i) == word.charAt(j)) {
    
19.                 i++;
    
20.                 j++;
    
21.             } else {
    
22.                 i++;
    
23.             }
    
24.         }
    
25. 
    
26.         return j == word.length();
    
27.     }
    
28. 
    
29. 
    
30.     public String longestSubsequenceWord1(String s, Set<String> dict) {
    
31.         String res = "";
    
32.         HashMap<Character, TreeSet<Integer>> cachedS = buildCachedS(s);
    
33.         
    
34.         for (String word : dict) {
    
35.             if (word.length() > res.length() && isSebsequence1(cachedS, word)) {
    
36.                 res = word;
    
37.             }
    
38.         }
    
39. 
    
40.         return res;
    
41.     }
    
42. 
    
43.     private HashMap<Character,TreeSet<Integer>> buildCachedS(String s) {
    
44.         HashMap<Character,TreeSet<Integer>> map = new HashMap<>();
    
45.         for (int i = 0; i < s.length(); i++) {
    
46.             char c = s.charAt(i);
    
47.             if (map.containsKey(c)) {
    
48.                 map.get(c).add(i);
    
49.             } else {
    
50.                 map.put(c, new TreeSet<>());
    
51.                 map.get(c).add(i);
    
52.             }
    
53.         }
    
54. 
    
55.         return map;
    
56.     }
    
57. 
    
58.     private boolean isSebsequence1(HashMap<Character, TreeSet<Integer>> map, String word) {
    
59.         int pos = 0;
    
60.         int i = 0;
    
61.         for (; i < word.length(); i++) {
    
62.             char c = word.charAt(i);
    
63.             if (!map.containsKey(c) || map.get(c).ceiling(pos) == null) {
    
64.                 return false;
    
65.             }
    
66.             pos = map.get(c).ceiling(pos);
    
67. 
    
68.         }
    
69.         return i == word.length();
    
70.     }
    
71. 
    
72. 
    
73. 
    
74.     public static void main(String[] args) {
    
75.         LongestSubsequenceInDict l = new LongestSubsequenceInDict();
    
76.         HashSet<String> set = new HashSet<>();
    
77.         set.add("abc");
    
78.         set.add("abbbc");
    
79.         set.add("abb");
    
80.         System.out.println(l.longestSubsequenceWord1("aaaaaaabbbbbbdddddd", set));
    
81.         System.out.println(l.longestSubsequenceWord1("aaaaaaabbbbbbddddddc", set));
    
82.     }
    
83. }
    

复制代码

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

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

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

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

一轮题二：
这道题只是写了dfs里while里的框架，解释思路面试官看到#action 1那里确实是dfs就首肯过了。当时没有写完整。

1. <p>def isValid(s):</p><p>    decodeCount = [0] # syntax hack to make this variable accessible in dfs</p><p>                      # it does not need to be a list</p><p>
   
2. </p><p>    def dfs(s):</p><p>        if s == '':</p><p>            decodeCount[0] += 1 # if reaches end, it there is a decoding way</p><p>        if not s[0].isdigit():</p><p>            return</p><p>        count = 0</p><p>        idx = 0</p><p>        while idx < len(s):</p><p>            c = s[idx]</p><p>            if c.isdigt():</p><p>                # action 1 take current as a count</p><p>                count = count * 10 + int(c)</p><p>                dfs(s[idx+count:]) # depth first search along this action</p><p>
   
3. </p><p>                # ation 2 continue adding</p><p>                count = count * 10 + int(c)</p><p>                idx += 1</p><p>                </p><p>            else:</p><p>                # if not integer, we cannot move on</p><p>                break</p><p>
   
4. </p><p>    dfs(s)</p><p>
   
5. </p><p>    # return True if and only if there is only one way of decoding</p><p>    return decodeCount[0] == 1</p>

复制代码

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

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

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

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

第五轮咋搞？

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

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

谢谢楼主分享，祝楼主好运！

楼主，第三轮的subsequence都是前缀匹配的是吗？

补充内容 (2017-2-3 06:13):
不好意思，sb了。忽略我忽略我