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 hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Anthropic.

What role is this question designed for?

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

Implement a hierarchical file store | Anthropic Coding Question

Implement a hierarchical file store

Company: Anthropic

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

Implement a simplified in-memory file store. The store uses absolute Unix-style paths such as `/`, `/docs`, and `/docs/readme.txt`. A path component contains only lowercase letters, digits, underscores, and periods. Implement a class with the following operations: 1. `list(path) -> List[str]` - If `path` is a directory, return the names of its immediate children in lexicographic order. - If `path` is a file, return a list containing only that file name. 2. `makeDirectory(path) -> None` - Create the directory at `path`, including any missing parent directories. 3. `writeFile(path, content) -> None` - Create the file if it does not exist. - Append `content` to the file if it already exists. - Create missing parent directories if necessary. 4. `readFile(path) -> str` - Return the full content of the file at `path`. Example: - `makeDirectory(/a/b)` - `writeFile(/a/b/c.txt, hello)` - `list(/)` returns `[a]` - `list(/a/b/c.txt)` returns `[c.txt]` - `readFile(/a/b/c.txt)` returns `hello` - `writeFile(/a/b/c.txt, world)` - `readFile(/a/b/c.txt)` returns `helloworld` Discuss the data structures you would use and the time complexity of each operation.

Quick Answer: This question evaluates proficiency in modeling hierarchical file systems, path parsing and manipulation, managing mutable file contents, and analyzing algorithmic time and space complexity within the Coding & Algorithms domain.

You are given a sequence of operations to perform on an initially empty in-memory file store. The root directory `/` always exists. Paths are absolute Unix-style paths such as `/`, `/docs`, and `/docs/readme.txt`. Each path component contains only lowercase letters, digits, underscores, and periods. Supported operations: 1. `list(path)` - If `path` is a directory, return the names of its immediate children in lexicographic order. - If `path` is a file, return a list containing only that file name. 2. `makeDirectory(path)` - Create the directory at `path`, including any missing parent directories. 3. `writeFile(path, content)` - Create the file if it does not exist. - Append `content` to the file if it already exists. - Create missing parent directories if necessary. 4. `readFile(path)` - Return the full content of the file at `path`. For this problem, implement a function that receives all operations at once: - `operations[i]` is one of: `"list"`, `"makeDirectory"`, `"writeFile"`, `"readFile"` - `arguments[i]` contains the arguments for that operation: - `[path]` for `list`, `makeDirectory`, and `readFile` - `[path, content]` for `writeFile` Return the results of the query operations in order: - For each `list` operation, append its returned list of names. - For each `readFile` operation, append a single-element list containing the file content. All operations are guaranteed to be valid.

Constraints

1 <= len(operations) <= 20000
len(operations) == len(arguments)
The sum of all path lengths is at most 200000
The sum of all appended content lengths is at most 200000
All paths are valid absolute paths
All `list` and `readFile` operations refer to existing paths
`readFile` is only called on file paths

Examples

Input: (['makeDirectory', 'writeFile', 'list', 'list', 'readFile', 'writeFile', 'readFile'], [['/a/b'], ['/a/b/c.txt', 'hello'], ['/'], ['/a/b/c.txt'], ['/a/b/c.txt'], ['/a/b/c.txt', 'world'], ['/a/b/c.txt']])

Expected Output: [['a'], ['c.txt'], ['hello'], ['helloworld']]

Explanation: Creates `/a/b`, writes to `c.txt`, lists the root and the file path, then reads before and after appending more content.

Input: (['list'], [['/']])

Expected Output: [[]]

Explanation: Edge case: the file store is empty except for the root directory, so listing `/` returns an empty list.

Input: (['makeDirectory', 'writeFile', 'writeFile', 'makeDirectory', 'list', 'readFile', 'list'], [['/docs'], ['/docs/z.txt', 'z'], ['/docs/a.txt', 'a'], ['/docs/sub_dir'], ['/docs'], ['/docs/a.txt'], ['/docs/sub_dir']])

Expected Output: [['a.txt', 'sub_dir', 'z.txt'], ['a'], []]

Explanation: Children of `/docs` must be returned in lexicographic order, and listing an empty directory returns an empty list.

Input: (['writeFile', 'list', 'list', 'list', 'readFile'], [['/logs/2024.01_run_1.txt', 'x'], ['/'], ['/logs'], ['/logs/2024.01_run_1.txt'], ['/logs/2024.01_run_1.txt']])

Expected Output: [['logs'], ['2024.01_run_1.txt'], ['2024.01_run_1.txt'], ['x']]

Explanation: Writing a file should automatically create missing parent directories. Listing a file path returns only that file name.

Input: (['writeFile', 'makeDirectory', 'writeFile', 'list', 'readFile'], [['/b.txt', 'one'], ['/a'], ['/b.txt', 'two'], ['/'], ['/b.txt']])

Expected Output: [['a', 'b.txt'], ['onetwo']]

Explanation: The root can contain both directories and files. Names must be sorted together, and repeated writes append content.

Hints

Model the file store as a tree (trie) where each directory maps child names to child nodes.
Use a hash map for children so creation and lookup are fast, and only sort child names when answering a `list` query.

Quick Overview

This question evaluates proficiency in modeling hierarchical file systems, path parsing and manipulation, managing mutable file contents, and analyzing algorithmic time and space complexity within the Coding & Algorithms domain.