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

Какая будет сложность удаления элемента с начала в vector ? Спросят с вероятностью 17% Удаление элемента из начала вектора (std::vector) имеет линейную временную сложность, то есть \(O(n)\), где \(n\) — текущее количество элементов в векторе. Это связано с тем, что std::vector представляет собой динамический массив, где элементы хранятся в непрерывном блоке памяти. Почему удаление из начала имеет сложность \(O(n)\) Когда вы удаляете элемент из начала вектора, все элементы, которые следуют за удаленным элементом, должны быть сдвинуты на одну позицию влево, чтобы заполнить образовавшийся пробел. Этот процесс сдвига каждого элемента является причиной того, что операция удаления элемента из начала имеет линейную сложность: ✅Сдвиг элементов: Для каждого элемента, начиная со второго и до последнего, требуется копирование в предыдущую позицию. Это значит, что если в векторе \(n\) элементов, вам потребуется выполнить \(n-1\) операций копирования. Вот как может выглядеть удаление первого элемента вектора на C++:

#include <iostream>
#include <vector>

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

    // Удаление первого элемента
    vec.erase(vec.begin());

    // Вывод результата
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

В этом примере, метод erase вызывается с итератором, указывающим на начало вектора. Этот вызов приводит к сдвигу всех остальных элементов вектора на одну позицию влево. Альтернативы для улучшения производительности Если в вашем приложении часто требуется удалять элементы из начала контейнера, возможно, стоит рассмотреть использование других структур данных, таких как std::deque или std::list. Эти структуры данных обеспечивают более эффективное удаление элементов из начала или конца: ✅`std::deque`: Двусторонняя очередь (deque) позволяет быстрое добавление и удаление элементов как в начале, так и в конце, с постоянной временной сложностью \(O(1)\). ✅`std::list`: Список в C++ представляет собой двусвязный список, который также позволяет удаление элементов с любой позиции, в том числе из начала и конца, с постоянной временной сложностью \(O(1)\). Выбор структуры данных зависит от конкретных требований вашего приложения, особенно от типов операций, которые вы планируете наиболее часто выполнять. 👉 Можно посмотреть Примеры как отвечают люди на этот вопрос, или перейти К списку 434 вопроса на C/C++ разработчика. Ставь 👍 если нравится контент 🔐 База собесов | 🔐 База тестовых

❤️ Все платные курсы и книги выложили в Telegram Найденные материалы по всем популярным языкам программирования теперь доступны бесплатно. Выбирай направление и обучайся: — Frontend-разработчик — Backend-разработчик — Python-разработчик — Kotlin-разработчик — Swift-разработчик — Golang-разработчик — Java-разработчик — C#-разработчик — C/C++-разработчик — PHP-разработчик — Rust-разработчик — QA-тестировщик — DevOps-инженер 🔒 Ежедневно куча материалов сливается в канал Easy Dev

Зачем нужен чисто виртуальный метод и какой синтаксис ? Спросят с вероятностью 17% Чисто виртуальный метод используется для создания абстрактного базового класса, который определяет интерфейс для всех производных классов, не предоставляя конкретной реализации этого метода. Это позволяет обеспечить единообразие и строгую структуру для семейства классов, а также гарантировать, что каждый производный класс предоставляет свою реализацию абстрактных методов. Зачем они нужны 1️⃣Определение интерфейса: Чисто виртуальные методы определяют интерфейс, который должны реализовать все производные классы. Это гарантирует, что все производные классы будут иметь согласованное поведение. 2️⃣Предотвращение создания экземпляров базового класса: Классы с чисто виртуальными методами называются абстрактными классами. Экземпляры абстрактных классов не могут быть созданы, что помогает предотвратить ошибки использования неполных или некорректных реализаций. 3️⃣Поддержка полиморфизма: Использование абстрактных классов вместе с чисто виртуальными методами позволяет применять полиморфное поведение, где вызов метода через базовый класс приведет к выполнению соответствующей реализации в производном классе. Чисто виртуальный метод объявляется с помощью синтаксиса = 0 в конце объявления метода в классе. Вот пример абстрактного базового класса с чисто виртуальным методом:

class AbstractClass {
public:
    virtual void abstractMethod() = 0; // Чисто виртуальный метод

    virtual ~AbstractClass() {} // Виртуальный деструктор для корректного удаления
};

class ConcreteClass : public AbstractClass {
public:
    void abstractMethod() override {
        std::cout << "Реализация метода в производном классе." << std::endl;
    }
};

int main() {
    // AbstractClass a; // Ошибка: нельзя создать объект абстрактного класса
    AbstractClass* ptr = new ConcreteClass();
    ptr->abstractMethod(); // Вызывает метод, реализованный в ConcreteClass

    delete ptr; // Освобождение памяти
    return 0;
}

В этом примере, AbstractClass содержит чисто виртуальный метод abstractMethod(), что делает его абстрактным. Вы не можете создать экземпляр AbstractClass, но можете использовать указатели и ссылки на AbstractClass для доступа к объектам ConcreteClass. ConcreteClass реализует этот метод, предоставляя конкретные действия. Чисто виртуальные методы являются ключевыми для проектирования расширяемых и модульных систем, использующих полиморфизм и абстракцию, что особенно важно в больших программных проектах и системах с развитой иерархией классов. 👉 Можно посмотреть Примеры как отвечают люди на этот вопрос, или перейти К списку 434 вопроса на C/C++ разработчика. Ставь 👍 если нравится контент 🔐 База собесов | 🔐 База тестовых

Какое присваивание разрешает unique_ptr ? Спросят с вероятностью 17% unique_ptr — это умный указатель, предоставляющий строгую собственность и управление одним объектом через указатель. Один из его ключевых аспектов заключается в том, что он не позволяет копирование объекта, чтобы гарантировать, что только один unique_ptr может владеть объектом. Однако unique_ptr поддерживает перемещение, что позволяет передавать право собственности на объект от одного unique_ptr к другому. Разрешенные операции присваивания 1️⃣Присваивание перемещением (Move assignment): unique_ptr может быть перемещен с помощью оператора присваивания перемещения. Это изменяет владельца ресурса, освобождая предыдущего владельца от ответственности и перенося права на новый unique_ptr.

      std::unique_ptr<int> ptr1 = std::make_unique<int>(10);
   std::unique_ptr<int> ptr2;

   ptr2 = std::move(ptr1);  // ptr1 теперь пуст, ptr2 владеет ресурсом
   

После этого присваивания ptr1 будет пустым (null), а ptr2 будет владеть ресурсом, который ранее принадлежал ptr1. 2️⃣Присваивание `nullptr`: Вы можете присвоить unique_ptr значение nullptr для освобождения ресурса, которым он владеет, и сделать указатель пустым.

      std::unique_ptr<int> ptr = std::make_unique<int>(10);

   ptr = nullptr;  // освобождает память и обнуляет ptr
   

Это автоматически освободит память (или другой ресурс), которым управлял unique_ptr, и установит указатель в состояние null. Запрещенные операции присваивания ✅Копирование и присваивание копированием: unique_ptr не поддерживает копирование или присваивание копированием. Это означает, что вы не можете скопировать unique_ptr напрямую, так как его конструктор копирования и оператор присваивания копированием удалены.

    std::unique_ptr<int> ptr1 = std::make_unique<int>(10);
  std::unique_ptr<int> ptr2;

  // ptr2 = ptr1;  // Ошибка компиляции: оператор присваивания удален
  // std::unique_ptr<int> ptr3(ptr1);  // Ошибка компиляции: конструктор копирования удален
  

unique_ptr разрешает только присваивание перемещением и присваивание nullptr, поддерживая тем самым уникальное владение ресурсом. Это обеспечивает безопасность при управлении ресурсами и предотвращает случайное создание нескольких владельцев одного и того же ресурса. Это делает unique_ptr отличным выбором для управления ресурсами, где требуется четкая собственность и автоматическое управление ресурсами. 👉 Можно посмотреть Примеры как отвечают люди на этот вопрос, или перейти К списку 434 вопроса на C/C++ разработчика. Ставь 👍 если нравится контент 🔐 База собесов | 🔐 База тестовых

