Read N Characters Given read4 II - Call Multiple Times solution and explanation
Google
9 more videos on this problem
LeetCode 158. Read N Characters Given Read4 II - Call multiple times Explanation and Solutionhappygirlzt · 4:02 · 6K views
Leetcode 157/158 Read N Characters Given Read 4 I/IIRen Zhang · 23:39 · 5K views
LeetCode 157 & 158. Read N Characters Given Read4 II - Call multiple times Solutionhappygirlzt · 9:26 · 5K views
Google Coding Interview Question | Leetcode 158 | Read N Characters Given Read4 IIWorkWithGoogler · 9:21 · 3K views
Leetcode 158(hard). Read N Characters Given Read4 II Call multiple times【String】中文AndroidBabies安卓大宝贝们 · 13:07 · 1K views
LeetCode 158. Read N Characters Given Read4 II - Call multiple times | JSer - JavaScript & AlgorithmJSer · 5:01 · 1K views
leetcode158 Read N Characters Given Read4 II - Call multiple timesBonnie · 10:01 · 1K views
LeetCode 158. Read N Characters Given Read4 II - Call multiple times | Locked Problem宰相小甘罗 · 5:07 · 763 views
LeetCode 158. Read N Characters Given Read4 II - Call multiple times 中文 | 加锁题宰相小甘罗 · 4:16 · 686 views
Leetcode 158. Read N Characters Given read4 II - Call Multiple Times in Python | Python LeetcodeCode is Art · 3:03 · 150 views
The problem
Given a file and assume that you can only read the file using a given method read4, implement a method read to read n characters. Your method read may be called multiple times.
Method read4:
The API read4 reads four consecutive characters from file, then writes those characters into the buffer array buf4.
The return value is the number of actual characters read.
Note that read4() has its own file pointer, much like FILE *fp in C.
Definition of read4:
Parameter: char[] buf4
Returns: int
buf4[] is a destination, not a source. The results from read4 will be copied to buf4[].
Below is a high-level example of how read4 works:
File file("abcde"); // File is "abcde", initially file pointer (fp) points to 'a'
char[] buf4 = new char[4]; // Create buffer with enough space to store characters
read4(buf4); // read4 returns 4. Now buf4 = "abcd", fp points to 'e'
read4(buf4); // read4 returns 1. Now buf4 = "e", fp points to end of file
read4(buf4); // read4 returns 0. Now buf4 = "", fp points to end of file
Method read:
By using the read4 method, implement the method read that reads n characters from file and store it in the buffer array buf. Consider that you cannot manipulate file directly.
The return value is the number of actual characters read.
Definition of read:
Parameters: char[] buf, int n
Returns: int
buf[] is a destination, not a source. You will need to write the results to buf[].
Note:
- Consider that you cannot manipulate the file directly. The file is only accessible for
read4but not forread. - The read function may be called multiple times.
- Please remember to RESET your class variables declared in Solution, as static/class variables are persisted across multiple test cases. Please see here for more details.
- You may assume the destination buffer array,
buf, is guaranteed to have enough space for storingncharacters. - It is guaranteed that in a given test case the same buffer
bufis called byread.
Example 1:
Input: file = "abc", queries = [1,2,1]
Output: [1,2,0]
Explanation: The test case represents the following scenario:
File file("abc");
Solution sol;
sol.read(buf, 1); // After calling your read method, buf should contain "a". We read a total of 1 character from the file, so return 1.
sol.read(buf, 2); // Now buf should contain "bc". We read a total of 2 characters from the file, so return 2.
sol.read(buf, 1); // We have reached the end of file, no more characters can be read. So return 0.
Assume buf is allocated and guaranteed to have enough space for storing all characters from the file.
Example 2:
Input: file = "abc", queries = [4,1]
Output: [3,0]
Explanation: The test case represents the following scenario:
File file("abc");
Solution sol;
sol.read(buf, 4); // After calling your read method, buf should contain "abc". We read a total of 3 characters from the file, so return 3.
sol.read(buf, 1); // We have reached the end of file, no more characters can be read. So return 0.
Constraints:
1 <= file.length <= 500fileconsist of English letters and digits.1 <= queries.length <= 101 <= queries[i] <= 500
Approach overview
Problem Overview: Implement read(n) using the provided read4() API, which reads up to 4 characters from a file at a time. The catch: read() may be called multiple times, so leftover characters from previous calls must be preserved.
Approach 1: Stateless read4 Calls (Naive Simulation) (Time: O(n), Space: O(1))
The simplest idea repeatedly calls read4() until n characters are collected or the file ends. Each call copies characters directly into the destination buffer. This works for a single invocation of read(), but it fails when the function is called multiple times because extra characters returned by read4() are discarded instead of saved. The approach demonstrates the mechanics of the read4 API but ignores persistent state across calls.
Approach 2: Persistent Internal Buffer (Optimal Simulation) (Time: O(n), Space: O(1))
The correct solution maintains an internal buffer that stores unused characters returned by read4(). When read(n) is called, you first consume characters from this leftover buffer before requesting more data from read4(). If read4() returns more characters than needed, the extra ones stay in the internal buffer for the next call. This design ensures no characters are lost across calls while still reading the file in chunks of four.
Implementation typically uses a small array of size 4 plus two pointers: one pointer tracks the current read position inside the temporary buffer, and another tracks how many valid characters are stored. When the buffer is exhausted, call read4() again to refill it. The logic becomes a straightforward simulation of file streaming.
This problem mainly tests careful state management and API interaction rather than complex algorithms. The pattern frequently appears in system design scenarios where data arrives in chunks and consumers read arbitrary amounts. It connects closely to array manipulation and simulation techniques, and it is categorized as an interactive style problem because the solution interacts with a provided API.
Recommended for interviews: The persistent buffer approach is what interviewers expect. The naive approach shows you understand how read4() works, but the optimal solution demonstrates correct state handling across multiple function calls.
Solution
# The read4 API is already defined for you.
# def read4(buf4: List[str]) -> int:
class Solution:
def __init__(self):
self.buf4 = [None] * 4
self.i = self.size = 0
def read(self, buf: List[str], n: int) -> int:
j = 0
while j < n:
if self.i == self.size:
self.size = read4(self.buf4)
self.i = 0
if self.size == 0:
break
while j < n and self.i < self.size:
buf[j] = self.buf4[self.i]
self.i += 1
j += 1
return j/**
* The read4 API is defined in the parent class Reader4.
* int read4(char[] buf4);
*/
public class Solution extends Reader4 {
private char[] buf4 = new char[4];
private int i;
private int size;
/**
* @param buf Destination buffer
* @param n Number of characters to read
* @return The number of actual characters read
*/
public int read(char[] buf, int n) {
int j = 0;
while (j < n) {
if (i == size) {
size = read4(buf4);
i = 0;
if (size == 0) {
break;
}
}
while (j < n && i < size) {
buf[j++] = buf4[i++];
}
}
return j;
}
}/**
* The read4 API is defined in the parent class Reader4.
* int read4(char *buf4);
*/
class Solution {
public:
/**
* @param buf Destination buffer
* @param n Number of characters to read
* @return The number of actual characters read
*/
int read(char* buf, int n) {
int j = 0;
while (j < n) {
if (i == size) {
size = read4(buf4);
i = 0;
if (size == 0) break;
}
while (j < n && i < size) buf[j++] = buf4[i++];
}
return j;
}
private:
char* buf4 = new char[4];
int i = 0;
int size = 0;
};/**
* The read4 API is already defined for you.
*
* read4 := func(buf4 []byte) int
*
* // Below is an example of how the read4 API can be called.
* file := File("abcdefghijk") // File is "abcdefghijk", initially file pointer (fp) points to 'a'
* buf4 := make([]byte, 4) // Create buffer with enough space to store characters
* read4(buf4) // read4 returns 4. Now buf = ['a','b','c','d'], fp points to 'e'
* read4(buf4) // read4 returns 4. Now buf = ['e','f','g','h'], fp points to 'i'
* read4(buf4) // read4 returns 3. Now buf = ['i','j','k',...], fp points to end of file
*/
var solution = func(read4 func([]byte) int) func([]byte, int) int {
buf4 := make([]byte, 4)
i, size := 0, 0
// implement read below.
return func(buf []byte, n int) int {
j := 0
for j < n {
if i == size {
size = read4(buf4)
i = 0
if size == 0 {
break
}
}
for j < n && i < size {
buf[j] = buf4[i]
i, j = i+1, j+1
}
}
return j
}
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stateless read4 Simulation | O(n) | O(1) | Useful for understanding the read4 API or when read() is guaranteed to be called only once |
| Persistent Internal Buffer | O(n) | O(1) | Required when read() can be called multiple times and leftover characters must be preserved |
Frequently asked questions
Is Read N Characters Given read4 II - Call Multiple Times easy or hard?
The problem is typically labeled Hard because it requires handling multiple function calls with persistent state. The algorithm itself is simple simulation, but managing leftover characters correctly across calls introduces subtle edge cases.
Read N Characters Given read4 II - Call Multiple Times Python/Java solution
Implement a class-level buffer of size 4 plus two integers tracking the current index and number of valid characters. In Python, Java, C++, or Go, the read(n) method repeatedly consumes buffered characters and calls read4() when needed. Extra characters returned by read4() remain stored for the next invocation.
How to solve Read N Characters Given read4 II - Call Multiple Times in O(n)?
Maintain a small internal buffer of size 4 along with two pointers: one for the current read position and one for the number of valid characters in the buffer. First consume leftover characters from previous calls. When the buffer becomes empty, call read4() to refill it and continue copying into the destination buffer until n characters are read or EOF is reached.
What is the best approach for Read N Characters Given read4 II - Call Multiple Times?
The best approach uses a persistent internal buffer to store leftover characters returned by read4(). Each call to read(n) first consumes characters from this buffer before calling read4() again. This prevents losing characters when read4() returns more than needed and supports multiple invocations correctly. The overall complexity remains O(n) time and O(1) extra space.
Is Read N Characters Given read4 II - Call Multiple Times asked at Google/Amazon/Meta?
This problem has historically appeared in Meta (Facebook) interview preparation materials and is commonly discussed in system-style API simulation questions. Variants involving read4 are widely referenced in interviews focused on API design, state management, and streaming data handling.
What data structure is used in Read N Characters Given read4 II - Call Multiple Times?
The solution uses a fixed-size array (size 4) as a temporary buffer along with pointer indices to track the current read position and available characters. No advanced data structures are required; careful buffer management and simulation logic are the key aspects.
What is the time complexity of Read N Characters Given read4 II - Call Multiple Times?
The time complexity is O(n), where n is the number of characters requested by read(). Each character is copied at most once into the destination buffer. The read4() API is called roughly n/4 times in the worst case, so the total work still scales linearly.