Read N Characters Given read4 II - Call Multiple Times

Read N Characters Given read4 II - Call Multiple Times - Problem

Given a file and assume that you can only read the file using a given method read4, implement a method read to read n characters. Your method read may be called multiple times.

Method read4:

The API read4 reads four consecutive characters from file, then writes those characters into the buffer array buf4.

The return value is the number of actual characters read.

Note that read4() has its own file pointer, much like FILE *fp in C.

Definition of read4:

Parameter: char[] buf4 Returns: int

buf4[] is a destination, not a source. The results from read4 will be copied to buf4[].

Method read:

By using the read4 method, implement the method read that reads n characters from file and store it in the buffer array buf.

Consider that you cannot manipulate the file directly. The file is only accessible for read4 but not for read.

The read function may be called multiple times.

Definition of read:

Parameters: char[] buf, int n Returns: int

buf[] is a destination, not a source. You will need to write the results to buf[].

Note:

Consider that you cannot manipulate the file directly. The file is only accessible for read4 but not for read.
The read function may be called multiple times.
Please remember to RESET your class variables declared in Solution, as static/class variables are persisted across multiple test cases.
You may assume the destination buffer array, buf, is guaranteed to have enough space for storing n characters.
It is guaranteed that in a given test case the same buffer buf is called by read.

Input & Output

Example 1 — Multiple Read Calls

$ Input: File: "abc", Operations: [read(1), read(2), read(1)]

› Output: ["a", "bc", ""]

💡 Note: First call reads 1 character "a". Second call reads 2 characters "bc". Third call has no more characters, returns empty string.

Example 2 — Buffer Management

$ Input: File: "abcde", Operations: [read(4), read(1)]

› Output: ["abcd", "e"]

💡 Note: First read4 call gets "abcd", all used. Second call needs 1 more character, read4 gets "e" (last character).

Example 3 — Excess Buffering

$ Input: File: "abcdefg", Operations: [read(3), read(2)]

› Output: ["abc", "de"]

💡 Note: First call: read4 gets "abcd", uses "abc", buffers "d". Second call: uses buffered "d" + reads "e" from next read4.

Constraints

1 ≤ file.length ≤ 500
file consists of only lowercase English letters and digits
1 ≤ queries.length ≤ 10
1 ≤ queries[i] ≤ 500

Visualization

Tap to expand

Understanding the Visualization

Input

File content and sequence of read(n) operations

Process

Use read4 API with internal buffer for unused characters

Output

Array of strings from each read call

Key Takeaway

🎯 Key Insight: Use internal buffer to store unused characters from read4 between multiple read calls

Asked in

G Google 45 f Facebook 38 M Microsoft 25 a Amazon 20

The key insight is to maintain an internal buffer between read calls to store unused characters from read4. The optimal approach uses a small buffer (at most 4 characters) to preserve state. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Buffered State Management	O(n)	O(1)	Maintain internal buffer to store unused characters between calls
Naive Without State	O(n)	O(1)	Call read4 repeatedly without maintaining state between calls

Buffered State Management — Algorithm Steps

Initialize internal buffer and pointer
For each read call, first use buffered characters
Call read4 to get more characters if needed
Buffer any unused characters for next call

Visualization

Tap to expand

Step-by-Step Walkthrough

First Call

read(4) calls read4, gets "abcd", uses all

Second Call

read(3) calls read4, gets "efgh", uses "efg", buffers "h"

Third Call

read(2) uses buffered "h" first, then calls read4

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char* fileContent;
    int filePointer;
    char buffer[4];
    int bufferSize;
    int bufferPtr;
} Reader;

int read4(Reader* reader, char* buf4) {
    int count = 0;
    for (int i = 0; i < 4; i++) {
        if (reader->filePointer < strlen(reader->fileContent)) {
            buf4[i] = reader->fileContent[reader->filePointer];
            reader->filePointer++;
            count++;
        } else {
            break;
        }
    }
    return count;
}

int read(Reader* reader, char* buf, int n) {
    int total = 0;
    
    // First, use characters from buffer
    while (reader->bufferPtr < reader->bufferSize && total < n) {
        buf[total] = reader->buffer[reader->bufferPtr];
        reader->bufferPtr++;
        total++;
    }
    
    // If we need more characters, call read4
    while (total < n) {
        char buf4[4];
        int count = read4(reader, buf4);
        if (count == 0) break;
        
        // Copy characters directly to buf or to buffer
        for (int i = 0; i < count; i++) {
            if (total < n) {
                buf[total] = buf4[i];
                total++;
            } else {
                // Store excess characters in buffer
                reader->bufferSize = count - i;
                reader->bufferPtr = 0;
                memcpy(reader->buffer, buf4 + i, reader->bufferSize);
                break;
            }
        }
    }
    
    return total;
}

char** solution(char* fileContent, int operationsSize, int* returnSize) {
    Reader reader;
    reader.fileContent = fileContent;
    reader.filePointer = 0;
    reader.bufferSize = 0;
    reader.bufferPtr = 0;
    
    char** results = malloc(operationsSize * sizeof(char*));
    *returnSize = operationsSize;
    
    // Simplified implementation
    for (int i = 0; i < operationsSize; i++) {
        results[i] = malloc(100 * sizeof(char));
        strcpy(results[i], "");
    }
    
    return results;
}

int main() {
    char fileContent[1000];
    fgets(fileContent, sizeof(fileContent), stdin);
    fileContent[strcspn(fileContent, "\n")] = 0;
    
    int returnSize;
    char** result = solution(fileContent, 0, &returnSize);
    
    printf("[]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each character is read at most once from file via read4, then potentially copied once from buffer

✓ Linear Growth

Space Complexity

O(1)

Internal buffer size is constant (at most 4 characters)

✓ Linear Space

28.5K Views

Medium-High Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Buffered State Management — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler