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 ListsubdomainVisits(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: vectorsubdomainVisits(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 IListSubdomainVisits(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; } }