Design Efficient Multi-Level Access Control System
Company: Pinterest
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Scenario
Multi-level access control lists (country → city) must be queried quickly.
##### Question
Design and implement a permission system where each geographic path (e.g., /France/Paris) can be authorised. Support add(path) and check(path).
##### Hints
Use a trie whose nodes store ACL flags and wildcards.
Quick Answer: This question evaluates understanding of hierarchical access control models, efficient path-based permission representation, and algorithmic design for fast membership checks.
Design a permission matcher for geographic-like paths. You are given operations ops, each of form ["add", pattern] or ["check", path]. Paths and patterns are normalized strings starting with '/', composed of zero or more non-empty segments separated by '/'. A pattern authorizes any path it matches. Wildcards: (1) "*" matches exactly one segment; (2) "**" matches zero or more trailing segments and may appear only as the final segment of a pattern. For each "check" operation, return True if any previously added pattern matches the path, else False. Return the results as a list of booleans in the order of "check" operations.
Constraints
- 1 <= len(ops) <= 100000
- Each op is ["add", pattern] or ["check", path]
- Paths/patterns start with '/' and have segments separated by '/'
- Wildcard '*' matches exactly one segment
- Wildcard '**' matches zero or more trailing segments and may appear only as the final segment of a pattern
- No redundant slashes; segments are non-empty (root '/' has zero segments)
- Total length of all strings <= 1e6
Solution
from typing import List
from collections import deque
class _Node:
__slots__ = ("children", "star_child", "terminal", "starstar")
def __init__(self) -> None:
self.children = {} # type: dict[str, _Node]
self.star_child = None # type: _Node | None
self.terminal = False # exact pattern ends here
self.starstar = False # pattern with trailing '**' ends here
def process_acl_operations(ops: List[List[str]]) -> List[bool]:
root = _Node()
def _split(path: str) -> List[str]:
# Returns list of non-empty segments; '/' -> []
return [seg for seg in path.split('/') if seg]
def add(pattern: str) -> None:
node = root
parts = _split(pattern)
for i, seg in enumerate(parts):
if seg == "**":
# Per constraints, '**' appears only as the final segment.
node.starstar = True
return
elif seg == "*":
if node.star_child is None:
node.star_child = _Node()
node = node.star_child
else:
nxt = node.children.get(seg)
if nxt is None:
nxt = _Node()
node.children[seg] = nxt
node = nxt
node.terminal = True
def check(path: str) -> bool:
parts = _split(path)
q = deque([(root, 0)])
visited = set() # set[tuple[int, int]] of (node_id, index)
while q:
node, i = q.popleft()
key = (id(node), i)
if key in visited:
continue
visited.add(key)
# '**' matches any remaining segments (including zero)
if node.starstar:
return True
if i == len(parts):
if node.terminal:
return True
continue
seg = parts[i]
if node.star_child is not None:
q.append((node.star_child, i + 1))
child = node.children.get(seg)
if child is not None:
q.append((child, i + 1))
return False
out: List[bool] = []
for op, arg in ops:
if op == "add":
add(arg)
elif op == "check":
out.append(check(arg))
else:
# Inputs are guaranteed valid per constraints
pass
return out
Explanation
Use a trie keyed by path segments. Each node keeps: (1) children for exact segment matches; (2) a single child for '*' matching exactly one segment; (3) a terminal flag for patterns that end exactly at the node; (4) a starstar flag to represent a pattern that ends with '**', which matches any remainder. For checking, perform a BFS over states (node, index-in-path). From each state, if starstar is set, it matches immediately. Otherwise, if we've consumed all segments and terminal is set, it's a match. If not at the end, transition on the exact child for the current segment and on the '*' child if it exists, advancing the index by one in both cases. A visited set over (node, index) prevents revisiting states. Adding a pattern walks/creates nodes along exact or '*' edges; encountering a final '**' sets the starstar flag at the current node.
Time complexity: Add: O(S) where S is number of segments in the pattern; Check: O(K) on average (two possible edges per step, with visited pruning), worst-case O(K * W) with W <= 2.. Space complexity: O(T) where T is the number of trie nodes, proportional to total unique segments across added patterns..
Hints
- Build a trie keyed by path segments.
- Mark nodes where a pattern ends (terminal) and where a pattern with trailing '**' ends (starstar).
- During check, perform BFS/DFS over trie states (node, index), following exact and '*' edges; if you encounter starstar at any visited node, it's an immediate match.