158.Read N Characters Given Read4 II - Call multiple times

Tags: [queue], [data_structure], [file], [file_system], [cache]

Com: {fb}

Link: https://leetcode.com/problems/read-n-characters-given-read4-ii-call-multiple-times/\#/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 theread4API, implement the functionint read(char *buf, int n)that readsncharacters from the file.

Note:
The readfunction may be called multiple times.

Solution: Queue

# The read4 API is already defined for you.
# @param buf, a list of characters
# @return an integer
# def read4(buf):

from collections import deque

class Solution(object):
    def __init__(self):
        self.queue = deque()

    def read(self, buf, n):
        """
        :type buf: Destination buffer (List[str])
        :type n: Maximum number of characters to read (int)
        :rtype: The number of characters read (int)
        """
        if not n:
            return 0

        # If there are no enough chars in queue, 
        # read chars from file by read4, and load them into the queue.
        while len(self.queue) < n:
            sub_buf = ['' for _ in xrange(4)]
            num_of_chars = read4(sub_buf)
            if not num_of_chars:
                break

            sub_index = 0
            while sub_index < num_of_chars:
                self.queue.append(sub_buf[sub_index])
                sub_index += 1

        # Load the chars from queue into buf.
        index = 0
        while self.queue and index < n:
            buf[index] = self.queue.popleft()
            index += 1

        return index

Revelation:

• read4() each time will try its best to fetch 4 chars, but we may not use out of these chars. And read(buf, n) will called multiple times, so we need use a container to store the chars which not get used.
• There are two main approaches for this problem.
• One is 'lazy fetch', which means each time we try to consume from the queue, if the chars are not enough, then we load from file by calling read4(), if there are chars not be used, we put them back into the queue.
• The other approach is 'pre fetch', this time we need n chars, we first check whether the chars in the queue is enough or not. If not, we read the file by calling the read4(), to load the chars into queue, we keep loading the chars into the queue, until the len(queue) >= n, then we consume chars from the queue. Here we use this approach, because applying this approach, the code become more readable and clear.

Note:

• Time complexity = O(n).