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

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

Быстрый старт в кибербез: с нуля до первой работы Ищешь перспективную профессию с быстрым ростом зарплаты? Кибербезопасность — востребованная сфера с острой нехваткой специалистов. Здесь реально выйти на доход от 70 000 уже за полгода. Даже без опыта и образования в ИТ. С чего начать и как построить карьеру, расскажут эксперты Солара на вебинаре 11 сентября в 19:00: ✅Какие профессии доступны новичкам без опыта и как быстро их освоить. ✅Как найти свою первую работу. ✅Какие ошибки допускают новички в начале пути. 👌Всем участникам подарим пошаговый план по саморазвитию и быстрому старту в кибербезопасность. Зарегистрироваться #реклама 16+ rt-solar.ru О рекламодателе

🤔 Какие знаешь сортировки? Существует множество алгоритмов сортировки, каждый из которых имеет свои преимущества и недостатки в зависимости от условий использования. Рассмотрим основные из них. 🟠Сортировка пузырьком (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);
    }
}{}
    

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

🤔 Что такое абстрактный класс? Это класс, который содержит хотя бы одну чисто виртуальную функцию. Он не может быть создан как объект и предназначен для использования в качестве базового класса. Такие классы служат для определения интерфейсов и полиморфного поведения. Ставь 👍 если знал ответ, 🔥 если нет Забирай 📚Базу знаний

Большая распродажа: скидки на серверы Dell, HPE В Сервер Молл выгодное предложение на серверы Dell, HPE предыдущих поколений — самое время для апгрейда и масштабирования. Модели серверов под любые задачи: 1С, базы данных, виртуализация, видеонаблюдение, файловое хранилище, VPN и иные нагрузки. Конфигурации — от бюджетных до некогда топов с двумя процессорами Intel Xeon Gold. Все серверы в наличии и готовы к отправке! Выберите готовый вариант или сконфигурируйте под свои задачи. Консультации в любом объёме. ⚡ Бесплатная Гарантия 5 лет ⚡Доставка по всей России = 0 руб ⚡Постпродажная поддержка Если вы ждали повод собрать инфраструктуру с нуля, масштабировать или заменить старую технику — он перед вами. Акция продлится, пока серверы есть в наличии ✅ Пишите в наш Чат или Звоните — 8 800 755-25-51 📞 Узнать цену #реклама 16+ servermall.ru О рекламодателе

🤔 Почему со стеком работать быстрее чем с кучей? 🟠Управление памятью Стек: Память в стеке управляется автоматически. Когда вызывается функция, память для её локальных переменных выделяется одним блоком при входе в функцию и освобождается при выходе из неё. Эта операция выполняется за постоянное время (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;
}{}
    

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

Получи грант до 1,2 млн руб. на обучение в магистратуре 4 офлайн программы, онлайн-магистратура по ML. Гранты до 1,2 млн руб. Стажировки, диплом гос. образца и фокус на твоей карьере в ЦУ Подать заявку #реклама 16+ apply.centraluniversity.ru О рекламодателе

🤔 Знаком с spinlock и deadlock? Spinlock — это механизм синхронизации, где поток активно проверяет блокировку, не засыпая. Deadlock возникает, когда два или более потока ждут друг друга, создавая бесконечную блокировку. Ставь 👍 если знал ответ, 🔥 если нет Забирай 📚Базу знаний

🤔 Как сделать операцию удаления элемента из начала, если порядок элементов не важен, в 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;
}{}
    

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

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