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

🤔 Асимптотическая сложность вставки и удаления в list и vector?

В list сложность вставки и удаления — O(1), так как он двусвязный. В vector вставка и удаление в конец — O(1), а в произвольное место — O(n) из-за необходимости сдвига элементов.

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

🤔 Для чего используется ключевое слово volatile?

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

🚩Основные применения

🟠Аппаратные регистры
Переменные, связанные с аппаратными устройствами, такими как порты ввода-вывода, часто меняются вне контроля программы. Использование volatile предотвращает оптимизации, которые могли бы кэшировать значение регистров.

volatile int* port = reinterpret_cast<int*>(0x400);
*port = 42; // Запись в аппаратный регистр   

🟠Переменные, изменяемые прерываниями
В системах реального времени и встроенных системах значения переменных могут изменяться в обработчиках прерываний. volatile гарантирует, что каждое обращение к такой переменной будет действительным.

volatile bool interruptFlag = false;

void interruptHandler() {
    interruptFlag = true; // Устанавливается в обработчике прерывания
}

void mainFunction() {
    while (!interruptFlag) {
        // Ожидание установки флага прерывания
    }
    // Обработка прерывания
}   

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

volatile bool stopThread = false;

void workerThread() {
    while (!stopThread) {
        // Выполнение работы
    }
}

int main() {
    std::thread t(workerThread);
    // ...
    stopThread = true; // Остановка рабочего потока
    t.join();
    return 0;
}   

🚩Особенности и ограничения

🟠Оптимизация компиляции
volatile предотвращает оптимизации компилятором, которые могли бы удалить или кэшировать доступы к переменной.

🟠Не потокобезопасность
volatile не обеспечивает потокобезопасность. Для обеспечения корректной работы в многопоточной среде следует использовать мьютексы, атомарные операции или другие механизмы синхронизации.

🟠Совместное использование с `const`
Переменные могут быть как const volatile, если они не должны изменяться программой, но могут изменяться внешними факторами.

🚩Пример: Аппаратные регистры

#include <iostream>

volatile int* hardwareRegister = reinterpret_cast<int*>(0x400);

void writeToRegister(int value) {
    *hardwareRegister = value; // Запись в регистр
}

int readFromRegister() {
    return *hardwareRegister; // Чтение из регистра
}

int main() {
    writeToRegister(100);
    std::cout << "Register value: " << readFromRegister() << std::endl;
    return 0;
}

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

🤔 Когда возникает самый худший случай поиска в unordered_set?

Худший случай возникает, когда все элементы попадают в одну ячейку хеш-таблицы из-за коллизий, превращая поиск в линейный (O(n)).

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

🤔 Как работает счетчик у shared_ptr?

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

🚩Как он работает

🟠Инициализация и копирование
Когда создается shared_ptr и он начинает управлять объектом, создается "блок управления" (control block), содержащий счетчик ссылок.
Каждый раз, когда создается новый shared_ptr, который указывает на тот же объект (через копирование или присваивание), счетчик ссылок увеличивается.

🟠Уничтожение и перемещение
Когда shared_ptr уничтожается или его значение присваивается другому shared_ptr, счетчик ссылок уменьшается.
Если shared_ptr перемещается (используя move-семантику), счетчик ссылок не изменяется, так как владение объектом передается новому shared_ptr, а старый перестает владеть объектом.

🟠Освобождение ресурсов
Как только счетчик ссылок достигает нуля (то есть последний shared_ptr, указывающий на объект, был уничтожен или переназначен), объект удаляется. Соответственно, если для объекта был задан пользовательский делетер, он вызывается вместо стандартного delete.

🚩Счетчик слабых ссылок

shared_ptr также поддерживает weak_ptr, который представляет собой "слабую" ссылку на объект. weak_ptr позволяет наблюдать за объектом, не увеличивая счетчик сильных ссылок:
Счетчик слабых ссылок отслеживает, сколько weak_ptr указывает на объект. Он не предотвращает удаление объекта, когда счетчик сильных ссылок достигает нуля.
Когда счетчик сильных ссылок достигает нуля и объект удаляется, счетчик слабых ссылок все еще отслеживает, сколько weak_ptr наблюдают за объектом. Объект блока управления остается, пока не исчезнут все weak_ptr.

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

🤔 В set сложность вставки, удаления, поиска - логарифмическая?

Да, в стандартной реализации `std::set` в C++ вставка, удаление и поиск выполняются за O(log n), так как `set` реализован как сбалансированное бинарное дерево (обычно красно-чёрное дерево). Логарифмическая сложность обеспечивается благодаря тому, что элементы хранятся в отсортированном порядке, и операция деления дерева пополам происходит при каждом шаге. Это делает операции эффективными даже для больших наборов данных.

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

