Skip to main content

Juspay

Juspay OA-8 2023

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.