Dado un mapa mundial en forma de Generic M-ary Tree que consta de N Nodes y una array queries[] , la tarea es implementar las funciones Lock , Unlock y Upgrade para el árbol dado. Para cada consulta en queries[] , las funciones devuelven verdadero cuando la operación se realiza correctamente; de lo contrario, devuelve falso . Las funciones se definen como:
X: Nombre del Node en el árbol y será único
uid: ID de usuario de la persona que accede al Node X
1. Lock(X, uid): Lock tiene acceso exclusivo al subárbol enraizado.
- Una vez que Lock(X, uid) tiene éxito, lock(A, cualquier usuario) debería fallar, donde A es descendiente de X .
- Lock (B. cualquier usuario) debería fallar donde X es un descendiente de B.
- La operación de bloqueo no se puede realizar en un Node que ya está bloqueado.
2. Desbloquear (X, uid): para desbloquear el Node bloqueado.
- El desbloqueo revierte lo que se hizo con la operación de bloqueo .
- Solo se puede invocar y desbloquear con el mismo uid .
3. UpgradeLock(X, uid): el usuario uid puede actualizar su bloqueo a un Node antepasado.
- Solo es posible si cualquier Node antepasado solo está bloqueado por el mismo uid de usuario .
- La actualización debería fallar si hay algún Node bloqueado por algún otro uid Y a continuación.
Ejemplos:
Entrada: N = 7, M = 2, Nodes = [‘Mundo’, ‘Asia’, ‘África’, ‘China’, ‘India’, ‘Sudáfrica’, ‘Egipto’],
consultas = [‘1 China 9’ , ‘1 India 9’, ‘3 Asia 9’, ‘2 India 9’, ‘2 Asia 9’]
Salida: verdadero verdadero verdadero falso verdaderoEntrada: N = 3, M = 2, Nodes = [‘Mundo’, ‘China’, ‘India’],
consultas = [‘3 India 1’, ‘1 Mundo 9’]
Salida: falso verdadero
A continuación se muestra la implementación del enfoque anterior:
Python3
# Python Implementation
# Locking function
def lock(name):
ind = nodes.index(name)+1
c1 = ind * 2
c2 = ind * 2 + 1
if status[name] == 'lock' \
or status[name] == 'fail':
return 'false'
else:
p = ind//2
status[nodes[p-1]] = 'fail'
status[name] = 'lock'
return 'true'
# Unlocking function
def unlock(name):
if status[name] == 'lock':
status[name] = 'unlock'
return 'true'
else:
return 'false'
# Upgrade function
def upgrade(name):
ind = nodes.index(name)+1
# left child of ind
c1 = ind * 2
# right child of ind
c2 = ind * 2 + 1
if c1 in range(1, n) and c2 in range(1, n):
if status[nodes[c1-1]] == 'lock' \
and status[nodes[c2-1]] == 'lock':
status[nodes[c1-1]] = 'unlock'
status[nodes[c2-1]] = 'unlock'
status[nodes[ind-1]] = 'lock'
return 'true'
else:
return 'false'
# Precomputation
def precompute(queries):
d = []
# Traversing the queries
for j in queries:
i = j.split()
d.append(i[1])
d.append(int(i[0]))
status = {}
for j in range(0, len(d)-1, 2):
status[d[j]] = 0
return status, d
# Function to perform operations
def operation(name, code):
result = 'false'
# Choose operation to perform
if code == 1:
result = lock(name)
elif code == 2:
result = unlock(name)
elif code == 3:
result = upgrade(name)
return result
# Driver Code
if __name__ == '__main__':
# Given Input
n = 7;m = 2
apis = 5
nodes = ['World', 'Asia', \
'Africa', 'China', \
'India', 'SouthAfrica', 'Egypt']
queries = ['1 China 9', '1 India 9', \
'3 Asia 9', '2 India 9', '2 Asia 9']
# Precomputation
status, d = precompute(queries)
# Function Call
for j in range(0, len(d) - 1, 2):
print(operation(d[j], d[j + 1]), end = ' ')
true true true false true
Complejidad temporal: O(LogN)
Espacio auxiliar: O(N)