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

🤔 Какую сложность от О большое имеет сортировка QuickSort, BubbleSort, HeapSort ? В анализе алгоритмов сортировки, сложность по большому O показывает, как изменяется время выполнения в зависимости от размера входных данных. Рассмотрим три алгоритма: QuickSort, BubbleSort и HeapSort. 🚩QuickSort 🟠Худший случай O(n²) Происходит, если при каждом разбиении выбирается самый большой или самый маленький элемент в качестве опорного (pivot). Например, это может случиться, если массив уже отсортирован или отсортирован в обратном порядке. 🟠Средний и лучший случай: O(n log n) Средняя сложность достигается за счет удачных разбиений, где каждый раз массив делится примерно пополам. В лучшем случае массив уже делится равномерно на две части каждый раз.

    
        void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return (i + 1);
}{}
    

🚩BubbleSort 🟠Худший и средний случай: 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]);
            }
        }
    }
}{}
    

🚩HeapSort Худший, средний и лучший случай: O(n log n) HeapSort всегда имеет сложность O(n log n), так как независимо от начального порядка данных, он сначала строит двоичную кучу (heap), что занимает O(n), а затем повторно извлекает максимальный элемент и перестраивает кучу, что занимает O(log n) на каждый элемент.

    
        void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest != i) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    for (int i = n - 1; i > 0; i--) {
        std::swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}{}
    

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

🤔 Unordered_set, unordered_map и set, map чем отличаются? 1. Set/Map: элементы хранятся в отсортированном порядке, используются бинарные деревья (обычно красно-чёрные). 2. Unordered_set/Unordered_map: элементы не сортируются, используют хеш-таблицы для быстрого доступа. 3. Set и Map медленнее на вставке/поиске (O(log N)), но позволяют итерировать в отсортированном порядке. 4. Unordered_set и Unordered_map быстрее для поиска (O(1) в среднем), но не поддерживают упорядоченный доступ. Ставь 👍 если знал ответ, 🔥 если нет Забирай 📚Базу знаний

🤔 Какая сложность поиска в set и unordered_set? Контейнеры set и unordered_set представляют собой различные структуры данных, каждая из которых имеет свои особенности по скорости выполнения основных операций, включая поиск. Вот как работают эти контейнеры и какова сложность их операций поиска: 🚩set Реализуется как сбалансированное двоичное дерево поиска, обычно как красно-черное дерево. Он хранит элементы в отсортированном порядке, что позволяет выполнять двоичный поиск. Сложность поиска: Поиск в нем выполняется за логарифмическое время, \(O(\log n)\), где \(n\) — количество элементов в set. Эта эффективность достигается за счёт использования структуры сбалансированного дерева, которое позволяет быстро делить данные на меньшие сегменты. 🚩unordered_set Реализуется с использованием хеш-таблицы. Это позволяет, при идеальных условиях, выполнять поиск за константное время. Сложность поиска: В среднем, поиск в нем занимает константное время \(O(1)\). Однако в худшем случае, например, при неудачной работе хеш-функции или при большом количестве коллизий, поиск может деградировать до \(O(n)\). В таких ситуациях все ключи могут оказаться в одной "корзине" или "ведре" (bucket), и для нахождения правильного элемента потребуется просмотреть все элементы в этом ведре. Для set

    
        #include <iostream>
#include <set>

int main() {
    std::set<int> mySet = {5, 3, 9, 1};
    auto search = mySet.find(3);
    if (search != mySet.end()) {
        std::cout << "Found " << *search << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }
    return 0;
}{}
    

Для unordered_set

    
        #include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> mySet = {5, 3, 9, 1};
    auto search = mySet.find(3);
    if (search != mySet.end()) {
        std::cout << "Found " << *search << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }
    return 0;
}{}
    

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

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

Сегодня последний день, когда можно приобрести пожизненный PRO тариф easyoffer Акция до 20 февраля 00:00 Покупаешь сейчас один раз — пользуешься всю жизнь без лимита, включая все будущие функции. 👉 Смотри подробности тарифа и покупай на https://easyoffer.ru/

🤔 Какая сложность работы с map и unordered_map? В std::map и std::unordered_map используются разные структуры данных, поэтому их операции (insert, find, erase) имеют разную сложность. 🚩Почему `std::map` медленнее? std::map – это самобалансирующееся красно-чёрное дерево, где все операции (insert, find, erase) выполняются за O(log n).

    
        std::map<int, std::string> m;
