Python solution with detailed explanation

  • 0

    Solution with discussion

    Read N Characters Given Read4 II - Call multiple times

    General Approach to solve

    • First we need to understand what this problem means - i.e. what is exactly meant by calling multiple times.
    • Think that you have 4 chars "a, b, c, d" in the file, and you want to call your function twice like this:
      read(buf, 1); // should return 'a'
      read(buf, 3); // should return 'b, c, d'
      All the 4 chars will be consumed in the first call. So the tricky part of this question is how can you preserve the remaining 'b, c, d' to the second call.
    • We use global state within the class as:
      self.temp, self.left_over_start, self.left_over_end = [""]*4, 0, -1
    • First fill up the buffer from any left over characters from previous call. If the leftovers are sufficient (i.e. n < 4 and we have sufficient leftovers), then return what we read.
    • If after reading leftovers, we still have characters left to read (i.e. n is not zero), then we initialize another variable offset2 and use it in the algorithm we devised for 157. Read N Characters Given Read4.
    class Solution(object):
        def __init__(self):
            self.temp, self.left_over_start, self.left_over_end = [""]*4, 0, -1
        def read_previous_leftover(self, buf, n):
            offset_in_buf_1 = 0
            while n and self.left_over_start <= self.left_over_end:
                buf[offset_in_buf_1] = self.temp[self.left_over_start]
                self.left_over_start, offset_in_buf_1, n = self.left_over_start + 1, offset_in_buf_1 + 1, n - 1
            return offset_in_buf_1, n
        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)
            offset_in_buf_1, n = self.read_previous_leftover(buf, n)
            if n == 0:
                return offset_in_buf_1
            offset_in_buf_2 = 0
            while True:
                x = read4(self.temp)
                # Assume n=10 and count = 9. x can be anything from 1 to 4. We need to reda 10-9 more characters.
                (self.left_over_start, self.left_over_end) = (n-offset_in_buf_2, x-1) if offset_in_buf_2 + x > n else (0, -1)
                add_char = n-offset_in_buf_2 if offset_in_buf_2 + x > n else x            
                for i in range(add_char):
                    buf[offset_in_buf_1 + offset_in_buf_2], offset_in_buf_2 = self.temp[i], offset_in_buf_2 + 1
                if x < 4 or offset_in_buf_2 == n:
            return offset_in_buf_1 + offset_in_buf_2

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.