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
- lock(X, uid)
2 unlock(X, uid)
- upgradelock(x, id)
where X the name of a node in the Tee that would be unique and uid is the men who access the node
Here are the definitions for the APIs:
Lock(X, uid)
Lock takes an exclusive access on the subtree rooted
Once lock(X, uid) succeeds, then
• lock(A, anyuser) should fail, where A is a descendent of X
• lock(B. anyuset) should fail where X is a descendent of B
Lock operation cannot be performed on a node which is already locked
Unlock(X, uid)
Unlock reverts what was done by the Lock operation. It can only be called on same
UpgradeLock(X, uid)
It helps the user uid upgrade their lock to an ancestor node.
It is only possible if any ancestor node is only locked by the same user uid.
Upgrade should fall if there is any node that is locked by some other uid Y below.
Sample Input 1
7
2
Asia
Africa
China
India
SouthAfrica
Egypt
view More
Explanation
Query 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 descenda
Query 4 2 India 9 This should fall as the India is now not locked
Query 5 2 Asia 9 This should be success as Asia was earlier (refer Query 3) locked by user 9
My Sample Code :
public class aryTree {
public class TreeNode {
int val;
boolean locked = false;
TreeNode parent;
Vector child;
int lockedDescendent = 0;
}
static TreeNode newNode(int key) {
TreeNode temp = new TreeNode();
temp.val = key;
temp.child = new Vector<TreeNode>();
return temp;
}
public static boolean isLocked(TreeNode node) {
return node.locked;
}
public static boolean lock(TreeNode node) {
if (isLocked(node)) {
return false;
}
if (!canLockOrUnlock(node)) {
return false;
}
node.locked = true;
TreeNode parentNode = node.parent;
while (parentNode != null) {
parentNode.lockedDescendent += 1;
parentNode = parentNode.parent;
}
return true;
}
public boolean unLock(TreeNode node) {
//in unlock we are only writing not reading
if (!isLocked(node)) {
return false;
}
node.locked = false;
TreeNode parentNode = new TreeNode();
while (parentNode != null) {
parentNode.lockeddescendent -= 1;
parentNode = parentNode.parent;
}
return true;
}
public boolean canLockOrUnlock(TreeNode node) {
if (node.lockedDescendent > 0) {
return false;
}
TreeNode parentNode = new TreeNode();
while (parentNode != null) {
if (isLocked(parentNode)) {
return false;
}
parentNode = parentNode.parent;
}
return true;
}
}
}
How can we approach on making such a problem thread safe ?