hye i have written this code and interviewr asked me to implemtn cas and set and test threadsafe to the LOCK method in this code, as it is for iterview dointit use modules threading or any and also ignore the GIL as it is for showing logic and interview purposed
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.
"""
class Node:
def init(self, val):
self.val = val
self.uid = None
self.parent = None
self.children = []
self.locked_descendant_count = 0
self.isLocked = False

class M_Arr_Tree:
def init(self, n, m, name_list):
self.node_list = []
self.node_map = {}

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_idx = m * i + j + 1
if child_idx < n:
self.node_list[i].children.append(self.node_list[child_idx])
self.node_list[child_idx].parent = self.node_list[i]
def _update_lock_count_upwards(self, node, delta):
current = node.parent
while current:
current.locked_descendant_count += delta
current = current.parent

def Lock(self, node, uid):
if node.isLocked or node.locked_descendant_count > 0:
return 'false'

Check if any ancestors are locked
current = node.parent
while current:
if current.isLocked:
return 'false'
current = current.parent

node.isLocked = True
node.uid = uid
self._update_lock_count_upwards(node, 1)
return 'true'
def Unlock(self, node, uid):
if not node.isLocked or node.uid != uid:
return 'false'

node.isLocked = False
node.uid = None
self._update_lock_count_upwards(node, -1)
return 'true'
def Upgrade(self, node, uid):
if node.isLocked or node.locked_descendant_count == 0:
return 'false'

Check if any ancestors are locked
current = node.parent
while current:
if current.isLocked:
return 'false'
current = current.parent

Collect all locked descendants
locked_nodes = []
stack = [node]
while stack:
current = stack.pop()
if current.isLocked:
locked_nodes.append(current)
for child in current.children:
stack.append(child)

if not locked_nodes:
return 'false'

Ensure all locked descendants are locked by the same uid
for ld in locked_nodes:
if ld.uid != uid:
return 'false'

Unlock all descendants
for ld in locked_nodes:
ld.isLocked = False
ld.uid = None
self._update_lock_count_upwards(ld, -1)

Lock the current node
node.isLocked = True
node.uid = uid
self._update_lock_count_upwards(node, 1)

return 'true'
def Process(self, queries):
res = []
for q in queries:
parts = q.strip().split()
if len(parts) != 3:
res.append('false')
continue
ops, node_name, uid = parts
uid = int(uid)
node = self.node_map.get(node_name, None)
if not node:
res.append('false')
continue
if ops == '1':
res.append(self.Lock(node, uid))
elif ops == '2':
res.append(self.Unlock(node, uid))
elif ops == '3':
res.append(self.Upgrade(node, uid))
else:
res.append('false')
return res
def main():
n = int(sys.stdin.readline().strip())
m = int(sys.stdin.readline().strip())
q = int(sys.stdin.readline().strip())

name_list = []
for _ in range(n):
name = sys.stdin.readline().strip()
name_list.append(name)

queries = []
for _ in range(q):
query = sys.stdin.readline().strip()
queries.append(query)

tree = M_Arr_Tree(n, m, name_list)
res = tree.Process(queries)
for r in res:
print(r)

if name == "main":
main()

"""
nwo the real question is
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.

give me two aproaches CAS and set and test