Что известно о таком контейнере как куча ? Спросят с вероятностью 17% Куча (heap) — это специализированный тип дерева, который удовлетворяет свойству кучи. Это свойство гарантирует, что элемент в каждом узле является больше (в максимальной куче) или меньше (в минимальной куче) всех элементов в его дочерних узлах. Это дает ряд полезных свойств, особенно для организации и управления приоритетными очередями. Типы: 1️⃣Минимальная куча (Min-Heap): Ключ в каждом родительском узле меньше или равен ключам в дочерних узлах. Корень, следовательно, содержит минимальный ключ во всем дереве. 2️⃣Максимальная куча (Max-Heap): Ключ в каждом родительском узле больше или равен ключам в дочерних узлах. Корень содержит максимальный ключ. Основные операции: ✅Вставка (Insert): Добавление нового элемента в кучу. Новый элемент добавляется в конец, чтобы сохранить полноту бинарного дерева, и затем "всплывает" до правильной позиции, чтобы восстановить свойство кучи. Эта операция требует \(O(\log n)\) времени. ✅Удаление максимума/минимума (Extract Max/Min): Удаление максимального (в максимальной куче) или минимального (в минимальной куче) элемента из кучи. Обычно удаляется элемент на вершине кучи, затем последний элемент в куче перемещается на вершину, и "проседает" вниз, чтобы восстановить свойство кучи. Это также требует \(O(\log n)\) времени. ✅Просеивание вверх (Percolate Up) или просеивание вниз (Percolate Down): Эти операции используются для восстановления свойств кучи после вставки или удаления элементов. ✅Построение кучи (Build Heap): Создание кучи из неупорядоченного массива. Может быть выполнено за \(O(n)\) времени. ✅Поиск максимума/минимума (Find Max/Min): Получение максимального или минимального элемента кучи без его удаления. Это операция \(O(1)\), так как максимальный или минимальный элемент всегда находится на вершине. Кучи часто используются в приложениях, требующих частого доступа к наибольшим или наименьшим элементам. Наиболее распространенные случаи использования включают: ✅Приоритетные очереди: Структуры данных, где элементы извлекаются на основе приоритета, а не порядка добавления. Приоритетные очереди широко используются в алгоритмах планирования, сетевом маршрутизировании и в симуляции дискретных событий. ✅Алгоритмы на графах: Например, алгоритм Дейкстры для поиска кратчайшего пути использует минимальную кучу (или приоритетную очередь) для выбора следующей вершины для обработки. ✅Сортировка кучей (Heap Sort): Эффективный алгоритм сортировки, который использует кучу для сортировки элементов. Имплементация Может быть реализована с помощью контейнера std::priority_queue, который по умолчанию является максимальной кучей. Для создания минимальной кучи можно использовать стандартный контейнер с реверсированным компаратором. 👉 Можно посмотреть Примеры как отвечают люди на этот вопрос, или перейти К списку 434 вопроса на C/C++ разработчика. Ставь 👍 если нравится контент 🔐 База собесов | 🔐 База тестовых

Что будет если несколько раз вызвать lock ? Спросят с вероятностью 17% Если несколько раз вызвать метод lock на одном и том же мьютексе из одного и того же потока, произойдет взаимоблокировка самого себя, что приведет к зависанию программы. Это связано с тем, что мьютекс не позволяет одному и тому же потоку захватывать его несколько раз подряд, так как он не является рекурсивным мьютексом. Пример:

#include <iostream>
#include <thread>
#include <mutex>

std::mutex mtx;

void threadFunction() {
    mtx.lock();  // Первый захват мьютекса
    std::cout << "Mutex locked once" << std::endl;

    // Попытка повторного захвата того же мьютекса
    mtx.lock();  // Здесь произойдет взаимоблокировка
    std::cout << "This will never be printed" << std::endl;

    mtx.unlock();
    mtx.unlock();
}

