Design an in-memory file system with limits
Company: Harvey
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Design and implement an in-memory hierarchical file system. Requirements:
1) addFile(String path): Given an absolute path like "path/to/somewhere/file.txt", create intermediate folders as needed and store a file at the leaf.
2) get(String path): Given a directory path, return the names of its immediate children; for example, if the only child of "path/to/somewhere" is "file.txt", return "file.txt"; if the only child of "path/to" is the subfolder "somewhere", return "somewhere". Constraints: a) Capacity—each directory may contain at most 5 entries (files + folders); if an insertion would cause a directory to exceed 5 entries at that level, reject the operation. b) Auto-rename on duplicates—within the same directory, if a file name already exists, automatically rename the new file using OS-style suffixing: base
(
1).ext, base
(
2).ext, ... Maintain counters per base name. Example sequence: add("file.txt"), add("file.txt"), add("file
(
1).txt") should result in files named "file.txt", "file
(
1).txt", and "file
(
1)(
1).txt". Clarify behaviors and edge cases (invalid paths, conflicts where a file exists where a folder is required, idempotency, case sensitivity), and provide time/space complexity.
Quick Answer: This question evaluates the ability to design and implement hierarchical in-memory data structures, manage capacity constraints and OS-style duplicate naming, and reason about edge cases and time/space complexity.
You are given a sequence of operations on an initially empty in-memory hierarchical file system.
Implement a function that processes all operations in order.
Supported operations:
- `addFile(path)`: Create a file at the given absolute path. Missing intermediate directories must be created automatically.
- `get(path)`: Return the immediate children of an existing directory.
Rules and edge cases:
- Paths are case-sensitive and must be absolute, so they must start with `/`.
- A valid path cannot contain empty segments, `.` or `..`. Examples of invalid paths: `relative/file.txt`, `/a//b.txt`, `/a/./b`.
- `addFile('/')` is invalid because there is no file name.
- Each directory may contain at most 5 direct entries total (files + folders). If an operation would make any directory exceed 5 entries, reject the entire `addFile` operation.
- Rejected `addFile` operations are atomic: they must not leave partially created directories behind.
- If an intermediate component is a file where a directory is required, reject the operation.
- Only files are auto-renamed. If the leaf name already exists as a directory, reject the operation.
- Duplicate files inside the same directory are auto-renamed using OS-style suffixes on the exact requested leaf name:
- `file.txt` -> `file(1).txt` -> `file(2).txt`
- `file(1).txt` duplicated becomes `file(1)(1).txt`
- For consistency, `get(path)` always returns a sorted list of child names. If a directory has one child, return a one-element list.
- `get(path)` returns `None` if the path is invalid, does not exist, or points to a file.
- `addFile(path)` is not idempotent: adding the same file twice creates another file with a renamed leaf if capacity allows.
Return the result of every operation in order:
- `addFile(path)` returns the final stored absolute path, or `None` if rejected.
- `get(path)` returns a sorted list of immediate child names, or `None` if invalid.
Constraints
- 1 <= len(operations) <= 10^4
- 1 <= len(path) <= 200 for every operation path
- Each directory can store at most 5 direct entries
- Path segments are non-empty, case-sensitive strings that cannot contain `/`, and segments `.` and `..` are invalid
Examples
Input: [('get', '/')]
Expected Output: [[]]
Explanation: The filesystem starts empty, so the root directory has no children.
Input: [('addFile', '/path/to/somewhere/file.txt'), ('get', '/'), ('get', '/path'), ('get', '/path/to'), ('get', '/path/to/somewhere')]
Expected Output: ['/path/to/somewhere/file.txt', ['path'], ['to'], ['somewhere'], ['file.txt']]
Explanation: Intermediate directories are created automatically. Each `get` returns the immediate children of that directory.
Hints
- A tree/trie is a natural fit: each directory node can store a hash map of `name -> child node`.
- Handle duplicate file names only in the parent directory of the leaf. Split the leaf into `base + extension`, then try suffixes `(1)`, `(2)`, ... until you find a free name.