Read N Characters Given Read4 II - Call Multiple Times

hard string simulation queue interactive

Problem

Implement read(buf, n) using read4 such that read may be called multiple times. Between calls, any chars from a previous read4 that were not yet consumed must be kept and served first on the next call.

Inputfile = "abcdefg", calls = [read(1), read(2), read(4)]

Output["a", "bc", "defg"]

First call consumes 'a' from the read4 result; "bcd" stays in the buffer for the next call.

file

calls (comma-separated n's)

class Solution:
    def __init__(self):
        self.buf4 = [''] * 4
        self.head = 0
        self.size = 0

    def read(self, buf, n):
        total = 0
        while total < n:
            if self.size == 0:
                self.size = read4(self.buf4)
                self.head = 0
                if self.size == 0:
                    break
            take = min(self.size, n - total)
            for i in range(take):
                buf[total + i] = self.buf4[self.head + i]
            self.head += take
            self.size -= take
            total += take
        return total

class Solution {
  constructor() {
    this.buf4 = new Array(4);
    this.head = 0;
    this.size = 0;
  }
  read(buf, n) {
    let total = 0;
    while (total < n) {
      if (this.size === 0) {
        this.size = read4(this.buf4);
        this.head = 0;
        if (this.size === 0) break;
      }
      const take = Math.min(this.size, n - total);
      for (let i = 0; i < take; i++) buf[total + i] = this.buf4[this.head + i];
      this.head += take;
      this.size -= take;
      total += take;
    }
    return total;
  }
}

public class Solution extends Reader4 {
    private char[] buf4 = new char[4];
    private int head = 0, size = 0;

    public int read(char[] buf, int n) {
        int total = 0;
        while (total < n) {
            if (size == 0) {
                size = read4(buf4);
                head = 0;
                if (size == 0) break;
            }
            int take = Math.min(size, n - total);
            for (int i = 0; i < take; i++) buf[total + i] = buf4[head + i];
            head += take;
            size -= take;
            total += take;
        }
        return total;
    }
}

class Solution {
    char buf4[4];
    int head = 0, size = 0;
public:
    int read(char* buf, int n) {
        int total = 0;
        while (total < n) {
            if (size == 0) {
                size = read4(buf4);
                head = 0;
                if (size == 0) break;
            }
            int take = min(size, n - total);
            for (int i = 0; i < take; i++) buf[total + i] = buf4[head + i];
            head += take;
            size -= take;
            total += take;
        }
        return total;
    }
};

Explanation

The hard part of this version is that read can be called many times, and read4 always grabs up to 4 characters at once. If a call needs fewer than what read4 returned, the leftover characters must survive until the next call. The fix is a small persistent buffer stored on the object.

We keep three fields between calls: buf4 (the last 4-char chunk), head (index of the next unread char in it), and size (how many chars are still unread). Because they live on the instance, leftovers carry over automatically.

Inside read, we loop until we have delivered n characters. Whenever the buffer is empty (size == 0), we refill it with a fresh read4 and reset head; if that returns 0 we have hit end of file and stop. Otherwise we copy take = min(size, n - total) characters out, then advance head, shrink size, and grow total.

Example: file "abcdefg" with calls read(1), read(2), read(4). The first call triggers read4 which loads "abcd"; it takes just "a" and leaves "bcd" buffered. The next call serves "bc" from the buffer, then "defg" is read for the final call. Outputs: ["a", "bc", "defg"].

Time: O(n) per call Space: O(1) persistent buffer of 4