Tree of Space – Locking and Unlocking N-Ary Tree
Given a world map in the form of Generic M-ary Tree consisting of N nodes and an array queries[], the task is to implement the functions Lock, Unlock and Upgrade for the given tree. For each query in queries[], the functions return true when the operation is performed successfully, otherwise it returns false. The functions are defined as:
X: Name of the node in the tree and will be unique
uid: User Id for the person who accesses node X
1. Lock(X, uid): Lock takes exclusive access to the subtree rooted.
- Once Lock(X, uid) succeeds, then lock(A, any user) should fail, where A is a descendant of X.
- Lock(B. any user) should fail where X is a descendant of B.
- Lock operation cannot be performed on a node that is already locked.
2. Unlock(X, uid): To unlock the locked node.
- The unlock reverts what was done by the Lock operation.
- It can only be called on same and unlocked by same uid.
3. UpgradeLock(X, uid): The user uid can upgrade their lock to an ancestor node.
- It is only possible if any ancestor node is only locked by the same user uid.
- The Upgrade should fail if there is any node that is locked by some other uid Y below.
Examples:
Input: N = 7, M = 2, nodes = [‘World’, ‘Asia’, ‘Africa’, ‘China’, ‘India’, ‘SouthAfrica’, ‘Egypt’],
queries = [‘1 China 9’, ‘1 India 9’, ‘3 Asia 9’, ‘2 India 9’, ‘2 Asia 9’]
Output: true true true false trueInput: N = 3, M = 2, nodes = [‘World’, ‘China’, ‘India’],
queries = [‘3 India 1’, ‘1 World 9’]
Output: false true
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; const int N = 1000005; map<string, int > status; vector<string> nodes; int n, m, apis, ind; // Locking function string lock(string name) { ind = find(nodes.begin(), nodes.end(), name) - nodes.begin() + 1; int c1 = ind * 2, c2 = ind * 2 + 1; if (status[name] == 1 || status[name] == 2) return "false" ; else { int p = ind / 2; status[nodes[p - 1]] = 2; status[name] = 1; return "true" ; } } // Unlocking function string unlock(string name) { if (status[name] == 1) { status[name] = 0; return "true" ; } else return "false" ; } // Upgrade function string upgrade(string name) { ind = find(nodes.begin(), nodes.end(), name) - nodes.begin() + 1; // left child of ind int c1 = ind * 2; // right child of ind int c2 = ind * 2 + 1; if (c1 >= 1 && c1 < n && c2 >= 1 && c2 < n) { if (status[nodes[c1 - 1]] == 1 && status[nodes[c2 - 1]] == 1) { status[nodes[c1 - 1]] = 0; status[nodes[c2 - 1]] = 0; status[nodes[ind - 1]] = 1; return "true" ; } else return "false" ; } } // Function to perform operations string operation(string name, int code) { string result = "false" ; // Choose operation to perform if (code == 1) result = lock(name); else if (code == 2) result = unlock(name); else if (code == 3) result = upgrade(name); return result; } int main() { // Given Input n = 7; m = 2; apis = 5; nodes = { "World" , "Asia" , "Africa" , "China" , "India" , "SouthAfrica" , "Egypt" }; vector<pair< int , string> > queries = { { 1, "China" }, { 1, "India" }, { 3, "Asia" }, { 2, "India" }, { 2, "Asia" } }; // Precomputation for ( auto q : queries) status[q.second] = 0; // Function Call for ( auto q : queries) cout << operation(q.second, q.first) << " " ; return 0; } |
Java
//Java code for the above approach import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; class Main { // Locking function static String lock(String name, Map<String, String> status) { if ( "lock" .equals(status.get(name)) || "fail" .equals(status.get(name))) { return "false" ; } else { status.put(name, "lock" ); return "true" ; } } // Unlocking function static String unlock(String name, Map<String, String> status) { if ( "lock" .equals(status.get(name))) { status.put(name, "unlock" ); return "true" ; } else { return "false" ; } } // Upgrade function static String upgrade(String name, Map<String, String> status, List<String> nodes) { int ind = nodes.indexOf(name) + 1 ; int c1 = ind * 2 ; int c2 = ind * 2 + 1 ; if (c1 < nodes.size() && c2 < nodes.size()) { if ( "lock" .equals(status.get(nodes.get(c1 - 1 ))) && "lock" .equals( status.get(nodes.get(c2 - 1 )))) { status.put(nodes.get(c1 - 1 ), "unlock" ); status.put(nodes.get(c2 - 1 ), "unlock" ); status.put(name, "lock" ); return "true" ; } else { return "false" ; } } return "false" ; } // Precomputation static Map<String, String> precompute(List<String> nodes, List<String> queries) { List<String> d = new ArrayList<>(); for (String query : queries) { String[] parts = query.split( " " ); d.add(parts[ 1 ]); d.add(parts[ 0 ]); } Map<String, String> status = new HashMap<>(); for ( int j = 0 ; j < d.size() - 1 ; j += 2 ) { status.put(d.get(j), "unlock" ); } return status; } // Function to perform operations static String operation(String name, int code, Map<String, String> status, List<String> nodes) { String result = "false" ; switch (code) { case 1 : result = lock(name, status); break ; case 2 : result = unlock(name, status); break ; case 3 : result = upgrade(name, status, nodes); break ; } return result; } public static void main(String[] args) { // Given Input int n = 7 ; int m = 2 ; int apis = 5 ; List<String> nodes = new ArrayList<>(); nodes.add( "World" ); nodes.add( "Asia" ); nodes.add( "Africa" ); nodes.add( "China" ); nodes.add( "India" ); nodes.add( "SouthAfrica" ); nodes.add( "Egypt" ); List<String> queries = new ArrayList<>(); queries.add( "1 China 9" ); queries.add( "1 India 9" ); queries.add( "3 Asia 9" ); queries.add( "2 India 9" ); queries.add( "2 Asia 9" ); // Precomputation Map<String, String> status = precompute(nodes, queries); // Function Call List<String> d = new ArrayList<>(); for (String query : queries) { String[] parts = query.split( " " ); d.add(parts[ 1 ]); d.add(parts[ 0 ]); } for ( int j = 0 ; j < d.size() - 1 ; j += 2 ) { System.out.print( operation(d.get(j), Integer.parseInt(d.get(j + 1 )), status, nodes) + " " ); } } } //This code is contributed by Potta Lokesh |
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 = ' ' ) |
C#
using System; using System.Collections.Generic; using System.Linq; class Program { public static Dictionary< string , int > status = new Dictionary< string , int >(); public static List< string > nodes = new List< string >(); public static int n, m, apis, ind; // Locking function public static string Lock( string name) { ind = nodes.IndexOf(name) + 1; if (status.ContainsKey(name) && (status[name] == 1 || status[name] == 2)) return "false" ; else { int p = ind / 2; status[nodes[p - 1]] = 2; status[name] = 1; return "true" ; } } // Unlocking function public static string Unlock( string name) { if (status.ContainsKey(name) && status[name] == 1) { status[name] = 0; return "true" ; } else return "false" ; } // Upgrade function public static string Upgrade( string name) { ind = nodes.IndexOf(name) + 1; int c1 = ind * 2; int c2 = ind * 2 + 1; if (c1 >= 1 && c1 < n && c2 >= 1 && c2 < n) { if (status[nodes[c1 - 1]] == 1 && status[nodes[c2 - 1]] == 1) { status[nodes[c1 - 1]] = 0; status[nodes[c2 - 1]] = 0; status[nodes[ind - 1]] = 1; return "true" ; } else return "false" ; } else return "false" ; } // Function to perform operations public static string Operation( string name, int code) { string result = "false" ; // Choose operation to perform if (code == 1) result = Lock(name); else if (code == 2) result = Unlock(name); else if (code == 3) result = Upgrade(name); return result; } public static void Main() { // Given Input n = 7; m = 2; apis = 5; nodes = new List< string > { "World" , "Asia" , "Africa" , "China" , "India" , "SouthAfrica" , "Egypt" }; var queries = new List<Tuple< int , string >> { Tuple.Create(1, "China" ), Tuple.Create(1, "India" ), Tuple.Create(3, "Asia" ), Tuple.Create(2, "India" ), Tuple.Create(2, "Asia" )}; // Precomputation foreach ( var q in queries) status[q.Item2] = 0; // Function Call foreach ( var q in queries) Console.Write(Operation(q.Item2, q.Item1) + " " ); } } |
Javascript
// JavaScript code for the above approach function lock(name, status) { if (status[name] === "lock" || status[name] === "fail" ) { return "false" ; } else { status[name] = "lock" ; return "true" ; } } function unlock(name, status) { if (status[name] === "lock" ) { status[name] = "unlock" ; return "true" ; } else { return "false" ; } } function upgrade(name, status, nodes) { let ind = nodes.indexOf(name) + 1; let c1 = ind * 2; let c2 = ind * 2 + 1; if (c1 < nodes.length && c2 < nodes.length) { if ( status[nodes[c1 - 1]] === "lock" && status[nodes[c2 - 1]] === "lock" ) { status[nodes[c1 - 1]] = "unlock" ; status[nodes[c2 - 1]] = "unlock" ; status[name] = "lock" ; return "true" ; } else { return "false" ; } } return "false" ; } function precompute(nodes, queries) { let d = []; for (let query of queries) { let parts = query.split( " " ); d.push(parts[1]); d.push(parts[0]); } let status = {}; for (let j = 0; j < d.length - 1; j += 2) { status[d[j]] = "unlock" ; } return status; } function operation(name, code, status, nodes) { let result = "false" ; switch (code) { case 1: result = lock(name, status); break ; case 2: result = unlock(name, status); break ; case 3: result = upgrade(name, status, nodes); break ; } return result; } // Given Input let n = 7; let m = 2; let apis = 5; let nodes = [ "World" , "Asia" , "Africa" , "China" , "India" , "SouthAfrica" , "Egypt" , ]; let queries = [ "1 China 9" , "1 India 9" , "3 Asia 9" , "2 India 9" , "2 Asia 9" , ]; // Precomputation let status = precompute(nodes, queries); // Function Call let d = []; for (let query of queries) { let parts = query.split( " " ); d.push(parts[1]); d.push(parts[0]); } let output = "" ; for (let j = 0; j < d.length - 1; j += 2) { output += operation(d[j], parseInt(d[j + 1]), status, nodes) + " " ; } console.log(output); |
true true true false true
Time Complexity: O(m+LogN)
Auxiliary Space: O(N)
Contact Us