Google 电面

贴个我写的code， 望指点

1. import java.util.Map;
   
2. import java.util.HashMap;
   
3. import java.util.List;
   
4. import java.util.ArrayList;
   
5. 
   
6. class TrieNode{
   
7.         boolean isWord;
   
8.         String prefix;
   
9.         Map<String, TrieNode> child;
   
10.         TrieNode(String prefix, boolean isWord){
    
11.                 this.prefix  = prefix;
    
12.                 this.isWord = isWord;
    
13.         }
    
14. }
    
15. 
    
16. public class MiniCompression {
    
17.         public static List<String> minCompress(String[] input) {               
    
18.                 if(input == null)                return null;       
    
19.                 List<String> comp = new ArrayList<String>();       
    
20.                
    
21.                 TrieNode root = buildTrieTree(input);       
    
22.                 for(String s : input){
    
23.                         TrieNode prex = root, curr        = root;
    
24.                         int len = s.length();
    
25.                         boolean single = true;
    
26.                         int i = 0;
    
27.                         for(; i < len; ++i) {                                       
    
28.                                 Map<String, TrieNode> mp = curr.child;
    
29.                                 if((mp.size() > 1) || (i < len && curr.isWord) )                single = false;
    
30.                                 else{
    
31.                                         if(!single){
    
32.                                                 prex = curr;
    
33.                                                 single = true;
    
34.                                         }
    
35.                                 }                               
    
36.                                 curr = mp.get(s.substring(0, i + 1));
    
37.                         }
    
38.                         if(i == len && !single)                prex = curr;  
    
39.                         comp.add(s+":"+prex.prefix);
    
40.                 }
    
41.                 return comp;
    
42.         }
    
43.        
    
44.         public static TrieNode buildTrieTree(String[] input) {
    
45.                 if(input == null)                return null;
    
46.                 TrieNode root = new TrieNode("", false);
    
47.                 if(input.length > 0) {
    
48.                         for(String s : input){
    
49.                                 int len = s.length();
    
50.                                 TrieNode curr = root;
    
51.                                 for(int i = 1; i < len + 1; ++i) {
    
52.                                         if(curr.child == null)                curr.child = new HashMap<String, TrieNode>();                                       
    
53.                                         if(curr.child.containsKey(s.substring(0, i))) {
    
54.                                                 if(i == len)         curr.child.get(s.substring(0, i)).isWord = true;                                               
    
55.                                         }else{
    
56.                                                 curr.child.put(s.substring(0, i), new TrieNode(s.substring(0, i), i == len));
    
57.                                         }
    
58.                                         curr = curr.child.get(s.substring(0, i));
    
59.                                 }
    
60.                         }
    
61.                 }
    
62.                 return root;
    
63.         }
    
64.        
    
65.         public static void main(String[] args) {
    
66.                 String[] input = new String[]{"zebra", "dog", "duck", "dot"};
    
67.                 System.out.println(minCompress(input));
    
68.         }
    
69. }

复制代码

Arthur2012 发表于 2014-10-27 05:13
请问：ab，abb，abbb这种情况怎么办，第一个word是后面word的一个前缀

这种情况下，{ab：“”, abb: "abb", abbb:"abbb"}

averillzheng 发表于 2014-11-3 14:12
这种情况下，{ab：“”, abb: "abb", abbb:"abbb"}

既然ab是"",为什么abb不也是呀？
abb也还是abbb的前缀呀

第一种output挺简单，5-10分钟就能写完。后面改的那种要加count才行。

1. #include <string>
   
2. #include <unordered_map>
   
3. #include <vector>
   
4. #include <iostream>
   
5. using std::string;
   
6. using std::unordered_map;
   
7. using std::cout;
   
8. using std::vector;
   
9. using std::endl;
   
10. 
    
11. struct TrieNode{
    
12.         char val;
    
13.         int count;
    
14.         //bool used;
    
15.         unordered_map<char, TrieNode*> children;
    
16.         TrieNode(char x) : val(x), count(0) {};       
    
17. };
    
18. 
    
