We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Read N Characters Given read4 II - Call Multiple Times

Number: 158

Difficulty: Hard

Paid? Yes

Companies: Google, Lyft, Meta, Bloomberg

Problem Description

Implement a function read(buf, n) that reads n characters from a file. The only available API to read data from the file is read4, which reads 4 consecutive characters at a time. Note that read may be called multiple times, so you need to persist between calls any extra characters read from read4.

Key Insights

  • Persist extra characters read from read4 using a class variable.
  • Use an intermediate buffer (of size 4) to store characters from read4.
  • Maintain pointers to track current position in the extra buffer.
  • When read is called, first consume the leftover characters.
  • If additional characters are required, keep calling read4 until n characters are read or the file ends.

Space and Time Complexity

Time Complexity: O(n) per call in the worst-case where n characters are requested. Space Complexity: O(1) extra space as the auxiliary buffer is of fixed size 4.

Solution

We use a leftover buffer (and two pointers indicating the current index and the count of characters available) to save any extra characters retrieved by read4 that haven't been requested yet. In each call to read, we exhaust these leftover characters first. If more characters are needed, we repeatedly call read4 until we either fill the destination buffer or run out of characters (indicating the end of the file). This design allows the function to be used across multiple calls while maintaining the file reading state.

Code Solutions

class Solution:
    def __init__(self):
        # Persistent buffer to hold characters read by read4 but not yet consumed.
        self.buffer = [''] * 4  
        self.buffPtr = 0  # Pointer to next unread character in self.buffer.
        self.buffCnt = 0  # Number of characters currently in self.buffer.
    
    # The read4 API is assumed to be defined elsewhere.
    # def read4(self, buf4: List[str]) -> int:
    
    def read(self, buf: List[str], n: int) -> int:
        index = 0  # Number of characters read so far.
        while index < n:
            if self.buffPtr == 0:
                # Refill the buffer by reading from file via read4.
                self.buffCnt = self.read4(self.buffer)
            # If no characters are read, we have reached EOF.
            if self.buffCnt == 0:
                break
            # Transfer characters from self.buffer to buf.
            while index < n and self.buffPtr < self.buffCnt:
                buf.append(self.buffer[self.buffPtr])
                self.buffPtr += 1
                index += 1
            # Reset the pointer if all characters in self.buffer are used.
            if self.buffPtr >= self.buffCnt:
                self.buffPtr = 0
        return index
← Back to All Questions