🤔 Какой подсчет ссылок имеется в shared_ptr?

В умном указателе shared_ptr используется два основных счётчика: счётчик сильных ссылок (strong reference count) и счётчик слабых ссылок (weak reference count). Эти счётчики управляют жизненным циклом объекта и связанных с ним ресурсов различными способами.

🚩Счётчик сильных ссылок

Увеличивается каждый раз, когда новый shared_ptr создаётся как копия другого shared_ptr или когда объект присваивается shared_ptr. Этот счётчик уменьшается, когда shared_ptr уничтожается или когда его значение присваивается другому объекту. Когда счётчик достигает нуля, это означает, что больше нет shared_ptr, управляющих этим объектом, и объект удаляется. Это гарантирует, что ресурсы, связанные с объектом, будут освобождены только тогда, когда не останется ни одной "сильной" ссылки.

🚩Счётчик слабых ссылок

Используется вместе с weak_ptr, другим типом умных указателей, который может ссылаться на объект, управляемый shared_ptr, но не увеличивает счётчик сильных ссылок. Слабые ссылки не предотвращают удаление объекта, к которому они имеют доступ, так как не участвуют в владении объектом. Счётчик слабых ссылок увеличивается каждый раз, когда создаётся weak_ptr, указывающий на объект, и уменьшается, когда такой weak_ptr уничтожается. Когда счётчик сильных ссылок достигает нуля и объект удаляется, память, выделенная под сам объект, освобождается, но "control block" (блок управления), содержащий счётчики, сохраняется до тех пор, пока счётчик слабых ссылок также не обнулится.

#include <iostream>
#include <memory>

int main() {
    std::shared_ptr<int> sp1 = std::make_shared<int>(10);
    std::cout << "sp1 use_count: " << sp1.use_count() << '\n';  // Вывод: 1

    {
        std::shared_ptr<int> sp2 = sp1;  // Копирование shared_ptr
        std::cout << "sp1 use_count after copy: " << sp1.use_count() << '\n';  // Вывод: 2

        std::weak_ptr<int> wp1 = sp1;  // Создание weak_ptr
        std::cout << "wp1 use_count: " << wp1.use_count() << '\n';  // Вывод: 2
    }  // sp2 выходит из области видимости, use_count уменьшается до 1

    std::cout << "sp1 use_count after sp2 destruction: " << sp1.use_count() << '\n';  // Вывод: 1
    return 0;
}

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

🤔 Что происходит, когда случается коллизия при получении ключа для контейнера?

1. При коллизии несколько ключей имеют одинаковый хеш-код.
2. Контейнер использует методы разрешения коллизий:
o Связанные списки (chaining): все элементы с одним хешем добавляются в связанный список внутри одного bucket'а.
o Открытая адресация: поиск свободной ячейки для хранения данных.
3. После нахождения bucket'а выполняется проверка на равенство ключей с помощью метода equals.

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

🤔 Для чего используется ключевое слово volatile?

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

🚩Основные применения

🟠Аппаратные регистры
Переменные, связанные с аппаратными устройствами, такими как порты ввода-вывода, часто меняются вне контроля программы. Использование volatile предотвращает оптимизации, которые могли бы кэшировать значение регистров.

volatile int* port = reinterpret_cast<int*>(0x400);
*port = 42; // Запись в аппаратный регистр   

🟠Переменные, изменяемые прерываниями
В системах реального времени и встроенных системах значения переменных могут изменяться в обработчиках прерываний. volatile гарантирует, что каждое обращение к такой переменной будет действительным.

volatile bool interruptFlag = false;

void interruptHandler() {
    interruptFlag = true; // Устанавливается в обработчике прерывания
}

void mainFunction() {
    while (!interruptFlag) {
        // Ожидание установки флага прерывания
    }
    // Обработка прерывания
}   

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

volatile bool stopThread = false;

void workerThread() {
    while (!stopThread) {
        // Выполнение работы
    }
}

int main() {
    std::thread t(workerThread);
    // ...
    stopThread = true; // Остановка рабочего потока
    t.join();
    return 0;
}   

🚩Особенности и ограничения

🟠Оптимизация компиляции
volatile предотвращает оптимизации компилятором, которые могли бы удалить или кэшировать доступы к переменной.

🟠Не потокобезопасность
volatile не обеспечивает потокобезопасность. Для обеспечения корректной работы в многопоточной среде следует использовать мьютексы, атомарные операции или другие механизмы синхронизации.

🟠Совместное использование с `const`
Переменные могут быть как const volatile, если они не должны изменяться программой, но могут изменяться внешними факторами.

🚩Пример: Аппаратные регистры

#include <iostream>

volatile int* hardwareRegister = reinterpret_cast<int*>(0x400);

void writeToRegister(int value) {
    *hardwareRegister = value; // Запись в регистр
}

