Data Structures

Block-Based Deque

Difficulty

Asked at Citadel Securities

Theory: Data Structures You Implement, Not Import

Read the problem, hints and solution here. The editor needs a bigger screen: open this page on a laptop to write and run your code.

Available in C++ and Python. You are solving it in C++. Switch to Python

xxxxxxxxx xxxxxxxxxx, x xxxxxx-xxxxx xxxxx xxxx x xxxxx xxxx xx x xxxx xxxxx xxxxx x xxxxxx xxxxxxx. xx xxxxx xxxxxxxx xx xxxxx-xxxx xxxxxx xxx x xxx xx xxxxx xxx xxxxxx xxx. xxx::xxxxxx xxxxx xx xxx xxxxx xxxx xxxxxxx: xxxx xx xxxxx, xxxxxxxxxx xxxxx, xxx xxxxx xxxxxxx xxx xxxxxxxxx xxxx xx xxxxxxx xxxxxxxx. xx xx xxxxx xxxx xxxxx xxxxxxxxx xxxx xx xxxxxxx x xxxxxxx xx xx xxxxx, xxxx xx xxx x xxxxxxxxxxx xxxxxxxx, xx xx x xxxxxxxxxxx xxx. xxx::xxxxx xxxx xxx xxxx xxx xxxxxxxx. xx xxxxxx xxxx xx xxxxx-xxxx xxxxxx xxx xxxxx x xxx xx xxxxx xxx xxxxxx xxx, xx xxxxxxx xx xxxxxx xxx xxxxxxxxx x xxxxx xxx xxxxxxx xxx xxx, xxx xxxxx xxxxxxxx xxxxxxxx xxxxxxx xxxxxx. xxx xxxxxxxxxx: xxxx_xxxx(x), xxxx_xxxxx(x) xxxxx(), xxxx(), xxxx() xxxxx_xxxxx(): xxx xxxx xxxxxx xxx xxxxxxxxx xxxxxxxx[](x): xxxxx xxx xxxxxxx, x xxxxxxx xxxx xxx xxxxx xxx xxxxxxxxxx, xxxxx xxxxx xxx xxxxxx xxx xxxxx xxxxxxxxx xxxxx xxxxxxxxxx { xxxxxx: xxxxxx xxxxxxxxx xxx::xxxx_x xxxxxx = x; xxxxxxxxxx(); ~xxxxxxxxxx(); xxxxxxxxxx(xxxxx xxxxxxxxxx&) = xxxxxx; xxxxxxxxxx& xxxxxxxx=(xxxxx xxxxxxxxxx&) = xxxxxx; xxxx xxxx_xxxx(xxxx xxxx xxxxx); xxxx xxxx_xxxxx(xxxx xxxx xxxxx); xxxx xxxx& xxxxxxxx[](xxx::xxxx_x xxxxx); xxxxx xxxx xxxx& xxxxxxxx[](xxx::xxxx_x xxxxx) xxxxx; xxxx xxxx& xxxxx(); xxxx xxxx& xxxx(); xxx::xxxx_x xxxx() xxxxx; xxx::xxxx_x xxxxx_xxxxx() xxxxx; }; xxxxxxxx xxxxxxxxxx x; xxx (xxx x = x; x < x; ++x) x.xxxx_xxxx(x); // xxxx x, xxx xxxxx x.xxxx_xxxxx(-x); // x xxxxxx xxxxx, xx xxx xxxxx x[x]; // -x: xxxxxxx xxx xxxxxxxxxx, xxxxxxx xx xxx xxx xxxxxxxx xxxxx xxxxxx: xxxxxxxxxx x; x.xxxx_xxxx(xxxx); xxxx xxxx* xxxx = &x[x]; xxx (xxx x = x; x < xxx; ++x) { x.xxxx_xxxx(x); x.xxxx_xxxxx(-x); } *xxxx; // xxxxx xxxx, xxxxx x xxxxxxxx xxxxxx xxxxxxxxxxx xxxxxxxx xxxx xx ( x(x) ) xxxxxxxxxx: xxxxxxx x xxxx xx xxxx xxxxxx (xxx xxxxxxxx'x xxxxx_) xxxx xxx xxxx xxxxx xxxxxx xx xxx xxxxxx xxxx xxx xx xxx, xx xxxxxxxx[](x) xx xxx_[(xxxxx_ + x) / x][(xxxxx_ + x) % x], xxx xxxxxxxxx xxx xxx xxxxx. xxxxxxx xxx xxxxxx xx xxxx xxxxxxx ( x ) xxxxxxx xxx xxxxxxxxx. xxxxxxxx xxxx xxxxx xxxx. x xxxxx, xxxx xxxxxxxxx, xxxxx xxx xxxxxxxx xx xxx xxxx xxxxxxxxx xxx xxx xxxxxxxx xx xxx xxxxx. xxxxxxx xx xxx xxxxx xxx xx xxx x xxxxx xx xxxxx xx xxx xxxxxxxx xxxx. xxx xxx xxxxx xxx xxxxxxx xxx x xxxxxxxx, xx xxxxxx xxx xxx xx xx xxxxxx xx xxx xxxx xx xxxxxx xxx xxxxxxxx xxx xxxxxxx xx xxxxxx xx xxxxx. x xxxx_xxxxx xxxx xx xxxx xxxx xx xxxxx xxxxxxxx x xxxxx xxxxx xxx xxxxxx xxx xxxxxxx xx xxxx xxxxx'x xxxx xxxx, xx xxxxxxxxx xxxxxx xx xxx xxxxx xxxx xx xxxxxxxxx xxxxxx xxxx x; xxxx xxxxx xxxx xxx xxxx xxxxx xxxx_xxxxx xx xx xxxxx xxxxx, xxxxx xxxxxxxxx xxxxx xx xxx xxx xx x xxxxxxx xxxxxxxxx xxxxx (xxxxx_ xxxxx xx xxx xxx xxxxx xxxxx xxx xx xxxxxxxxxxx). xxx xxxxx xxxx xxx xxxxxx. xxx xxx xxxxx xxx xxxxxxxx xx xxxxxx xxx xxxxxxxx xxxx xxx xxxx xxxx[x], xx xxx xxxxxxxxxx xxxxx xxxx xxx xxxx xxxxxx[]. xxxx xx xxx xxxx xxxxxx xxxxxxxxxx xxx xxxxx xxxxx. xxxxx xx xx xxx. xxxx xx xxx xxxxxxxxx, xxx x xxxx xxxxx. xxxx xxx xxxxxxxxxx xxx xxxxxxx.

