Juspay Tree of Space Hackathon part B SOLUTION # Problem Overview Tree of Space is a problem involving the management of locks within a tree structure under specific constraints. The challenge is to implement a locking system where: Each node can be locked by a user only if none of its ancestors or descendants are locked. Locking and unlocking operations must be thread-safe. The solution must efficiently handle concurrent operations. # Solution **1. Minimize Write Operations in the lock Function** As we know, write-read and write-write conflicts can cause issues in concurrent systems. To avoid these, we aim to minimize write operations. In the lock function, we first check if any ancestor or descendant node is already locked. These are read operations only. If the check passes, we perform a single write operation to update the isLocked variable. **2. Exploiting Independent Sibling Threads** Observe that we can allow threads to proceed independently if they are locking sibling nodes. Consider this: ![WhatsApp Image 2025-05-23 at 16.32.25_0bf09157.jpg](https://assets.leetcode.com/users/images/a8f3d37b-a390-40ee-aa32-86f17241652a_1747998175.912878.jpeg) Conflict occurs when trying to lock nodes D and B if they are on the same path (could result in write-read conflict). No conflict when locking sibling nodes like D and F. Only read-read operations occur on their common ancestor node A. To manage this efficiently, we can implement a custom thread scheduling algorithm in the main function. **3. Custom Thread Scheduling Algorithm** We maintain a map of string pairs to booleans to check if two nodes are siblings. For example, "india|china" → true indicates that India and China are siblings. This structure is built using a buildSiblingsStructure function during preprocessing. Custom Thread Scheduling Logic Suppose all requests are for the lock function. We place all the requests in a queue. The scheduler processes queries in a loop, ensuring safe concurrent execution: Step 1: Fetch the Next Query ``` Query curQuery = queryQueue.poll(); // Get the oldest pending query String curName = curQuery.name; // Node this query wants to access ``` Step 2: Check for Conflicts with Active Threads ``` boolean canRun = true; for (Pair active : restOfTheActiveThread) { Thread alreadyCalled = active.th; String alreadyCalledThreadName = active.name; if (alreadyCalled.isAlive() && !lockingTree.areSiblings.getOrDefault( alreadyCalledThreadName + "|" + curName, false)) { canRun = false; // Conflict found! break; } } ``` If an active thread exists and its node is not a sibling of the current query’s node, we have a conflict. Step 3: Execute or Requeue ``` If canRun == true //(No Conflict): ``` Create a new thread to execute the query: ``` Thread tr = new Thread(() -> { boolean result = lockingTree.lock(curName, uid); System.out.println("From multiThreading: -> " + curName + " " + result); }); ``` Add the thread to restOfTheActiveThread structure. Start the thread with tr.start(). ``` If canRun == false // (Conflict Detected): ``` Re-queue the query: ``` queryQueue.add(curQuery); // Try again later ``` Step 4: Repeat Until All Queries Are Processed The loop continues until the queryQueue is empty. # **Thread Safe Code** ``` import java.util.*; class Pair{ public Thread th; public String name; Pair(Thread t,String n){ this.th=t; this.name=n; } } class Query { int op; String name; int uid; Query(int op,String name,int uid) { this.op=op; this.name=name; this.uid=uid; } } class Node { String name; Node parent; Set childs = new HashSet<>(); volatile boolean isLocked = false; // This field must be volatile to ensure visibility across threads Node(String name, Node parent) { this.name = name; this.parent = parent; } } class LockingTree { Node root; Map nodeMap = new HashMap<>(); Map areSibling = new HashMap<>(); LockingTree(Listnames,int m) { int n=names.size(); root=new Node(names.get(0), null); nodeMap.put(names.get(0), root); Queueq=new LinkedList<>(); q.add(root); int idx = 1; while (!q.isEmpty()&&idxnames) { List nodeVec=new ArrayList<>(); for (String name: names) { nodeVec.add(nodeMap.get(name)); } for (int i=0;i it: areSibling.entrySet()){ // System.out.println(it.getKey()+" "+it.getValue()); // } } private boolean areSiblings(Node a,Node b) { SetquickSet = new HashSet<>(); Node temp = a; while (temp!=null) { quickSet.add(temp.name); temp=temp.parent; } temp=b; while (temp!=null) { if (quickSet.contains(temp.name)) { //no matter if they have common ancestor //but they should not belong to same path return !temp.name.equals(a.name) && !temp.name.equals(b.name); } temp=temp.parent; } return false; } public boolean lock(String nodeName,int uid) { // Aim to minimize write operations, even at the cost of time complexity Node node=nodeMap.get(nodeName); Queue q= new LinkedList<>(); q.add(node); // Check descendants while (!q.isEmpty()) { Node cur=q.poll(); if (cur.isLocked)return false; q.addAll(cur.childs); } //O n // Check ancestors for (Node p=node.parent;p!=null;p=p.parent) { if (p.isLocked)return false; } // O logn node.isLocked=true; //single write operation //node.lockedBy=uid; return true; // without using ancestor count // No mutex :) } } public class Attempt3 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(),m=sc.nextInt(),q=sc.nextInt(); Listnames=new ArrayList<>(); for (int i=0;iqueryQueue=new LinkedList<>(); SetrestOfTheActiveThread=new HashSet<>(); for (int i = 0; i < q; i++) { int op = sc.nextInt(); String name=sc.next(); int uid=sc.nextInt(); queryQueue.add(new Query(op,name,uid)); } // Custom Thread Scheduling Algorithm // Key idea: allow a thread to call the lock function only if all other alive threads are its siblings. // Otherwise, the query must wait. while (!queryQueue.isEmpty()) { Query curQuery=queryQueue.poll(); String curName=curQuery.name; boolean canRun=true; for (Pair active:restOfTheActiveThread) { Thread alreadyCalled = active.th; String alreadyCalledThreadName = active.name; if (alreadyCalled.isAlive()&&!lockingTree.areSibling.getOrDefault(alreadyCalledThreadName + "|" + curName, false)) { canRun=false; break; } //if thread is terminated , we can also remove it from restOfTheActiveThread set } if (canRun) { //Yehh! there is no conflict, we can allocate the thread int uid=curQuery.uid; Thread tr=new Thread(()->{ boolean result=lockingTree.lock(curName, uid); System.out.println("From multiThreading: -> " +curName+" "+result); }); restOfTheActiveThread.add(new Pair(tr, curName)); tr.start(); } else { queryQueue.add(curQuery); //opps this query has to wait } } } } ``` TestCase: 7 2 5 A B C D E F G 1 B 1 1 E 2 1 F 3 1 A 4 1 G 5 And that’s the setup! Enjoy!