g家电面

继续攒人品。

汇报下前段时间的两轮google电面。recruiter莫名奇妙的联系了，然后莫名奇妙的就安排面试了，人生第一个技术面试，leetcode刷了几个题就上了，太渣已跪
第一个题是瑞士的engineer面的，第二题是伦敦的engineer面的

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

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

种data structure猜了一轮以后，猜中trie。然后要求implement

然后，就没有然后了。

crystal3721 发表于 2014-7-18 20:01
跪求大牛code怎么写～怎么用trie？？

用c ++ 写的

1. #include<iostream>
   
2. #include<string>
   
3. #include<unordered_map>
   
4. using namespace std;
   
5. 
   
6. class Trie {
   
7. 
   
8. public:
   
9.     bool leaf;
   
10.     unordered_map<char, Trie*> children;     
    
11.     Trie() {
    
12.         leaf = false;
    
13.     }
    
14. 
    
15.     void insert(string word) {
    
16.         if(children[word[0]] == NULL) {
    
17.             children[word[0]] = new Trie();
    
18.         }
    
19.    
    
20.         if(word.size() == 1) {
    
21.             children[word[0]]->leaf = true;
    
22.         }else {
    
23.             children[word[0]]->insert(word.substr(1));
    
24.         }
    
25.     }
    
26. 
    
27.     bool find(string word) {
    
28.         if(children[word[0]] == NULL) {
    
29.             return false;
    
30.         }
    
31. 
    
32.         if(word.size() == 1) {
    
33.             return children[word[0]]->leaf;
    
34.         }else {
    
35.             return children[word[0]]->find(word.substr(1));
    
36.         }
    
37.     }
    
38. 
    
39.     void remove(string word) {
    
40.         if(children[word[0]] == NULL) {
    
41.             return;
    
42.         }
    
43. 
    
44.         if(word.size() == 1) {
    
45.             children[word[0]]->leaf = false;
    
46.             if(children[word[0]]->children.size() == 0) {
    
47.                 delete children[word[0]];
    
48.             }
    
49.         }else{
    
50.             children[word[0]]->remove(word.substr(1));
    
51.         }
    
52.     }
    
53. };
    
54. 
    
55. 
    
56. 
    
57. int main() {
    
58.     Trie* test = new Trie();
    
59.     test->insert("whese");
    
60.     test->insert("who");
    
61.     test->insert("whose");
    
62.     test->insert("find");
    
63.     test->insert("fin");
    
64.     test->remove("fin");
    
65.     test->insert("aaa");
    
66. 
    
67.     cout << "whese" << test->find("whese") << endl;
    
68.     cout << "who" << test->find("who") << endl;
    
69.     cout << "whose" << test->find("whose") << endl;
    
70.     cout << "what" << test->find("what") << endl;
    
71.     cout << "aa" << test->find("aa") << endl;
    
72.     cout << "fin" << test->find("fin") << endl;
    
73.     cout << "find" << test->find("find") << endl;
    
74. 
    
75. }
    

复制代码

第二题可以参考leetcode的roman integer

xiatian122 发表于 2014-7-18 19:20
第二题可以参考leetcode的roman integer

跪求大牛code怎么写～怎么用trie？？

对,是字典树.
选字典的原因是号码总体的长度很小, 所以树的高度不高.
建树很简单啊. 就是从第一个字符(数字)开始扫, 然后把同类的加在一起.
比如
+44 UK
+4420 London
+447 UK Mobile
+44750 Vodafoned
要是题是这么给的, 已经很明显提示你要用字典树了
这4个是
root -> 4->4
root -> 4->4->2->0
root -> 4->4->7
root -> 4->4->7->5->0

可以用排序二叉树吗？

trie。。是我我也挂了

为什么不能直接用字典呢？

谢谢楼主分享！！！

感谢！！！！