Решения задач для подготовки к интервью SWE.
В каком из контейнеров поиск будет работать быстрее и почему?
void generate_vector(std::vector<ssize_t>& vector, size_t size)
{
for (size_t i = 0u; i < size; ++i) {
vector.push_back(i);
}
}
void generate_set(std::set<ssize_t>& set, size_t size)
{
for (size_t i = 0u; i < size; ++i) {
set.insert(i);
}
}
int main(int argc, char** argv)
{
using std::chrono::high_resolution_clock;
using std::chrono::duration_cast;
using std::chrono::duration;
using std::chrono::nanoseconds;
constexpr size_t SIZE = 10000u;
std::cout << "SIZE: " << SIZE << std::endl;
std::set<ssize_t> set;
generate_set(set, SIZE);
std::vector<ssize_t> vector;
generate_vector(vector, SIZE);
{
std::cout << "Vector: ";
auto t1 = high_resolution_clock::now();
std::binary_search(begin(vector), end(vector), SIZE / 2u + 3); // O(log(N))
auto t2 = high_resolution_clock::now();
std::cout
<< duration_cast<nanoseconds>(t2 - t1).count()
<< " ns" << std::endl;
}
{
std::cout << "Set: ";
auto t1 = high_resolution_clock::now();
set.find(SIZE / 2u + 3); // O(log(N))
auto t2 = high_resolution_clock::now();
std::cout
<< duration_cast<nanoseconds>(t2 - t1).count()
<< " ns" << std::endl;
}
return 0;
}
Поиск в std::set обычно медленнее, чем в отсортированном std::vector, несмотря на одинаковую асимптотическую сложность O(log(N))O(\log(N)), из-за разницы в использовании памяти и кэш-локальности.
- std::vector (отсортированный): Поиск выполняется с использованием алгоритма std::binary_search, который опирается на последовательное обращение к элементам памяти. Память вектор хранит непрерывно, что приводит к высокой кэш-локальности и снижению накладных расходов при доступе.
- std::set: Реализован на основе самобалансирующихся деревьев, таких как красно-черное дерево. Хотя сложность поиска также составляет O(log(N))O(\log(N)), каждая операция требует косвенного обращения к узлам через указатели. Это увеличивает накладные расходы из-за уменьшенной кэш-локальности и дополнительных затрат на управление структурой дерева.
В данном примере поиск в отсортированном std::vector будет быстрее за счет оптимального использования кэша и меньших накладных расходов на доступ к данным.
Задача 2
Вам дается время в формате “ЧЧ:ММ”. Вам нужно вернуть минимальную разницу в минутах между любыми двумя данными из листа.
Пример 1:
Input: TimePoints = [“23:59”, “00:00”]
Input: TimePoints = [“00:00”, “23:59”, “00:00”]
#include <algorithm>
#include <array>
#include <iostream>
#include <limits>
#include <string>
#include <vector>
int findMinDifference(const std::vector<std::string>& timePoints)
{
if (timePoints.size() > 1440) return 0; // Принцип Дирихле
std::array<int, 1440> minuteMarks {};
for (const auto& time: timePoints) {
int minutesValue = std::stoi(time.substr(0, 2)) * 60 + std::stoi(time.substr(3, 2));
if (minuteMarks[minutesValue]++ > 0) return 0; // Совпадающие значения во входных данных
}
int prevMinuteMark = -1;
int firstMinuteMark = -1;
int result = std::numeric_limits<int>::max();
for(int i = 0; i < minuteMarks.size(); ++i) {
if (!minuteMarks[i]) continue;
if (firstMinuteMark == -1) {
firstMinuteMark = i;
}
if (prevMinuteMark != -1) {
result = std::min(result, i - prevMinuteMark);
}
prevMinuteMark = i;
}
// Сравниваем текущий минимальный интервал и интервал между крайними значениями через 0
return std::min(result, firstMinuteMark - (prevMinuteMark - 1440));
}
int main() {
// Пример 1
std::vector<std::string> timePoints1 = {"23:59", "00:00"};
std::cout << "Output for Example 1: "
<< findMinDifference(timePoints1)
<< std::endl;
// Пример 2
std::vector<std::string> timePoints2 = {"00:00", "23:59", "00:00"};
std::cout << "Output for Example 2: "
<< findMinDifference(timePoints2)
<< std::endl;
// Пример 3
std::vector<std::string> timePoints3 = {"00:30", "15:00"};
std::cout << "Output for Example 3: "
<< findMinDifference(timePoints3)
<< std::endl;
return 0;
}
Задача 3:
Что такое явное и неявное приведение типов в С++? Зачем делать explicit-конструктор? Приведите простой пример.
Явное приведение типов — это преобразование типов, которое программист указывает явно с помощью операторов приведения, таких как (Type) или static_cast<Type>(). Оно требует явного согласия программиста и обеспечивает контроль над преобразованием.
Неявное приведение типов — это автоматическое преобразование типов, выполняемое компилятором, например, при передаче аргументов в функцию или при инициализации объекта, если возможно безопасное преобразование.
explicit-конструктор запрещает неявное приведение типов, требуя явного вызова конструктора, чтобы избежать неожиданного поведения и ошибок.
#include <iostream>
class MyClass {
public:
explicit MyClass(int value) : value_(value) {} // explicit-конструктор
int getValue() const { return value_; }
private:
int value_;
};
void print(const MyClass& obj) {
std::cout << obj.getValue() << std::endl;
}
int main() {
MyClass obj1 = 10; // Ошибка: неявное приведение запрещено
MyClass obj2(10); // Верно: явный вызов конструктора
print(20); // Ошибка: требуется явное приведение
print(MyClass(20)); // Верно: явное приведение
return 0;
}
Задача 4:
Что такое системный вызов и почему их частое использование может негативно сказаться на производительности приложения? Как можно минимизировать количество системных вызовов?
Системный вызов — это механизм, позволяющий приложению обратиться к ядру для выполнения привилегированных операций, таких как доступ к файловой системе или сетевое взаимодействие. Частое использование системных вызовов может замедлять приложение, поскольку каждый вызов требует переключения контекста между пользовательским и системным режимами, что добавляет накладные расходы на обработку. Чтобы уменьшить количество системных вызовов, можно буферизовать операции, выполняя их батчами, использовать асинхронный ввод-вывод для сокращения времени ожидания и кэшировать результаты, снижая частоту обращений к системе.
Задача 5:
Объясните концепцию виртуальной памяти и роль TLB (Translation Lookaside Buffer) в этом механизме. Как промахи в TLB влияют на производительность системы? Почему использование больших страниц памяти (HugePages) может повысить производительность приложения? Какие есть потенциальные недостатки этого подхода?
Виртуальная память — это технология, которая позволяет каждому процессу использовать свое собственное адресное пространство, сопоставляя виртуальные адреса с физическими через таблицы страниц. TLB — это кэш-память в процессоре, предназначенная для быстрого преобразования виртуальных адресов в физические. Промахи в TLB замедляют доступ к памяти, поскольку требуют дополнительного обращения к таблице страниц. Использование больших страниц памяти (HugePages) полезно тем, что они уменьшают количество промахов в TLB, охватывая больший диапазон адресов и повышая эффективность кэширования. Однако это может привести к фрагментации памяти, так как большие страницы требуют больших непрерывных блоков.