Store explicit rules on the nodes of a folder tree. To resolve a path, walk down from the root and remember the latest rule for the user; the deepest one wins. Cache answers by user and path, and when a rule changes, drop only that user's cached answers at or below the changed folder. O(depth) per uncached check.
mediumPattern: TreesFrom Devana's Microsoft question set
Problem
Folders inherit permissions from their parent unless a folder sets an explicit rule. A rule names a user and a permission such as read, write or deny. Given a user and a path, the effective permission is the rule on the nearest folder, walking up from the path, that has one for that user.
The same checks repeat constantly, so they must be fast, and a permission change must never leave a stale answer behind. Write PermissionResolver with set_override(path, user, permission) and effective(user, path).
class PermissionResolver:
def set_override(self, path: str, user: str, permission: str) -> None: ...
def effective(self, user: str, path: str) -> str: ...This is one of Devana's own questions, written in the style of Microsoft's interviews. It is not a question leaked from Microsoft, and Devana is not affiliated with Microsoft.
Constraints
- Paths look like
/root/docs/a.txt./is the top of the tree and can hold rules too. - The nearest explicit rule for the user wins, whatever it says: a
denyon a folder overrides areadabove it. - With no rule anywhere on the path, the answer is
none. - A path that does not exist yet still inherits from its existing ancestors.
- Trees are up to 100 levels deep, and checks far outnumber changes.
Examples
Example 1
Input: set_override("/root", "alice", "read")
effective("alice", "/root/docs/a.txt")
Output: "read"Neither /root/docs nor the file has a rule for alice, so the nearest rule is the one on /root.
Example 2
Input: set_override("/root", "alice", "read")
set_override("/root/private", "alice", "deny")
effective("alice", "/root/private/x.txt")
Output: "deny"The nearer rule wins over the more distant one, even though it is more restrictive.
Hints
Open one at a time, and try the problem again after each.
Hint 1
The answer depends only on the rules along the path from the root to the file. Which structure stores things by path segment?
Hint 2
Walk from the root down rather than from the file up, and overwrite your answer each time you meet a rule for the user. What is left at the end?
Hint 3
If you cache answers, which ones can a new rule on /root/docs change? Only one user's, and only for some paths.
Hint 4
Watch the prefixes: /root/doc is not an ancestor of /root/docs.
Approach: from brute force to optimal
Brute force: a dict of rules by path
Keep rules in a dict keyed by (path, user). To resolve, strip the last segment of the path again and again, looking up each ancestor until a rule turns up. Nothing is cached, and each lookup hashes a whole path string.
Complexity: O(depth) lookups per check, each hashing a path of up to O(depth) segments
A tree of folders and a targeted cache
Mirror the folders as a tree of path segments, each node holding {user: permission}. A walk from the root visits each segment once and keeps the last rule it saw for the user.
Cache answers by (user, path). A change on folder F for user U can only affect U's answers at F or below it, so delete exactly those and keep everyone else's.
Complexity: O(depth) per uncached check and O(1) per cached one; O(rules + cached answers) space
How to say it in the interview
Say "the nearest explicit rule wins" and restate it as "the deepest rule on the path from the root", because that turns the problem into one walk down a tree. When you add the cache, state the invalidation rule before the interviewer asks: one user, one subtree.
Solution
Python
class PermissionResolver:
def __init__(self):
self.root = {"children": {}, "rules": {}} # a folder: subfolders and rules
self.cache = {} # (user, path) -> permission
@staticmethod
def _parts(path):
return [part for part in path.split("/") if part]
def set_override(self, path, user, permission):
node = self.root
for part in self._parts(path):
node = node["children"].setdefault(part, {"children": {}, "rules": {}})
node["rules"][user] = permission
# Only this user's answers at or below this folder can change.
folder = "/" + "/".join(self._parts(path))
below = folder.rstrip("/") + "/"
stale = [k for k in self.cache
if k[0] == user and (k[1] == folder or k[1].startswith(below))]
for key in stale:
del self.cache[key]
def effective(self, user, path):
key = (user, "/" + "/".join(self._parts(path)))
if key not in self.cache:
node = self.root
found = node["rules"].get(user, "none")
for part in self._parts(path):
node = node["children"].get(part)
if node is None:
break # deeper folders have no rules
found = node["rules"].get(user, found)
self.cache[key] = found
return self.cache[key]JavaScript
class PermissionResolver {
constructor() {
this.root = { children: new Map(), rules: new Map() }; // a folder: subfolders and rules
this.cache = new Map(); // user + "\n" + path -> permission
}
static parts(path) {
return path.split("/").filter(Boolean);
}
setOverride(path, user, permission) {
let node = this.root;
for (const part of PermissionResolver.parts(path)) {
if (!node.children.has(part)) node.children.set(part, { children: new Map(), rules: new Map() });
node = node.children.get(part);
}
node.rules.set(user, permission);
// Only this user's answers at or below this folder can change.
const folder = "/" + PermissionResolver.parts(path).join("/");
const below = folder.replace(/\/$/, "") + "/";
for (const key of [...this.cache.keys()]) {
const [u, p] = key.split("\n");
if (u === user && (p === folder || p.startsWith(below))) this.cache.delete(key);
}
}
effective(user, path) {
const key = user + "\n" + "/" + PermissionResolver.parts(path).join("/");
if (!this.cache.has(key)) {
let node = this.root;
let found = node.rules.get(user) ?? "none";
for (const part of PermissionResolver.parts(path)) {
node = node.children.get(part);
if (!node) break; // deeper folders have no rules
found = node.rules.get(user) ?? found;
}
this.cache.set(key, found);
}
return this.cache.get(key);
}
}Both versions are tested against the same cases, including every example on this page.
- Invalidation scans the cache, which is simple and correct. At scale, keep each cached answer on its folder's node instead, so a change clears one subtree without looking at anything else.
- The prefix test adds a trailing slash, so a rule on
/root/docnever clears answers for/root/docs. - A path below the deepest folder with rules stops the walk early and inherits whatever was found above it.
Follow-up questions
What exactly must be invalidated when a permission changes on a mid-tree folder?
Only the changed user's answers for that folder and everything under it. Other users are unaffected, and so are siblings and ancestors. A rule for a group widens "the user" to every member of the group.
How do you handle a user in several groups with conflicting grants?
Choose a precedence and state it, for example: a user's own rule beats a group rule, and among rules at the same depth a deny beats an allow. Resolve each principal's nearest rule, then combine them with that precedence.
How would you answer "list everything alice can read"?
Walk the tree once, carrying alice's current permission down, and report the folders where it is read or write. A subtree under a deny with no deeper rule for her can be skipped entirely.
How do you sustain 10^5 checks a second?
Most checks hit the cache, and a miss is at most 100 steps. Precomputing each folder's effective permissions for active users removes even that, at the cost of memory and more invalidation.
Common mistakes
- Taking the first rule found walking down from the root instead of the last, which lets a distant ancestor win.
- Clearing the whole cache on every change, which is correct but throws away every other user's answers.
- Matching path prefixes without a separator, so
/root/docaffects/root/docs. - Returning nothing for a path that does not exist yet instead of inheriting from its ancestors.
Practice it in a mock interview
Reading a solution and explaining one under questioning are different skills. The button below starts this problem as a voice mock interview with Josh, Devana's AI interviewer, with an editor that runs your code.
Practice this problem in a mock interview
Related problems
- Match an Address Against a List of IP Ranges: A binary trie over address bits; remember the last action seen on the way down.
- Build a Document Outline from Headings: Keep the open chain of headings on a stack and pop until the top is a shallower level.
- Trees: the pattern guide, with more practice questions.