My first Citadel SWE interview. The interviewer was on the hedge fund side. I gave a brief introduction. Before I had a chance to tell the behavioral stories I'd prepared, he went straight into technical questions. The interview was basically 100% coding and system design.
Problem:
Suppose a file system contains files with identical contents. For example, /a/b/c.txt and /a/b/e.txt both contain the string "hello". How would you optimize storage space?
Initial approach
When a new file is written, calculate a hash to check whether the content already exists.
If identical content already exists, point to the single existing copy on disk through something like a soft link / symbolic link, avoiding duplicate storage.
Follow-up:
The interviewer pointed out that hashing every write was too expensive. How could I optimize it?
Optimization: Keep the size of each file. On a write, first check whether the global collection already contains a file of the same size. Only calculate and compare hashes when the size matches. Otherwise, just store the size and path. This greatly reduces the cost of hashing large files.
Code implementation
I used Python. The interviewer gave me a FileSystem class skeleton and asked me to implement writefile(path, data) and readfile(path).
Data structure design
fs: A dictionary mapping path to data, simulating actual physical storage on disk.
shared_files: A dictionary mapping path to original_path, simulating symbolic links.
global_set: A dictionary maintaining the global index. The key is the file size, and the value is a list of (hash_value, original_path) pairs.
The interviewer supplied a simple hash(x) function as a mock.
The writefile(path, data) logic:
Get the incoming data's size, size = len(data), and calculate its data_hash.
Check whether size is in global_set. If it is, traverse the corresponding list and compare hashes. If an identical hash is found, a duplicate file exists. Record a mapping in shared_files, self.shared_files[path] = original_path, as a soft link, and return early.
If the size isn't present or no hash matches, write the actual content into physical storage, self.fs[path] = data, and append the current (data_hash, path) pair to global_set[size].
The readfile(path) logic:
First check whether the target path exists in shared_files.
If it's a soft link, get the original file path it points to, orig_path, and return self.fs[orig_path]. Otherwise, return the actual content directly from self.fs[path].
Follow-up:
Finally, the interviewer asked me to verbally summarize the full design with Delete added: put reference counts in global_set, mount identical writes onto a shared storage pool, decrement the count on deletion, and clear the underlying block when the count reaches zero.
There was no time left for behavioral questions, so we went straight to Q&A.
Discussion
Loading comments…