Block type with the most children

A workspace stores documents as a tree of blocks. Each block has a type (page, heading, text, list, ...) and a parent, except top-level blocks. Find the block type whose blocks have the most children in total.

Interface

Unless you agree on a different interface with the interviewer, assume:

• blocks: rows of (block_id, block_type, parent_id), where parent_id is None for a top-level block.
• type_with_most_children(blocks) -> str — for each type, add up the number of direct children of every block of that type, and return the type with the largest total. Break ties alphabetically.

Example

p1 page   (top level)        p2 page   (top level)
h1 heading -> p1             l1 list   -> p1          l2 list -> p1
t1 text    -> p2
i1, i2, i3 list_item -> l1   i4, i5 list_item -> l2

children by parent type: page 3 (p1) + 1 (p2) = 4, list 3 (l1) + 2 (l2) = 5
type_with_most_children(blocks)  ->  "list"

p1 and l1 both have 3 children, so the answer depends on totalling per type, not taking the single biggest block.

Constraints

• Up to 10^7 blocks. Rows are in no particular order: a child can appear before its parent.

Clarifying questions

• Is "most children" the total over all blocks of a type, the average per block, or the single block with the most?
• Direct children only, or every descendant?
• What if a row's parent_id points to a block that isn't in the table?
• How are ties broken?

What a strong answer covers

• A first pass to map each block id to its type, a second to count each row against its parent's type: O(n) time.
• Why two passes are needed when children can come before parents, or how to do it in one by storing pending counts per parent id.
• The SQL: a self-join of blocks to their parent, GROUP BY parent.block_type, ordered by count and type.
• Orphan rows and top-level blocks handled on purpose.

Follow-ups

• Return the average number of children per block of each type, counting childless blocks as 0.
• Count all descendants, not only direct children, for each type. What is the cost on a very deep tree?
• Find the deepest page, and the block type that most often appears at the deepest level.