Technical test for a job interview.
me.vylion.com
1#include "trie_node.hpp"
2
3typedef std::unordered_map<char, TrieNode *>::iterator ChildIt;
4
5TrieNode *TrieNode::next(char c)
6{
7 if (_children.find(c) != _children.end())
8 {
9 return _children[c];
10 }
11
12 TrieNode *new_child = new TrieNode;
13 _children[c] = new_child;
14
15 return new_child;
16}
17
18bool TrieNode::hasChildren()
19{
20 return _children.size() > 0;
21}
22
23bool TrieNode::insert(const std::string &word, int &pos)
24{
25 if (pos == word.length())
26 {
27 if (!_is_leaf)
28 {
29 _is_leaf = true;
30 return true;
31 }
32 return false;
33 }
34 else
35 {
36 char c = word[pos];
37 TrieNode *next_node = next(c);
38 pos++;
39
40 return next_node->insert(word, pos);
41 }
42}
43
44bool TrieNode::remove(const std::string &word, int &pos, bool &to_remove)
45{
46 // base case: end of string
47 if (pos == word.length() && _is_leaf)
48 {
49 _is_leaf = false;
50 to_remove = !hasChildren(); //to be deleted if no _children
51 return true;
52 }
53
54 // otherwise keep going
55 char c = word[pos];
56 pos++;
57 ChildIt it = _children.find(c);
58
59 // found nothing
60 if (it == _children.end())
61 {
62 to_remove = false;
63 return false;
64 }
65
66 bool success = it->second->remove(word, pos, to_remove);
67
68 // if child gets marked for removal
69 if (to_remove)
70 {
71 delete it->second; // delete the pointer
72 _children.erase(it); // remove the entry
73 to_remove = !_is_leaf && !hasChildren(); // remove if not a leaf either and no more _children remaining
74 }
75
76 return success;
77}
78
79bool TrieNode::search(const std::string &word, int &pos)
80{
81 if (pos == word.length())
82 {
83 return _is_leaf;
84 }
85
86 char c = word[pos];
87 pos++;
88 ChildIt it = _children.find(c);
89
90 if (it == _children.end())
91 {
92 return 0;
93 }
94
95 return it->second->search(word, pos);
96}
97
98int TrieNode::size()
99{
100 return _children.size();
101}