Join Us
Loading Similar Posts
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
lock(X, uid)
unlock(x, uid)
upgradeLock(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.
UpgradeLock(x, uid)
- 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 3 for upgradeLockNodeName - 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
Additional Notes:
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.
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);
Queue<TreeNode> queue = new LinkedList<>();
queue.add(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);
removedNode.child.add(node);
queue.add(node);
ind++;
}
}
}
boolean answer;
for(String query: queries){
String parts[]= query.split(" ");
if(parts[0].equals("1"))
answer=lock(map.get(parts[1]), Integer.parseInt(parts[2]));
else if(parts[0].equals("2"))
answer=unlock(map.get(parts[1]), Integer.parseInt(parts[2]));
else
answer=upgrade(map.get(parts[1]), Integer.parseInt(parts[2]));
System.out.println(answer);
}
}
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;
else child.add(node);
}
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
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> children = new ArrayList<>();
TreeNode(String name, TreeNode parent) {
this.name = name;
this.parent = parent;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// Reading the number of nodes, children per node, and number of queries
int N = sc.nextInt();
int M = sc.nextInt();
int Q = sc.nextInt();
sc.nextLine(); // Consume newline
// Reading the nodes
Map<String, TreeNode> map = new HashMap<>();
TreeNode root = new TreeNode(sc.nextLine(), null);
map.put(root.name, root);
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int ind = 1;
while (!queue.isEmpty() && ind < N) {
TreeNode parentNode = queue.poll();
for (int i = 0; i < M && ind < N; i++) {
TreeNode childNode = new TreeNode(sc.nextLine(), parentNode);
parentNode.children.add(childNode);
map.put(childNode.name, childNode);
queue.add(childNode);
ind++;
}
}
// Reading the queries and processing them
for (int i = 0; i < Q; i++) {
String[] parts = sc.nextLine().split(" ");
int operation = Integer.parseInt(parts[0]);
String nodeName = parts[1];
int userId = Integer.parseInt(parts[2]);
boolean result = false;
TreeNode node = map.get(nodeName);
if (operation == 1) {
result = lock(node, userId);
} else if (operation == 2) {
result = unlock(node, userId);
} else if (operation == 3) {
result = upgrade(node, userId);
}
System.out.println(result);
}
sc.close();
}
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 child : node.children) {
informDescendant(child, 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;
List<TreeNode> lockedDescendants = new ArrayList<>();
if (!collectLockedDescendants(node, lockedDescendants, id)) {
return false;
}
for (TreeNode descendant : lockedDescendants) {
unlock(descendant, id);
}
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 boolean collectLockedDescendants(TreeNode node, List<TreeNode> lockedDescendants, int id) {
if (node == null) return true;
if (node.isLocked) {
if (node.id != id) {
return false;
}
lockedDescendants.add(node);
}
for (TreeNode child : node.children) {
if (!collectLockedDescendants(child, lockedDescendants, id)) {
return false;
}
}
return true;
}
}
Hello, Can you please provide the Thread safe code for this question. Also Kindly include code for reducing Time complexity and Space complexity.
bro,can u please send the second part of the solution for hackathon part b and is the above executed and passed all testcas?