C/C++ | Вопросы собесов

🤔 Зачем нужен виртуальный деструктор?

Виртуальный деструктор необходим, когда класс предполагает полиморфное использование, то есть когда объекты базового класса могут быть удалены через указатель на производный класс. Без виртуального деструктора вызов `delete` на указатель базового типа приведет к вызову только деструктора базового класса, что может вызвать утечку памяти для производных классов. Виртуальный деструктор гарантирует, что будет вызван правильный деструктор для производного класса, обеспечивая корректное освобождение всех ресурсов.

Ставь 👍 если знал ответ, 🔥 если нет
Забирай 📚Базу знаний

🤔 Что такое deque?

Deque (double-ended queue, двусторонняя очередь) — это последовательный контейнер в C++, который позволяет добавлять и удалять элементы как с начала, так и с конца очереди с постоянной временной сложностью O(1). Контейнер deque является частью стандартной библиотеки шаблонов (STL) и объявляется в заголовочном файле <deque>.

🚩Основные характеристики:

🟠Быстрый доступ к элементам:
deque обеспечивает доступ к элементам по индексу с амортизированной временной сложностью O(1).
🟠Двусторонняя очередь:
Позволяет эффективно добавлять и удалять элементы как с начала, так и с конца очереди.
🟠Динамический размер:
deque автоматически изменяет свой размер по мере добавления или удаления элементов, подобно vector.
🟠Не требует смежного хранения:
В отличие от vector, элементы deque могут быть размещены в различных сегментах памяти, что делает его более гибким для частых операций вставки и удаления.

🚩Основные операции:

🟠Добавление элементов:
push_back(), push_front()
🟠Удаление элементов:
pop_back(), pop_front()
🟠Доступ к элементам:
operator[], at(), front(), back()
🟠Размер и емкость:
size(), empty(), resize()
🟠Итераторы:
Поддержка итераторов для прохода по элементам

#include <iostream>
#include <deque>

