File System with Access Permissions (Topmost Accessible Nodes)

"""
File System with Access Permissions

Context: 
You have a hierarchical file system where design files and folders are organized in a 
tree structure (similar to Figma's file organization). Each file/folder has specific 
user access permissions.

Problem Statement:
Given a file system tree where each node (file/folder) has:
- A unique ID (string)
- Parent ID (None for root nodes)
- Type ("file" or "folder")
- Access permissions (list of user IDs who can access this item)
- Name (string)

Write a function that finds all the "topmost" accessible files/folders for a given user.

"Topmost" means: If a user has access to both a parent and its child, only return the parent.
In other words, return the highest-level nodes the user can access, excluding any 
descendants they can also access.

Example 1:
fileSystem = {
    "nodes": [
        {
            "id": "1",
            "parentId": None,
            "type": "folder",
            "name": "root",
            "accessibleBy": ["user1"]
        },
        {
            "id": "2",
            "parentId": "1",
            "type": "folder",
            "name": "folder1",
            "accessibleBy": ["user1", "user2"]
        },
        {
            "id": "3",
            "parentId": "2",
            "type": "file",
            "name": "file1",
            "accessibleBy": ["user2"]
        }
    ]
}

getTopAccessible("user1", fileSystem)
# Should return: ["1"]
# user1 has access to both "1" and "2", but "1" is the topmost

getTopAccessible("user2", fileSystem)
# Should return: ["2"]
# user2 has access to both "2" and "3", but "2" is the topmost
# user2 does NOT have access to "1", so "2" is their topmost

Example 2:
fileSystem = {
    "nodes": [
        {
            "id": "1",
            "parentId": None,
            "type": "folder",
            "name": "root",
            "accessibleBy": ["user1"]
        },
        {
            "id": "2",
            "parentId": "1",
            "type": "folder",
            "name": "folder1",
            "accessibleBy": ["user1", "user2"]
        },
        {
            "id": "3",
            "parentId": "2",
            "type": "file",
            "name": "file1",
            "accessibleBy": ["user2"]
        },
        {
            "id": "4",
            "parentId": "1",
            "type": "file",
            "name": "file2",
            "accessibleBy": ["user2"]
        }
    ]
}

getTopAccessible("user2", fileSystem)
# Should return: ["2", "4"]
# user2 can access "2", "3", and "4"
# "2" is topmost for the "2"→"3" branch
# "4" is topmost (and only node) for its branch
# Both "2" and "4" have the same parent "1", but user2 can't access "1"

Example 3:
fileSystem = {
    "nodes": [
        {
            "id": "1",
            "parentId": None,
            "type": "folder",
            "name": "root",
            "accessibleBy": []
        },
        {
            "id": "2",
            "parentId": "1",
            "type": "folder",
            "name": "folder1",
            "accessibleBy": ["user1"]
        },
        {
            "id": "3",
            "parentId": "1",
            "type": "folder",
            "name": "folder2",
            "accessibleBy": ["user1"]
        }
    ]
}

getTopAccessible("user1", fileSystem)
# Should return: ["2", "3"]
# user1 cannot access "1", but can access both "2" and "3"
# Both are topmost for their respective branches

Requirements:
1. Return list of node IDs that are topmost accessible for the user
2. Handle empty file systems
3. Handle users with no accessible nodes
4. Handle multiple root nodes (parentId = None)
5. Efficiently handle large file systems

Follow-up Questions:
1. If we move a file/folder to a different location in the tree, 
   how would this affect the "topmost accessible files" results?
   
2. What is the time complexity of your solution?

3. How would you optimize for repeated queries with the same user?

Test Cases to Handle:
1. User has no access to any nodes
2. User has access to all nodes
3. Multiple topmost nodes at different levels
4. Single long chain where user has access to middle node only
5. User has access to root (should return only root)
"""

def getTopAccessible(user, fileSystem):
    """
    Find all topmost accessible nodes for a given user.
    
    Args:
        user (str): User ID to check access for
        fileSystem (dict): Dictionary containing "nodes" list
        
    Returns:
        list[str]: List of node IDs that are topmost accessible
    """
    pass

# Write your implementation here


# Test cases
if __name__ == "__main__":
    # Test 1: Basic hierarchy
    fileSystem1 = {
        "nodes": [
            {"id": "1", "parentId": None, "type": "folder", "name": "root", "accessibleBy": ["user1"]},
            {"id": "2", "parentId": "1", "type": "folder", "name": "folder1", "accessibleBy": ["user1", "user2"]},
            {"id": "3", "parentId": "2", "type": "file", "name": "file1", "accessibleBy": ["user2"]}
        ]
    }
    
    print("Test 1:")
    print(getTopAccessible("user1", fileSystem1))  # Expected: ["1"]
    print(getTopAccessible("user2", fileSystem1))  # Expected: ["2"]
    
    # Test 2: Multiple topmost nodes
    fileSystem2 = {
        "nodes": [
            {"id": "1", "parentId": None, "type": "folder", "name": "root", "accessibleBy": ["user1"]},
            {"id": "2", "parentId": "1", "type": "folder", "name": "folder1", "accessibleBy": ["user1", "user2"]},
            {"id": "3", "parentId": "2", "type": "file", "name": "file1", "accessibleBy": ["user2"]},
            {"id": "4", "parentId": "1", "type": "file", "name": "file2", "accessibleBy": ["user2"]}
        ]
    }
    
    print("\nTest 2:")
    print(getTopAccessible("user2", fileSystem2))  # Expected: ["2", "4"]
    
    # Test 3: No access to root
    fileSystem3 = {
        "nodes": [
            {"id": "1", "parentId": None, "type": "folder", "name": "root", "accessibleBy": []},
            {"id": "2", "parentId": "1", "type": "folder", "name": "folder1", "accessibleBy": ["user1"]},
            {"id": "3", "parentId": "1", "type": "folder", "name": "folder2", "accessibleBy": ["user1"]}
        ]
    }
    
    print("\nTest 3:")
    print(getTopAccessible("user1", fileSystem3))  # Expected: ["2", "3"]