Let’s say you are running the lock/unlock in a multi core machine. Now you want to let multiple threads to run lock() As we saw in part A, locking a node has multiple validations inside. Will doing lock on two nodes cause a race condition. If yes, how will you solve it. In short,
how do make the lock() function thread safe? - Multiple threads running it simultaneously shouldn’t not affect the correctness. -Try to make the critical sections more granular.
ie. don’t create any big atomic/synchronised blocks that will make parallelism suffer.
Consider each operation is atomic.
Implement thread safe concurrent lock method without using any atomic method, mutex, semaphores, synchronized keywork
dont use any inbuilt threading show logicwrute the code ahand wruteetn in as in interview
"""

import sys

class Node:
def init(self, val):
self.val = val
self.uid = None
self.parent = None
self.child = []
self.isLocked = False
self.lockedDescendantCount = 0

class Tree:
def init(self, m, n, name_list):
self.node_list = []
self.node_map = {}
self.locked_nodes = set()
self.time = 0
self.in_time = {}
self.out_time = {}

for name in name_list:
node = Node(name)
self.node_list.append(node)
self.node_map[name] = node

for i in range(n):
for j in range(m):
child_index = m * i + j + 1
if child_index < n:
self.node_list[i].child.append(self.node_list[child_index])
self.node_list[child_index].parent = self.node_list[i]

self.root = self.node_list[0]

self.dfs(self.root)
def dfs(self, node):
self.time += 1
self.in_time[node] = self.time
for child in node.child:
self.dfs(child)
self.time += 1
self.out_time[node] = self.time

def is_descendant(self, ancestor, node):
"""Check if node is a descendant of ancestor using in-time and out-time."""
return self.in_time[ancestor] < self.in_time[node] and self.out_time[node] < self.out_time[ancestor]

def lock(self, node, uid):
if node.isLocked:
return False

if self.isAncestorLocked(node):
return False

if node.lockedDescendantCount > 0:
return False

Lock the node
node.isLocked = True
node.uid = uid
self.locked_nodes.add(node) # Add node to locked nodes set

Update the lockedDescendantCount for ancestors
parent = node.parent
while parent:
parent.lockedDescendantCount += 1
parent = parent.parent

return True
def unlock(self, node, uid):
if not node.isLocked or node.uid != uid:
return False

Unlock the node
node.isLocked = False
node.uid = None
self.locked_nodes.remove(node) # Remove node from locked nodes set

Update the lockedDescendantCount for ancestors
parent = node.parent
while parent:
parent.lockedDescendantCount -= 1
parent = parent.parent

return True
def upgrade(self, node, uid):
if node.isLocked:
return False

if self.isAncestorLocked(node):
return False

if node.lockedDescendantCount == 0:
return False

Collect all locked descendants using precomputed locked nodes
locked_descendants = []
for locked_node in self.locked_nodes:
if self.is_descendant(node, locked_node) and locked_node.uid == uid:
locked_descendants.append(locked_node)
elif self.is_descendant(node, locked_node) and locked_node.uid != uid:
return False # Locked by a different user

Unlock all locked descendants
for descendant in locked_descendants:
descendant.isLocked = False
descendant.uid = None
self.locked_nodes.remove(descendant) # Remove from locked nodes set


# Update the lockedDescendantCount for ancestors
parent = descendant.parent
while parent:
    parent.lockedDescendantCount -= 1
    parent = parent.parent
Lock the current node
node.isLocked = True
node.uid = uid
self.locked_nodes.add(node) # Add node to locked nodes set

Update the lockedDescendantCount for ancestors
parent = node.parent
while parent:
parent.lockedDescendantCount += 1
parent = parent.parent

return True
def isAncestorLocked(self, node):
"""Check if any of the ancestors of the given node are locked."""
curr = node.parent
while curr:
if curr.isLocked:
return True
curr = curr.parent
return False

def process_queries(self, queries):
results = []
for query in queries:
operation, node_name, uid = query.strip().split()
uid = int(uid)
node = self.node_map[node_name]
if operation == "1":
result = self.lock(node, uid)
elif operation == "2":
result = self.unlock(node, uid)
elif operation == "3":
result = self.upgrade(node, uid)
else:
result = False # Invalid operation
results.append('true' if result else 'false')
return results
def main():
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
q = int(sys.stdin.readline())
name_list = []
queries = []

for _ in range(n):
name_list.append(sys.stdin.readline().strip())

for _ in range(q):
queries.append(sys.stdin.readline().strip())

tree = Tree(m, n, name_list)
results = tree.process_queries(queries)
for res in results:
print(res)
main()

"""
explain show me so that i can learn and so it

ignore about Gil and stuff in interview imporatnt ot demonstrate coding and logic right so make it good

solve without using mutex/semaphore locks and only concentrate on the lock method