what would beexpected output of this tc "description": "Test Case 10: Maximum Nodes and…
- User
what would beexpected output of this tc "description": "Test Case 10: Maximum Nodes and Upgrade Lock", "input": """31 2 16 Root A B C D E F G H I J K L M N O P Q R S T U V W X Y Z AA AB AC AD 1 Z 1 1 AA 1 1 AB 1 1 AC 1 1 AD 1 3 Root 1 1 E 2 1 F 2 1 G 2 3 Root 2
for this problem
Locking The Tree of Space
You have a world map represented as an M-Ary tree (sample tree below)
In graph theory, an m-ary tree (for nonnegative integers m) (also known as n-ary, k-ary or k-way tree) is an arborescence (or an ordered tree) in which each node has no more than m children. A binary tree is the special case where m = 2, and a ternary tree is another case with m = 3 that limits its children to three.
In graph theory, an arborescence is a directed graph in which, for a vertex u (called the root) and any other vertex v, there is exactly one directed path from u to v. A graph is a collection of vertices (also known as nodes) and edges that connect these vertices. A tree is a special type of graph that is connected and acyclic, meaning that there are no cycles in the graph. In a tree, there is a unique path between any two vertices, and there is a single vertex called the root that is used as the starting point for traversing the tree.
[image: Sample Tree]
You need to define three operations on it:
1. lock(X, uid) 2. unlock(X, uid) 3. upgradeLock(X, uid)where
Xthe name of a node in the tree (that would be unique) anduidis the user who is performing the operation.
Input format: x is country name (string) and uid is user number (number).Here are the definitions for the operations:
lock(x, uid)
Lock takes an exclusive access on the subtree rooted atX. It is formally defined like this: Oncelock(x, uid)succeeds, then:
lock(A, anyUserid)should fail (returns false), whereAis a descendent ofX,lock(B, anyUserld)should fail (returns false), whereXis a descendent ofB, Lock operation cannot be performed on a node which is already locked i.e.lock(x, anyUserld)should fail (returns false).
Exclusive access means that only one user can lock a node and its descendants at a time, and no other user can lock any node that is related to the locked node by ancestry or descent. This ensures that there is no conflict or interference between different users who want to perform operations on the tree.unlock(X, uid)
Unlock reverts what was done by the lock operation. It can only be called on same node on which useruidhad called a Lock on before. Returns true if it is successful.upgradeLock(x, uid)
It helps the useruidupgrade their lock to an ancestor node. It is only possible if the nodeXalready has locked descendants and all of them are only locked by the same useruid. Upgrade should fail if there is any node which is descendant of X that is locked by a different user. Successful Upgrade will 'lock' the node.upgradeLockcall shouldn't violate the consistency model that Lock/Unlock function requires.Notes
- The number of nodes in the tree
Nis very large. So, optimize the time complexity for the above algorithms. - The below section contains the input format.
-
The first line contains the number of Nodes in the tree (
N). -
The second line contains number of children per node (value
min m-ary Tree). -
The third line contains number of queries (
Q). -
Next
Nlines contains theNodeName(string) in the m-Ary Tree. -
Next
Qlines contains queries which are in format:Operation TypeNodeNameUserld -
Operation Type
1for lock
2for unlock
3for upgradeLock -
NodeName- Name of any node (unique) in m-Ary Tree. -
Userld- Integer value representing a unique user.
-
Example input
7 2 3 World Asia Africa China India South Africa Egypt 1 China 9 2 India 9 3 Asia 9With the above input you represent a 2-ary tree with 7 nodes as follows:
World / \ Asia Africa / \ / \ China India South Africa EgyptAdditional Notes
- Here
1 China 3indicates the following 'Operation TypeNodeNameUserld'. - The tree is always fully balanced.
- Constraints on the inputs are as follows:
1 < N < 5 * 10^5
1 < m < 30
1 < Q <5 * 10^5
1 < length of NodeName < 20 - Optimize the time complexity:
- Lock - O(logmN)
- Unlock - O(logmN)
- UpgradeLock - O(numberOfLockedNodes * logmN)
- Lock operation on already locked node should fail.
- Once Upgrade lock(X, uid) succeeds on X. It is equivalent to X being locked by uid. So, Lock(A/B, anyuser) should fail as per the definition of Lock and Unlock(X, uid) should also work.
- Upgrade lock operation on a node having no locked descendants should fail and upgrade lock on already locked node should also fail.
Example input
7 2 5 World Asia Africa China India SouthAfrica Egypt 1 China 9 1 India 9 3 Asia 9 2 India 9 2 Asia 9Example input
true true true false trueQuery 1:
1 China 9⇒ This operation is success as initially China is unlocked.Query 2:
1 India 9⇒ This should be success as none of ancestors and descendants of India are locked.Query 3:
3 Asia 9⇒ This also should be success as upgrade operation is done by same user who has locked descendants.Query 4:
2 India 9⇒ This should fail as the India is now not lockedQuery 5:
2 Asia 9⇒ This should be success as Asia was earlier (refer Query 3) locked by user 9. understand and go to the deoth and give me a resultant output - The number of nodes in the tree
- Assistant
The expected output based on the provided test case is:
true true true true true true false false false falseHere's how each query yields its result:
- Lock Z by user 1 (
1 Z 1): Success, as Z is unlocked and no ancestors or descendants are locked. - Lock AA by user 1 (
1 AA 1): Success, similar to above. - Lock AB by user 1 (
1 AB 1): Success, similar to above. - Lock AC by user 1 (
1 AC 1): Success, similar to above. - Lock AD by user 1 (
1 AD 1): Success, similar to above. - Upgrade lock on Root by user 1 (
3 Root 1): Success, Root is unlocked, has locked descendants (Z, AA, AB, AC, AD) all locked by user 1. After upgrade, Root is locked by user 1, and all its descendants are unlocked. - Lock E by user 2 (
1 E 2): Fail, cannot lock because ancestor Root is locked by user 1. - Lock F by user 2 (
1 F 2): Fail, same reason as above. - Lock G by user 2 (
1 G 2): Fail, same reason as above. - Upgrade lock on Root by user 2 (
3 Root 2): Fail, cannot upgrade because Root is already locked by user 1.
Overall, user 1 successfully locks several nodes and upgrades to lock the Root, while user 2 cannot lock or upgrade due to the lock held by user 1.
- Lock Z by user 1 (