Interview Design Problems

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class LRUCache {
    using Pair = std::pair<int,int>;
    std::list<Pair> items_;                                  // front = newest
    std::unordered_map<int, std::list<Pair>::iterator> map_;
    std::size_t cap_;
public:
    explicit LRUCache(std::size_t cap) : cap_(cap) {}

    std::optional<int> get(int key) {
        auto it = map_.find(key);
        if (it == map_.end()) return std::nullopt;
        items_.splice(items_.begin(), items_, it->second);   // O(1) move to front
        return it->second->second;
    }

    void put(int key, int value) {
        if (auto it = map_.find(key); it != map_.end()) {
            it->second->second = value;
            items_.splice(items_.begin(), items_, it->second);
            return;
        }
        if (map_.size() == cap_) {
            map_.erase(items_.back().first);
            items_.pop_back();
        }
        items_.emplace_front(key, value);
        map_[key] = items_.begin();
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

template <typename T>
class SharedPtr {
    T* ptr_ = nullptr;
    std::atomic<int>* count_ = nullptr;
public:
    explicit SharedPtr(T* p) : ptr_(p), count_(new std::atomic<int>(1)) {}

    SharedPtr(const SharedPtr& o) : ptr_(o.ptr_), count_(o.count_) {
        if (count_) count_->fetch_add(1, std::memory_order_relaxed);
    }

    ~SharedPtr() {
        if (count_ && count_->fetch_sub(1, std::memory_order_acq_rel) == 1) {
            delete ptr_;
            delete count_;
        }
    }
    T& operator*()  const { return *ptr_; }
    T* operator->() const { return ptr_; }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class ThreadPool {
    std::vector<std::jthread> workers_;
    std::queue<std::function<void()>> tasks_;
    std::mutex m_; std::condition_variable cv_; bool stop_ = false;
public:
    explicit ThreadPool(unsigned n = std::thread::hardware_concurrency()) {
        for (unsigned i = 0; i < n; ++i)
            workers_.emplace_back([this]{
                for (;;) {
                    std::function<void()> job;
                    {
                        std::unique_lock lk(m_);
                        cv_.wait(lk, [this]{ return stop_ || !tasks_.empty(); });
                        if (stop_ && tasks_.empty()) return;
                        job = std::move(tasks_.front()); tasks_.pop();
                    }
                    job();
                }
            });
    }
    void submit(std::function<void()> job) {
        { std::lock_guard lk(m_); tasks_.push(std::move(job)); }
        cv_.notify_one();
    }
    ~ThreadPool() {
        { std::lock_guard lk(m_); stop_ = true; }
        cv_.notify_all();          // jthread members join automatically
    }
};