Help me in this interview Problem #Threads, #Locking, #Unlocking

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)

  1. 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 ?

1 Like

error is came.main method is missing.please solve fastly

what’s the solution?