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

🤔 Что будет, если вызвать оператор delete на nullptr? Если вызвать оператор delete на nullptr, ничего не произойдет. Это безопасная операция, так как стандарт гарантирует, что освобождение nullptr не вызовет ошибок или исключений. Ставь 👍 если знал ответ, 🔥 если нет Забирай 📚Базу знаний

🤔 Сложность поиска в бинарных деревьях логарифмическая, всегда ли так? Нет, сложность поиска в бинарных деревьях не всегда логарифмическая. Она зависит от структуры дерева. Хотя логарифмическая сложность \(O(\log N)\) считается идеальной, это справедливо только для сбалансированных бинарных деревьев. Давайте разберём, когда эта сложность сохраняется, а когда может увеличиваться. 🚩Идеальный случай: сбалансированное бинарное дерево Если бинарное дерево поиска (Binary Search Tree, BST) сбалансировано, глубина дерева пропорциональна \( \log_2 N \), где \(N\) – количество узлов. В этом случае поиск, вставка и удаление элемента выполняются за \(O(\log N)\). 🚩Худший случай: несбалансированное дерево Если дерево несбалансировано, то оно может выродиться в связный список, где каждый узел имеет только одного потомка (левого или правого). 🚩Как избежать вырождения дерева? Чтобы поддерживать сложность операций \(O(\log N)\), используют сбалансированные бинарные деревья, такие как: 🟠AVL-деревья Поддерживают балансировку после каждой операции вставки/удаления. 🟠Красно-чёрные деревья Гарантируют, что глубина дерева остаётся \(O(\log N)\). 🟠B-деревья и B+ деревья Используются для работы с большими объёмами данных, например, в базах данных. Ставь 👍 и забирай 📚 Базу знаний

🤔 Как работает priority_queue? priority_queue управляет элементами на основе их приоритетов, используя бинарную кучу: на вершине всегда элемент с наивысшим приоритетом, а операции добавления и удаления имеют сложность O(log n). Ставь 👍 если знал ответ, 🔥 если нет Забирай 📚Базу знаний

🤔 Чем отличаются 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;
}{}
    

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

🤔 Что такое рекурсивный mutex? Рекурсивный mutex — это тип мьютекса, который позволяет одному и тому же потоку захватывать его несколько раз без блокировки. Это полезно, когда одна и та же функция вызывает себя рекурсивно или косвенно через другие функции и при этом требуется захватить один и тот же мьютекс. В отличие от обычного мьютекса, рекурсивный мьютекс учитывает количество захватов и освобождается только после того, как поток выполнит соответствующее количество вызовов unlock(). Это предотвращает взаимоблокировки при рекурсивных вызовах. Ставь 👍 если знал ответ, 🔥 если нет Забирай 📚Базу знаний

Канал для IT-спецов о том, как запустить свой проект Даже если у тебя нет готовой идеи и все прошлые попытки провалились. Ты узнаешь: Как заранее понять, будет ли кто-то платить за твой продукт? Как выбрать идею, которая "выстрелит"? Как получить первые оплаты, еще ДО создания продукта - и не заплатить за это ни копейки. Если тебе уже надоело тратить жизнь, работая в корпорации, и есть желание "сделать что-то своё", но уходить строить бизнес страшно - ты в правильном месте. Подписаться #реклама 16+ О рекламодателе

🤔 Что такое POD тип ? POD (Plain Old Data) тип — это простой тип данных в C++, который совместим с C и обладает определенными свойствами, делающими его поведение предсказуемым и простым. 🚩Основные характеристики POD типов 🟠Тривиальность (Trivial) Тривиальный конструктор (конструктор по умолчанию, копирования и перемещения). Тривиальный деструктор. Компилятор генерирует их автоматически, если они не определены явно. 🟠Стандартная макетируемость (Standard Layout) Все нестатические члены данных имеют один и тот же доступ (public, private, или protected). Нет виртуальных функций и нет виртуальных базовых классов. Все базовые классы являются POD типами. Стандартные правила выравнивания и макетирования данных в памяти.

    
        struct MyPOD {
    int x;
    float y;
};{}
    

Пример НЕ POD типа

    
        struct NonPOD {
    int x;
    virtual void func() {}  // Наличие виртуальной функции делает тип не POD
};{}
    

🚩Применение POD типов 🟠Совместимость с C Поскольку POD типы совместимы с C, они могут быть безопасно использованы в смешанных C/C++ программах. 🟠Серилизация Легко сохранять и загружать из файлов или передавать по сети, так как их память может быть прочитана или записана напрямую. 🟠Оптимизация Компиляторы могут лучше оптимизировать код с POD типами из-за их простоты и предсказуемости. 🚩Проверка, является ли тип POD В C++11 и новее можно использовать стандартную библиотеку для проверки, является ли тип POD

    
        #include <type_traits>

struct MyPOD {
    int x;
    float y;
};

struct NonPOD {
    int x;
    virtual void func() {}
};

int main() {
    std::cout << std::is_pod<MyPOD>::value << std::endl;  // вывод: 1 (true)
    std::cout << std::is_pod<NonPOD>::value << std::endl; // вывод: 0 (false)
    return 0;
}{}
    

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

🤔 Что будет, если несколько раз вызвать lock? 1. Если используется обычный std::mutex, повторный вызов lock из того же потока вызовет deadlock. 2. Для избежания этой ситуации можно использовать std::recursive_mutex, который позволяет одному потоку многократно блокировать мьютекс Ставь 👍 если знал ответ, 🔥 если нет Забирай 📚Базу знаний

🤔 В каких STL контейнерах внутри находится хеш таблица? 🚩В стандартной библиотеке шаблонов (STL) C++ хеш-таблица используется для реализации следующих контейнеров 🟠std::unordered_map Ассоциативный контейнер, который хранит пары ключ-значение, с уникальными ключами. Обеспечивает амортизированное среднее время доступа, вставки и удаления за O(1). 🟠std::unordered_multimap Ассоциативный контейнер, который хранит пары ключ-значение, где ключи могут повторяться. Обеспечивает амортизированное среднее время для основных операций за O(1), несмотря на дублирование ключей. 🟠std::unordered_set Ассоциативный контейнер, который хранит уникальные элементы, неупорядоченные. Обеспечивает амортизированное среднее время для основных операций за O(1). 🟠std::unordered_multiset Ассоциативный контейнер, который хранит элементы, где значения могут повторяться, неупорядоченные. Обеспечивает амортизированное среднее время для основных операций за O(1), несмотря на дублирование элементов. Ставь 👍 и забирай 📚 Базу знаний

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