Katkat
Back

Low-Level Design of an In-Memory File System with mkdir and ls

Uber FreightSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

A low-level design interview question asking you to model a basic in-memory file system that supports mkdir and ls. It tests entity and class design for files and directories, representing the directory hierarchy and parent-child links, path resolution, and clear operation semantics.

Design a basic file system that supports two operations, mkdir and ls. The interviewer cares about the design and the approach rather than complete running code: draw an entity/class diagram and explain it. The discussion must cover the File and Directory entities, the directory hierarchy, how parent-child relationships are represented, how mkdir creates a directory, how ls traverses and lists contents, and the relationships between the entities and classes.

Assume an in-memory file system in a single process, with paths written as /-separated strings that start at the root /.

Clarifying Questions

  • Does mkdir create missing intermediate directories, like mkdir -p, or fail when the parent does not exist? What if the directory already exists?
  • What should ls return for a directory, for a file, and for a path that does not exist, and in what order?
  • Can a file and a directory have the same name inside the same directory?
  • Are relative paths, . and .. in scope?
  • Will several threads call the file system at the same time?

Part 1 — Entities, hierarchy and relationships

Identify the entities and classes, draw the class diagram, and explain how the directory hierarchy and the parent-child relationships are represented.

What This Part Should Cover

  • The File and Directory entities and what they share
  • How the tree and its parent-child links are stored, in both directions
  • The kind of each relationship (inheritance, composition, association), and which class owns path handling

Part 2 — mkdir

Explain, step by step, how mkdir(path) creates a directory, including its error cases.

What This Part Should Cover

  • Path parsing and resolution from the root
  • Behavior for missing parents, an existing directory, and path components that are files
  • The cost of one call in terms of path length

Part 3 — ls

Explain how ls(path) finds its target and lists the contents.

What This Part Should Cover

  • Resolving the target, and the directory and file cases
  • The output order and what it costs
  • Errors for missing paths

Hints

Hint 1

Shared and distinct: List what a file and a directory have in common and what only a directory has. Let that decide whether they share a base type and where the children are stored.

Hint 2

One component at a time: Walk the path from the root one component at a time, and decide what happens at each step when the component is missing, is a directory, or is a file.

Hint 3

Two kinds of target: `ls` on a directory and `ls` on a file behave differently. Decide where that difference lives in your classes, and how the order of the output is guaranteed.

Follow-up questions

  • Add `mv` for directories. Which parts of your design make it cheap or expensive?
  • Add file content with a `cat` operation. What changes?
  • How would you support a directory with millions of entries that `ls` must page through?
  • How would you persist this file system so it survives a restart?