int main() {
    std::deque<int> dq;

    // Добавление элементов в конец
    dq.push_back(1);
    dq.push_back(2);
    dq.push_back(3);

    // Добавление элементов в начало
    dq.push_front(0);

    std::cout << "Deque elements: ";
    for (int elem : dq) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // Удаление элемента с конца
    dq.pop_back();

    // Удаление элемента с начала
    dq.pop_front();

    std::cout << "Deque elements after pop operations: ";
    for (int elem : dq) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

Ставь 👍 и забирай 📚 Базу знаний

🤔 Как работает хеш таблица?

Хеш-таблица использует хеш-функцию для вычисления индекса в массиве, по которому будет сохранено или найдено значение. Ключ преобразуется хеш-функцией в индекс массива, куда сохраняется значение. При поиске значения ключ снова хешируется для определения индекса. Если происходит коллизия (разные ключи дают один и тот же хеш), то используются методы разрешения коллизий, такие как цепочки (связные списки) или открытая адресация.

Ставь 👍 если знал ответ, 🔥 если нет
Забирай 📚Базу знаний

🤔 Сколько занимает места объект пустого класса?

Объект пустого класса не может иметь нулевой размер из-за требований стандарта. Поэтому компилятор добавляет "фиктивный байт" (dummy byte), чтобы каждый объект имел уникальный адрес.

Простой пример

#include <iostream>

class Empty {};

int main() {
    std::cout << "Размер пустого класса: " << sizeof(Empty) << " байт\n";
    return 0;
}

Вывод (на большинстве компиляторов):

Размер пустого класса: 1 байт

Что если создать массив пустых объектов?

#include <iostream>

class Empty {};

int main() {
    Empty arr[10]; // Создаем массив из 10 объектов

    std::cout << "Размер массива из 10 пустых объектов: " << sizeof(arr) << " байт\n";
    return 0;
}

Вывод

Размер массива из 10 пустых объектов: 10 байт

🟠Унаследованный пустой класс (Empty Base Optimization - EBO)
Если пустой класс используется в наследовании, компилятор может убрать его размер (оптимизация Empty Base Optimization, EBO).

#include <iostream>

class Empty {};

class Derived : public Empty {
    int value; // 4 байта (обычно)
};

int main() {
    std::cout << "Размер пустого класса: " << sizeof(Empty) << " байт\n";
    std::cout << "Размер наследника: " << sizeof(Derived) << " байт\n";
    return 0;
}

Вывод

Размер пустого класса: 1 байт
Размер наследника: 4 байта (а не 5!)

Ставь 👍 и забирай 📚 Базу знаний

🤔 Когда нужно объявлять деструктор виртуальным?

Деструктор должен быть виртуальным, если класс предназначен для использования в качестве базового, и предполагается полиморфное удаление через указатель (Base* ptr = new Derived; delete ptr;). Без виртуального деструктора деструкторы производных классов не будут вызваны, что приведет к утечке памяти.

Ставь 👍 если знал ответ, 🔥 если нет
Забирай 📚Базу знаний

🤔 Как называется одинаковый результат после применения хэш функции?

Одинаковый результат после применения хэш-функции называется коллизией.

🚩Что такое коллизия?

Коллизия возникает, когда две разные входные величины (ключи) при обработке одной и той же хэш-функцией дают одинаковое хэш-значение. Это проблема, так как хэш-функции обычно используются для быстрого доступа к данным (например, в хэш-таблицах), и одинаковые хэши для разных данных нарушают уникальность ключей.

🚩Почему коллизии возникают?

🟠Ограниченный размер хэш-значений
Хэш-функция генерирует значения фиксированной длины (например, 32 или 64 бита), поэтому существует конечное количество возможных хэшей. Однако количество входных данных, которые можно подать на вход, теоретически бесконечно.
🟠Особенности алгоритма хэширования
Некоторые хэш-функции менее устойчивы к коллизиям из-за их структуры.

🚩Как справляться с коллизиями?

Есть несколько способов обработки коллизий в хэш-таблицах:

🟠Метод цепочек (chaining)
Каждое значение хэша хранит список элементов, которые получили одинаковый хэш. При добавлении нового ключа он просто добавляется в связанный список.

#include <iostream>
#include <list>
#include <vector>
using namespace std;

class HashTable {
    int size;
    vector<list<int>> table;

public:
    HashTable(int s) : size(s), table(s) {}

    int hashFunction(int key) {
        return key % size;
    }

    void insert(int key) {
        int index = hashFunction(key);
        table[index].push_back(key);
    }

    void display() {
        for (int i = 0; i < size; i++) {
            cout << i << ": ";
            for (int key : table[i]) {
                cout << key << " -> ";
            }
            cout << "NULL" << endl;
        }
    }
};

int main() {
    HashTable ht(5);
    ht.insert(10);
    ht.insert(15);
    ht.insert(20);
    ht.insert(7);
    ht.insert(2);
    ht.display();
    return 0;
}

🟠Открытая адресация (open addressing)
При коллизии новое значение записывается в следующую свободную ячейку в таблице. Используются разные стратегии, такие как линейное пробирование, квадратичное пробирование или двойное хэширование.

🟠Использование криптографических хэш-функций
Устойчивые хэш-функции (например, SHA-256) уменьшают вероятность коллизий, но они медленнее и чаще используются в безопасности.

Ставь 👍 и забирай 📚 Базу знаний

🤔 Как называется одинаковый результат после применения хэш-функции?

Это называется коллизия (hash collision) — ситуация, при которой два разных значения дают один и тот же хэш.

Ставь 👍 если знал ответ, 🔥 если нет
Забирай 📚Базу знаний

Завтра последний день!

Успей купить пожизненный easyoffer PRO - по цене 1 года

Покупаешь один раз — пользуешься всю жизнь.

👉 Акция до 31 марта: https://easyoffer.ru/pro

🤔 В каком порядке элементы списка инициализируются в конструкторе после двоеточия?

Порядок инициализации элементов списка инициализации конструктора (initializer list) определяется порядком объявления членов класса, а не порядком, указанным в списке инициализации. Это важно понимать, так как неправильный порядок может привести к неожиданным ошибкам, особенно при инициализации зависимых членов.

#include <iostream>

class MyClass {
private:
    int a;
    int b;
    int c;

public:
    MyClass(int x, int y, int z) : c(z), b(y), a(x) {
        std::cout << "a: " << a << ", b: " << b << ", c: " << c << std::endl;
    }
};

int main() {
    MyClass obj(1, 2, 3);
    return 0;
}

🚩Список инициализации конструктора

В конструкторе MyClass список инициализации указан в порядке c(z), b(y), a(x). Однако это не влияет на порядок инициализации членов класса. Члены класса будут инициализированы в порядке их объявления: a, затем b, затем c.

🚩Порядок инициализации

1⃣a инициализируется первым (значение x).
2⃣b инициализируется вторым (значение y).
3⃣c инициализируется третьим (значение z).

🚩Вывод программы

Программа выведет

a: 1, b: 2, c: 3

🚩Почему это важно

Неправильный порядок в списке инициализации не приведет к ошибке компиляции, но может вызвать логические ошибки, особенно если один член зависит от другого. Рассмотрим пример с зависимыми членами:

class MyClass {
private:
    int a;
    int& ref;

public:
    MyClass(int x) : ref(a), a(x) { // Неправильный порядок: ref инициализируется до a
        std::cout << "a: " << a << ", ref: " << ref << std::endl;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

🤔 Когда начинают жить и умирают глобальные и локальные переменные в С++?

Глобальные переменные живут на протяжении всей программы, начиная с инициализации до завершения. Локальные переменные живут с момента входа в блок кода до выхода из него.

Ставь 👍 если знал ответ, 🔥 если нет
Забирай 📚Базу знаний

🤔 Что знаешь про гарантии безопасности исключений?

Гарантии безопасности исключений (Exception Safety Guarantees) — это концепция, связанная с корректным поведением программы при возникновении исключений. Она определяет, насколько безопасно может завершиться выполнение функции или блока кода в случае выбрасывания исключения.

🚩Никаких гарантий (No Guarantee)

Этот уровень означает, что при возникновении исключения состояние программы может быть непредсказуемым. Объекты могут остаться в недопустимом состоянии, и поведение программы после выброса исключения неопределено.

void unsafeFunction(std::vector<int>& vec, int value) {
    vec.push_back(value); // Если здесь выбросится исключение, состояние vec не определено
    // ...
}

🚩Базовая гарантия (Basic Guarantee)

Этот уровень гарантирует, что не произойдёт утечек ресурсов или нарушений инвариантов объектов. После выброса исключения все объекты остаются в допустимом состоянии, однако состояние программы может быть частично изменено.

void safeFunction(std::vector<int>& vec, int value) {
    try {
        vec.push_back(value); // Если исключение, состояние vec остаётся корректным
    } catch (...) {
        // Обработка исключения
        std::cerr << "Ошибка при добавлении элемента!" << std::endl;
    }
}

🚩Сильная гарантия (Strong Guarantee)

Этот уровень гарантирует, что в случае возникновения исключения программа останется в исходном состоянии, как будто вызов функции никогда не происходил. Состояние откатывается до того, что было до вызова функции.

void addValue(std::vector<int>& vec, int value) {
    std::vector<int> temp = vec; // Создаём копию
    temp.push_back(value);       // Работаем с копией
    vec = temp;                  // Замена содержимого
}

🚩Гарантия отсутствия исключений (No-Throw Guarantee)

Этот уровень гарантирует, что функция никогда не выбрасывает исключений. Обычно применяется к ключевым операциям (например, деструкторам, перемещениям).

void safeSwap(std::vector<int>& a, std::vector<int>& b) noexcept {
    a.swap(b); // std::vector::swap гарантирует отсутствие исключений
}

🚩Как достигаются гарантии безопасности исключений?

🟠RAII (Resource Acquisition Is Initialization)
Использование классов, где ресурсы освобождаются в деструкторах. Например, std::unique_ptr или std::lock_guard.

🟠Копирование перед изменением
Применение принципа работы с временными копиями (как в примере сильной гарантии).

🟠Использование стандартных контейнеров
Библиотека STL предоставляет базовую гарантию безопасности исключений для большинства операций.

Ставь 👍 и забирай 📚 Базу знаний

🤔 Какая сложность поиска в set и unordered_set?

В set поиск имеет сложность O(log n), так как он реализован как сбалансированное бинарное дерево. В unordered_set сложность поиска в среднем O(1), но в худшем случае (при большом количестве коллизий) может достигать O(n).

Ставь 👍 если знал ответ, 🔥 если нет
Забирай 📚Базу знаний

🤔 Какое преимущество у list перед vector?

List обеспечивает быстрые вставки и удаления за \(O(1)\) в произвольной позиции, благодаря двусвязной структуре. В отличие от vector, list не требует перераспределения памяти при добавлении элементов. Однако доступ к элементам в list медленнее, так как отсутствует прямой индексированный доступ.

🚩Основные преимущества `std::list`

🟠Эффективные вставка и удаление элементов в середине контейнера
std::list реализован как двусвязный список, что позволяет эффективно вставлять и удалять элементы в любом месте контейнера за постоянное время O(1), если у вас уже есть итератор на нужное место.

#include <list>
#include <iostream>

int main() {
    std::list<int> myList = {1, 2, 3, 4, 5};
    auto it = myList.begin();
    std::advance(it, 2); // Переместить итератор на третий элемент

    myList.insert(it, 10); // Вставка за O(1)
    myList.erase(it);      // Удаление за O(1)

    for (int n : myList) {
        std::cout << n << " ";
    }

    return 0;
}   

🟠Нет необходимости в перемещении элементов при вставке или удалении
В std::vector при вставке или удалении элементов в середине контейнера происходит сдвиг элементов, что может быть дорогостоящей операцией (сложность O(n)). В std::list этого не происходит, так как элементы не хранятся в смежных блоках памяти.

🟠Постоянное время для операций вставки и удаления в произвольной позиции
Операции вставки и удаления в произвольной позиции в std::list всегда выполняются за O(1) (при условии, что у вас есть итератор на эту позицию), в то время как в std::vector они могут занимать до O(n) из-за необходимости сдвига элементов.

🟠Итераторы не инвалидируются при вставке или удалении элементов
В std::vector итераторы могут быть инвалидированы (становятся недействительными) при вставке или удалении элементов. В std::list итераторы остаются валидными, что делает работу с итераторами более безопасной и предсказуемой.

🚩Примеры, когда `std::list` предпочтительнее

🟠Частые вставки и удаления в середине контейнера
Если ваша задача предполагает частые операции вставки и удаления в середине контейнера, std::list будет предпочтительнее из-за своей эффективности в этих операциях.

🟠Работа с большим количеством итераторов
Если вам нужно работать с множеством итераторов, которые должны оставаться валидными даже после вставки или удаления элементов, std::list будет лучше подходить для таких задач.

🚩Ограничения `std::list`

🟠Доступ по индексу
В отличие от std::vector, в std::list нет возможности быстрого доступа к элементам по индексу. Для доступа к элементу необходимо пройти весь список от начала до нужного элемента (сложность O(n)).

🟠Высокие накладные расходы на память
std::list требует больше памяти на хранение элементов, так как для каждого элемента хранится два дополнительных указателя (на следующий и предыдущий элементы).

Ставь 👍 и забирай 📚 Базу знаний

🤔 Как называется возможность вызова функции без явного указания namespace?

Такую возможность называют ADL (Argument-Dependent Lookup) или Koenig Lookup. Компилятор автоматически ищет функцию в пространстве имен аргумента, если оно не указано явно.

Ставь 👍 если знал ответ, 🔥 если нет
Забирай 📚Базу знаний

🤔 Расскажи как запретить от него наследоваться

В C++ можно запретить наследование от класса несколькими способами.

🟠Использование `final` (C++11 и новее)
Ключевое слово final запрещает наследование от класса.

class Base final {
public:
    void show() { std::cout << "Base class\n"; }
};

// Ошибка! Наследование запрещено
class Derived : public Base {
};

🟠Закрытый или удалённый конструктор копирования и операторы присваивания
Можно сделать так, чтобы класс нельзя было создать или скопировать в унаследованных классах.

class Base {
private:
    Base() = default;  // Приватный конструктор
};

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

class Base {
protected:
    ~Base() = default; // Деструктор защищённый
};

🟠Закрытый (private) деструктор
Если сделать деструктор private, то класс нельзя будет корректно удалить через указатель.

class Base {
private:
    ~Base() = default;  // Закрытый деструктор
};

Ставь 👍 и забирай 📚 Базу знаний

🤔 В unordered_set поиск — константа?

Поиск в unordered_set имеет среднюю сложность O(1), но в худшем случае при хеш-коллизиях может быть O(n).

Ставь 👍 если знал ответ, 🔥 если нет
Забирай 📚Базу знаний

🤔 Вызов function call для конструктора и деструктора?

В C++ конструктор вызывается автоматически при создании объекта, а деструктор – при его уничтожении. Однако, если говорить о вызове конструктора и деструктора как function call (операция ()), то такой вызов невозможен напрямую, потому что конструкторы и деструкторы не являются обычными функциями.

🚩Вызов конструктора (function call)

Конструктор вызывается только через создание объекта

class A {
public:
    A() { std::cout << "Конструктор A\n"; }
};

int main() {
    A obj; // Автоматический вызов конструктора
}

Нельзя вызвать конструктор явно как функцию. Попытка вызвать конструктор напрямую приведет к ошибке

A(); // ❌ Ошибка: нельзя вызвать конструктор как обычную функцию

Можно вручную вызвать конструктор через placement new

#include <iostream>
#include <new>

class A {
public:
    A() { std::cout << "Конструктор A\n"; }
    ~A() { std::cout << "Деструктор A\n"; }
};

int main() {
    char buffer[sizeof(A)];  // Выделяем сырую память под объект
    A* obj = new (buffer) A; // Вызываем конструктор вручную (placement new)
    
    obj->~A(); // Вызываем деструктор вручную

    return 0;
}

🚩Вызов деструктора (function call)

Деструктор вызывается автоматически при уничтожении объекта

class A {
public:
    ~A() { std::cout << "Деструктор A\n"; }
};

int main() {
    A obj;  // Деструктор вызовется автоматически при выходе из `main`
}

Можно вызвать деструктор вручную, но это редко нужно. Деструктор можно вызвать явно, используя ~ИмяКласса()

A obj;
obj.~A(); // Вызов деструктора вручную (обычно не нужен)

Деструктор обязательно вызывается вручную при new. Если объект создается через new, то его нужно удалить вручную через delete, иначе будет утечка памяти:

A* ptr = new A();
delete ptr; // Автоматически вызывает деструктор

Вызов деструктора при placement new. Если объект создавался с placement new, то деструктор вызывается вручную

char buffer[sizeof(A)];
A* obj = new (buffer) A;

obj->~A(); // Явный вызов деструктора, так как delete не применяется

Ставь 👍 и забирай 📚 Базу знаний

🤔 Что пришло на смену auto_ptr?

На смену auto_ptr пришли умные указатели unique_ptr и shared_ptr. unique_ptr безопаснее управляет памятью и исключает случайное копирование, что было проблемой в auto_ptr. Эти новые указатели входят в стандарт C++11 и являются более надежными.

Ставь 👍 если знал ответ, 🔥 если нет
Забирай 📚Базу знаний

🤔 Почему со стеком работать быстрее чем с кучей?

🟠Управление памятью
Стек: Память в стеке управляется автоматически. Когда вызывается функция, память для её локальных переменных выделяется одним блоком при входе в функцию и освобождается при выходе из неё. Эта операция выполняется за постоянное время (O(1)).
Куча: Память в куче управляется вручную (программистом) или через автоматическое управление памятью (например, сборщик мусора). Выделение и освобождение памяти в куче требуют поиска подходящего блока памяти, что может занимать больше времени (O(log n) или даже O(n)).

🟠Локальность данных
Стек: Данные в стеке расположены компактно и последовательно. Это означает, что доступ к данным будет быстрее из-за лучшего использования кэш-памяти процессора.
Куча: Данные в куче могут быть фрагментированы, что приводит к меньшей эффективности кэширования и увеличению времени доступа.

🟠Предсказуемость
Стек: Память в стеке выделяется и освобождается в строго определённом порядке (LIFO - Last In, First Out). Это делает операции со стеком предсказуемыми и упрощает управление памятью.
Куча: Память в куче может выделяться и освобождаться в произвольном порядке, что приводит к фрагментации и усложняет управление памятью.

🟠Минимизация накладных расходов
Стек: Операции выделения и освобождения памяти на стеке имеют минимальные накладные расходы, так как это просто смещение указателя стека.
Куча: Операции выделения и освобождения памяти в куче требуют более сложных алгоритмов и могут включать в себя дополнительные накладные расходы, такие как управление списками свободных блоков и слияние фрагментов.

#include <iostream>

void stackFunction() {
    int stackArray[1000]; // Массив на стеке
    // Работа с массивом
}

void heapFunction() {
    int* heapArray = new int[1000]; // Массив в куче
    // Работа с массивом
    delete[] heapArray; // Освобождение памяти
}

int main() {
    stackFunction(); // Быстрая работа со стеком
    heapFunction();  // Медленная работа с кучей
    return 0;
}

Ставь 👍 и забирай 📚 Базу знаний

🤔 Как можно отсортировать list?

Контейнер std::list предоставляет встроенный метод sort(), который использует алгоритм сортировки слиянием (merge sort) с временной сложностью O(n log n). Также можно использовать std::vector, скопировав в него данные, отсортировав с std::sort(), а затем записав обратно в list.

Ставь 👍 если знал ответ, 🔥 если нет
Забирай 📚Базу знаний