Comment on page
Permission Management for a General Tree
1) Implement a TreeNode class that represents a general tree, i.e. one where each node can have an arbitrary number of children.
2) Implement the following methods:
void grantAccess(TreeNode root);
void revokeAccess(TreeNode root);
boolean hasAccess(TreeNode root);
Once one grants access to a certain node, access is also granted to all of the nodes below that node too. The same logic follows for revokeAccess. Finally, hasAccess should be able to decide whether a hypothetical use has access to a certain node at a given time.
Examples
10
1 2 3
5 13 9 0 4 8
// ex 1
hasAccess(4); // false
revokeAccess(10);
hasAccess(4); // false
grantAccess(2);
hasAccess(4); // true
// ex 2
hasAccess(4); // false
grantAccess(2);
hasAccess(4); // true
revokeAccess(10);
hasAccess(4); // false
The Idea: We need to define some kind of priority for when we want to conclude whether or not a node has access priveleges. One way to do this is to define use time element where the closest relevent time decides permission priveleges.
Complexity: O(1) time and space for both revokeAccess and grantAccess. O(N) worse case time where N is the number of nodes for hasAccess (consider the linkedlist n-ary tree). If the tree is fairly balanced: revokeAccess and grantAccess is the same, but now hasAccess is O(log_k(N)) time (which is proportional to the number of levels in the tree).
class TreeNode {
public:
TreeNode(vector<TreeNode*> children, int id) :
id(id), children(children) {
parent = nullptr;
}
TreeNode *parent;
bool hasAccess = false;
int time_element = 0;
private:
const int id;
vector<TreeNode*> children;
};
class PermissionManagement {
public:
void grantAccess(TreeNode* root) {
root->hasAccess = true;
root->time_element = counter++;
}
void revokeAccess(TreeNode* root) {
root->hasAccess = false;
root->time_element = counter++;
}
bool hasAccess(TreeNode* root) {
TreeNode *iter = root;
vector<TreeNode*> time_elements;
while (iter) {
time_elements.push_back(iter);
iter = iter->parent;
}
auto top_counter = *max_element(time_elements.begin(), time_elements.end(),
[] (const TreeNode* a, const TreeNode* b) {
return a->time_element > b->time_element;
});
return top_counter->hasAccess;
}
static long long counter;
};
long long PermissionManagement::counter = 0;
Last modified 4yr ago