SWE 1st Tech Interview Tasks

Задача 1

Есть несколько тредов-воркеров, которые обрабатывают сообщения в бесконечном цикле. Точка входа в тред — функция PollEvents. Она получает свой уникальный instrument_id (от 0 до MAX_INSTRUMENTS_COUNT) и занимается только им. Какие проблемы производительности есть в этом коде?

/* there are a few workers (threads), each receives messages with the following scheme:
{
  "e": "string", // event_type: "price" or "announcement"
  "id": int32,   // msg id, only for e = price
  "T": int64,    // exchange time
  "s": int32,    // instrument id
  "data": string // current price (eg. "25.3519") or announcement message
}
each worker handles messages with the same symbol "s" */
 
struct PriceUpdate {
    double price;
    int64_t timestamp;
};

struct Announcement {
    std::string message;
    int64_t timestamp;
};

struct Item {
    int last_id = -1;
    double min_price = -1;
    int64_t timestamp = -1;
};

std::vector<Item> prices_info(MAX_INSTRUMENTS_COUNT); // shared between threads
 
/* worker code starts here */
 
std::variant<PriceUpdate, Announcement> GetNextMessage(int instrument_id) {
    std::string message = ReadNextMessage();
    auto parsed = ParseJson(message);
    std::string data = parsed.GetField<std::string>("data");
    int64_t ts = parsed.GetField<int64_t>("T");
    if (parsed.GetField<std::string>("e") == "announcement") {
        return Announcement{data, ts};
    } else {
        int id = parsed.GetField<int>("id");
        if (id < prices_info[instrument_id].last_id && prices_info[instrument_id].last_id != -1) {
            throw std::runtime_error("Unexpected id " + std::to_string(id));
        }
        double price = std::stod(data);
        if (prices_info[instrument_id].min_price < 0 || price < prices_info[instrument_id].min_price) {
            prices_info[instrument_id].min_price = price;
        }
        prices_info[instrument_id].last_id = id;
        prices_info[instrument_id].timestamp = ts;
        return PriceUpdate{price, ts};
    }
}

void PollEvents(int instrument_id) {
    for (;;) {
        std::variant<PriceUpdate, Announcement> next_message;
        try {
            next_message = GetNextMessage(instrument_id);
        } catch (const std::exception& e) {
            LogError(e);
            continue;
        }
        std::visit([&](auto&& event) {
            using T = std::decay_t<decltype(event)>;
            if constexpr(std::is_same<T, PriceUpdate>) {
                HandlePriceUpdate(event);
            } else {
                HandleAnnouncement(event);
            }
        }, next_message);
    }
}

Задача 2

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

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

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

Задача 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, чтобы второй конструктор вызывался только для настоящих итераторов, а для всего остального вызывался первый?

Задача 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;
}