File System Access Control

Design a simple access-control system for a Unix-like file system. You are given a list of access-control entries (ACEs) that explicitly grant a user access to specific absolute paths, and you are then asked to answer a series of queries. Each query gives you a user name and an absolute file path; you must return true if that user is allowed to access the path, false otherwise. Access is inherited: if a user is granted access to /A/B, they automatically have access to every path underneath /A/B (e.g., /A/B/C, /A/B/C/D.txt). The root path “/” is special: granting access to “/” gives access to the entire file system. Paths may or may not end with a trailing slash; your code must treat /A/B/ and /A/B as the same directory. You may assume all paths are absolute, start with “/”, contain only alphanumeric characters and slashes, and never have consecutive slashes or interior “.” or “..” components. Implement the following two functions (or their equivalent in your language):

void addACE(String user, String path); // record that <user> is granted access to <path> boolean canAccess(String user, String path); // return true if <user> is allowed to access <path>

You may call addACE many times (up to 10^5), and you may call canAccess many times (up to 10^5). Your solution must be efficient for both operations.