1040. Domain Visit Rollup
A web analytics team receives visits, a list of log lines. Each line looks like domain|count, for example mail.shop.org|1200: the number of page views recorded for exactly that domain name. A domain is a few lowercase labels separated by dots.
A visit to mail.shop.org also counts as a visit to its parent domains shop.org and org, obtained by repeatedly dropping the leftmost label. Return a map from every domain that appears in visits, or is a parent of one, to the total views counted for it, including views logged for the domain itself and for any domain below it.
Aim for time linear in the total length of the input lines.
Example 1
- Input:
- visits = ["mail.shop.org|1200","shop.org|300"]
- Output:
- {"mail.shop.org":1200,"org":1500,"shop.org":1500}
- Explanation:
mail.shop.org adds 1200 to itself, shop.org and org; shop.org|300 adds 300 to shop.org and org, giving 1500 for both of those.
Example 2
- Input:
- visits = ["a.io|5","b.io|7","a.io|1"]
- Output:
- {"a.io":6,"b.io":7,"io":13}
- Explanation:
a.io appears twice for 6 views, b.io has 7, and their shared parent io collects 13.
Example 3
- Input:
- visits = ["localhost|40"]
- Output:
- {"localhost":40}
- Explanation:
A domain with a single label has no parent, so only localhost is counted.
Constraints
0 ≤ visits.length ≤ 104.
Each domain has between 1 and 5 labels; labels are 1 to 10 characters from a-z and 0-9.
0 ≤ count ≤ 104 for each line, so every total fits in a 32-bit signed integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(total input length)
- Space
- O(number of distinct domains)