MiddleCodeOccasionalNot answered yet

Wrap a near-sorted int stream into a fully sorted stream

A source stream yields positive ints that are out of order by at most k positions (each value arrives within k of its sorted spot); -1 marks the end. Design a SortedStream wrapping the source that yields the values in sorted order.

Requirements:

Use the same int get() interface; -1 means exhausted.
Buffer at most k + 1 elements at a time.

struct Stream { virtual int get() = 0; };

struct SortedStream : Stream {
    // wrap a Stream*; your code here
};

Write the implementation.

Keep a min-heap of size at most k + 1. On each get, refill it from the source until it holds k + 1 items or the source ends, then pop the smallest. Every value is within k of its slot, so the smallest of any k + 1-window is the next in order. Return -1 when it drains.

✗Buffering the whole stream, defeating the bounded-memory point
✗Sizing the window at k instead of k + 1, so the next element can still be smaller
✗Not draining the buffer after the source ends, dropping the tail

→Why must the buffer hold k + 1 rather than k elements?
→What data structure gives O(log k) pop-min and insert here?

Contents

Task

Design a SortedStream over a near-sorted stream (displacement up to k).

Solution

#include <queue>

struct Stream { virtual int get() = 0; virtual ~Stream() = default; };

struct SortedStream : Stream {
    Stream* src; size_t cap;
    std::priority_queue<int, std::vector<int>, std::greater<int>> buf;  // min-heap
    SortedStream(Stream* s, size_t k) : src(s), cap(k + 1) {}

    int get() override {
        while (buf.size() < cap) {           // refill the k+1 window
            int v = src->get();
            if (v < 0) break;                // source ended
            buf.push(v);
        }
        if (buf.empty()) return -1;          // fully drained
        int v = buf.top(); buf.pop();
        return v;
    }
};

Key points

A k + 1 window guarantees its minimum is the next value in order.
Buffer in bounded fashion, not the whole stream.
Drain the remainder after the source ends, or the tail is lost.

Open topic in roadmap →

Contents

Wrap a near-sorted int stream into a fully sorted stream

Requirements:

Use the same int get() interface; -1 means exhausted.
Buffer at most k + 1 elements at a time.

struct Stream { virtual int get() = 0; };

struct SortedStream : Stream {
    // wrap a Stream*; your code here
};

Write the implementation.

Solution

#include <queue> struct Stream { virtual int get() = 0; virtual ~Stream() = default; }; struct SortedStream : Stream { Stream* src; size_t cap; std::priority_queue<int, std::vector<int>, std::greater<int>> buf; // min-heap SortedStream(Stream* s, size_t k) : src(s), cap(k + 1) {} int get() override { while (buf.size() < cap) { // refill the k+1 window int v = src->get(); if (v < 0) break; // source ended buf.push(v); } if (buf.empty()) return -1; // fully drained int v = buf.top(); buf.pop(); return v; } };