Find the Royal Lineage - codepath/compsci_guides GitHub Wiki

Unit 11 Session 2 Advanced (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 45 mins
  • 🛠️ Topics: Graph Traversal, Topological Sort, DAG

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • How are the family relationships structured?
    • The relationships are represented as a directed acyclic graph (DAG), where edges go from elder to descendant.
  • What should be the output format?
    • Return a dictionary where each key is a member's name and the value is a list of their ancestors sorted alphabetically.
HAPPY CASE
Input: 
    names = [""Henry"", ""Elizabeth"", ""George"", ""Mary"", ""Charles"", ""William""]
    relationships = [""Henry"", ""Mary""], [""Elizabeth"", ""Mary""], [""George"", ""Mary""], [""Charles"", ""William""], [""William"", ""Mary""](/codepath/compsci_guides/wiki/""Henry"",-""Mary""],-[""Elizabeth"",-""Mary""],-[""George"",-""Mary""],-[""Charles"",-""William""],-[""William"",-""Mary"")
Output: 
{
    ""Henry"": [],
    ""Elizabeth"": [],
    ""George"": [],
    ""Mary"": [""Elizabeth"", ""George"", ""Henry"", ""William""],
    ""Charles"": [],
    ""William"": [""Charles""]
}

EDGE CASE
Input: 
    names = [""Alice"", ""Bob"", ""Catherine"", ""Diana"", ""Edward""]
    relationships = [""Alice"", ""Bob""], [""Alice"", ""Catherine""], [""Bob"", ""Diana""], [""Catherine"", ""Diana""], [""Diana"", ""Edward""](/codepath/compsci_guides/wiki/""Alice"",-""Bob""],-[""Alice"",-""Catherine""],-[""Bob"",-""Diana""],-[""Catherine"",-""Diana""],-[""Diana"",-""Edward"")
Output:
{
    ""Alice"": [],
    ""Bob"": [""Alice""],
    ""Catherine"": [""Alice""],
    ""Diana"": [""Alice"", ""Bob"", ""Catherine""],
    ""Edward"": [""Alice"", ""Bob"", ""Catherine"", ""Diana""]
}

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Lineage (Ancestor relationships) problems, we want to consider the following approaches:

  • Topological Sort: Since we are given a DAG, topological sort will help us process ancestors in the correct order (elders first).
  • Graph Traversal: We can traverse the graph using either BFS or DFS to propagate ancestor information.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use topological sorting (Kahn's Algorithm) to process the members in the correct order. For each member, propagate its ancestors to its descendants and keep them sorted alphabetically.

1) Initialize a graph to represent family relationships and an in-degree map for each member.
2) Traverse the relationships to build the graph and update the in-degree map.
3) Perform topological sorting using Kahn’s Algorithm:
    a) Start with all members who have no ancestors (in-degree = 0).
    b) Process each member in the queue, and for each descendant, propagate the ancestor information.
    c) Sort the ancestors alphabetically for each descendant.
4) Return the lineage dictionary with all members and their sorted ancestors.

⚠️ Common Mistakes

  • Forgetting to sort the ancestors alphabetically after each update.
  • Not handling edge cases where there are no relationships (return an empty list for each member).

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

def find_kingdom_lineage(names, relationships):
    # Step 1: Initialize graph and in-degree map
    graph = {name: [] for name in names}
    in_degree = {name: 0 for name in names}
    lineage = {name: [] for name in names}

    # Step 2: Build the graph and update in-degrees
    for elder, descendant in relationships:
        graph[elder].append(descendant)
        in_degree[descendant] += 1
    
    # Step 3: Topological sort using Kahn's Algorithm
    queue = deque([name for name in names if in_degree[name] == 0])
    
    while queue:
        elder = queue.popleft()
        
        # Propagate the lineage to all descendants
        for descendant in graph[elder]:
            # Add elder to the descendant's lineage
            lineage[descendant].extend(lineage[elder])
            lineage[descendant].append(elder)
            lineage[descendant] = sorted(lineage[descendant])  # Sort alphabetically
            
            # Reduce in-degree and if it becomes 0, add to queue
            in_degree[descendant] -= 1
            if in_degree[descendant] == 0:
                queue.append(descendant)

    return lineage

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

Example 1:

  • Input: names = [""Henry"", ""Elizabeth"", ""George"", ""Mary"", ""Charles"", ""William""] relationships = [""Henry"", ""Mary""], [""Elizabeth"", ""Mary""], [""George"", ""Mary""], [""Charles"", ""William""], ""William"", ""Mary""
  • Expected Output:
{
    ""Henry"": [],
    ""Elizabeth"": [],
    ""George"": [],
    ""Mary"": [""Elizabeth"", ""George"", ""Henry"", ""William""],
    ""Charles"": [],
    ""William"": [""Charles""]
}
  • Watchlist:
    • Ensure the ancestors are propagated correctly through the topological sort.
    • Confirm that the ancestors are sorted alphabetically.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume n is the number of names and m is the number of relationships.

  • Time Complexity: O(m + n log n) because we process each relationship once and sort the ancestors alphabetically.
  • Space Complexity: O(m + n) to store the graph, in-degree map, and lineage for each member.