How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Leaf Domain Cumulative Scores | Amazon Coding Question

Quick Overview

This question evaluates a candidate's ability to model hierarchical string data and aggregate values along a tree structure, a common pattern in coding interviews involving tries and suffix-based hierarchies. It tests practical algorithm design skills such as identifying leaf nodes, propagating ancestor sums, and handling edge cases like single-label entries efficiently at scale.

Leaf Domain Cumulative Scores

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

# Leaf Domain Cumulative Scores A search system assigns an integer score to individual domain names. Domains form a hierarchy based on their dot-separated labels: the domain `b.c` is the **parent** of `a.b.c`, which is in turn the parent of `x.a.b.c`, and so on. The right-most label (e.g. `com`) sits at the top of the hierarchy. Formally, a domain `X` is an **ancestor** of a domain `Y` if `Y` ends with `"." + X` — that is, `X` is a proper suffix of `Y` aligned on a label boundary. For example, the ancestors of `mail.domain.com` are `domain.com` and `com`. A **leaf domain** is a domain present in the input that is **not** an ancestor of any other domain in the input (no other input domain has it as a parent or higher ancestor). For every leaf domain, its **cumulative score** is the sum of: - its own score, plus - the scores of all of its ancestors that appear in the input. Return, for each leaf domain, its cumulative score. ### Input - A collection of entries, each pairing a domain string with an integer score (for example, a list of `(domain, score)` pairs — match the provided function signature). - Domain strings are lowercase ASCII made of one or more non-empty labels separated by single dots (`.`). There are no leading or trailing dots. - Each domain appears at most once. - Scores are integers and may be negative. ### Output - A mapping from each leaf domain to its cumulative score. - If the result is returned as a list of pairs, order the pairs in ascending lexicographic order of the domain string. ### Example Input: ``` com 20 domain.com 10 mail.domain.com 5 test.com 10 user.test.com 30 contact.user.test.com -5 ``` The leaf domains are `mail.domain.com` and `contact.user.test.com` (`com`, `domain.com`, `test.com`, and `user.test.com` are all ancestors of some other domain, so they are not leaves). Cumulative scores: ``` mail.domain.com = 5 + 10 + 20 = 35 contact.user.test.com = -5 + 30 + 10 + 20 = 55 ``` So the answer (ascending lexicographic by domain) is: ``` contact.user.test.com -> 55 mail.domain.com -> 35 ``` ### Constraints & Notes - $1 \le$ number of domains $\le 10^5$. - The total length of all domain strings is at most $10^6$ characters. - An ancestor that does not appear in the input contributes nothing; only the scores of domains actually present are summed. - A domain may have several children; every leaf is reported independently. - A single-label domain (e.g. `com`) that has no children is itself a leaf, and its cumulative score is just its own score.

Quick Answer: This question evaluates a candidate's ability to model hierarchical string data and aggregate values along a tree structure, a common pattern in coding interviews involving tries and suffix-based hierarchies. It tests practical algorithm design skills such as identifying leaf nodes, propagating ancestor sums, and handling edge cases like single-label entries efficiently at scale.

A search system assigns an integer score to individual domain names. Domains form a hierarchy based on their dot-separated labels: `b.c` is the parent of `a.b.c`, which is the parent of `x.a.b.c`, and so on (the right-most label sits at the top). A domain `X` is an **ancestor** of a domain `Y` if `Y` ends with `"." + X` — that is, `X` is a proper suffix of `Y` aligned on a label boundary. For example, the ancestors of `mail.domain.com` are `domain.com` and `com`. A **leaf domain** is a domain present in the input that is **not** an ancestor of any other input domain. For every leaf domain, its **cumulative score** is its own score plus the scores of all of its ancestors that appear in the input. Return, for each leaf domain, its cumulative score, ordered ascending lexicographically by domain string. **Example** Input: `com=20, domain.com=10, mail.domain.com=5, test.com=10, user.test.com=30, contact.user.test.com=-5` The leaf domains are `mail.domain.com` and `contact.user.test.com`. Their cumulative scores: - `mail.domain.com = 5 + 10 + 20 = 35` - `contact.user.test.com = -5 + 30 + 10 + 20 = 55` Output: `[["contact.user.test.com", 55], ["mail.domain.com", 35]]` **Notes** - Domain strings are lowercase ASCII of one or more non-empty dot-separated labels, no leading/trailing dots; each domain appears at most once; scores may be negative. - An ancestor absent from the input contributes nothing. - A single-label domain (e.g. `com`) with no children is itself a leaf. - 1 <= number of domains <= 1e5; total length of all domain strings <= 1e6.

Constraints

1 <= number of domains <= 10^5
Total length of all domain strings <= 10^6 characters
Domains are lowercase ASCII, one or more non-empty labels separated by single dots, no leading/trailing dots
Each domain appears at most once
Scores are integers and may be negative

Examples

Input: ([['com', 20], ['domain.com', 10], ['mail.domain.com', 5], ['test.com', 10], ['user.test.com', 30], ['contact.user.test.com', -5]],)

Expected Output: [['contact.user.test.com', 55], ['mail.domain.com', 35]]

Explanation: Only mail.domain.com and contact.user.test.com are leaves; com/domain.com/test.com/user.test.com are ancestors of others. Scores: 5+10+20=35 and -5+30+10+20=55, sorted lexicographically.

Input: ([['com', 20]],)

Expected Output: [['com', 20]]

Explanation: A single-label domain with no children is itself a leaf; its cumulative score is just its own score.

Input: ([['com', 20], ['a.b.com', 7]],)

Expected Output: [['a.b.com', 27]]

Explanation: com is an ancestor of a.b.com (not a leaf). a.b.com is a leaf; ancestor b.com is absent so contributes 0, but com=20 is present: 7+20=27.

Input: ([['x', 10], ['a.x', -5], ['b.x', 3]],)

Expected Output: [['a.x', 5], ['b.x', 13]]

Explanation: x has two children and is not a leaf. Both a.x and b.x are leaves: -5+10=5 and 3+10=13.

Input: ([['a', 1], ['b.a', 2], ['c.b.a', 3]],)

Expected Output: [['c.b.a', 6]]

Explanation: A straight 3-level chain; only the deepest domain c.b.a is a leaf: 3+2+1=6.

Input: ([['net', -4], ['sub.net', -1]],)

Expected Output: [['sub.net', -5]]

Explanation: All-negative scores: net is an ancestor (not a leaf); sub.net leaf = -1 + -4 = -5.

Hints

A domain X is a leaf iff no other input domain has X as a proper dot-boundary suffix. First collect every domain that appears as such a suffix — those are exactly the non-leaves.
The ancestors of a domain are exactly the strings you get by dropping its leading labels one at a time: mail.domain.com -> domain.com -> com.
Store scores in a hash map keyed by the full domain. A leaf's cumulative score is its own score plus the scores of the ancestor suffixes that are actually present in the map (missing ones contribute nothing).

Quick Overview