360的总部在北京望京798附近，这周有朋友去面试了，讲了下大致过程。360总部一楼有个大厅，前台有很多MM，说明来意，被指向面试区（人还挺多的，应该很缺人，或者有新项目）。

一面：

技术面，是个小弟面的。

1）介绍下自己

2）说了几个重要的项目，问了些项目的情况，这都是面试官感兴趣的话题。

3）出了个编程题：设计一个trie树，实现创建 trie树和检索功能，数据为一批英文单词，都是小写字母。

分析：

这题目主要是三个方面，第一是设计trie树的数据结构，第二是实现trie树创建函数，第三是检索英文单词，看是否存在。

实现如下：

[cpp] view plaincopy

 

1. #include<iostream>  
2. #include<string.h>  
3. using namespace std;  
4.   
5. #define MAXNODE 26  
6. struct TrieNode{  
7.         int counts;  
8.         TrieNode* next[MAXNODE];//next character  
9.         TrieNode():counts(1){  
10.                 int i = 0;  
11.                 while(i < MAXNODE)  
12.                 {  
13.                         next[i++] = NULL;  
14.                 }  
15.         }  
16. };  
17. void createTrie(TrieNode* &root, char* str)  
18. {  
19.         if(strlen(str) <= 0) return;  
20.         if(root == NULL)  
21.                 root = new TrieNode();  
22.         int i = 0;  
23.         TrieNode* p = root;  
24.   
25.         while(i < strlen(str))  
26.         {  
27.                 int k = str[i++] - 'a';  
28.                 if(p->next[k])  
29.                 {  
30.                         p->next[k]->counts ++;  
31.                 }  
32.                 else  
33.                         p->next[k] = new TrieNode();  
34.                 p = p->next[k];  
35.         }  
36. }  
37.   
38. int SearchTrie(TrieNode* root, char* str)  
39. {  
40.         TrieNode* p = root;  
41.         if(p == NULL) return -1;  
42.         int i = 0;  
43.         while(i < strlen(str))  
44.         {  
45.                 int k = str[i++] - 'a';  
46.                 if(p->next[k] == NULL)  
47.                         return 0;  
48.                 else  
49.                         p = p->next[k];  
50.                 if(i == strlen(str))  
51.                         return p->counts;  
52.         }  
53. }  
54.   
55. int main()  
56. {  
57.         char a[][4] = {"abc", "bcd", "ade", "acd", "bgf"};  
58.         int i = 0;  
59.         int j = 0;  
60.         TrieNode* root = NULL;  
61.         while(i < 5)  
62.         {  
63.                 createTrie(root, a[i++]);  
64.         }  
65.         char* b = "bcd";  
66.         int in = SearchTrie(root, b);  
67.         if( in <= 0)  
68.                 cout << "Trie can't find \"" << b << "\"" << endl;  
69.         else  
70.                 cout << "Trie have find \"" << b << "\"" << endl;  
71.         return 0;  
72. }  

Trie have find "bcd"

总结：

这个算法可以用于字符串的前缀查询，比如搜索TIPS等。