About Teletype
Join
Spectral::Technologies
@spectraltech
October 31, 2025

Решение 2-4 задач из 1st Tech Interview SWE

Задача 2

У нас есть приложение, которое обрабатывает некоторые заказы. В процессе работы заказы могут добавляться и удаляться (но не изменяться). У каждого заказа есть уникальный числовой id. Нужно написать кеш, где будем хранить N последних использованных (добавленных или запрошенных) заказов.

Дополнительные вопросы:

  • Что, если структура Order большая?
  • Что, если мы хотим делиться значениями, которые возвращает get()?
  • Что, если мы хотим смотреть на эти значения из разных тредов?

Решение

Классическое решение этой задачи — скомбинировать unordered_map для поиска за O(1) и list для хранения порядка заказов.

#include <unordered_map>
#include <list>
#include <optional>

struct Order{
    // ...
};

class Cache {
    public:
        Cache(size_t max_size): max_size(max_size) {
            if(max_size == 0) {
                throw "max_size == 0";
            }
        }
        
        void put(int id, const Order& order) {
            if(auto it = index.find(id); it != index.end()) {
                // Считаем, что заказ не меняется
                moveToTop(it->second);
                return;
            }
            if(index.size() == max_size) {
                OrderEx &oldest = lru.back();
                index.erase(oldest.id);
                oldest.id = id;
                oldest.order = order;
                auto oldestIt = std::prev(lru.end());
                index[id] = oldestIt;
                moveToTop(oldestIt);
                return;
            }
            lru.emplace_front(OrderEx{id, order});
            index[id] = lru.begin();
        }
        
        std::optional<Order> get(int id) {
            auto it = index.find(id);
            if(it == index.end()) {
                return std::nullopt;
            }
            moveToTop(it->second);
            return it->second->order;
        }
    private:
        const size_t max_size;

        struct OrderEx {
            int id;
            Order order;
        };
        using List = std::list<OrderEx>;
        List lru;
        std::unordered_map<int, List::iterator> index;
        
        void moveToTop(List::iterator it) {
            lru.splice(lru.begin(), lru, it);
        }

};

Если структура большая, то лучший выход здесь: хранить и передавать не сами их значения, а указатели на них. Но как только появляются дополнительные участники процесса, становится сложно уследить за валидностью этих указателей. Тогда к нам на помощь приходит shared_ptr! Завернем наш Order в shared_ptr<Order>, получим безопасное копирование и управление временем жизни объекта, ценой дополнительных переходов по указателю и расходов на атомарные счётчики ссылок и их инкремент-декремент.

Можно использовать более оптимальные структуры данных.

std::list отдельно аллоцирует память для каждого элемента, так как его размер потенциально не ограничен. У этого подхода есть два недостатка в контексте LRU-cache: частые аллокации памяти и неэффективное использование памяти с точки зрения кэша процессора.

Мы можем заранее аллоцировать всю требуемую память для списка, и далее либо использовать стек для отслеживания свободных нод, либо реализовать интрузивный список, в котором свободные ноды будут связаны в цепочку сразу за последним элементом списка.

Аналогично можно поступить с unordered_hashmap. Можно использовать flat_hash_map фиксированного размера, что повысит кэш-локальность.

Задача 3

Какой вызовется конструктор, #1 или #2?

template<class T>
class Vector {
public:
    Vector(size_t size, T default_value) { ... }  // <-- #1
 
    template<class Iterator>
    Vector(Iterator first, Iterator last) { ... } // <-- #2
};
 
...
Vector<int> data(5, 3);

Дополнительный вопрос: Как нам изменить класс Vector, чтобы второй конструктор вызывался только для настоящих итераторов, а для всего остального вызывался первый?

Решение

