Adapt Throne Inheritance When Initialization Does Not Supply a King

# Adapt Throne Inheritance When Initialization Does Not Supply a King Design the throne-inheritance data structure when its initializer no longer receives the first monarch. The structure still needs to preserve birth order, record deaths, and produce the living succession order, but the mechanism that establishes the dynasty root is intentionally unspecified. Begin by asking how the first monarch enters the system. Compare reasonable APIs, select one only after the interviewer chooses the contract, and then explain the implementation and edge cases. Do not assume that a fabricated `found` event must be the first item in a batch. ### Clarifying Questions to Ask - Is there a separate `establishMonarch(name)` operation, a nullable-parent birth, a factory call, or an external root record? - Can any birth or death operation occur before the monarch is established, and how should it fail? - May the root be established more than once, or replaced later? - Are names globally unique, and must referenced parents already exist? - When a person dies, do their living descendants remain in succession order? - Is the required API an online object with operations, a final batch result, or both? ### Part 1 — Define root-establishment semantics Describe at least two viable interfaces and their trade-offs. State the validation rules for the empty state, duplicate establishment, and operations that reference a dynasty before its root exists. #### What This Part Should Cover - The distinction between “constructor has no king” and any particular replacement operation. - One explicit source of truth for the root and an unambiguous transition from empty to initialized. - Errors or idempotency behavior for duplicate and out-of-order requests. ### Part 2 — Maintain births, deaths, and succession order Once a root contract is selected, design the state and algorithms for adding a child as the youngest child, marking a person dead, and returning the living inheritance order. #### What This Part Should Cover - An ordered child list per person, membership validation, and a dead-person set or flag. - Pre-order traversal from the established root, omitting dead people while retaining their descendants. - Complexity for updates and for producing an order, including a stack-safe traversal for a deep dynasty. ### Part 3 — Exercise the missing edge cases Walk through empty-state queries, death of the monarch, duplicate names, unknown parents, repeated death, and a very deep lineage. Explain which behavior follows the selected contract and which choice would need another interviewer decision. ### What a Strong Answer Covers - Preserves the reported no-king initializer variant without inventing how the root appears. - Makes invalid state transitions explicit and keeps the object internally consistent. - Uses birth-order pre-order traversal and handles deceased ancestors correctly. - Separates operation complexity from the cost of materializing the full succession order. - Calls out concurrency or persistence only if the interviewer expands the in-memory task. ### Follow-up Questions 1. How would you make monarch establishment idempotent when a client retries after a timeout? 2. Can the current order be queried faster than a full traversal after many deaths and births? 3. What invariant prevents two concurrent requests from establishing different roots?