Handling an Ambiguous "Family Tree" Prompt

Below is a structured, interview-ready approach you can use to lead under ambiguity, while making your assumptions explicit and validating early. ## 1) Top five clarification questions I would prioritize breadth-first clarity across goals, operations, scale, integrity, and evaluation: 1. Target use cases and audiences - Are we building for read queries (e.g., find ancestors, siblings, relationships) or also write updates (add person, set parent-child, adoption)? - Is the goal algorithmic problem-solving (e.g., LCA), data modeling, or API design? 2. Required query and update surface - Which queries must be supported? Examples: is_ancestor(a,b), ancestors(b, k), siblings(x), relationship_degree(a,b), lowest_common_ancestor(a,b), list_descendants(x, depth), count_offspring(x), lineage_path(a→b). - Which updates must be supported? add_person, add_parent_child, remove_person, adopt/step-parent, marriage/divorce? Are spouse relationships in scope? 3. Data shape and constraints - Is this a strict tree (each child has ≤1 parent) or a genealogy DAG (each child can have up to 2 biological parents)? Are adoptions/guardians allowed beyond 2? - Are cycles strictly forbidden? (I will assume yes.) How do we handle unknown parents or missing gender/age? Are multiple families (forest) allowed? 4. Scale and complexity goals - Expected N (people) and E (parent-child edges)? Are queries online with frequent updates? - Any latency targets (e.g., is_ancestor in O(log N) vs O(N))? Memory constraints? 5. Evaluation criteria and deliverables - Should I deliver a working core API with unit tests and complexity analysis, or also UX/visualization? - How will correctness be judged (sample tests provided vs my own), and what constitutes success for this round? If the interviewer won’t specify, I’ll make minimal, explicit assumptions and proceed. ## 2) Minimal viable example (MVE) with walk-through Assumptions for MVE (stated out loud and in comments): - Data model is a genealogy DAG: each child may have 0–2 parents; cycles are invalid. - We support: add_person, add_parent_child, get_parents, get_children, is_ancestor, get_siblings, lowest_common_ancestor (LCA). Spouses out of scope for MVE. - Unknown parents allowed. Names are not unique; use stable IDs. People (IDs, Name, Gender?): - 1: Alice (F) - 2: Bob (M) - 3: Carol (F) — child of Alice and Bob - 4: Dan (M) — child of Alice and unknown father - 5: Eva (F) — parent(s) unknown (isolated) Edges (parent → child): - (1 → 3), (2 → 3), (1 → 4) Resulting structure: - Parents(3) = {1, 2}, Parents(4) = {1}, Parents(5) = {} - Children(1) = {3, 4}, Children(2) = {3}, Children(5) = {} Example queries with expected outputs: - get_parents(3) → {Alice, Bob} - get_children(1) → {Carol, Dan} - get_siblings(3) → {Dan} (half-sibling via Alice) - is_ancestor(1, 3) → true; is_ancestor(2, 4) → false; is_ancestor(1, 1) → false (by definition, no self-ancestry) - LCA(3, 4) → {Alice} (lowest common ancestor set can be multiple; here it’s just Alice) - LCA(3, 5) → {} (no relationship) Proposed core API (pseudo-code signatures): - add_person(id: int, name: str, gender: Optional[str]) -> bool - add_parent_child(parent_id: int, child_id: int) -> bool // rejects if cycle or >2 parents - get_parents(id: int) -> Set[int] - get_children(id: int) -> Set[int] - is_ancestor(ancestor_id: int, person_id: int) -> bool // DFS/BFS up parents or down children (choose one and be consistent) - get_siblings(id: int) -> Set[int] - lowest_common_ancestor(a: int, b: int) -> Set[int] // intersection of ancestor sets; filter to lowest by depth - validate() -> List[str] // integrity checks (cycles, >2 parents, missing nodes) Complexity notes for MVE: - Store adjacency: parents[id], children[id]. Most queries via BFS/DFS → O(N + E) worst case. - For demo scale (<1e4), this is acceptable; can optimize later (e.g., ancestor memoization, topological depths, binary lifting only if strict tree). ## 3) Recording/confirming assumptions; timeboxing and delivering under limited guidance - Document at top (and read back): - Model: DAG genealogy, ≤2 parents/child, no cycles, unknown parents allowed, forest allowed, IDs unique, names not unique, spouses out of scope. - Scope: implement core reads (parents, children, siblings, is_ancestor, LCA) and minimal writes (add_person, add_parent_child) with validation. - Complexity: correctness-first with O(N+E) traversals. - Oral confirmation: “Unless you prefer otherwise, I’ll proceed with these assumptions and the MVE I described.” If the interviewer declines to provide more detail: - Timebox 2–3 minutes to sketch the data structures and tests. - Deliver the skeleton API and key path first: 1) Data model + add_person/add_parent_child with validation (no cycles, ≤2 parents). 2) Read operations: get_parents/get_children → is_ancestor → siblings → LCA. - Iterate: add edge cases only after the core path runs (unknown parents, half-siblings, disconnected persons). Keep a visible TODO list. - Narrate trade-offs (e.g., why not precompute heavy indexes initially) and mark where optimization would go if scale demands it. ## 4) Verifiable success criteria and re-alignment points Success criteria I would define and commit to: - Correctness via unit tests on the MVE and a few adversarial cases. - Integrity checks enforced on every update: no cycles; ≤2 parents; referenced IDs exist. - Complexity commitments for MVE: O(1) add_person; O(1) amortized add_parent_child (plus cycle check); O(N+E) for is_ancestor/LCA; acceptable for N ≤ 1e4 in screen. - Clear, well-documented API with examples; readable code. Example unit tests: 1) Parents/Children basics - parents(3) == {1,2}; children(1) == {3,4} 2) Half-siblings - siblings(3) == {4}; siblings(4) == {3} 3) Ancestor checks - is_ancestor(1,3) == true; is_ancestor(2,4) == false; is_ancestor(1,1) == false 4) LCA - lca(3,4) == {1}; lca(3,5) == {} 5) Integrity - Reject third parent for a child; reject edge that introduces a cycle; reject edges to missing nodes. Re-alignment triggers: - If interviewer hints spouse/marriage or adoption must be modeled now → pause to agree on data model changes (e.g., relation types). - If performance constraints tighten (e.g., N≈1e6) → discuss precomputation (topological order, ancestor bitsets, or move to strict-tree optimizations if the model changes). - If they require minimal memory → revisit indexes and trade-offs. ## 5) Example of handling ambiguous requirements (Goal–Action–Result–Reflection) - Goal: Own a relationship-graph feature where the only initial instruction was “model organizational relationships and answer access questions quickly.” No concrete queries or scale given. - Actions: 1) Drove clarity: identified primary use cases (is_manager_of, chain_of_command, common_manager), update operations (reorg moves), and integrity rules (no cycles; one primary manager; dotted-line edges allowed but tagged). 2) Proposed an MVE with a small org: a few teams, a contractor, and a dotted-line report. Defined inputs (nodes, typed edges) and outputs (queries + expected answers). Wrote unit tests to align early. 3) Delivered in stages: core DAG with validations → ancestor queries via BFS → common manager via ancestor intersections. Timeboxed 2 days per stage; demoed each. 4) Optimized after alignment: cached depths and ancestors for O(log N) LCA in the strict-tree view and kept a fallback BFS when dotted lines created a DAG. - Results: Met latency SLOs, reduced authorization query times by ~80%, and enabled a new audit report. Stakeholders adopted the API across two services. - Reflection: The combination of a concrete MVE, explicit assumptions, and incremental deliverables reduces risk. Align on data shape early (tree vs DAG), because it dictates algorithms and performance strategies. This approach shows leadership under ambiguity: clarify, propose, validate quickly with an MVE, and deliver incrementally with guardrails on correctness and complexity.