Здесь нужно посмотреть на правила, по которым компилятор выбирает подходящий метод для вызова. И в первую очередь здесь считается, как хорошо подходят типы аргументов. Здесь мы вызываем Vector(5, 3), аргументы 5 и 3 получаются типа int. Тогда для конструктора #1 нам нужно сделать одно преобразование int(5) -> size_t(5)(тип T для Vector<int> уже int), а для конструктора #2 тип Iterator выведется как int и выходит ноль преобразований, то есть конструктор #2 подходит идеально. Поэтому ответ: вызовется конструктор #2!

Можно вспомнить еще одно правило при разрешении перегрузок: предпочтение отдается наиболее специализированному методу. Такое правило действительно есть, но оно работает после правила типов, то есть если бы у нас был нешаблонный конструктор, принимающий два аргумента типа int, то вызвался бы он, а в данном случае все-таки вызывается конструктор #2.

Чтобы изменить класс Vector так, чтобы второй конструктор вызывался только для настоящих итераторов, а для всего остального вызывался первый, воспользуемся стандартным концептом input_iterator:

#include <iterator>

...

    template<std::input_iterator Iterator>
    Vector(Iterator first, Iterator last) { ... } // <-- #2
    
...

Или если нам надо проверить какие-то параметры этого итератора вручную, то можно написать свои requiresвручную:

#include <iterator>
#include <type_traits>

template<class T>
class Vector {
public:
    template<class Iterator>
    requires requires {
        typename std::iterator_traits<Iterator>::iterator_category;
        // ...
    }
    Vector(Iterator first, Iterator last) { ... } // <-- #2
};

Задача 4

Напишите упрощенную реализацию мьютекса, похожую на реализацию из стандартной библиотеки.Воспользуйтесь такой заготовкой:

// Design syscalls to your taste
void syscall_wait(...);  // to block the thread until the mutex is available
void syscall_wake(...);  // to wake up one waiting thread

struct Spinlock {
  bool try_lock() {
    // todo
  }
  
  void unlock() {
    // todo
  }
  // todo
};

struct Mutex {
  void lock() {
    // todo
  }
  
  void unlock() {
    // todo
  }
  
  Spinlock spinlock;
}

Решение

Мьютекс работает на спинлоке + паре системных вызовов. Сначала попробуем заблокировать спинлок, и если никто в это время не держит мьютекс, или быстро отпускает, то нам повезло! Спинлок заблокирован, переключение контекста не произошло, мьютекс блокируется очень быстро. Если же не получилось, то с помощью системных вызовов отправляемся спать, пока текущий держатель мьютекса его не отпустит и не сигнализирует об этом.

// Настоящие системные вызовы, конечно же, имеют другие параметры. Но в рамках этой задачи
// мы сами их дизайним, поэтому сделаем, как проще и удобнее.
void syscall_wait(atomic_flag* lock);// to block the thread until the mutex is available
void syscall_wake(atomic_flag* lock);// to wake up one waiting thread

struct Spinlock {
    bool try_lock() {
        bool success = false;
        for(int i = 0; i < try_count && !success; ++i) {
            // Решение с такой проверкой называется TTAS (test + test_and_set).
            // Можно обойтись и просто TAS, но тогда каждый TAS будет инвалидировать
            // кеш процессора, даже если значение locked не изменилось.
            bool already_locked = locked.test(std::memory_order_relaxed) ||
                locked.test_and_set(std::memory_order_acquire);
            success = !already_locked;
        }
        return success;
    }

    void unlock() {
        locked.clear(std::memory_order_release);
    }

    std::atomic_flag locked = ATOMIC_FLAG_INIT; // Такая инициализация необходима до C++20

    static constexpr int try_count {100};
};

struct Mutex {
    void lock() {
        bool success = false;
        while(!success) {
            success = spinlock.try_lock();
            if(!success) {
                syscall_wait(&spinlock.locked);
            }
        }
    }

    void unlock() {
        spinlock.unlock();
        syscall_wake(&spinlock.locked);
    }

    Spinlock spinlock;
};
Spectral::Technologies
October 31, 2025, 07:41
0 views
1 reaction
1 reply