Tree of Space | Juspay Interview Question | Optimal | Lock,Unlock,Upgrade
I got this question in my second round of Interview with Juspay in 2021 . One of the best Question , I have ever got in an Interview . In first attempt only , I was able to solve this problem with all TC passed.
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
-
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. -
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. -
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 true
Input: N = 3, M = 2, nodes = [‘World’, ‘China’, ‘India’],
queries = [‘3 India 1’, ‘1 World 9’]
Output: false true
Solution :
#include<bits/stdc++.h>
using namespace std;
class TreeNode{
public:
TreeNode *parent;
string data;
vector <TreeNode*> children;
bool isLocked=false;
bool isLockable=true;
int locker_id=-1;
};
bool lock_node(TreeNode* node, int uid){
if(node->isLocked || !node->isLockable) return false;
queue<TreeNode*> q;
q.push(node);
while(q.size()!=0){
TreeNode* temp = q.front();
q.pop();
for(int i=0;i<temp->children.size();i++){
q.push(temp->children[i]);
if(temp->children[i]->isLocked) return false;
}
}
node->isLocked=true;
node->locker_id=uid;
queue<TreeNode*> q1;
q1.push(node);
while(q1.size()!=0){
TreeNode* temp = q1.front();
q1.pop();
for(int i=0;i<temp->children.size();i++){
q1.push(temp->children[i]);
temp->children[i]->isLockable=false;
}
}
return true;
}
bool unlock_node(TreeNode* node, int uid){
if(!node->isLocked || node->locker_id != uid) return false;
node->locker_id = -1;
node->isLocked=false;
queue<TreeNode*> q1;
q1.push(node);
while(q1.size()!=0){
TreeNode* temp = q1.front();
q1.pop();
for(int i=0;i<temp->children.size();i++){
q1.push(temp->children[i]);
temp->children[i]->isLockable=true;
}
}
return true;
}
bool upgrade_node(TreeNode* node, int uid, unordered_map<string, TreeNode*>& treemap){
if(node->isLocked || !node->isLockable) return false;
int count=0;
queue<TreeNode*> q;
q.push(node);
while(q.size()!=0) {
TreeNode* temp = q.front();
q.pop();
for(int i=0;i<temp->children.size();i++){
if(temp->children[i]->isLocked){
if(temp->children[i]->locker_id!=uid)
return false;
else
count++;
}
q.push(temp->children[i]);
}
}
if(count>0){
node->isLocked=true;
node->locker_id=uid;
queue<TreeNode*> q1;
q1.push(node);
while(q1.size()!=0){
TreeNode* temp = q1.front();
q1.pop();
for(int i=0;i<temp->children.size();i++){
q1.push(temp->children[i]);
temp->children[i]->isLockable=false;
temp->children[i]->isLocked=false;
temp->children[i]->locker_id=-1;
}
}
return true;
}
else
return false;
}
bool solve(int pid, TreeNode* node, int uid, unordered_map<string, TreeNode*>& treemap){
if(pid == 1) return lock_node(node, uid);
if(pid == 2) return unlock_node(node, uid);
if(pid == 3) return upgrade_node(node, uid, treemap);
return false;
}
int main(){
int n, m, Q;
cin >> n >> m >> Q;
if(n==0||m==0||Q==0)
return 0;
unordered_map<string, TreeNode*> treemap;
vector<string> v;
for(int i = 0; i < n; i++){
string str;
cin >> str;
v.push_back(str);
}
int j=0;
string rootData = v[j++];
TreeNode* root = new TreeNode();
root->parent=NULL;
root->data=rootData;
queue<TreeNode*> pendingNodes;
pendingNodes.push(root);
while(pendingNodes.size()!=0){
TreeNode* front = pendingNodes.front();
treemap[front->data]=front;
pendingNodes.pop();
int numChild= n-j>m ? m : n-j;
for(int i=0;i<numChild;i++){
string childData = v[j++];
TreeNode* child = new TreeNode();
child->parent=front;
child->data=childData;
front->children.push_back(child);
pendingNodes.push(child);
}
}
while(Q--){
int pid, uid;
string node;
cin >> pid >> node >> uid;
cout << (solve(pid, treemap[node], uid, treemap) ? "true" : "false")<<endl;
}
return 0;
}