谷歌电面面经

T大农民伯伯 发表于 2018-11-30 14:42
你的做法对应的场景是品牌一个一个的给出，如果一下子把所有要处理的品牌给出了的话。用trie要更快。时间 ...

你能详细说说吗，这题我想过用Trie，但是思考了一下，觉得貌似用Trie来做并没有任何优势啊。。。

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

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

写了一个小代码

1. # Find all the possible brand from one sentence
   
2. import string
   
3. D = {}
   
4. for c in string.lowercase:
   
5.     D[c] = []
   
6. for c in string.uppercase:
   
7.     D[c] = []
   
8. 
   
9. sentence = 'I do not want to have to go where you do not follow'
   
10. brands = ['wow', 'abc', 'dove', 'have']
    
11. ret = []
    
12. for idx, brand in enumerate(brands):
    
13.     D[brand[0]].append((1, idx))
    
14. 
    
15. for word in sentence.split(' '):
    
16.     word = set(word)
    
17.     for c in word:
    
18.         for (loc_idx, word_idx) in D[c]:
    
19.             if loc_idx == len(brands[word_idx]):
    
20.                 ret.append(brands[word_idx])
    
21.             else:
    
22.                 D[brands[word_idx][loc_idx]].append((loc_idx+1,word_idx))
    
23.             D[c] = []
    
24. print D
    
25. print ret

复制代码

补充内容 (2018-12-3 11:02):
这个代码有问题，没有处理一个单词只能提供一个字母的情况，需要维护两个dictionary，一个是temp记录当前单词操作后的样子。

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

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

lukuang 发表于 2018-12-1 02:44
pre-process 可以从后往前做，如果某个字母出现于后一个词，那最小index就是后一个词的index，如果没有， ...

嗯 从后往前做preprocess这个想法不错，加上O(1) 的字符查找，应该就是最优解了～

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

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

给你点个赞！

Thanks for sharing


Can't see it now.

Mark..

1. public List<String> isSubsequence(String sentence, List<String> words) {
   
2.   HashMap<Character, TreeSet<Integer>> map = new HashMap<>();
   
3.   String[] sen = sentence.toLowerCase().split("\\s+");
   
4.   for (int i = 0; i < sen.length; i++) {
   
5.     for (int j = 0; j < sen[i].length; j++) {
   
6.        char temp = sen[i].charAt(j);
   
7.        if (!map.containsKey(temp)) {
   
8.              map.put(temp, new TreeSet<>());
   
9.       }
   
10.       map.get(temp).add(i);
    
11.     }
    
12.   }
    
13.   List<String> res = new ArrayList<>();
    
14.   for (String w : words) {
    
15.        int index = -1;
    
16.        char[] tep = w.toCharArray();
    
17.        for (int i = 0; i < tep.length; i++) {
    
18.            if (!map.containsKey(tep[i])) break;
    
19.            for (int v : map.get(tep[i])) {
    
20.                if (v > index) {
    
21.                    index = v; break;
    
22.                }
    
23.            }
    
24.        }
    
25.        if (i == tep.length) res.add(w);
    
26. 
    
27.   }
    
28. }

复制代码

Time Complexity: O(len(# of word in sentence)*O(len of average of word in sentence)) + O(# of word in search) * O(# of the length of word)

follow up就是往trie上面凑么，不然的话一般做法都得重新for一遍的样子啊，最多加一个map之类记录一下出现过的状态