Solution For Subdomain Visit Count

Problem statement:

You are given a list of website domain strings cpdomains and their respective count. For example, ["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]. Now, you are required to compute the sum of count of each website domain along with all sub-domains that it contains. For example, visit count for “mail.com” is the sum of “intel.mail.com” and “google.mail.com”, and visit count for “google.mail.com” is “900”.

Solution:

This problem can be solved using a dictionary to store the count of each sub-domain. We will iterate over each element in the given list cpdomains. For each element, we will extract the count and the domain, and then split the domain by “.” to get all the subdomains.

We will then iterate over all the subdomains and create a key-value pair in the dictionary where the key is the subdomain and the value is the count of the domain. If the subdomain already exists in the dictionary, we will increment its count by the count of the current domain.

Finally, we will iterate over all the key-value pairs in the dictionary and add the value to the result sum.

Here is the python implementation of this approach:

“`
def subdomainVisits(cpdomains: List[str]) -> List[str]:
counts = {}
for domain in cpdomains:
count, domain = domain.split()
count = int(count)
subdomains = domain.split(“.”)
for i in range(len(subdomains)):
subdomain = “.”.join(subdomains[i:])
if subdomain not in counts:
counts[subdomain] = count
else:
counts[subdomain] += count

result = []
for subdomain, count in counts.items():
    result.append(str(count) + " " + subdomain)

return result

“`

Complexity Analysis:

• Time Complexity: O(N*M) where N is the number of domains and M is the maximum number of subdomains in a domain.
• Space Complexity: O(N*M) as we are storing each subdomain in the dictionary.

Step by Step Implementation For Subdomain Visit Count

class Solution {
    public List subdomainVisits(String[] cpdomains) {
        HashMap map = new HashMap<>();
        for(String domain: cpdomains){
            String[] cpinfo = domain.split("\\s+");
            String[] frags = cpinfo[1].split("\\.");
            int count = Integer.valueOf(cpinfo[0]);
            String cur = "";
            for(int i = frags.length - 1; i >= 0; i--){
                cur = frags[i] + (i < frags.length - 1 ? "." : "") + cur;
                map.put(cur, map.getOrDefault(cur, 0) + count);
            }
        }
        List res = new ArrayList<>();
        for(String dom: map.keySet()){
            res.add("" + map.get(dom) + " " + dom);
        }
        return res;
    }
}

class Solution:
    def subdomainVisits(self, cpdomains):
        """
        :type cpdomains: List[str]
        :rtype: List[str]
        """
        # create a dictionary to store the count of each subdomain
        d = {}
        
        # loop through each domain in the input
        for domain in cpdomains:
            
            # split the domain into count and domain
            count, domain = domain.split(' ')
            
            # convert count to an integer
            count = int(count)
            
            # split domain into subdomains
            subdomains = domain.split('.')
            
            # reverse the subdomains so we can iterate from the top level domain down
            subdomains = subdomains[::-1]
            
            # create a variable to store the current subdomain
            current = ''
            
            # iterate through each subdomain
            for subdomain in subdomains:
                
                # add the subdomain to the current variable
                current = subdomain + '.' + current
                
                # if the current subdomain is not in the dictionary, add it
                if current not in d:
                    d[current] = count
                    
                # otherwise, increment the count for that subdomain
                else:
                    d[current] += count
                    
        # create a list to store the output
        output = []
        
        # loop through each subdomain in the dictionary
        for subdomain, count in d.items():
            
            # add the subdomain and count to the output list
            output.append(str(count) + ' ' + subdomain)
            
        # return the output list
        return output

var subdomainVisits = function(cpdomains) {
    var map = {};
    
    for (var i = 0; i < cpdomains.length; i++) {
        var count = cpdomains[i].split(' ')[0];
        var domain = cpdomains[i].split(' ')[1];
        var subdomains = domain.split('.');
        
        for (var j = 0; j < subdomains.length; j++) {
            var curr = subdomains.slice(j).join('.');
            
            if (!map[curr]) {
                map[curr] = 0;
            }
            
            map[curr] += parseInt(count);
        }
    }
    
    var result = [];
    
    for (var key in map) {
        result.push(map[key] + ' ' + key);
    }
    
    return result;
};

class Solution {
public:
    vector subdomainVisits(vector& cpdomains) {
        unordered_map counts;
        for (const string& domain : cpdomains) {
            istringstream iss(domain);
            int n;
            iss >> n;
            string s;
            iss >> s;
            do {
                counts[s] += n;
                size_t pos = s.find('.');
                s = s.substr(pos + 1);
            } while (!s.empty());
        }
        vector result;
        for (const auto& count : counts) {
            result.push_back(to_string(count.second) + " " + count.first);
        }
        return result;
    }
};

public class Solution {
    public IList SubdomainVisits(string[] cpdomains) {
        // create a dictionary to store the subdomain counts
        Dictionary subdomainCounts = new Dictionary();
        
        // loop through each domain in the input array
        foreach(string domain in cpdomains) {
            // split the domain into count and domain
            string[] domainSplit = domain.Split(' ');
            int count = Int32.Parse(domainSplit[0]);
            string domainName = domainSplit[1];
            
            // create an array of subdomains by splitting the domain on the '.' character
            string[] subdomains = domainName.Split('.');
            
            // create a string for the current subdomain
            string currentSubdomain = "";
            
            // loop through each subdomain in reverse order
            for(int i = subdomains.Length - 1; i >= 0; i--) {
                // append the current subdomain to the string
                currentSubdomain = subdomains[i] + (currentSubdomain.Length > 0 ? "." : "") + currentSubdomain;
                
                // add the subdomain to the dictionary or increment the count if it already exists
                if(subdomainCounts.ContainsKey(currentSubdomain)) {
                    subdomainCounts[currentSubdomain] += count;
                }
                else {
                    subdomainCounts.Add(currentSubdomain, count);
                }
            }
        }
        
        // create a list to store the results
        List results = new List();
        
        // loop through each key in the dictionary
        foreach(string key in subdomainCounts.Keys) {
            // add the key and value to the results list
            results.Add(subdomainCounts[key] + " " + key);
        }
        
        // return the results
        return results;
    }
}