In-Memory Filesystem (Op-Replay)

Reported in interviews at Hudson River Trading

Problem statement

Implement an in-memory filesystem as a single pure function that replays a list of operations and returns the results of the query operations, in order.

There is one root directory /. Paths are absolute, slash-separated (for example /a/b/c); the root path is /. The operations are:

  • ["mkdir", path] - create the directory at path, creating any missing intermediate directories. Returns nothing.
  • ["addContentToFile", path, content] - if the file at path does not exist, create it (creating any missing parent directories); then append the string content to the file's current content. Returns nothing.
  • ["readContentFromFile", path] - return the file's full concatenated content (all appended pieces in order).
  • ["ls", path] - if path is a file, return a list containing only that file's name; otherwise return the list of names (files and subdirectories) directly under the directory path, sorted in lexicographic (ascending) order.

Implement:

def runFs(ops):
    ...

where ops is a list of operations as described. Return a list containing the result of each ls and each readContentFromFile operation, in the order those operations appear (mkdir and addContentToFile produce no entry in the returned list). You may assume every operation is valid (no reading a nonexistent file, no ls of a nonexistent path).

Constraints: $1 \le \lvert \text{ops} \rvert \le 10^4$; paths and contents consist of lowercase letters; directory and file names are non-empty.

Example: ops = [["ls", "/"], ["mkdir", "/a/b/c"], ["addContentToFile", "/a/b/c/d", "hello"], ["ls", "/"], ["readContentFromFile", "/a/b/c/d"]].

  • ls / on the empty filesystem returns [].
  • mkdir /a/b/c creates directories a, a/b, a/b/c (no output).
  • addContentToFile /a/b/c/d hello creates file d and writes "hello" (no output).
  • ls / now returns ["a"] (only a lives directly under root).
  • readContentFromFile /a/b/c/d returns "hello".

So the returned list is [[], ["a"], "hello"].

Show hint

What single node type could represent both a directory and a file so that every operation looks alike?

Relevant roles: ML Engineer, MLOps Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems