# Contacts programming challenge

Posted on

Problem

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];

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;
}

Solution

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.