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

🤔 Когда нужно объявлять деструктор виртуальным? Деструктор должен быть виртуальным, если класс предназначен для использования в качестве базового, и предполагается полиморфное удаление через указатель (Base* ptr = new Derived; delete ptr;). Без виртуального деструктора деструкторы производных классов не будут вызваны, что приведет к утечке памяти. Ставь 👍 если знал ответ, 🔥 если нет Забирай 📚Базу знаний

🤔 Чем отличаются STL контейнеры vector и array? Это контейнеры из стандартной библиотеки, но у них есть важные различия в управлении памятью, гибкости и производительности. 🟠Различия в управлении памятью std::vector использует динамическую память, выделяемую в куче (heap). Его размер может изменяться во время выполнения. std::array использует статическую память, выделяемую в стеке (stack) или в статической области памяти, и его размер фиксирован на этапе компиляции.

    
        #include <vector>
#include <array>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3}; // Размер может изменяться динамически
    vec.push_back(4);                 // Добавляем новый элемент

    std::array<int, 3> arr = {1, 2, 3}; // Размер фиксирован, нельзя добавить новый элемент

    std::cout << "Vector size: " << vec.size() << std::endl; // Выведет 4
    std::cout << "Array size: " << arr.size() << std::endl;  // Выведет 3

    return 0;
}{}
    

🟠Гибкость и изменение размера std::vector позволяет изменять размер в процессе работы, автоматически выделяя новую память при необходимости. std::array имеет фиксированный размер, который нельзя изменить после создания.

    
        std::vector<int> v = {1, 2, 3};
v.push_back(4); // Увеличиваем размер

std::array<int, 3> a = {1, 2, 3};
// a.push_back(4); // Ошибка! У std::array нет метода push_back{}
    

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

    
        #include <vector>
#include <array>
#include <chrono>
#include <iostream>

int main() {
    constexpr int N = 1'000'000;
    
    std::vector<int> vec(N, 1); // Динамический массив
    std::array<int, N> arr{};   // Статический массив
    
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; ++i) vec[i] += 1;
    auto end = std::chrono::high_resolution_clock::now();
    std::cout << "Vector time: " 
              << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() 
              << " us" << std::endl;

    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; ++i) arr[i] += 1;
    end = std::chrono::high_resolution_clock::now();
    std::cout << "Array time: " 
              << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() 
              << " us" << std::endl;

    return 0;
}{}
    

🟠Совместимость с C-API std::array хранит данные как обычный C-массив, поэтому можно легко передавать его в функции, ожидающие int*. std::vector использует динамическую память, но можно получить указатель на внутренний буфер с помощью data().

    
        void processArray(int* arr, size_t size) {
    for (size_t i = 0; i < size; ++i) {
        std::cout << arr[i] << " ";
    }
}

int main() {
    std::array<int, 3> arr = {1, 2, 3};
    std::vector<int> vec = {4, 5, 6};

    processArray(arr.data(), arr.size()); // std::array можно передавать в C-функции
    processArray(vec.data(), vec.size()); // std::vector тоже можно передавать

    return 0;
}{}
    

🟠Итераторы и стандартные алгоритмы Оба контейнера поддерживают итераторы и совместимы со стандартными алгоритмами из #include <algorithm>

    
        #include <iostream>
#include <vector>
#include <array>
#include <algorithm>

int main() {
    std::vector<int> vec = {3, 1, 4, 1, 5};
    std::array<int, 5> arr = {3, 1, 4, 1, 5};

    std::sort(vec.begin(), vec.end());
    std::sort(arr.begin(), arr.end());

    for (int n : vec) std::cout << n << " "; // 1 1 3 4 5
    std::cout << std::endl;
    for (int n : arr) std::cout << n << " "; // 1 1 3 4 5

    return 0;
}{}
    

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

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

🤔 Какие знаешь сортировки? Существует множество алгоритмов сортировки, каждый из которых имеет свои преимущества и недостатки в зависимости от условий использования. Рассмотрим основные из них. 🟠Сортировка пузырьком (Bubble Sort) Простейший алгоритм, который многократно проходит по массиву, сравнивая соседние элементы и меняя их местами, если они стоят в неправильном порядке. Сложность: O(n²) в худшем и среднем случаях, O(n) в лучшем случае (если массив уже отсортирован). Когда использовать: Почти никогда, так как слишком медленный.

    
        void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
}{}
    