int main() {
    std::thread t(threadFunction);
    t.join();
    return 0;
}

Что происходит: 1️⃣Первый вызов mtx.lock() успешно захватывает мьютекс. 2️⃣Второй вызов mtx.lock() пытается захватить мьютекс, который уже захвачен тем же потоком. Так как мьютекс не рекурсивный, поток заблокируется и будет ждать освобождения мьютекса самим собой, что невозможно, поэтому поток зависнет навсегда. Решение проблемы: Для ситуаций, когда требуется захват мьютекса несколько раз из одного и того же потока, следует использовать рекурсивный мьютекс (std::recursive_mutex). Он позволяет одному и тому же потоку захватывать мьютекс несколько раз, и каждый вызов lock должен сопровождаться соответствующим вызовом unlock. Пример:

#include <iostream>
#include <thread>
#include <mutex>

std::recursive_mutex mtx;

void threadFunction() {
    mtx.lock();  // Первый захват мьютекса
    std::cout << "Mutex locked once" << std::endl;

    // Повторный захват того же мьютекса
    mtx.lock();  // Успешный повторный захват
    std::cout << "Mutex locked twice" << std::endl;

    mtx.unlock();  // Первый вызов unlock
    mtx.unlock();  // Второй вызов unlock
}

int main() {
    std::thread t(threadFunction);
    t.join();
    return 0;
}

Если несколько раз вызвать lock на обычном мьютексе (std::mutex), произойдет взаимоблокировка самого себя, и поток зависнет. Для многократного захвата мьютекса одним и тем же потоком следует использовать рекурсивный мьютекс (std::recursive_mutex), который позволяет это делать. 👉 Можно посмотреть Примеры как отвечают люди на этот вопрос, или перейти К списку 434 вопроса на C/C++ разработчика. Ставь 👍 если нравится контент 🔐 База собесов | 🔐 База тестовых

Пс.. Тут два С++ сеньора создали канал, где простым языком поясняют за плюсы, метапрограммирование, фишки новых стандартов, алгоритмы, вопросы с собеседований и другие непонятные штуки из современного программирования на С++. Прямо сейчас Вы можете бесплатно забрать гайды по собеседованиям, по категориям выражений и мув-семантике и по ключевому слову inline. Все найдете в закрепе канала. Подписывайтесь, чтобы пояснять друзьям за оптимизации компилятора, о которых вам никто не расскажет: Грокаем С++

В чем асимптотическая сложность вставки и удаления в list и vector ? Спросят с вероятностью 17% Структуры данных std::list и std::vector, обе являются частью стандартной библиотеки шаблонов (STL), предоставляют различные характеристики производительности для операций вставки и удаления элементов. Понимание их асимптотической сложности помогает выбирать между этими контейнерами в зависимости от требований конкретной задачи. std::vector Представляет собой динамический массив, и его производительность оптимизирована для эффективного доступа к элементам и добавления элементов в конец. 1️⃣Вставка элементов: ✅Вставка в конец (push_back): Амортизированно \(O(1)\). Это означает, что большинство операций вставки занимают константное время, но иногда, когда требуется увеличение размера внутреннего массива, операция может занять \(O(n)\), где \(n\) — текущее количество элементов. ✅Вставка в середину или начало: \(O(n)\), так как может потребоваться сдвигать все последующие элементы для освобождения места. 2️⃣Удаление элементов: ✅Удаление из конца (pop_back): \(O(1)\), так как элемент просто удаляется, а размер уменьшается на один. ✅Удаление из середины или начала: \(O(n)\), поскольку, как и при вставке, требуется сдвигать элементы для заполнения освободившегося места. std::list Это двусвязный список, который позволяет быстро вставлять и удалять элементы на любой позиции, но с затратами на производительность при доступе к элементам. 1️⃣Вставка элементов: ✅Вставка на любую позицию: \(O(1)\), предполагая, что у вас уже есть итератор на эту позицию. Однако, если необходимо сначала найти позицию, это может занять \(O(n)\). 2️⃣Удаление элементов: ✅Удаление на любой позиции: \(O(1)\), также предполагая наличие итератора на удаляемый элемент. Поиск удаляемого элемента займет \(O(n)\). Общие рассуждения ✅std::vector идеален, когда нужен быстрый произвольный доступ к элементам и основными операциями являются добавление и удаление элементов в конец списка. ✅std::list лучше использовать, когда важны быстрые вставки и удаления в любом месте списка, но произвольный доступ не требуется или не является критичным. Выбор между std::list и std::vector должен базироваться на конкретных требованиях к производительности и типе операций, которые наиболее часто выполняются с контейнером. 👉 Можно посмотреть Примеры как отвечают люди на этот вопрос, или перейти К списку 434 вопроса на C/C++ разработчика. Ставь 👍 если нравится контент 🔐 База собесов | 🔐 База тестовых

