811. Subdomain Visit Count
Model: qwen2.5-coder:14b
Topics: Hash Table
FAANG asked: 0
Acceptance rate: 71.7%
Problem Breakdown
The problem requires us to process a list of count-paired domains and return a list that explicitly counts the number of visits to each subdomain. Each input entry consists of a visit count followed by a domain name. The output should include the count for each subdomain, including the top-level domain.
Inputs:
- A list
cpdomainswhere each element is a string in the format “count domain”.
Outputs:
- A list of strings in the same format as the input, representing the total visits to each subdomain.
Implicit Constraints:
- The number of domains will not exceed 100.
- Each domain name will have either one or two ”.” characters.
- The count for any domain will not exceed 10000.
Intuition
A brute-force approach would involve iterating over each domain, splitting it into subdomains, and then counting the visits for each subdomain. This approach is inefficient because it requires multiple passes over the data and has a high time complexity.
The key insight is to use a hash table (dictionary) to keep track of the visit counts for each subdomain. By iterating over each domain only once, we can efficiently update the counts for all subdomains in constant time.
Approach
- Initialize an empty dictionary
subdomain_countto store the total visits for each subdomain. - Iterate over each entry in the input list
cpdomains. - For each entry, split it into the count and the domain name.
- Split the domain name into its subdomains by splitting on ”.”.
- For each subdomain (from the most specific to the least), update the corresponding entry in the dictionary with the given count.
- After processing all entries, construct the output list by iterating over the dictionary and formatting each entry as “count domain”.
Complexity Analysis
- Time Complexity: O(N * M), where N is the number of domains and M is the average length of a domain name. This is because we iterate over each domain and split it into subdomains.
- Space Complexity: O(K), where K is the number of unique subdomains. We store the count for each subdomain in the dictionary.
Solution
def subdomainVisits(cpdomains):
from collections import defaultdict
# Initialize a dictionary to store the visit counts for each subdomain
subdomain_count = defaultdict(int)
# Iterate over each count-paired domain
for cpdomain in cpdomains:
count, domain = cpdomain.split()
count = int(count)
# Split the domain into its subdomains
fragments = domain.split('.')
# Update the count for each subdomain
for i in range(len(fragments)):
subdomain = '.'.join(fragments[i:])
subdomain_count[subdomain] += count
# Construct the output list
result = []
for subdomain, count in subdomain_count.items():
result.append(f"{count} {subdomain}")
return result
# Example usage:
print(subdomainVisits(["9001 discuss.leetcode.com"]))
print(subdomainVisits(["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]))
Edge Cases Handled
- Empty Input: The function will return an empty list if the input is empty.
- Single Subdomain: Domains with only one subdomain (e.g., “com”) are handled correctly.
- Multiple Subdomains: Domains with multiple subdomains (e.g., “discuss.leetcode.com”) are split and counted appropriately.
- Duplicate Domains: If the same domain appears multiple times, its counts are aggregated correctly in the dictionary.
The solution provided is correct, efficient, and clear. It adheres to the problem constraints and handles all edge cases as described.