OS-Flavor Coding Problems — Read4, Task Scheduler

These problems mirror real OS and systems programming patterns — buffered I/O, task scheduling with cooldown constraints, and function call stack tracing. They test the systems-level thinking that embedded interviewers value most.

Problems

#	Problem	Difficulty	Frequency
1	Read N Characters Given Read4	Easy	★★★★★
2	Producer-Consumer / Shared Resource	Medium	★★★★★
3	Exclusive Time of Functions	Medium	★★★★★
4	Task Scheduler	Medium	★★★★★
5	Read N Characters Given Read4 II (call multiple times)	Hard	★★★★★

Pattern Cheat Sheet

Pattern	Technique	Problems
Buffered I/O	Internal buffer + position tracking	Read4, Read4 II
Stack-based call tracing	Push on start, pop on end, adjust parent	Exclusive Time
Greedy scheduling	Frequency counting + idle slot calculation	Task Scheduler
Stateful API	Private member variables persist across calls	Read4 II

Implementation

Read N Characters Given Read4 Easy ★★★★★

Problem: Given a method read4 that reads 4 characters at a time, implement read(buf, n) that reads n characters from a file.

QSolution — O(n) time, O(1) space — Temporary Buffer

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.

cpp

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;
    }
};

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.

Exclusive Time of Functions Medium ★★★★★

Problem: Given n functions with start/end logs on a single-threaded CPU, return the exclusive execution time of each function.

QSolution — O(n) time, O(n) space — Stack-Based Call Tracing

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.

cpp

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;
    }
};

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.

Task Scheduler Medium ★★★★★

Problem: Given tasks and a cooldown interval n between same tasks, return the minimum intervals the CPU needs to finish all tasks.

QSolution — O(n) time, O(1) space — Frequency-Based Formula

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).

cpp

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);
    }
};

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).

Read N Characters Given Read4 II (call multiple times) Hard ★★★★★

Problem: Given read4, implement read(buf, n) that may be called multiple times, reading n characters each time.

QSolution — O(n) time, O(1) space — Stateful Buffering

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.

cpp

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;
    }
};

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.