Problem

Using a read7() method that returns 7 characters from a file, implement readN(n) which reads n characters.

For example, given a file with the content “Hello world”, three read7() returns “Hello w”, “orld” and then “”.

Solution

Method 1 - Using Iteration

Here are the steps:

  1. Buffer Management: Maintain a buffer to store characters read by read7() that weren’t consumed by readN(n) calls.
  2. Reading n Characters: Continuously read using read7() until we have at least n characters in total. If read7() returns fewer than 7 characters, we’ve likely reached the end of the file.
  3. Serve the Required Characters: Serve characters from the buffer to fulfill the readN(n) request.

Code

 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

public class FileReader {
    private String content;
    private int index;

    public FileReader(String content) {
        this.content = content;
        this.index = 0;
    }

    public String read7() {
        if (index >= content.length()) {
            return "";
        }
        int end = Math.min(index + 7, content.length());
        String result = content.substring(index, end);
        index += 7;
        return result;
    }
}


public class Solution {
    private FileReader fileReader;
    private Queue<Character> buffer;

    public Solution(FileReader fileReader) {
        this.fileReader = fileReader;
        this.buffer = new LinkedList<>();
    }

    public String readN(int n) {
        StringBuilder result = new StringBuilder();

        while (result.length() < n) {
            // If buffer is empty, read more characters using read7()
            if (buffer.isEmpty()) {
                String readData = fileReader.read7();
                if (readData.isEmpty()) {
                    break;
                }
                for (char c : readData.toCharArray()) {
                    buffer.offer(c);
                }
            }

            // Add buffered characters to the result
            while (!buffer.isEmpty() && result.length() < n) {
                result.append(buffer.poll());
            }
        }

        return result.toString();
    }
}
 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

class FileReader:
    def __init__(self, content):
        self.content = content
        self.index = 0

    def read7(self):
        if self.index >= len(self.content):
            return ""
        result = self.content[self.index : self.index + 7]
        self.index += 7
        return result

class Solution:
    def __init__(self, file_reader):
        self.file_reader = file_reader
        self.buffer = []

    def readN(self, n):
        result = []

        while len(result) < n:
            if not self.buffer:
                self.buffer = list(self.file_reader.read7())
                if not self.buffer:
                    break

            remaining_len = n - len(result)
            result += self.buffer[:remaining_len]
            self.buffer = self.buffer[remaining_len:]

        return "".join(result)

Complexity

  • ⏰ Time complexity: O(n)  - Creating and initializing the FileReader and Solution objects themselves are ( O(1) ) operations and do not depend on input size ( n ).  - The main work is done in the readN(int n) method.
    • Every time read7() is called, it processes up to 7 characters. Therefore, in the worst-case scenario, read7() will be called ( O(\frac{n+6}{7}) = O(\frac{n}{7}) ) times to read n characters.
    • Each character read by read7() is processed in constant time ( O(1) ).
  • 🧺 Space complexity: O(n)
    • The buffer is used to store up to 6 unused characters from read7(). Hence, the buffer space is at most 6 characters.
    • The result string that stores characters read from the buffer and read7() can hold up to n characters.
    • Other variables such as the StringBuilder and counters (like result, remaining_len) use constant space.