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.
Overview: 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
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.