Read N Characters Given Read4

• https://leetcode.com/problems/read-n-characters-given-read4/
• https://leetcode.com/problems/read-n-characters-given-read4-ii-call-multiple-times/

The API: int read4(char *buf) reads 4 characters at a time from a file.

The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.

By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.

Note: The read function will only be called once for each test case.

Solution:

When read4 returns less than 4, we know it must reached the end of file. However, take note that read4 returning 4 could mean the last 4 bytes of the file.

To make sure that the buffer is not copied more than n bytes, copy the remaining bytes (n – readBytes) or the number of bytes read, whichever is smaller. ( If we read more than we supposed to, copy back the extra read value using buffer[4] )

public int read(char[] buf, int n) {
    char[] buffer = new char[4];
    int readBytes = 0;
    boolean eof = false;

    while (!eof && readBytes < n) {
        int sz = read4(buffer);
        if (sz < 4) eof = true;
        int bytes = Math.min(n - readBytes, sz); System.arraycopy(buffer /* src */, 0 /* srcPos */,
                       buf /* dest */, readBytes /* destPos */, bytes /* length */);
         readBytes += bytes;
    }
    return readBytes;
}

Follow up:

The read function may be called multiple times.

For example

["AB"] [Read(1);Read(2)]

["A"] ["B"]

Solution:

buffer – An array of size 4 use to store data returned by read4 temporarily. If the characters were read into the buffer and were not used partially, they will be used in the next call.

offset – Use to keep track of the offset index where the data begins in the next read call. The buffer could be read partially (due to constraints of reading up to n bytes) and therefore leaving some data behind.

bufsize – The real buffer size that stores the actual data. If bufsize > 0, that means there is partial data left in buffer from the last read call and we should consume it before calling read4 again. On the other hand, if bufsize == 0, it means there is no data left in buffer.

public int read(char[] buf, int n) {
    int readBytes = 0;
    boolean eof = false;

    while (!eof && readBytes < n) {
        if (bufsize == 0) {
            bufsize = read4(buffer); // it is possible we read more values
            eof = bufsize < 4;
        }
        // (n - readBytes) - remanning bytes need to be read
        // bufsize - actual bytes read
        int bytes = Math.min(n - readBytes, bufsize);
        System.arraycopy(buffer/* src */, offset/* srcPos */, buf/* dest */, readBytes/* destPos */, bytes/*length*/);
        offset = (offset + bytes) % 4;
        bufsize -= bytes;
        readBytes += bytes;
    }
    return readBytes;
}