This problem is only available to subscribers.

Language:

C++23 Python 3.12

BlockDeque

#include <cstddef>
#include <vector>

// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
class BlockDeque {
public:
    static constexpr std::size_t kBlock = 8;

    BlockDeque() {
        // ...
    }

    ~BlockDeque() {
        // ...
    }

    BlockDeque(const BlockDeque&) = delete;
    BlockDeque& operator=(const BlockDeque&) = delete;

    void push_back(long long value) {
        // ...
        (void)value;
    }

    void push_front(long long value) {
        // ...
        (void)value;
    }

    long long& operator[](std::size_t index) {
        // ...
        (void)index;
        static long long dummy = 0;
        return dummy;
    }

    const long long& operator[](std::size_t index) const {
        // ...
        (void)index;
        static long long dummy = 0;
        return dummy;
    }

    long long& front() { return (*this)[0]; }
    long long& back() { return (*this)[size_ - 1]; }

    std::size_t size() const { return size_; }
    std::size_t block_count() const { return map_.size(); }

private:
    std::vector<long long*> map_;
    std::size_t first_ = 0;   // ...
    std::size_t size_ = 0;
};

Unlock to runUpgrade

Unlock the problem to run it against the tests.

Next in STL From ScratchSmall-Buffer VectorData Structures