How should I practice Reference-Counted Deduplicating File System?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Citadel phone screen problems in FastPrep.

Is Reference-Counted Deduplicating File System associated with Citadel?

FastPrep tags this as a Citadel phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Design

Reference-Counted Deduplicating File System

Learn this problem

● Medium

CitadelNEW GRADPHONE SCREEN

Problem statement

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.