Katkat
Back

Design an in-memory filesystem and circular queue

SnowflakeSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates a candidate's skills in data-structure and algorithm design, API specification, correctness reasoning, and time/space complexity analysis within the Coding & Algorithms domain by combining an in-memory hierarchical filesystem design with a fixed-size circular queue implementation.

Part A — Design an in-memory hierarchical file system. Requirements:

  • Support operations: ls(path), mkdir(path), createFile(path, content), appendToFile(path, content), readFile(path).
  • Paths are absolute UNIX-style. Root is "/". No trailing slash except for "/".
  • Error handling: if any intermediate subfolder in the path does not exist, return an error and do not create missing directories. For example, mkdir("/a/b") should error if "/a" is missing; createFile("/a/b/c.txt", ...) should error if "/a/b" is missing.
  • ls(path): if path is a directory, return its child names in lexicographic order; if path is a file, return [fileName].
  • Assume no permissions or concurrency. Handle invalid inputs (empty segment, duplicate slashes). Scale to a large number of paths efficiently. Tasks:
  1. Specify data structures and APIs.
  2. Implement the operations.
  3. Analyze time and space complexity per operation and overall.
  4. Explain edge cases around the root directory and invalid paths.

Part B — Implement a fixed-size circular queue. Requirements:

  • Constructor(capacity).
  • Operations: enQueue(x): bool, deQueue(): bool, Front(): optional<int>, Rear(): optional<int>, isEmpty(): bool, isFull(): bool.
  • All operations must be O(
  1. time and O(capacity) space. Tasks:
  2. Implement the queue.
  3. Explain your choice of data structure (e.g., doubly linked list vs circular array) and trade-offs.
  4. Prove correctness and analyze complexity.