Quick Overview

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.

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.

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

Read the full Harvey Software Engineer interview experience this question came from

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

  1. A tree/trie is a natural fit: each directory node can store a hash map of `name -> child node`.
  2. 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.

Loading coding console...

Show the approach

Approach

Approach: a trie of directory nodes. The file system is a tree where each Node is either a file (leaf) or a directory holding a children dict mapping names to child nodes. A root directory anchors the tree.

Path parsing. parse_path validates and splits absolute paths. It rejects anything not starting with /, trailing-slash paths, and any empty/./.. segment. addFile disallows '/' (no filename); get allows '/' (returns []).

addFile walks the parent segments. For each missing intermediate it creates a directory, but only if the parent has < 5 children; otherwise it rolls back every node created during this call (tracked in created) so a rejected add leaves no partial state — that atomicity is the trickiest requirement. If an intermediate segment is an existing file, it rejects.

For the leaf:

  • name free + room → store as-is;
  • name taken by a directory → reject;
  • name taken by a file → auto-rename via make_unique (only when there's room).

make_unique splits the requested leaf into (base, ext) at the last . (split_name keeps . only when idx > 0, so dotfiles stay whole). It probes base(suffix)ext, caching the next suffix per (base, ext) in next_suffix to avoid rescanning. Because the base is the requested name, file(1).txt correctly becomes file(1)(1).txt.

get walks segments; returns None if any is missing or is a file, else the sorted child names.

The top loop dispatches each (op, path) tuple, appending None for malformed ops, and returns results in order. Correctness follows from validating before mutating and rolling back on any capacity/type failure.

Time complexity:
O(T), where T is the total number of path components across all operations. Each directory holds at most 5 children, so dict lookups, duplicate-suffix probing, and sorting in `get` are all O(1) per directory visited.
Space complexity:
O(N), where N is the total number of directories and files successfully created (the size of the tree). The per-call `created` rollback list is bounded by path depth.