C++ Coding Exercise - Subdomain Visit Count | Algorithms, Blockchain and Cloud

Given an array of string that is in the format of “count domain”, count the subdomain visits. For example, input [“2 google.com”, “3 helloacm.com”] the output is [“2 google.com”, “5 com”, “3 helloacm.com”] – could be in any order.

Explanation: when we visit google.com, we need to count its sub domains as well, in this case, there will be 5 visits to .com domain (2 from google.com and 3 from helloacm.com)

Each domain address in the input will have at least 1 “.”.

C++ Hash Table via unordered_map

The counts for each domain (including sub domains) need to be stored, and this can be done elegantly using a hash table – which provides O(1) insert, update, lookup and removal constant time. In C++, we can use unordered_map to allocate a hash table.

First, we analyse the string and find the first encountered space, where we split the string into two parts, the counter and the domain. Then we have loop to move forward the index pointer of the DOT delimiter, where we use substr to fetch each possible sub domain and update them in the hash table.

class Solution {
public:
    vector<string> subdomainVisits(vector<string>& cpdomains) {
        unordered_map<string, int> count;
        for (const auto &s: cpdomains) {
            auto spaceIndex = s.find(" ");
            auto num_s = s.substr(0, spaceIndex);
            int num = atoi(num_s.c_str());
            auto domain = s.substr(spaceIndex + 1);
            auto i = -1;
            do {
                auto cur = domain.substr(i + 1); // get next sub domain
                if (count.find(cur) != count.end()) { // first time in hash table?
                    count[cur] += num;
                } else {
                    count[cur] = num;
                }
                i = domain.find('.', i + 1) ; // jump to next dot
            } while (i != string::npos);  // reach end?
        }
        vector<string> r;
        // iterate the hash table for all key-value pairs
        for (auto iter = count.begin(); iter != count.end(); ++ iter) { 
            r.push_back(std::to_string(iter->second) + " " + iter->first);
        }
        return r;
    }
};

class Solution {
public:
    vector<string> subdomainVisits(vector<string>& cpdomains) {
        unordered_map<string, int> count;
        for (const auto &s: cpdomains) {
            auto spaceIndex = s.find(" ");
            auto num_s = s.substr(0, spaceIndex);
            int num = atoi(num_s.c_str());
            auto domain = s.substr(spaceIndex + 1);
            auto i = -1;
            do {
                auto cur = domain.substr(i + 1); // get next sub domain
                if (count.find(cur) != count.end()) { // first time in hash table?
                    count[cur] += num;
                } else {
                    count[cur] = num;
                }
                i = domain.find('.', i + 1) ; // jump to next dot
            } while (i != string::npos);  // reach end?
        }
        vector<string> r;
        // iterate the hash table for all key-value pairs
        for (auto iter = count.begin(); iter != count.end(); ++ iter) { 
            r.push_back(std::to_string(iter->second) + " " + iter->first);
        }
        return r;
    }
};

We could use boost library to split string, though.

#include <boost/algorithm/string.hpp>
 
class Solution {
public:
    vector<string> subdomainVisits(vector<string>& cpdomains) {
        unordered_map<string, int> count;
        for (const auto &s: cpdomains) {
            vector<string> str;
            boost::split(str, s, boost::is_any_of(" ")); // split the input to two parts
            int num = atoi(str[0].c_str());
            auto domain = str[1];
            auto i = -1;
            do {
                auto cur = domain.substr(i + 1); // get next sub domain
                if (count.find(cur) != count.end()) { // first time in hash table?
                    count[cur] += num;
                } else {
                    count[cur] = num;
                }
                i = domain.find('.', i + 1) ; // jump to next dot
            } while (i != string::npos);  // reach end?
        }
        vector<string> r;
        // iterate the hash table for all key-value pairs
        for (auto iter = count.begin(); iter != count.end(); ++ iter) { 
            r.push_back(std::to_string(iter->second) + " " + iter->first);
        }
        return r;
    }
};

#include <boost/algorithm/string.hpp>

class Solution {
public:
    vector<string> subdomainVisits(vector<string>& cpdomains) {
        unordered_map<string, int> count;
        for (const auto &s: cpdomains) {
            vector<string> str;
            boost::split(str, s, boost::is_any_of(" ")); // split the input to two parts
            int num = atoi(str[0].c_str());
            auto domain = str[1];
            auto i = -1;
            do {
                auto cur = domain.substr(i + 1); // get next sub domain
                if (count.find(cur) != count.end()) { // first time in hash table?
                    count[cur] += num;
                } else {
                    count[cur] = num;
                }
                i = domain.find('.', i + 1) ; // jump to next dot
            } while (i != string::npos);  // reach end?
        }
        vector<string> r;
        // iterate the hash table for all key-value pairs
        for (auto iter = count.begin(); iter != count.end(); ++ iter) { 
            r.push_back(std::to_string(iter->second) + " " + iter->first);
        }
        return r;
    }
};

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...

546 words
Last Post: Leetcode Online Judge Does Not Support Boost Library for C++ Solutions
Next Post: How to Count Number of Segments in a String?

The Permanent URL is: C++ Coding Exercise – Subdomain Visit Count

C++ Hash Table via unordered_map

Related posts:

Leave a Reply