Juspay OA 2023 - Locking the M-Ary Tree

Problem Description:

You are given a world map represented as an M-ary tree. Each node in the tree represents a location with a unique name. There are three types of operations to be performed on this tree:

1. lock(X, uid): Locks the subtree rooted at node X by user uid.
2. unlock(X, uid): Unlocks the node X if it is currently locked by the user uid.
3. upgradeLock(X, uid): Upgrades the lock on node X by the user uid if all its descendants are locked by the same user.

Definitions for Operations:

Lock(x, uid):

• Lock takes exclusive access to the subtree rooted at node X.
• Once lock(x, uid) is successful:
  • Any lock attempt on a descendant node A of X by any user should fail.
  • Any lock attempt on an ancestor node B of X by any user should fail.
  • A node cannot be locked if it is already locked by any user.

Unlock(x, uid):

• Unlock reverts the lock on node X, but only if the user uid who locked it is the same user calling the unlock.
• The unlock is successful only if it is the same user who had locked the node before.

UpgradeLock(x, uid):

• Upgrades the lock on an ancestor node X if all its descendants are locked by the same user uid.
• The operation fails if there is any descendant of node X locked by a different user.
• Once the upgrade is successful, node X will be locked, and any lock on a descendant or ancestor will fail, following the rules of the lock operation.

Input Format:

• The first line contains the number of nodes ( N ) in the tree.
• The second line contains the number of children per node ( m ) (M-ary tree).
• The third line contains the number of queries ( Q ).
• The next ( N ) lines contain the unique node names in the M-ary tree.
• The next ( Q ) lines contain queries in the format: OperationType NodeName UserId.

Query Operation Types:

• 1 NodeName UserId: Represents a lock operation.
• 2 NodeName UserId: Represents an unlock operation.
• 3 NodeName UserId: Represents an upgradeLock operation.

Output:

For each query, return True if the operation was successful, and False otherwise.

Example Input:

7
2
3
World
Asia
Africa
China
India
SouthAfrica
Egypt
1 China 9
2 India 9
3 Asia 9

Example Output:

True
False
True

Explanation:

• The input represents a 2-ary tree with 7 nodes. The structure of the tree is as follows:

           World
        /        \
     Asia       Africa
    /    \       /    \
 China  India SouthAfrica Egypt

1. lock(China, 9): This operation succeeds because no node in the subtree rooted at China or its ancestors are locked. Thus, the output is True.
2. unlock(India, 9): This operation fails because India was never locked, so the output is False.
3. upgradeLock(Asia, 9): This operation succeeds because the only locked descendant is China, and it is locked by user 9. The output is True.

Constraints:

• 1 < N < 5*10^5 (the number of nodes in the tree)
• 1 < m < 30 (the tree is an M-ary tree)
• 1 < Q < 5 *10^5 (the number of queries)
• 1 < length of NodeName < 20

Here’s a revised version of your requirements with an emphasis on clarity and conciseness:

Locking System Operations:

1. Lock Operation:
   • Time Complexity: O(logmN)
   • If a node is already locked, the operation fails.
2. Unlock Operation:
   • Time Complexity: O(logmN)
3. Upgrade Lock Operation:
   • Time Complexity: O(numberOfLockedNodes*logmN)
   • This operation succeeds only if:
     • The target node has no locked descendants.
     • The node is not already locked.
   • Once an upgrade lock operation on node X (by uid) succeeds, it is treated as if X is locked by uid. Consequently:
     • Any subsequent lock attempt on X by another user
       (e.g., Lock(A/B, anyuser)) fails.
     • Unlocking X (Unlock(X, uid)) remains valid.