Katkat
Back

Leaf Domain Cumulative Scores

AmazonSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to model hierarchical data using tree traversal and string manipulation to aggregate cumulative metrics across nested domains.

Problem Statement

You are given a list of domain names and their associated visit counts. A domain like mail.google.com is hierarchical, where mail is a subdomain of google.com, and google.com is a subdomain of com.

Your task is to calculate the cumulative visit counts for every domain in the hierarchy. The total count for a domain includes its own visits plus the visits of all its subdomains.

Function Signature

def get_cumulative_counts(domain_visits: List[str]) -> Dict[str, int]

Input Format

  • domain_visits: A list of strings in the format "count domain" (e.g., "900 google.com").

Output Format

  • A dictionary mapping each domain string to its cumulative count.

Constraints

  • Number of domain entries: 1 to 10,000.
  • String length: 1 to 100 characters.
  • Visit counts: 1 to 1,000,000.

Examples

Example 1: Input: ["900 google.com", "50 mail.google.com"] Output: {"google.com": 950, "mail.google.com": 50, "com": 950} Explanation: google.com inherits the 50 visits from mail.google.com. com inherits everything.

Example 2: Input: ["10 apple.com", "20 banana.com"] Output: {"apple.com": 10, "banana.com": 20, "com": 30}

Edge Cases

  • Domains with single labels (e.g., "com").
  • Domains with multiple identical subdomains.
  • Overlapping domain hierarchies.

Hints

Hint 1

Represent the hierarchy using a hash map where keys are the domain strings and values are their cumulative visit counts.

Hint 2

For each input string, split it into the count and the domain, then iteratively peel off the subdomains (e.g., 'a.b.c' becomes 'a.b.c', 'b.c', and 'c') and update the map.

Hint 3

Ensure your logic handles the accumulation by iterating through the split domain levels for every entry provided in the input list.

Follow-up questions

  • How would you modify your solution if the input was a massive stream of domain visits that exceeds available memory?
  • If you needed to find the 'top K' most visited domains globally, how would you optimize the current approach?
  • How would the complexity change if you were required to represent the hierarchy as a Trie instead of a hash map?