int readFromRegister() {
    return *hardwareRegister; // Чтение из регистра
}

int main() {
    writeToRegister(100);
    std::cout << "Register value: " << readFromRegister() << std::endl;
    return 0;
}

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

🤔 Как работает счетчик ссылок в shared_ptr?

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

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

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

В 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;  // Закрытый деструктор
};

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

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

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

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

🤔 Как сделать операцию удаления элемента из начала, если порядок элементов не важен, в vector?

Иногда требуется удалить элемент из начала контейнера std::vector, когда порядок элементов не важен. Операция удаления первого элемента может быть затратной по времени, поскольку требует сдвига всех последующих элементов. Чтобы минимизировать эти затраты, можно заменить первый элемент последним и затем удалить последний элемент.

🚩Как это используется?

Этот подход позволяет выполнить операцию удаления за постоянное время O(1) вместо линейного O(n).

🚩Пример

void removeFirstElement(std::vector<int>& vec) {
    if (!vec.empty()) {
        std::swap(vec.front(), vec.back()); // Обмен первого и последнего элементов
        vec.pop_back(); // Удаление последнего элемента
    }
}

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

    std::cout << "Before removal: ";
    for (int i : vec) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    removeFirstElement(vec);

    std::cout << "After removal: ";
    for (int i : vec) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

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

🤔 Что лежит в основе работы unordered_set, unordered_map и set, map?

1. Set и Map: основаны на сбалансированных бинарных деревьях, обычно красно-чёрных. Они поддерживают упорядоченность данных.
2. Unordered_set и Unordered_map: основаны на хеш-таблицах, обеспечивающих быструю вставку, удаление и поиск.
3. Основной принцип различия — структура данных: деревья для упорядоченности, хеш-таблицы для скорости.

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

🤔 Что такое наследование?

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

🚩Основные аспекты

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

🟠Расширяемость
Делает систему более гибкой, так как позволяет создавать новые классы на основе уже существующих. Это помогает в адаптации и расширении функциональности системы.

🟠Иерархия
Вводит естественную организацию, создавая иерархическую структуру классов. Это упрощает понимание отношений между различными классами и их взаимодействия.

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

🚩Типы

🟠Одиночное наследование
Класс наследуется от одного базового класса.

🟠Множественное наследование
Класс может наследоваться от более чем одного класса. Не все языки поддерживают множественное наследование из-за сложности разрешения различных аспектов, таких как ромбовидное наследование (diamond problem).

🟠Многоуровневое наследование
Формируется когда класс наследуется от другого производного класса, формируя многоуровневую структуру.

#include <iostream>
using namespace std;

// Базовый класс
class Animal {
public:
    void eat() {
        cout << "I can eat!" << endl;
    }
};

// Производный класс
class Dog : public Animal {
public:
    void bark() {
        cout << "I can bark! Woof woof!" << endl;
    }
};

int main() {
    Dog myDog;
    myDog.eat();  // Вызов метода базового класса
    myDog.bark(); // Вызов метода производного класса
    return 0;
}

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

🤔 Из чего состоит shared_ptr?

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

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

🤔 В какой момент принимается решение, что хеш таблице надо перестроиться?

Решение о необходимости перестроения (рехеширования) хэш-таблицы принимается на основе значения нагрузки (load factor). Нагрузка — это отношение количества элементов в хэш-таблице к количеству бакетов (размеру массива).

🚩Порог нагрузки

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

Формула нагрузки:

\text{load factor} = \frac{\text{number of elements}}{\text{size of table}} 

Типичные пороговые значения: Пороговое значение нагрузки часто устанавливается в пределах от 0.5 до 1.0, в зависимости от реализации. Например, std::unordered_map в стандартной библиотеке C++ по умолчанию использует пороговое значение 1.0.

🚩Процесс рехеширования

1⃣Увеличение размера таблицы
Размер массива увеличивается, часто в два раза.

2⃣Перераспределение элементов
Все существующие элементы перераспределяются в новую таблицу с использованием новой хэш-функции или той же хэш-функции, но с новым размером таблицы.

🚩Пример

#include <iostream>
#include <list>
#include <vector>

class HashTable {
private:
    int currentSize;
    int numberOfElements;
    double loadFactorThreshold;
    std::vector<std::list<std::pair<int, std::string>>> table;

    void rehash() {
        int oldSize = currentSize;
        currentSize *= 2; // Увеличиваем размер таблицы
        std::vector<std::list<std::pair<int, std::string>>> newTable(currentSize);

        for (const auto& list : table) {
            for (const auto& pair : list) {
                int hashValue = pair.first % currentSize;
                newTable[hashValue].emplace_back(pair.first, pair.second);
            }
        }

        table = std::move(newTable);
    }

public:
    HashTable(int size = 10, double threshold = 0.75) 
        : currentSize(size), numberOfElements(0), loadFactorThreshold(threshold) {
        table.resize(currentSize);
    }

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

