google 2018四月onsite面筋

北极猪一只 发表于 2018-4-30 02:44
写完了还没发，写了四千字累死我了

厉害了 坐等 先给你加米

谢谢楼主

楼主决定去狗家了么，是的话可以加下google full time 2018的群

想问下楼主，也是电话通知的吗？还是邮件通知的？

楼主从了狗家了么 是的话加我微信 我把你加进谷歌2018fulltime群  28222522

第一题可以用bit manipulation比较方便吧？ 类似用hashmap了，如果target里面不能有重复的话。
第三题我好像没太理解题意，如果是每一秒内random地返回n个true，那么每一秒总共有多少个query是已知的吗？假如说每秒总共x个，那x是远大于n吗？

楼主接了吗。可以去这里加下谷歌的fulltime群
http://www.1point3acres.com/bbs/thread-405535-1-1.html

题4。只是实现了主要算法。

1.     static class TrieNode {
   
2.         public TrieNode[] nodes = new TrieNode[26];
   
3.         public String word;
   
4.     }
   
5. 
   
6.     public static List<String> findWordInStream(char[] chs, String[] words) {
   
7.         TrieNode root = new TrieNode();
   
8.         for (String word : words) {
   
9.             TrieNode curr = root;
   
10.             for (char ch : word.toCharArray()) {
    
11.                 if (curr.nodes[ch - 'a'] == null) {
    
12.                     curr.nodes[ch - 'a'] = new TrieNode();
    
13.                 }
    
14.                 curr = curr.nodes[ch - 'a'];
    
15.             }
    
16.             curr.word = word;
    
17.         }
    
18.         List<TrieNode> nodeList = new ArrayList<>();
    
19.         Set<String> ansSet = new HashSet<>();
    
20.         for (char ch : chs) {
    
21.             if (root.nodes[ch - 'a'] != null) {
    
22.                 TrieNode curr = root;
    
23.                 nodeList.add(curr);
    
24.             }
    
25.             List<TrieNode> tmpNodeList = new ArrayList<>();
    
26.             for (TrieNode node : nodeList) {
    
27.                 if (node.nodes[ch - 'a'] != null) {
    
28.                     node = node.nodes[ch - 'a'];
    
29.                     if (node.word != null) {
    
30.                         ansSet.add(node.word);
    
31.                     }
    
32.                     tmpNodeList.add(node);
    
33.                 }
    
34.             }
    
35.             nodeList = tmpNodeList;
    
36.         }
    
37.         List<String> ans = new ArrayList<>();
    
38.         ansSet.forEach(p -> ans.add(p));
    
39.         return ans;
    
40.     }

复制代码