Everything Beneath

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
mid
Asked in
Veeva Systems

Problem

A life-sciences CRM stores customer accounts in a hierarchy: each record names its account id, the parent account it sits under (None for a top-level account), and the sales booked directly to it. For every account, report the combined sales of that account together with all the accounts below it, anywhere down the chain. Accounts with no children contribute only their own sales, and the records may describe several independent top-level accounts.

Every account carries the weight of all it contains.

Example 1

Input:

accounts = [{"id":"north_health","sales":100,"parent":null},{"id":"mercy_hospital","sales":50,"parent":"north_health"},{"id":"cardiology","sales":30,"parent":"mercy_hospital"},{"id":"oncology","sales":20,"parent":"mercy_hospital"},{"id":"west_clinic","sales":40,"parent":"north_health"}]

Output:

{"oncology":20,"cardiology":30,"west_clinic":40,"north_health":240,"mercy_hospital":100}

Example 2

Input:

accounts = [{"id":"east_region","sales":10,"parent":null},{"id":"west_region","sales":5,"parent":null},{"id":"downtown","sales":7,"parent":"east_region"}]

Output:

{"downtown":7,"east_region":17,"west_region":5}

Worked solution and explanation

Why this problem exists in real interviews

This is a subtree sum hiding inside a CRM account hierarchy. The accounts arrive as a flat list of parent pointers, not as a tree, so the real skill being probed is whether you can reconstruct the hierarchy from parent references and then total each account with everything beneath it in ONE pass. The trap is the obvious O(n^2) reading: for each account, walk all of its descendants again. On a deep org with thousands of accounts that re-walks the same branches over and over. The clean answer builds a children index once and lets each node's total reuse its children's totals.

Break down the requirements

Step 1: Invert the parent pointers into a children index

The input gives you child to parent, but a rollup needs parent to children. Walk the list once, recording each account's own sales and appending each account id to its parent's child list. Seed an empty child list for EVERY id so leaf nodes have an entry too, which removes a KeyError special case later.

Step 2: Find the roots, not just the first record

A top-level account is any record whose parent is None. There can be more than one, because the data may describe several independent health systems. Start a traversal from each root; assuming a single root is the most common way this breaks on the hidden forest case.

Step 3: Total each subtree once and remember it

A node's total is its own sales plus the totals of its children. Compute it depth first and store it as you unwind, so each account is visited exactly once. The recursion naturally handles arbitrary depth and the leaf case (no children means the total is just the node's own sales).

The solution

Build a children index, then total each subtree depth first
def rollup_sales(accounts):
    children = {}
    own_sales = {}
    for acct in accounts:
        acct_id = acct["id"]
        own_sales[acct_id] = acct["sales"]
        children.setdefault(acct_id, [])
        parent = acct["parent"]
        if parent is not None:
            children.setdefault(parent, []).append(acct_id)

    totals = {}

    def subtree_total(node):
        total = own_sales[node]
        for child in children[node]:
            total += subtree_total(child)
        totals[node] = total
        return total

    for acct in accounts:
        if acct["parent"] is None:
            subtree_total(acct["id"])

    return totals
Naive per-account walk
For each account, recursively descend and sum its descendants from scratch. Correct, but a node near the root is re-summed once for every ancestor, giving O(n * depth) and quadratic behavior on a tall hierarchy.
Index once, total once
Build the children index once, then each subtree total is computed a single time and reused by its parent. Every account is touched once: O(n).

Common follow-up questions