Question: Juspay | 21st October | Online Assessments | Locking the tree of space
2
Entering edit mode

# Question 1

## Locking the tree of space

You have a world map represented as an M-Ary tree (sample tree below)

You need to define three operations on it

1. lock(X, uid)

2. unlock(x, uid)

where X the name of a node in the tree (that would be unique) and uid is the user who is performing the operation.

Here are the definitions for the Operations:

Lock(x, uid)

Lock takes an exclusive access on the subtree rooted at X. It is formally defined like this: Once lock(x, uid) succeeds, then:

• lock(A, anyUserid) should fail (returns false), where A is a descendent of X,
• lock(B, anyUserld) should fail (returns false), where X is a descendent of B
• Lock operation cannot be performed on a node which is already locked i.e. lock(x, anyUserld) should fail (returns false).

Unlock(X, uid)

• Unlock reverts what was done by the lock operation. It can only be called on same node on which user uid had called a Lock on before. Returns true if it is successful.

• It helps the user uid upgrade their lock to an ancestor node. It is only possible if the node X already has locked descendants and all of them are only locked by the same user uid. 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. UpgradeLock call shouldn't violate the consistency model that Lock/Unlock function requires.

Notes

1) The number of nodes in the tree N is very large. So, optimize the time complexity for the above algorithms

2) 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 m in m-ary Tree).
• The third line contains number of queries (Q).
• Next N lines contains the NodeName (string) in the m-Ary Tree.
• Next Q lines contains queries which are in format: Operation Type NodeName Userld
• Operation Type -

``````1 for Lock

2 for unlock

``````
• 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 9

With the above input you represents a 2-ary tree with 7 nodes as follows:

``````                                                        World
/              \
Asia                 Africa
/      \                 /      \
China    India          South Africa   Egypt
``````

1) Here '1 China 3' indicates the following 'Operation Type NodeName Userld'

2) The tree is always fully balanced

3) 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

4) Optimize the time complexity

• Lock - O(logmN)
• Unlock - O(logmN)
• UpgradeLock - O(numberOfLockedNodes * logmN)

5) Lock operation on already locked node should fail.

6) 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.

7) Upgrade lock operation on a node having no locked descendants should fail and upgrade lock on already locked node should also fail.

6
Entering edit mode

``````import java.util.*;
public class Main {
static class TreeNode{
String name;
boolean isLocked;
int id;
TreeNode parent;
int anc_locked;
int des_locked;
ArrayList<TreeNode> child= new ArrayList<>();
TreeNode(String name, TreeNode parent){
this.name=name;
this.parent=parent;
}
}
public static void main(String[] args) {
int n = 3;
int m = 2;

String[] nodes = new String[]{"World","China","India"};

String[] queries = new String[]{"3 India 9", "1 World 9"};

Map<String, TreeNode> map= new HashMap<>();
TreeNode root= new TreeNode(nodes[0],null);
map.put(nodes[0],root);

int ind=1;

while(queue.size()>0 && ind<n){
int size=queue.size();
while(size-->0){
TreeNode removedNode=queue.remove();
for(int i=1; i<=m && ind<n ; i++){
TreeNode node= new TreeNode(nodes[ind],removedNode);
map.put(nodes[ind],node);
ind++;
}
}
}

for(String query: queries){
String parts[]= query.split(" ");
if(parts[0].equals("1"))
else if(parts[0].equals("2"))
else
}
}

static boolean lock(TreeNode node, int id){
if(node.isLocked)
return false;
if(node.anc_locked > 0 || node.des_locked > 0)
return false;
TreeNode cur= node.parent;
while(cur!=null){
cur.des_locked+=1;
cur=cur.parent;
}
informDescendant(node, 1);
node.isLocked= true;
node.id = id;
return true;
}
static void informDescendant(TreeNode node, int val){
if(node == null) return;
node.anc_locked+=val;
for(TreeNode des: node.child)
informDescendant(des, val);
}
static boolean unlock(TreeNode node, int id){
if(!node.isLocked || node.id!=id)
return false;
TreeNode cur= node.parent;
while(cur!=null){
cur.des_locked-=1;
cur=cur.parent;
}
informDescendant(node, -1);
node.isLocked= false;
node.id=0;
return true;
}

static boolean upgrade(TreeNode node, int id){
if(node.isLocked || node.anc_locked>0 || node.des_locked==0)
return false;
ArrayList<TreeNode> child= new ArrayList<>();
boolean res = getAllChild(node, child, id);
if(!res) return false;
informDescendant(node, 1);
for(TreeNode k: child){
unlock(k ,id);
}
node.isLocked = true;
node.id= id;
return true;
}

static boolean getAllChild(TreeNode node, ArrayList<TreeNode> child, int id){
if(node == null)
return true;
if(node.isLocked){
if(node.id != id) return false;
}
if(node.des_locked == 0) return true;
for(TreeNode k: node.child){
boolean res= getAllChild(k, child, id);
if(!res) return false;
}
return true;
}
}``````

Entering edit mode
2
Can you also provide the thread-safe code fro this question?
Ankit
• 60
Entering edit mode
0

Hello, Can you please provide the Thread safe code for this question. Also Kindly include code for reducing Time complexity and Space complexity.

0
Entering edit mode

Hello,