Amazon·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say

Jul 2026

Summary

Amazon SWE coding round, one problem the whole session. The domain hierarchy thing looked like a tree problem at first glance and I went down that path for a bit before realizing there's a cleaner way to think about it.

Questions Asked (1)

Given a list of domain-score pairs, find all leaf domains (domains that are not an ancestor of any other domain in the input) and return each leaf's cumulative score, which includes the scores of all its ancestor domains that also appear in the input. Return results sorted lexicographically.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I spent the first few minutes trying to build an actual tree structure and got tangled up pretty fast.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the input format and edge cases, then propose building a tree from the domain hierarchy. Traverse the tree to identify leaf domains and accumulate scores from ancestors present in the input, finally sorting the results lexicographically.

Pro tip: Mention that you would validate the input for cycles or invalid domains, and discuss how to handle large inputs efficiently with iterative traversal to avoid recursion limits.

1. Clarify Requirements and Edge Cases

Ask about input size, domain format, possible duplicates, and whether scores can be negative. Confirm that leaf domains are those with no children in the input set.

2. Build Domain Hierarchy

Construct a tree or graph where each domain points to its parent (by removing the leftmost label). Use a hash map to store domain-score pairs for quick lookup.

3. Identify Leaves and Compute Cumulative Scores

Traverse from each domain up to its ancestors, summing scores of those present in the input. Alternatively, do a DFS from roots, propagating cumulative sums, and collect leaves.

4. Sort and Return Results

Collect all leaf domains with their cumulative scores, sort lexicographically by domain name, and return the sorted list.

Key Points to Mention

Domain hierarchy representation: parent-child relationships via string manipulation (e.g., splitting on '.').
Efficient lookup: using a hash map to store domain scores for O(1) access.
Leaf identification: a domain is a leaf if no other domain in the input has it as an ancestor.
Cumulative score calculation: summing scores of all ancestors that appear in the input, including the leaf itself.
Time and space complexity: O(N * L) where N is number of domains and L is average domain length, due to string operations.
Handling edge cases: empty input, single domain, domains with no ancestors in input, and potential cycles (though unlikely).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.