Contacts programming challenge

Question

I successfully solved a problem on Hackerrank called Contacts, but I'm curious if my code in C++ looks good to C++ developers. If not, how it should be improved.

Below is the short description of the problem and then the code itself.

Problem

1. Add name, where name is a string denoting a contact name. This must store name as a new contact in the application.
2. Find partial, where partial is a string denoting a partial name to search the application for. It must count the number of contacts starting with partial and print the count on a new line.

So, given sequential add and find operations, perform each operation in order.

Solution

Use a Trie like structure to solve the problem. All the children of a node have a common prefix of the contact associated with that parent node, and the root is associated with the empty string.

Code

struct node {
 uint32_t count = 0;
 std::unordered_map<char, std::unique_ptr<node>> childrenMap;
};
/*
 * Complete the contacts function below.
 */
std::vector<uint32_t> contacts(std::vector<std::vector<std::string>>& queries) {
 std::vector<uint32_t> results;
 node root;
 for (const auto& row : queries) {
 const auto operation = row[0];
 const auto name = row[1];
 if (operation == "add") {
 auto* parent = &root;
 for (auto& ch : name) {
 auto& childrenMap = parent->childrenMap;
 if (!childrenMap.count(ch)) {
 childrenMap.emplace(ch, std::make_unique<node>());
 }
 childrenMap[ch]->count++;
 parent = childrenMap[ch].get();
 }
 } else {
 auto* parent = &root;
 auto result = 0;
 for (auto& ch : name) {
 auto& childrenMap = parent->childrenMap;
 if (!childrenMap.count(ch)) {
 result = 0;
 break;
 }
 parent = childrenMap[ch].get();
 result = childrenMap[ch]->count;
 }
 results.push_back(result);
 }
 }
 return results;
} 

Answer 1

The Trie approach might be overkill for this question. I think that a plain (ordered) std::set (or std::multiset) would be adequate. The set's lower_bound() member takes you directly to the first entry with the specified substring. From there, we can either count linearly, or use lower_bound again with a new key created by adding 1 to the last character, then just return the iterator difference.

I'd certainly consider writing separate add() and find() functions instead of plonking all the code in that big if/else. If nothing else, it makes the unit tests easier to write.

• G. Sliepen: Upvoted since it's a valid suggestion, but you are making a trade-off: Lookups in std::set are O(log(number of elements in set)), lookups in the trie are O(number of characters in the names). Once you have looked up the lower bound, the cost of counting is also different. So it depends on the exact distribution of operations in the input which will be faster.
• Toby Speight: Yes @G.Sliepen, and where I wrote "might", one should also read "(but might not)". It depends greatly on the actual data. I would start with the simple approach, and switch to the more complex code if and when I find that it's necessary.