Katkat
Back

Design a Workspace Resource Manager

Goldman SachsSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to design a tree-based hierarchical resource management system and implement efficient operations for path-based access, relocation, and cycle detection.

Workspace Resource Manager

You are tasked with designing a memory-resident Workspace Resource Manager. The system manages resources (like files or services) organized in a hierarchical tree structure. Each node has a unique identifier (string) and a parent pointer.

Your implementation should support the following operations:

  1. add_resource(resource_id, parent_id): Adds a new resource under the specified parent. If parent_id is null, the resource is added at the root level.
  2. get_path(resource_id): Returns a string representing the full path from the root to the node (e.g., "/root/child/subchild").
  3. move_resource(resource_id, new_parent_id): Moves an existing resource and its entire subtree to a new parent. You must prevent creating cycles (e.g., moving a parent into its own child).

Constraints

  • resource_id and parent_id are non-empty strings.
  • resource_id is globally unique.
  • The number of resources can be up to 10,000.
  • Assume add_resource is called only for new IDs.

Example

# manager = WorkspaceManager()
# manager.add_resource("root", None)
# manager.add_resource("A", "root")
# manager.add_resource("B", "A")
# manager.get_path("B") -> "/root/A/B"
# manager.move_resource("A", "B") -> Raise Error (Cycle detected)

Implementation Requirements

Provide a class structure that includes the fields necessary for efficient tree traversal and parent lookups. Consider how move_resource can validate the move without needing to traverse the entire tree repeatedly.

Hints

Hint 1

Use a dictionary to map each resource_id to its node object for O(1) access to parent pointers.

Hint 2

To validate a move, check if the new parent is currently a descendant of the resource being moved.

Hint 3

For the path string, consider caching or building the path upwards to the root, then reversing the result list.

Follow-up questions

  • How would you modify your design if multiple parents were allowed for a single resource (DAG instead of a tree)?
  • What concurrency issues might arise if multiple threads attempt to update the tree structure simultaneously, and how would you resolve them?
  • If you needed to serialize this structure to a database, what schema would you use to efficiently reconstruct the hierarchy?