🟠Сортировка выбором (Selection Sort) На каждом шаге ищется минимальный элемент и ставится в начало неотсортированной части массива. Сложность: O(n²) всегда. Когда использовать: Если важна простота реализации, но нужна немного лучшая производительность, чем у пузырьковой сортировки.

    
        void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        std::swap(arr[i], arr[minIdx]);
    }
}{}
    

🟠Сортировка вставками (Insertion Sort) Берём один элемент и вставляем его в правильное место среди уже отсортированных элементов. Сложность: O(n²) в худшем случае, O(n) в лучшем (если массив почти отсортирован). Когда использовать: Для небольших массивов или почти отсортированных данных.

    
        void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}{}
    

🟠Сортировка слиянием (Merge Sort) Разделяем массив на две части, рекурсивно сортируем их и затем сливаем. Сложность: O(n log n) всегда. Когда использовать: Когда нужна стабильность и предсказуемая скорость работы.

    
        void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1, n2 = r - m;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int i = 0; i < n2; i++) R[i] = arr[m + 1 + i];

    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) arr[k++] = (L[i] < R[j]) ? L[i++] : R[j++];
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}{}
    

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

🤔 Что будет, если для беззнаковой переменной, равной 0, сделать декремент? Значение переменной перейдёт в максимальное значение типа (например, UINT_MAX для unsigned int). Это связано с переполнением, так как беззнаковые типы используют арифметику по модулю. Ставь 👍 если знал ответ, 🔥 если нет Забирай 📚Базу знаний

🤔 Для чего может применяться в С++ виртуальное наследование? Виртуальное наследование применяется для решения проблемы "ромбовидного наследования" (или "diamond problem"), которая возникает в иерархиях классов с множественным наследованием. Это проблема возникает, когда класс наследуется от двух классов, которые в свою очередь наследуются от одного общего базового класса. В результате создаются две копии базового класса в наследнике, что приводит к неоднозначностям и увеличению использования памяти.

    
        #include <iostream>

class A {
public:
    void show() {
        std::cout << "Class A" << std::endl;
    }
};

class B : public A {};
class C : public A {};
class D : public B, public C {};

int main() {
    D obj;
    // obj.show(); // Ошибка: неоднозначность, show() есть и в B, и в C
    return 0;
}{}
    

🚩Решение проблемы с использованием виртуального наследования Виртуальное наследование решает эту проблему, гарантируя, что в иерархии будет только одна копия базового класса. Это достигается с помощью ключевого слова virtual при наследовании.

    
        #include <iostream>

class A {
public:
    void show() {
        std::cout << "Class A" << std::endl;
    }
};

class B : virtual public A {};
class C : virtual public A {};
class D : public B, public C {};

int main() {
    D obj;
    obj.show(); // Корректно: вызов метода show() из A
    return 0;
}{}
    

🚩Как работает виртуальное наследование 🟠Одна копия базового класса При виртуальном наследовании в наследуемом классе создается только одна копия базового класса, независимо от того, сколько раз он виртуально наследуется. 🟠Оптимизация памяти Виртуальное наследование предотвращает создание множества копий базового класса, что экономит память. 🟠Явное разрешение неоднозначности Виртуальное наследование устраняет неоднозначности, связанные с вызовом методов и доступом к членам базового класса. 🟠Пример с конструкторами При виртуальном наследовании конструкторы базовых классов вызываются инициализирующим классом.

    
        #include <iostream>

class A {
public:
    A() {
        std::cout << "Constructor of A" << std::endl;
    }
};

class B : virtual public A {
public:
    B() {
        std::cout << "Constructor of B" << std::endl;
    }
};

class C : virtual public A {
public:
    C() {
        std::cout << "Constructor of C" << std::endl;
    }
};

class D : public B, public C {
public:
    D() {
        std::cout << "Constructor of D" << std::endl;
    }
};

int main() {
    D obj; // Вывод: Constructor of A, Constructor of B, Constructor of C, Constructor of D
    return 0;
}{}
    

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

🤔 Что известно о ключевом слове override? Ключевое слово override используется для явного указания, что метод переопределяет виртуальный метод базового класса. Оно предотвращает ошибки, связанные с неправильным именованием или сигнатурой методов. Ставь 👍 если знал ответ, 🔥 если нет Забирай 📚Базу знаний