    void insertItem(int key, std::string value) {
        int hashValue = hashFunction(key);
        table[hashValue].emplace_back(key, value);
        numberOfElements++;

        // Проверяем, нужно ли выполнять рехеширование
        if (static_cast<double>(numberOfElements) / currentSize > loadFactorThreshold) {
            rehash();
        }
    }

    void displayTable() {
        for (int i = 0; i < currentSize; i++) {
            if (!table[i].empty()) {
                std::cout << "Bucket " << i << ": ";
                for (auto& pair : table[i]) {
                    std::cout << "[" << pair.first << ": " << pair.second << "] ";
                }
                std::cout << std::endl;
            }
        }
    }
};

int main() {
    HashTable ht;
    ht.insertItem(1, "one");
    ht.insertItem(2, "two");
    ht.insertItem(11, "eleven"); // Триггер рехеширования при необходимости

    ht.displayTable();
    // Вывод:
    // Bucket 1: [1: one] 
    // Bucket 2: [2: two] 
    // Bucket 11: [11: eleven]

    return 0;
}

🚩Когда происходит

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

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

🤔 Что будет, если вызвать оператор delete на nullptr?

Если вызвать оператор delete на nullptr, ничего не произойдет. Это безопасная операция, так как стандарт гарантирует, что освобождение nullptr не вызовет ошибок или исключений.

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

🤔 В чем разница map и unordered_map?

std::map и std::unordered_map – оба являются ассоциативными контейнерами в C++, но они устроены по-разному и имеют разные скорости работы.

🚩Как устроены контейнеры?

🟠`std::map` – красно-чёрное дерево (сбалансированное BST)
Все ключи хранятся упорядоченно.
Операции insert, erase, find выполняются за O(log n).
Упорядоченность важна, если требуется поиск в диапазоне (lower_bound, upper_bound).

#include <map>
#include <iostream>

int main() {
    std::map<int, std::string> m;
    m[2] = "B";
    m[1] = "A";
    m[3] = "C";

    for (const auto& [key, value] : m) {
        std::cout << key << " -> " << value << '\n'; 
    }
}

Вывод (отсортирован!)

1 -> A  
2 -> B  
3 -> C  

🟠`std::unordered_map` – хеш-таблица
Нет сортировки, но поиск выполняется быстро – O(1) (в среднем).
Использует хеш-функцию, поэтому доступ к элементам зависит от хеширования.
Может быть медленным при коллизиях (O(n) в худшем случае).

#include <unordered_map>
#include <iostream>

int main() {
    std::unordered_map<int, std::string> um;
    um[2] = "B";
    um[1] = "A";
    um[3] = "C";

    for (const auto& [key, value] : um) {
        std::cout << key << " -> " << value << '\n';
    }
}

Вывод (порядок непредсказуем!)

2 -> B  
1 -> A  
3 -> C  

🚩Когда использовать `map`, а когда `unordered_map`?

🟠Используйте `std::map`, если:
Нужно сортированное хранение ключей.
Требуется поиск по диапазону (lower_bound, upper_bound).
Хеш-функция для ключей сложна или недоступна (например, std::pair без кастомного хешера).

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

🤔 Как работает счетчик у shared_ptr?

Счетчик ссылок в `std::shared_ptr` увеличивается каждый раз, когда новый `shared_ptr` создается с указателем на объект, и уменьшается, когда `shared_ptr` уничтожается или перестает указывать на объект. Когда счетчик достигает нуля, объект уничтожается.

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

🤔 Асимптотическая сложность в list?

std::list — это двусвязный список, где каждый элемент хранит ссылку на предыдущий и следующий элементы. Это даёт эффективное добавление и удаление элементов в любой части списка, но делает доступ по индексу медленным

🚩Разбор операций в `std::list` с примерами

Добавление в начало и конец — O(1)

std::list<int> lst;
lst.push_back(10);  // O(1)
lst.push_front(5);  // O(1)

Доступ по индексу — O(n)

auto it = std::next(lst.begin(), 2); // O(n), приходится идти от начала
std::cout << *it << std::endl;

Вставка и удаление по итератору — O(1)

auto it = lst.begin();
std::advance(it, 1);  // Двигаем итератор на 1 элемент (O(n))

lst.insert(it, 8);  // O(1), просто меняем указатели
lst.erase(it);      // O(1), просто изменяем ссылки соседних элементов

Поиск элемента — O(n)

auto it = std::find(lst.begin(), lst.end(), 8); // O(n)

Сортировка — O(n log n)

lst.sort(); // O(n log n), потому что используется сортировка слиянием

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