19. class Trie {
    
20. private:
    
21.         TrieNode *root;
    
22. public:
    
23.         Trie() {
    
24.                 root = new TrieNode(0);
    
25.                 //root->count = -1;
    
26.         }
    
27. 
    
28.         ~Trie() {
    
29.                 Trie_deconst_util(root);
    
30.         }
    
31. 
    
32.         void Trie_deconst_util(TrieNode *root) {
    
33.                 if (!root)
    
34.                         return;
    
35. 
    
36.                 for (auto &x : root->children) {
    
37.                         Trie_deconst_util(x.second);
    
38.                 }
    
39. 
    
40.                 delete root;
    
41.         }
    
42. 
    
43.         void insertTrie(string word) {
    
44.                 //string substr;
    
45.                 TrieNode *node = root;
    
46.                 //bool IdontWantToUseFlag = false;
    
47.                 for (auto x : word) {
    
48.                         node->count++;
    
49.                         if (node->children.find(x) == node->children.end()) {
    
50.                                 node->children[x] = new TrieNode(x);
    
51.                                 node = node->children[x];
    
52.                                 continue;
    
53.                                 //if (!IdontWantToUseFlag)
    
54.                                 //substr += x;
    
55.                                 //IdontWantToUseFlag = true;
    
56.                                 //node = node->children[x];
    
57.                                 //continue;
    
58.                                 //return substr;
    
59.                         }
    
60.                         node = node->children[x];
    
61.                         //if (!IdontWantToUseFlag)
    
62.                         //substr += x;
    
63.                 }
    
64.         }
    
65. 
    
66.         string searchTrie(string word) {
    
67.                 string substr;
    
68.                 TrieNode *node = root;
    
69.                 for (auto x : word) {
    
70.                         substr += x;
    
71.                         node = node->children[x];
    
72.                         if (node->count <= 1) {
    
73.                                 //substr += x;
    
74.                                 return substr;
    
75.                         }
    
76.                 }
    
77.                 return "";
    
78.         }
    
79. };
    
80. 
    
81. unordered_map<string, string> shortest_prefix(vector<string> &words) {
    
82.         unordered_map<string, string> ans;
    
83.         Trie dict;
    
84.         for (auto word : words) {
    
85.                 dict.insertTrie(word);
    
86.         }
    
87.         for (auto word : words) {
    
88.                 ans[word] = dict.searchTrie(word);
    
89.         }
    
90.         return ans;
    
91. }
    
92. 
    
93. int main() {
    
94.         vector<string> input({"zebra", "dog", "duck","dot"});
    
95.         unordered_map<string, string> ans = shortest_prefix(input);
    
96.         for (auto x : ans) {
    
97.                 cout << x.first << " | " << x.second << endl;
    
98.         }
    
99. }
    

复制代码

王可雪 发表于 2014-11-3 17:26
第一种output挺简单，5-10分钟就能写完。后面改的那种要加count才行。

真牛，5-10分钟能写这么多。好要思考

averillzheng 发表于 2014-11-3 23:12
真牛，5-10分钟能写这么多。好要思考

最开始那种output建个trie的过程中就得到结果了，也没什么corner case所以比较好写。以前用lisp写过trie，再加上前两天参加个比赛刚写了个c++的trie，所以比较熟。不过悲剧的发现前两天写的那个貌似有memory leak。

zhenggao1986 发表于 2014-11-3 13:13
class PrefixTreeNode {
        public int count;
        public PrefixTreeNode[] next;

你的code里面有个小bug，不能test这种情况"dog" and "dogg"，应该前者返回空字符后者返回"dogg"。改正的话我觉得需要把get那个function最后返回的不应该是word，应该是new String();，只要是找到count是1的情况下就可以返回前缀，如果不出现count是1的情况就应该直接返回空。上例中的dog就不会出现count是1的时候，而dogg则在最后一位出现1。

flyaway25 发表于 2014-11-4 07:37
你的code里面有个小bug，不能test这种情况"dog" and "dogg"，应该前者返回空字符后者返回"dogg"。改正的 ...

这个bug好修，关键是对要求的理解，我觉得输出 dog dogg挺好的，输出个空有点怪异

24垅的代码不对，比如 [log]

哎，狗狗确实难啊。电面都这么难