FastPrepReference-Counted Deduplicating File System
Problems/Reference-Counted Deduplicating File System

Reference-Counted Deduplicating File System

Citadel logoCitadel● MediumNEW GRADPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: The report defines write, read, delete, size-first hashing, content deduplication, and reference-counted reclamation, but omits a portable operation encoding, lifecycle edge behavior, collision handling, and bounds. The judged core task matches the visible source at about 84%.

Implement an in-memory file system that processes an ordered sequence of operations. Logical paths may share one physical copy when their file contents are identical. The file system starts empty.

Each row of operations has one of these forms:

  • ["WRITE", path, data]: If path already exists, release its current reference first and immediately remove a physical block whose reference count becomes zero. Then store data at path. Search only physical blocks with the same data length. When that size bucket is nonempty, use the mock hash equal to the sum of the data's ASCII character codes to narrow the candidates, and confirm a match with an exact content comparison. Reuse a matching block or create a new physical block.
  • ["READ", path]: Read the content referenced by path.
  • ["DELETE", path]: Remove path. Decrement its block's reference count and release the physical block when the count reaches zero.

Return one row for each operation, in order:

  • A WRITE returns ["true"] when it creates a new physical copy and ["false"] when it reuses an existing copy.
  • A successful READ returns [data]. A missing read is the portable representation of null and returns an empty row [].
  • A DELETE returns ["true"] when it removes an existing logical path and ["false"] when the path is missing.

Physical blocks are independent of the path that first introduced them. Deleting that path must not affect other logical paths that still reference the same block. Hash collisions do not imply equal content.

Function

processFileOperations(operations: String[][]) → String[][]

Examples

Example 1

operations = [["WRITE","/a","alpha"],["WRITE","/b","alpha"],["READ","/b"],["DELETE","/a"],["READ","/b"],["DELETE","/b"],["READ","/b"]]return = [["true"],["false"],["alpha"],["true"],["alpha"],["true"],[]]

The first write allocates a block. The second path shares it. Deleting /a leaves the shared content readable through /b; deleting the final reference releases the block, so the last read returns an empty row.

Example 2

operations = [["WRITE","/left","ab"],["WRITE","/right","ba"],["WRITE","/copy","ab"],["DELETE","/left"],["READ","/copy"],["READ","/right"]]return = [["true"],["true"],["false"],["true"],["ab"],["ba"]]

ab and ba have the same length and mock hash, but their exact contents differ, so each needs a physical block. The third write shares the ab block, which remains available after /left is deleted.

Example 3

operations = [["WRITE","/x","red"],["WRITE","/y","red"],["WRITE","/x","blue"],["DELETE","/missing"],["READ","/x"],["READ","/y"],["WRITE","/y","blue"],["DELETE","/x"],["READ","/y"]]return = [["true"],["false"],["true"],["false"],["blue"],["red"],["false"],["true"],["blue"]]

Overwriting /x releases only its reference to red, which remains alive through /y, and creates a new blue block. Overwriting /y later releases the final red reference and shares the existing blue block.

Constraints

  • 1 <= operations.length <= 100000.
  • Every operation has exactly one of the documented forms, and command names are uppercase.
  • Each path is a non-empty printable ASCII string of length at most 128.
  • Each data value is a printable ASCII string of length at most 100000; an empty string is allowed.
  • The total length of all data values in WRITE operations is at most 1000000.
  • Paths and file contents are compared case-sensitively.

More Citadel problems

  • Portfolio Tickers with Constant-Time Random PickPHONE SCREEN · Seen Nov 2026
  • Square Root FunctionPHONE SCREEN · Seen Oct 2026
  • Reachable Transfer PositionsPHONE SCREEN · Seen Oct 2026
All Citadel interview questionsSee Citadel hiring insights
Saved
class Solution {
    public String[][] processFileOperations(String[][] operations) {
        // Write your code here
    }
}
Checking account…