🔥Тесты для подготовки к собеседованию🔥 Выбери своё направление: 1. Frontend 2. Python 3. Java 4. Тестировщик QA 5. Data Science 6. DevOps 7. C# 8. С/C++ 9. Golang 10. PHP 11. Kotlin 12. Swift

Можно ли сменить владельца у unique_ptr ? Спросят с вероятностью 17% Владельца объекта, управляемого std::unique_ptr, можно сменить. Это одна из основных особенностей std::unique_ptr. Смена владельца достигается с помощью операций перемещения (move). std::unique_ptr не поддерживает копирование, но позволяет передавать владение через перемещение, что можно сделать с помощью функции std::move или при инициализации/присваивании другому std::unique_ptr. Пример смены владельца с помощью std::move

#include <iostream>
#include <memory>

class MyClass {
public:
    MyClass() { std::cout << "MyClass constructed\n"; }
    ~MyClass() { std::cout << "MyClass destroyed\n"; }
};

void transferOwnership(std::unique_ptr<MyClass> ptr) {
    std::cout << "Ownership transferred\n";
    // ptr владеет объектом до конца функции
}

int main() {
    std::unique_ptr<MyClass> ptr1 = std::make_unique<MyClass>();

    std::cout << "Transferring ownership...\n";
    transferOwnership(std::move(ptr1));  // Передача владения

    if (!ptr1) {
        std::cout << "ptr1 no longer owns the object\n";
    }

    return 0;
}

Объяснение кода: 1️⃣Создание unique_ptr: ptr1 создается и владеет объектом типа MyClass. 2️⃣Передача владения: std::move(ptr1) передает владение объектом в функцию transferOwnership. 3️⃣Функция transferOwnership: Принимает владение объектом и будет владеть им до завершения функции. 4️⃣Проверка владения: После передачи владения ptr1 больше не владеет объектом (ptr1 становится nullptr). Владение можно также передавать путем присваивания одному unique_ptr другому с использованием std::move.

int main() {
    std::unique_ptr<MyClass> ptr1 = std::make_unique<MyClass>();

    std::unique_ptr<MyClass> ptr2;
    ptr2 = std::move(ptr1);  // ptr2 теперь владеет объектом

    if (!ptr1) {
        std::cout << "ptr1 no longer owns the object\n";
    }
    if (ptr2) {
        std::cout << "ptr2 owns the object\n";
    }

    return 0;
}

Объяснение кода: 1️⃣Создание unique_ptr: ptr1 создается и владеет объектом типа MyClass. 2️⃣Присваивание с перемещением: ptr2 = std::move(ptr1) передает владение объектом от ptr1 к ptr2. 3️⃣Проверка владения: После присваивания ptr1 больше не владеет объектом (ptr1 становится nullptr), а ptr2 теперь владеет объектом. Сменить владельца у std::unique_ptr можно с помощью перемещения (std::move). Это позволяет передавать владение объектом от одного unique_ptr к другому, обеспечивая уникальное владение в каждый момент времени. 👉 Можно посмотреть Примеры как отвечают люди на этот вопрос, или перейти К списку 434 вопроса на C/C++ разработчика. Ставь 👍 если нравится контент 🔐 База собесов | 🔐 База тестовых