Implement write with internal buffer

Q: Implement write with internal buffer

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.

Q: How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

Q: What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Datadog.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Datadog during technical interviews.

Question

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.

PracHub · Accepted Answer

from collections import deque

def process_operations(ops: list, M: int, B: int) -> list:
    device_calls = []

def writeToDevice(chunk):
        if not chunk:
            return
        if len(chunk) > M:
            raise ValueError("Device call exceeds M bytes")
        device_calls.append(list(chunk))

class BufferedWriter:
        def __init__(self, M: int, B: int, sink):
            self.M = M
            self.B = B
            self.sink = sink
            self.buf = deque()  # holds ints
            self.closed = False

def _spill_from_buffer(self):
            if not self.buf:
                return
            k = min(self.M, len(self.buf))
            out = []
            for _ in range(k):
                out.append(self.buf.popleft())
            self.sink(out)

def write(self, data):
            if self.closed:
                raise ValueError("write after close")
            i = 0
            n = len(data)
            while i < n:
                # Direct pass when buffer is empty and the current write has at least B bytes remaining
                if not self.buf and (n - i) >= self.B:
                    send = min(self.M, n - i)
                    self.sink(data[i:i + send])
                    i += send
                    continue
                # Ensure there is space in the buffer; if full, spill to free space
                if len(self.buf) == self.B:
                    self._spill_from_buffer()
                    continue
                # Buffer as much as fits
                space = self.B - len(self.buf)
                take = min(space, n - i)
                if take > 0:
                    self.buf.extend(data[i:i + take])
                    i += take
                # Next loop iteration will spill if needed

def flush(self):
            while self.buf:
                self._spill_from_buffer()

def close(self):
            if not self.closed:
                self.flush()
                self.closed = True

writer = BufferedWriter(M, B, writeToDevice)

for op in ops:
        typ = op.get('op')
        if typ == 'write':
            data = op.get('data', [])
            writer.write(data)
        elif typ == 'flush':
            writer.flush()
        elif typ == 'close':
            writer.close()
        else:
            raise ValueError(f"Unknown operation: {typ}")

return device_calls

Maintain a FIFO buffer (deque) with capacity B. On write(data), if the buffer is empty and at least B bytes remain in this write, bypass the buffer and send chunks directly to the device with size up to M, repeating until fewer than B remain. Otherwise buffer bytes until full; when full, spill min(M, len(buffer)) bytes from the front to free space, which minimizes calls by keeping the small tail in the buffer for future coalescing. flush() drains the buffer fully in chunks of size up to M. close() calls flush() and marks the writer closed. All device writes preserve byte order and never exceed M bytes.

Quick Overview

Solution

Explanation

Hints

Quick Overview