🤔 За счет чего появляетcя амортизированная константная сложность в map? std::map реализован как самобалансирующееся красно-чёрное дерево (Red-Black Tree). Вставка (insert) Поиск (find) Удаление (erase) выполняются за O(log n) в худшем и среднем случае. Однако std::map не имеет амортизированной O(1) сложности, как std::unordered_map. Амортизированная сложность O(1) появляется в std::unordered_map, но не в std::map! 🚩Как работает балансировка? Каждая операция (insert, erase) перестраивает дерево так, чтобы его высота оставалась O(log n). Это достигается с помощью поворотов (rotate left, rotate right) и перекраски узлов. Вставка нового элемента иногда требует перестройки дерева, но в среднем это занимает O(log n).

    
                10
       /  \
      5    20{}
    

🚩Почему `std::unordered_map` имеет амортизированное O(1)? В std::unordered_map используется хеш-таблица, где: Операции insert, find, erase – O(1) в среднем (поиск по хешу). Но если возникает коллизия (несколько ключей в одном бакете), сложность ухудшается до O(n). Чтобы избежать O(n), std::unordered_map использует rehash (перехеширование). При увеличении элементов контейнер расширяет бакеты. Операции разделяются по разным вызовам → за счёт этого амортизированная сложность O(1). Ставь 👍 и забирай 📚 Базу знаний

🤔 Асимптотическая сложность вставки и удаления в list и vector? В list сложность вставки и удаления — O(1), так как он двусвязный. В vector вставка и удаление в конец — O(1), а в произвольное место — O(n) из-за необходимости сдвига элементов. Ставь 👍 если знал ответ, 🔥 если нет Забирай 📚Базу знаний

🤔 Для чего при перегрузке оператора присваивания возвращать ссылку? При перегрузке оператора = в C++ принято возвращать ссылку на текущий объект (*this). Это позволяет цепочечное присваивание (a = b = c), а также улучшает производительность и удобство использования. 🚩Правильная сигнатура оператора `=`

    
        class MyClass {
public:
    MyClass& operator=(const MyClass& other) {
        if (this != &other) {  // Защита от самоприсваивания
            // Копируем данные
        }
        return *this; // Возвращаем ссылку на текущий объект
    }
};{}
    

🚩Что даёт возвращение ссылки (`T&`)? Поддержка цепочки присваивания (a = b = c)

    
        a = b = c;  // Интерпретируется как a = (b = c);{}
    

Пример

    
        #include <iostream>

class MyClass {
public:
    int value;
    MyClass(int v) : value(v) {}

    MyClass& operator=(const MyClass& other) {
        if (this != &other) { // Защита от самоприсваивания
            value = other.value;
        }
        return *this;
    }
};

int main() {
    MyClass a(1), b(2), c(3);
    a = b = c; // Работает, потому что `b = c` возвращает ссылку на `b`
    std::cout << "a: " << a.value << ", b: " << b.value << ", c: " << c.value << std::endl;
}{}
    

Вывод

    
        a: 3, b: 3, c: 3{}
    

🟠Убираем лишнее копирование (повышаем производительность) Если оператор = вернёт не ссылку, а объект, то произойдёт лишнее копирование. Плохо (возвращаем объект, а не ссылку)

    
        MyClass operator=(const MyClass& other) { // ⚠️ Ошибка: возвращаем объект
    value = other.value;
    return *this; // Здесь создаётся временный объект (лишняя копия!)
}{}
    

Хорошо (возвращаем T&)

    
        MyClass& operator=(const MyClass& other) { // ✅ Возвращаем ссылку
    value = other.value;
    return *this;
}{}
    

🚩Поддержка `if (a = b)` Если оператор = вернёт ссылку, мы можем использовать его в условии:

    
        if ((a = b).value == 42) { // ОК
    std::cout << "Присваивание выполнено, a == 42";
}{}
    

🚩Что если вернуть `void`? Если оператор = вернёт void, цепочка a = b = c; не будет работать.

    
        class MyClass {
public:
    void operator=(const MyClass& other) { // ⚠️ Ошибка!
        value = other.value;
    }
};

int main() {
    MyClass a, b, c;
    a = b = c; // ❌ Ошибка: `b = c` возвращает void, а `a = void` не работает!
}{}
    

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