Data Structures

Intrusive List

Difficulty

Asked at Jump Trading, Hudson River Trading

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.

xx xxxxx xxxx xxxxxxx xxxxxx xxxxxxxxxx, xxx xxxx xx xxxxxxxx xxxxxxxxx xxxx xxxxx xxxxxxx xxxx xxxxx: x xxxxxx xxxx xx xxx xxxxx xxxxx, xx x xxxx xxx xxxx xxxxx xx xx xxxxxxxx xxxx xxx xx xx xxxx xx xxxx xxxx xxx xxxx. xxxx xxxx xxxx xxxx xxx xxxxxx xxxx xxxxx xx xxxxxx. xx xxxxxxxxx xxxx xxxx xxx xxxxx xxxxxx xxx xxxxxx. xxxxxx xxx xxxxx xx xxxxxx xxx xxxxxxxx, xx xxxxxxxxxx xx xxxx xxxxxxx xxxxxx xxx xx xxxxxx xx xxx. xx xx xxx xxxxxxx xxx xxxxxxxx xxxxxxx xxx xxxx xxx xxx xxx::xxxx xx xxx xxxx x xxx xxxx xxxxxxx xxx. x xxxxxxxx xxx xx xxxxx xxxx xxxxxxx xxx xxx xxxxxxxx. xxxxxxxxx xxxxxxxxx: xxxx_xxxx(xxxxx), xxxx_xxxxx(xxxxx): ( x(x) ) xxxxx(xxxxx): xxxxxx xx, xxxxx xxx xxxxx, xxxx xx xxxxxx, ( x(x) ) xxxxxxxx(xxxxx): xx xx xx x xxxx xxxxx xxx xxxx(), xxx xxx() xxxxxxxxx xxx xxx xxxxx xx xxxx xxx xxxxxx xxxxxxxx xxx xx xxxxxxxxxxxx. xx xxxxxxxxx xxxx xxxxxxxxx xxxxxxx, xxxx, xxx xxx xxxxx xxxxxx xxxx. xxxxxxxx xxxxx x(x, xx), x(x, xx), x(x, xx); xxxxxxxxx xxxx; xxxx.xxxx_xxxx(x); xxxx.xxxx_xxxx(x); xxxx.xxxx_xxxx(x); xxxx.xxx(); // {x, x, x} xxxx.xxxxx(x); // xx xxxxxx, xx xxxxxxxx, xx xx xxxxxx xxxx.xxx(); // {x, x} xxxxxxxxxxx xxxxxxx xx xxxxx xxxx xx xxx xxxxxx xxxx xx x xx-xx, xxx xxxxxxxxxx. x xxxxxx xxxxxx xx xxx x xxxxxxxxx xxxxx, xx xx xx xxxxxxxx xxxx xxxxxxx x xxxxxx xxxxxx xxx x xxxx, xxx x xxxxx xxxx/xxxx xxxx xxxx xxxxxxx xxxxx xxxxxxx xxxxx xxxxxx. xxx xxxx xxx xxxx xxxxxx xxx xxxxxxxx xxxxx xxxx xxx xxxxxx xxx, xxx xxx xxxx-xxxxxxx xxxxx xx xxxx xx xxxx. xxx xxxx xxxx xxxxxxx. xxxxxxxx xxxxxxx xx xxxxxxx xxxxxxx xxx xxxxxx. xxxx xxxxxxxxx xxxxxxxxx xxx xxx xxxxx xxx xx xxxxxxx xxxxx xx xxxx xx xxxxxx xx xxxxxxx xxxxxx xxxxx xxx xxxxxxx xxxx xxxx xxxxx xxx xx xxx, xxx xxx xxxxx::xxxxxxxxx xxxx; xxxx xxx xxxx xx x xxxx xxxxx, xx xxxx, xxxx xxxx xxx xxxx (xxx xxxxxx xxxxxxxx xxxxxxx xxx xxxx xxxx xxxxx), x xxxxxxx xxxx xxxxxxxx xxxxxxxxxx xxxx.

This problem is only available to subscribers.

Language: C++23OrderList

#include <cstddef>
#include <cstdlib>
#include <new>
#include <vector>

// ...
// ...
// ...
// ...
// ...
namespace probe {
inline long long& counter() {
    static long long calls = 0;
    return calls;
}
inline long long allocations() { return counter(); }
inline void reset() { counter() = 0; }
}  // ...

void* operator new(std::size_t bytes) {
    ++probe::counter();
    void* p = std::malloc(bytes ? bytes : 1);
    if (!p) throw std::bad_alloc();
    return p;
}
void* operator new[](std::size_t bytes) { return ::operator new(bytes); }
void operator delete(void* p) noexcept { std::free(p); }
void operator delete[](void* p) noexcept { std::free(p); }
void operator delete(void* p, std::size_t) noexcept { std::free(p); }
void operator delete[](void* p, std::size_t) noexcept { std::free(p); }

// ...
// ...
// ...
struct ListHook {
    ListHook* prev = nullptr;
    ListHook* next = nullptr;
    bool linked = false;
};

struct Order : ListHook {
    long long id = 0;
    long long qty = 0;

    Order(long long order_id, long long quantity) : id(order_id), qty(quantity) {}
};

// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
class OrderList {
public:
    void push_back(Order& order) {
        // ...
        (void)order;
    }

    void push_front(Order& order) {
        // ...
        (void)order;
    }

    void erase(Order& order) {
        // ...
        (void)order;
    }

    bool contains(const Order& order) const {
        // ...
        (void)order;
        return false;
    }

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

    std::vector<long long> ids() const {
        // ...
        return {};
    }

private:
    ListHook* head_ = nullptr;
    ListHook* tail_ = nullptr;
    std::size_t size_ = 0;
};

Unlock to runUpgrade

Unlock the problem to run it against the tests.