google 2018四月onsite面筋

题目1

1.     public static String getShortestWord(String[] words, String target) {
   
2.         String ans = null;
   
3.         Map<Character, Integer> map = new HashMap<>();
   
4.         for (char ch : target.toCharArray()) {
   
5.             map.put(ch, map.getOrDefault(ch, 0) + 1);
   
6.         }
   
7.         for (String word : words) {
   
8.             Map<Character, Integer> currMap = new HashMap<>(map);
   
9.             if (word.length() < target.length()) {
   
10.                 continue;
    
11.             }
    
12.             for (char ch : word.toCharArray()) {
    
13.                 if (!currMap.containsKey(ch)) {
    
14.                     continue;
    
15.                 }
    
16.                 int count = currMap.get(ch);
    
17.                 if (count == 1) {
    
18.                     currMap.remove(ch);
    
19.                 } else {
    
20.                     currMap.put(ch, count - 1);
    
21.                 }
    
22.             }
    
23.             if (currMap.size() == 0 && (ans == null || word.length() < ans.length())) {
    
24.                 ans = word;
    
25.             }
    
26.         }
    
27.         return ans;
    
28.     }

复制代码

多谢分享！！！！！！

多谢分享！！！

楼主厉害，内容有帮助，谢谢

感谢分享！恭喜！

感谢分享！恭喜！
题目感觉有点难。楼主厉害！
第一题 貌似倒排索引题目。words看作doc，char看作term。words首先根据长短排序，然后根据char建立倒排。匹配target的时候，把几个posting list求交，找到第一个交集。可能需要考虑target有重复char的情况。
第三题 貌似概率问题。比如每秒10个。第一个query被allow的概率是10/10.第二个query的概率是9/10.第三个query的概率是9/10 或者 8/10 （根据上一次是否allow更新概率）。
第四题 貌似AC自动机。多串匹配，且允许相互覆盖（比如匹配abc，bc）。建立失败跳转的指针，和查找匹配串都难写。楼主厉害！

感谢楼主分享！下周二我也要面试了希望有用！

恭喜恭喜，也求文档，谢谢楼主！