How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Dropbox.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Dropbox during technical interviews.

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.

Input: (["/"], ["/"], ["/"])

Expected Output: [True]

Explanation: Root is directly granted, so HasAccess('/') is True.

Input: (["/", "/A", "/A/B", "/A/B/C"], ["/A/B"], ["/", "/A", "/A/B", "/A/B/C"])

Expected Output: [False, False, True, True]

Explanation: Grant is on the mid-tree folder /A/B. Its ancestors / and /A are NOT accessible (access flows downward only); /A/B (direct) and its descendant /A/B/C are accessible.

Input: (["/", "/A", "/B", "/A/X", "/B/X"], ["/A"], ["/A/X", "/B/X", "/B"])

Expected Output: [True, False, False]

Explanation: Sibling isolation: granting /A covers /A/X but not the identically-named /B/X under a different parent, nor /B itself.

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 /'.

Quick Overview

This question evaluates understanding of hierarchical data structures, access-control semantics, ancestor/descendant relationships, and efficient query handling for repeated membership checks.