Problem description:

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 may be called multiple times.

Example 1:

Given buf = “abc”
read(“abc”, 1) // returns “a”
read(“abc”, 2); // returns “bc”
read(“abc”, 1); // returns “”
Example 2:

Given buf = “abc”
read(“abc”, 4) // returns “abc”
read(“abc”, 1); // returns “”

Solution:

Use two variable, readPos and writePos to store the position of read and write. Scanning from 0…n, if the position of read and write are equal, the call read4 and give the return value to writePos because it’s the number characters read from input buffer. One thing to notice is that, if writePos == 0, it means input buffer is empty, we should return current location i.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// Forward declaration of the read4 API.
int read4(char *buf);

class Solution {
public:
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    int read(char *buf, int n) {
        for (int i = 0; i < n; ++i) {
            if (readPos == writePos) {
                writePos = read4(buff); //return 3 if only 3 char left
                readPos = 0;
                if (writePos == 0) return i;
            }
            buf[i] = buff[readPos++];
        }
        return n;
    }
private:
    int readPos = 0, writePos = 0;
    char buff[4];
};

Another solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Forward declaration of the read4 API.
int read4(char *buf);

class Solution {
public:
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    char buff[4];
    int buffPtr= 0;
    int buffCnt= 0;
    
    int read(char *buf, int n) {
        int ptr= 0;
        while(ptr< n){
            if(buffPtr== 0){
                buffCnt= read4(buff);
            }
                
            while(ptr< n && buffPtr< buffCnt){
                buf[ptr++]= buff[buffPtr++];
            }
            
            // all chars in buff used up, set pointer to 0
            if(buffPtr== buffCnt) buffPtr= 0;
            // read4 returns less than 4, end of file
            if(buffCnt < 4) break;
        }
        return ptr;
    }
};

time complexity: $O()$
space complexity: $O()$
reference: