Skip to main content
Fixed link
Source Link
vnp
  • 58.7k
  • 4
  • 55
  • 144

Use a TrieTrie 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.

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.

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.

Became Hot Network Question
Tweeted twitter.com/StackCodeReview/status/1378724061245808643
Source Link
Anatolii
  • 992
  • 5
  • 17

Contacts programming challenge

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