Implement write with internal buffer
Company: Datadog
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a buffered writer over an expensive sink API. You are given a function writeToDevice(byte[] chunk) that may accept at most M bytes per call and has high per-call overhead. Implement a class BufferedWriter with methods: write(byte[] data), flush(), and close(). Requirements: maintain byte order across multiple calls, minimize the number of writeToDevice calls, handle inputs larger than the internal buffer, and ensure no data loss on flush/close. Describe your buffer management, edge cases across consecutive writes, and the time/space complexity. Optionally discuss how you would add thread-safety.
Quick Answer: This question evaluates proficiency with buffered I/O, buffer management, memory handling, and performance optimization, including maintaining byte order, handling partial writes, and edge cases across consecutive write/flush/close operations.
You must simulate a buffered writer over an expensive device API. The device API writeToDevice may accept at most M bytes per call. Implement a function process_operations(ops, M, B) that processes a sequence of operations on a BufferedWriter with internal capacity B and returns the exact sequence of chunks passed to writeToDevice, preserving byte order and obeying the limit M. Operations are objects: {"op": "write", "data": [ints 0..255]}, {"op": "flush"}, or {"op": "close"}. Semantics and policy (to make output deterministic and minimize device calls): 1) write(data): append bytes to the internal buffer; if the buffer becomes full, immediately write min(M, current_buffer_size) bytes from the front of the buffer to the device to free space; repeat as needed while processing the same write call. 2) If the buffer is empty and the current write call has at least B bytes remaining, bypass the buffer and write chunks directly to the device in maximum chunks of size up to M, repeating until fewer than B bytes remain in this write; any remaining (< B) bytes are buffered. 3) flush(): write all remaining buffered bytes to the device in chunks of size up to M, leaving the buffer empty. 4) close(): same as flush(), then no further writes should occur (tests will not issue writes after close). Return the list of device chunks in call order. No device write may exceed M bytes, and no data may be lost.
Constraints
- 1 <= M <= 100000
- 1 <= B <= 100000
- 1 <= len(ops) <= 100000
- Sum of lengths of all write data <= 200000
- Byte values are integers in [0, 255]
- Operations are processed sequentially; writes after close will not be present in tests
Hints
- Use a FIFO structure (e.g., deque) to implement the internal buffer efficiently.
- When the buffer is full during write(), spill only min(M, len(buffer)) bytes to free space; do not drain the small tail unless flushing.
- When the buffer is empty and the write batch is large (>= B), bypass the buffer and send maximum chunks (size up to M) directly.
- flush() must drain the buffer completely in chunks of size up to M; close() should call flush().