Find lowest ancestor in a list

Question

I have an array of objects storing users which have Manager as a key. I want to find lowest Manager for any of the two user ids in the list.The number of objects would be large, hence looking for an efficient solution. For Example, for below list,

[
  {
    "User": "John",
    "Manager": "Jake"
  },
  {
    "User": "Ben",
    "Manager": "John"
  },
  {
    "User": "Steve",
    "Manager": "John"
  }...
]

The common Manager for Ben & Steve would be John. However, for Ben & John would be Jake.

My initial thoughts include converting list to a tree & then finding the lowest common ancestor, but I suspect there probably is a better approach.

Answer 1

@ShihabRahman's now deleted answer is efficient but didn't quite work since users, not managers, were considered part of the path. Make managers part of the path instead and it would work:

users = [
    {"User": "John", "Manager": "Jake"},
    {"User": "Ben", "Manager": "John"},
    {"User": "Steve", "Manager": "John"}
]

def find_lowest_common_manager(users, user1, user2):
    # Build a dictionary mapping each user to their manager
    managers = {u['User']: u['Manager'] for u in users}

    # Create a set to store the path from user1 to their manager
    path = set()

    # Traverse up the manager hierarchy from user1 and store the path
    while user1 in managers:
        user1 = managers[user1]
        path.add(user1)

    # Traverse up the manager hierarchy from user2 until a common manager is found
    while user2 in managers:
        user2 = managers[user2]
        if user2 in path:
            # Found a common manager
            return user2

    # No common manager found
    return None

print(find_lowest_common_manager(users, 'Ben', 'Steve'))
print(find_lowest_common_manager(users, 'Ben', 'John'))

This outputs:

John
Jake

Demo: https://replit.com/@blhsing/ScientificHumongousGigabyte