m[10] = "ten";  // O(log n)
m[5] = "five";  // O(log n)
m[20] = "twenty";  // O(log n)
m.find(5);  // O(log n){}
    

Дерево std::map выглядит так

    
                10
       /  \
      5    20{}
    

🚩Почему `std::unordered_map` быстрее? std::unordered_map – это хеш-таблица, где insert, find, erase работают за O(1) в среднем.

    
        std::unordered_map<int, std::string> um;
um[10] = "ten";  // O(1)
um[5] = "five";  // O(1)
um[20] = "twenty";  // O(1)
um.find(5);  // O(1){}
    

Внутри std::unordered_map выглядит так (разбито по бакетам)

    
        Bucket 0:  ---
Bucket 1:  ---
Bucket 2:  (10, "ten")
Bucket 3:  (5, "five")
Bucket 4:  (20, "twenty"){}
    

🚩Когда `std::unordered_map` становится медленным (`O(n)`)? В худшем случае все элементы попадают в один бакет (из-за плохой хеш-функции), тогда поиск превращается в O(n).

    
        std::unordered_map<int, std::string> um;
um[1] = "one";
um[2] = "two";
um[3] = "three";{}
    

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

🤔 Альтернативное решение для хранения float цены в качестве ключа? Вместо хранения float можно: 1.Преобразовать цену в целочисленное значение (например, умножить на 100 или 1000 для точности до копеек/центов). 2.Хранить результат как int, что обеспечит точное сравнение и отсутствие ошибок округления. Ставь 👍 если знал ответ, 🔥 если нет Забирай 📚Базу знаний

Завтра конец акции на возможность приобрести PRO тариф по цене одного года Доступный функционал включает базы вопросов с собеседований, задач для live-coding, реальных интервью и тестовых заданий от топ-компаний, а также аналитику требований для резюме и тренажеры с режимом симуляции собеседования под конкретную компанию. Акция до 20 февраля (включительно) на PRO-тариф. Покупаешь сейчас один раз — пользуешься всю жизнь без лимита, включая все будущие функции. 👉 Смотри подробности тарифа и покупай на https://easyoffer.ru/

🤔 Как устроена хеш таблица в unordered_map? std::unordered_map в C++ реализован на основе хеш-таблицы. Это структура данных, обеспечивающая O(1) доступ к элементам в среднем случае. 🚩Основные компоненты хеш-таблицы 🟠Массив "бакетов" (buckets) Хеш-таблица состоит из массива бакетов, где каждый бакет содержит список элементов с одинаковым хеш-кодом. 🟠Функция хеширования (`std::hash<T>`) Для определения, в какой бакет попадёт ключ, используется функция хеширования (std::hash<T>). 🟠Проверка коллизий Если два разных ключа попадают в один бакет (коллизия), элементы сохраняются в связанном списке (чаще всего). 🟠Рехеширование При переполнении таблицы (load_factor > порогового значения) количество бакетов увеличивается, и все элементы перераспределяются. 🚩Как работает поиск и вставка в `unordered_map` Хеш-функция вычисляет хеш-код ключа

    
           std::hash<int> hash_fn;
   size_t hash_value = hash_fn(42); // Например, 23145123{}
    

Определяется индекс бакета

    
           size_t bucket_index = hash_value % bucket_count;{}
    

🚩Разрешение коллизий Когда два ключа попадают в один бакет, возникают коллизии. std::unordered_map использует метод цепочек (separate chaining): В каждом бакете хранится связанный список (или другой контейнер). Если несколько элементов имеют одинаковый хеш, они добавляются в этот список.

    
        #include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> myMap;

    myMap[1] = "One";  // Хеш-функция определит бакет
    myMap[2] = "Two";  // Если попадает в тот же бакет, создаётся список

    for (const auto& [key, value] : myMap) {
        std::cout << "Key: " << key << ", Value: " << value << '\n';
    }

    return 0;
}{}
    

🚩Рехеширование (увеличение количества бакетов) Когда таблица заполняется, выполняется rehash (увеличение массива бакетов в 2 раза). Load factor (load_factor()) показывает, насколько заполнена таблица:

    
        std::unordered_map<int, std::string> myMap;
std::cout << "Load factor: " << myMap.load_factor() << '\n';{}
    

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

Аукцион выделенных серверов! Серверы дешевеют у вас на глазах! Новые лоты каждый день, скидки до -35% на весь срок аренды. Успейте арендовать, пока лот не ушел другому! Получить предложение #реклама 16+ selectel.ru О рекламодателе