OS-Flavor Coding Problems — Read4, Task Scheduler

Key Insight: Read in fixed-size chunks (4 bytes) into a temporary buffer and copy to the output buffer, stopping on either of two conditions: you have read n bytes, or read4 returned fewer than 4 bytes (EOF).

Thought Process:

1. You cannot read individual bytes — the only primitive is read4, which reads exactly 4 (or fewer at EOF).
2. Call read4 in a loop, copying from the temp buffer to the output buffer byte by byte.
3. Two stopping conditions: (a) we have accumulated n bytes, or (b) read4 returned < 4, indicating end of file.
4. The inner loop copies min(read4_bytes, remaining) bytes, naturally handling the final partial chunk.

Approach: Call read4 into a temporary 4-byte buffer repeatedly. Copy bytes from the temp buffer to the output buffer, stopping when either n bytes have been read or read4 returns fewer than 4 bytes (EOF). This is exactly how buffered I/O works in device drivers — reading from a hardware FIFO in fixed-size chunks.

class Solution {
public:
    int read(char* buf, int n) {
        int read_bytes = 0, read4_bytes = 4;
        char tmp_buf[4];

        while (read_bytes < n && read4_bytes == 4) {
            read4_bytes = read4(tmp_buf);
            for (int i = 0; i < read4_bytes; i++) {
                if (read_bytes >= n) return read_bytes;
                *buf++ = tmp_buf[i];
                read_bytes++;
            }
        }
        return read_bytes;
    }
};

Time Complexity: O(n) — each byte is read once from read4 and copied once to the output buffer, with at most ceil(n/4) read4 calls.

Space Complexity: O(1) — only a fixed 4-byte temporary buffer and a few integer counters are used.

Embedded relevance: This is the exact pattern for reading from hardware peripherals — UART RX FIFOs, SPI flash page reads, and I2C block reads all deliver data in fixed-size chunks that must be buffered and assembled into the caller's requested size.

Key Insight: A stack naturally models nested function calls — when a function ends, its total time includes time spent in children, so you subtract the child's duration from the parent on the stack to get exclusive time.

Thought Process:

1. Each function's total time (end - start + 1) includes any nested function calls within it.
2. To get exclusive time, you need to subtract the time consumed by child functions.
3. A stack tracks nesting: push on "start", pop on "end". When popping, the elapsed time is added to the current function and subtracted from the parent (now the new stack top).
4. Single pass through the logs — O(n) time, O(n) stack space for the maximum nesting depth.

Approach: Use a stack to track the currently executing function. When a function starts, push it. When it ends, calculate its execution time and pop. Subtract the child function's time from the parent (the new stack top) to get exclusive time. This mirrors how profilers and debuggers track function execution.

class Solution {
    struct Log {
        int id;
        bool isStart;
        int time;
    };

    Log getLog(string& s) {
        string id, isStart, time;
        stringstream ss(s);
        getline(ss, id, ':');
        getline(ss, isStart, ':');
        getline(ss, time, ':');
        return {stoi(id), isStart == "start", stoi(time)};
    }

public:
    vector<int> exclusiveTime(int n, vector<string>& logs) {
        vector<int> exclusive(n, 0);
        stack<Log> s;

        for (auto& log : logs) {
            Log l = getLog(log);
            if (l.isStart)
                s.push(l);
            else {
                int time = l.time - s.top().time + 1;
                exclusive[l.id] += time;
                s.pop();
                if (!s.empty())
                    exclusive[s.top().id] -= time;
            }
        }
        return exclusive;
    }
};

Time Complexity: O(n) where n is the number of log entries — each entry is processed exactly once with O(1) stack operations.

Space Complexity: O(n) — the stack can grow up to n/2 entries deep in the worst case (all starts before any ends).

Embedded relevance: This is how embedded profiling tools (like Segger SystemView and Tracealyzer) compute per-function CPU usage — tracking nested function calls with a stack and attributing time exclusively to each function.

Key Insight: The most frequent task dictates the minimum schedule length — it creates a frame of (f_max - 1) groups of (n + 1) slots, and the answer is the larger of this frame size (plus ties) or the total task count.

Thought Process:

1. Simulation with a priority queue (greedy): always pick the most frequent available task — O(n log 26) which is O(n), but complex to implement.
2. Observation: the most frequent task forces (f_max - 1) mandatory gaps of size n between its executions.
3. Other tasks fill these gaps. If there are enough diverse tasks, no idle slots are needed and the answer is simply the total task count.
4. Formula: max(total_tasks, (f_max - 1) * (n + 1) + count_of_tasks_with_max_freq) — O(n) time, O(1) space (26-element array).

Approach: Count the frequency of each task. The most frequent task defines the structure: it creates (f_max - 1) groups of (n + 1) slots, plus a final group for all tasks with maximum frequency. The answer is the larger of this formula result and the total task count (no idle slots needed if there are enough diverse tasks to fill the gaps).

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        vector<int> count(26, 0);
        int tasks_size = tasks.size();
        int max_freq = 0;

        for (auto& it : tasks) {
            count[it - 'A']++;
            max_freq = max(max_freq, count[it - 'A']);
        }

        int result = (max_freq - 1) * (n + 1);
        for (auto& it : count) {
            if (max_freq == it) result++;
        }

        return max(result, tasks_size);
    }
};

Time Complexity: O(n) where n is the number of tasks — one pass to count frequencies, one pass through the 26-element count array (constant).

Space Complexity: O(1) — the frequency array is fixed at 26 entries regardless of input size.

Embedded relevance: This scheduling logic appears directly in RTOS task design — determining minimum cycle times when tasks have mandatory cooldown periods (e.g., sensor polling intervals, debounce delays, protocol retransmission backoffs).

Key Insight: The difference from Read4 I is statefulness — leftover bytes from a previous read4 call must be preserved between invocations using private member variables, turning a stateless function into a stateful buffered reader.

Thought Process:

1. Read4 I is stateless: each call starts fresh. But when called multiple times, a read4 call might return more bytes than the current read() needs.
2. Those leftover bytes must be stored between calls — use private member variables for the internal buffer, current position, and bytes available.
3. On each call, first drain any leftover bytes from the previous call, then read fresh chunks as needed.
4. The EOF check (read4_bytes != 4) must also be stateful — once EOF is reached, no more read4 calls should be made.

Approach: The difference from Read4 I: leftover bytes from a previous read4 call must be preserved between invocations. Use private member variables to store the internal buffer, current position, and how many bytes were last read. On each call, first drain any leftover bytes, then continue with fresh read4 calls as needed.

class Solution {
    int pos = 0, read4_bytes = 0;
    char tmp_buf[4];

public:
    int read(char* buf, int n) {
        int read_bytes = 0;

        // Drain leftover from previous call
        while (pos < read4_bytes && read_bytes < n) {
            *buf++ = tmp_buf[pos++];
            read_bytes++;
        }

        // Read fresh chunks
        while (read_bytes < n) {
            read4_bytes = read4(tmp_buf);
            for (pos = 0; pos < read4_bytes;) {
                if (read_bytes >= n) return read_bytes;
                *buf++ = tmp_buf[pos++];
                read_bytes++;
            }
            if (read4_bytes != 4) break;  // EOF
        }
        return read_bytes;
    }
};

Time Complexity: O(n) — each byte is processed at most once (either drained from leftover or read fresh), with at most ceil(n/4) read4 calls.

Space Complexity: O(1) — only a fixed 4-byte buffer and two integer state variables persist between calls.

Embedded relevance: This is the canonical stateful buffered reader pattern — every UART driver, file system read function, and network socket recv() implementation handles partial reads and leftover data exactly this way.