Read N Characters Given Read4 II - Call Multiple Times

Read N Characters Given Read4 II is a classic design/buffer problem. The hard part is not the reading — it is that read gets called multiple times, so any characters you over-read on one call have to wait around for the next one. The fix is a tiny piece of persistent state: an internal buffer.

The slow way first

If you only call read4 and copy exactly what the caller asked for, you hit a wall: read4 reads in chunks of 4, but the caller might want 1. Where do the other 3 characters go? In part I you could throw them away because read was called once. Here, a later call needs them — so discarding is wrong, not just slow.

The question to ask: what must survive between calls? The answer is the leftover characters from the last read4, plus how many are left and where to resume.

The idea: a buffer that lives between calls

Keep three pieces of instance state: a 4-slot buffer buf4, a head index (the next char to serve), and a count (how many valid chars remain). On each read, serve from buf4 first; only when count hits 0 do you call read4 to refill. If read4 returns 0, the file is exhausted and you stop.

The key insight: head and count persist as fields on the object, so the over-read characters are simply still sitting in buf4 when the next call arrives.

Walk through it

Step through the animation. The first read(buf, 1) finds the buffer empty, calls read4 to load "abc" (count becomes 3), serves "a", and leaves "bc" behind. The second read(buf, 2) sees count = 2 and serves "b" then "c" straight from the buffer — no read4 at all.

Pseudocode

state: buf4[4], head = 0, count = 0     # persist across read() calls
 
read(buf, n):
    i = 0
    while i < n:
        if count == 0:                  # internal buffer empty
            count = read4(buf4)          # refill
            head = 0
            if count == 0:               # nothing left in the file
                break
        buf[i] = buf4[head]              # serve one char
        head += 1
        count -= 1
        i += 1
    return i

The Python solution

def __init__(self):
    self.buf4 = [''] * 4
    self.head = 0
    self.count = 0
 
def read(self, buf, n):
    i = 0
    while i < n:
        if self.count == 0:
            self.count = read4(self.buf4)
            self.head = 0
            if self.count == 0:
                break
        buf[i] = self.buf4[self.head]
        self.head += 1
        self.count -= 1
        i += 1
    return i

• __init__ sets up the persistent state: a 4-char buffer, plus head and count both at 0.
• The while i < n loop fills the caller buffer one char at a time until we have n (or run out).
• if self.count == 0 is the refill check — only then do we call read4 and reset head to 0.
• The inner if self.count == 0: break after refilling catches end-of-file: read4 returned nothing.
• Lines 14-17 serve a single char from buf4[head], then advance head, shrink count, and bump i.
• return i reports how many characters we actually delivered — which may be fewer than n at EOF.

Complexity

The extra space is O(1) — the buffer is always exactly 4 slots, no matter how big the file or how many times read is called. All the cleverness is in remembering those 4 slots between calls.

When this pattern shows up

Practice