Read N Characters Given Read4 Ii Call Multiple Times - Leetcode Solution

Problem Statement:

The read4 API is already defined for you.

int read4(char *buf4);

buf4: A temporary buffer to store the result. 
Returns the number of actual characters read.

Implement the read function as follows:

int read(char *buf, int n);

buf: The buffer that will store the results.
n: The number of characters to read.

The read function may be called multiple times.

Example 1:

Input: file = "abc", queries = [1,2,1]
Output: [1,2,1]
Explanation: The first query reads 1 character using read4, so buf = "a". The second query reads 2 characters using read4, so buf = "bc". The third query reads 1 character using read4, so buf = "".

Example 2:

Input: file = "abcde", queries = [5]
Output: [5]
Explanation: The only query reads 5 characters using read4, so buf = "abcde".

Solution:

In this problem, we have to read the given number of characters from the file. The file is represented by read4 API which reads the next 4 characters from the file and returns the actual number of characters read. The read function must be called multiple times to read all the characters from the file. We have to read the given number of characters in each call to the read function.

Algorithm:

1. Define a class named Solution which will contain the implementation of read function.
2. Use two variables to keep track of the number of characters read and the number of characters stored in the buffer.
3. Define a buffer of size 4 which will store the characters read from the file using read4 API.
4. Define a queue or any other data structure to store the characters that are read but not yet consumed by the user.
5. In the read function, first check whether there are any characters in the queue. If yes, consume them and return the requested number of characters.
6. If there are no characters in the queue, call the read4 API to read the next chunk of characters from the file.
7. Add the read characters to the queue.
8. If the number of characters read from the file is equal to the requested number of characters, consume them and return.
9. If the number of characters read from the file is less than the requested number of characters, repeat steps 6 to 8.
10. If all the characters in the file are read and there are still some characters in the queue, consume them and return.

Time Complexity:

The time complexity of this algorithm is O(n) where n is the total number of characters in the file. This is because we need to read every character in the file at least once.

Space Complexity:

The space complexity of this algorithm is O(1) because we are using a fixed-size buffer of size 4 and a queue to store the read but not yet consumed characters. The size of the queue will not exceed 4 at any point in time.

Code Implementation:

1