Implement hierarchical folder access check
Company: Dropbox
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are asked to simulate a simple hierarchical file system and implement an access-check function.
The file system consists of folders arranged in a tree. A user is granted **direct access** to a subset of folders. Access is **inherited down the tree**: if the user has access to a parent folder, they automatically have access to all of its descendant folders.
You are given:
- A list of all folders in the system, represented as absolute paths from the root. For example, a tree like:
```text
/
├── A
│ ├── B
│ │ ├── C
│ │ └── D
│ └── E
└── F
```
could be represented as:
```text
allFolders = [
"/",
"/A",
"/A/B",
"/A/B/C",
"/A/B/D",
"/A/E",
"/F"
]
```
- A set of folder paths `accessibleFolders` representing folders to which the user has **direct** access. For example:
```text
accessibleFolders = { "/A", "/F" }
```
You need to implement the function:
```text
bool HasAccess(string folderPath)
```
that returns:
- `true` if the user has access to `folderPath` **either** because:
- `folderPath` is in `accessibleFolders`, **or**
- some ancestor folder of `folderPath` (e.g., `/A` is an ancestor of `/A/B/C`) is in `accessibleFolders`.
- `false` otherwise.
Assume:
- All folder paths in `allFolders` and `accessibleFolders` are normalized absolute paths starting with `'/'`, with components separated by `'/'` (e.g., `/A/B/C`).
- `folderPath` passed into `HasAccess` is always a valid folder path present in `allFolders`.
Examples (given the tree above and `accessibleFolders = {"/A", "/F"}`):
- `HasAccess("/A")` → `true` (direct access)
- `HasAccess("/A/B")` → `true` (inherits from `/A`)
- `HasAccess("/A/B/C")` → `true` (inherits from `/A`)
- `HasAccess("/A/E")` → `true` (inherits from `/A`)
- `HasAccess("/F")` → `true` (direct access)
- `HasAccess("/")` → `false` (no access to root unless `/` is in `accessibleFolders`)
Design and implement `HasAccess` so that it can be called many times efficiently after the initial inputs (`allFolders` and `accessibleFolders`) are known.
Quick Answer: This question evaluates understanding of hierarchical data structures, access-control semantics, ancestor/descendant relationships, and efficient query handling for repeated membership checks.
Simulate a simple hierarchical file system and implement an access-check function.
The file system is a tree of folders identified by normalized absolute paths (e.g. `/`, `/A`, `/A/B/C`). A user is granted **direct access** to a subset of folders. Access is **inherited down the tree**: if the user has direct access to a folder, they automatically have access to every descendant of that folder.
You are given:
- `all_folders`: a list of every folder path in the system (each is a normalized absolute path starting with `/`).
- `accessible_folders`: the list of folders to which the user has **direct** access.
- `queries`: a list of folder paths to check.
Return a list of booleans, one per query, where `result[i]` is `True` iff the user has access to `queries[i]` — that is, `queries[i]` itself is in `accessible_folders`, or some ancestor of it (e.g. `/A` is an ancestor of `/A/B/C`) is in `accessible_folders`.
Note that `/` is the root; it grants access to everything below it only if `/` itself is directly accessible. A folder is **not** considered its own ancestor's grantor unless that ancestor is in `accessible_folders`.
Design the check so it can be answered efficiently for many queries after the inputs are known.
Example (the tree `/` → `/A` → {`/A/B` → {`/A/B/C`, `/A/B/D`}, `/A/E`}, `/F`) with `accessible_folders = ["/A", "/F"]`:
- `HasAccess("/A")` → `True` (direct)
- `HasAccess("/A/B/C")` → `True` (inherits from `/A`)
- `HasAccess("/F")` → `True` (direct)
- `HasAccess("/")` → `False` (root not granted)
Constraints
- All paths are normalized absolute paths starting with '/'.
- The root is '/'; access to '/' is granted only if '/' is in accessible_folders.
- Every query path is guaranteed to be present in all_folders.
- 1 <= len(all_folders) <= 10^5
- 0 <= len(accessible_folders) <= len(all_folders)
- 1 <= len(queries) <= 10^5
Examples
Input: (["/", "/A", "/A/B", "/A/B/C", "/A/B/D", "/A/E", "/F"], ["/A", "/F"], ["/A", "/A/B", "/A/B/C", "/A/E", "/F", "/"])
Expected Output: [True, True, True, True, True, False]
Explanation: /A and /F are direct grants; /A/B, /A/B/C, /A/E all inherit from /A. The root / is not granted, so HasAccess('/') is False.
Input: (["/"], [], ["/"])
Expected Output: [False]
Explanation: No folders are accessible, so the root returns False.
Hints
- A folder is accessible if it OR any of its ancestors was directly granted. Put accessible_folders in a hash set for O(1) membership tests.
- To enumerate a path's ancestors, repeatedly strip the last '/component' off the path until you reach '/'. Stop early the moment you find a path already in the accessible set.
- Be careful with the root: the parent of '/A' is '/', not the empty string. Use rfind('/') and treat an index of 0 as 'parent is /'.