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

Не грузится? Понимаем. Бесплатный мессенджер для вашей компании - Битрикс24. Личные и групповые чаты, видеозвонки, каналы и нейросеть. Всё привычно и удобно. Начните работать на бесплатном тарифе уже сейчас. Узнать больше #реклама 16+ bitrix24.ru О рекламодателе

🤔 Какие есть операторы приведения типов? 1. static_cast: Для явного и безопасного приведения типов, известных на этапе компиляции. 2. dynamic_cast: Для приведения указателей или ссылок в иерархии классов с проверкой типов во время выполнения. 3. const_cast: Для снятия или добавления const и volatile квалификаторов. 4. reinterpret_cast: Для низкоуровневого преобразования указателей или других типов без проверки безопасности. Ставь 👍 если знал ответ, 🔥 если нет Забирай 📚Базу знаний

🤔 Как называется одинаковый результат после применения хэш функции? Одинаковый результат после применения хэш-функции называется коллизией. 🚩Что такое коллизия? Коллизия возникает, когда две разные входные величины (ключи) при обработке одной и той же хэш-функцией дают одинаковое хэш-значение. Это проблема, так как хэш-функции обычно используются для быстрого доступа к данным (например, в хэш-таблицах), и одинаковые хэши для разных данных нарушают уникальность ключей. 🚩Почему коллизии возникают? 🟠Ограниченный размер хэш-значений Хэш-функция генерирует значения фиксированной длины (например, 32 или 64 бита), поэтому существует конечное количество возможных хэшей. Однако количество входных данных, которые можно подать на вход, теоретически бесконечно. 🟠Особенности алгоритма хэширования Некоторые хэш-функции менее устойчивы к коллизиям из-за их структуры. 🚩Как справляться с коллизиями? Есть несколько способов обработки коллизий в хэш-таблицах: 🟠Метод цепочек (chaining) Каждое значение хэша хранит список элементов, которые получили одинаковый хэш. При добавлении нового ключа он просто добавляется в связанный список.

    
        #include <iostream>
#include <list>
#include <vector>
using namespace std;

class HashTable {
    int size;
    vector<list<int>> table;

public:
    HashTable(int s) : size(s), table(s) {}

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

    void insert(int key) {
        int index = hashFunction(key);
        table[index].push_back(key);
    }

    void display() {
        for (int i = 0; i < size; i++) {
            cout << i << ": ";
            for (int key : table[i]) {
                cout << key << " -> ";
            }
            cout << "NULL" << endl;
        }
    }
};

int main() {
    HashTable ht(5);
    ht.insert(10);
    ht.insert(15);
    ht.insert(20);
    ht.insert(7);
    ht.insert(2);
    ht.display();
    return 0;
}{}
    

🟠Открытая адресация (open addressing) При коллизии новое значение записывается в следующую свободную ячейку в таблице. Используются разные стратегии, такие как линейное пробирование, квадратичное пробирование или двойное хэширование. 🟠Использование криптографических хэш-функций Устойчивые хэш-функции (например, SHA-256) уменьшают вероятность коллизий, но они медленнее и чаще используются в безопасности. Ставь 👍 и забирай 📚 Базу знаний

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

Яндекс Музыка до 360 дней бесплатно Яндекс Музыка для вас и 3-х ваших близких. Кинопоиск и Яндекс Книги тоже в подписке. Попробуйте бесплатно❤️ Слушать #реклама 18+ music.yandex.ru О рекламодателе

🤔 Асимптотическая сложность в 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), потому что используется сортировка слиянием{}
    

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

🤔 Какой имеется побочный эффект при работе с кодом в хидере? При работе с кодом в хидерах возможны проблемы, связанные с повторным включением файлов (multiple inclusion), что может вызвать ошибки компиляции. Это решается использованием включающих защит (#pragma once или #ifndef). Также код в хидере увеличивает время компиляции, так как включается в несколько исходных файлов. Ставь 👍 если знал ответ, 🔥 если нет Забирай 📚Базу знаний

🤔 Как убедиться что нет багов в коде? Чтобы убедиться, что в коде нет багов, используют различные методы и инструменты проверки. Рассмотрим основные подходы: 🟠Внимательная проверка кода (Code Review) Перед тем как запускать код, полезно просмотреть его вручную или с коллегами. Это помогает: Найти логические ошибки Улучшить читаемость кода Проверить соответствие код-стайлу

    
        // Опытный разработчик может заметить, что деление на 0 возможно
int divide(int a, int b) {
    return a / b; // Потенциальная ошибка, если b == 0
}{}
    

Лучше добавить проверку

    
        int divide(int a, int b) {
    if (b == 0) {
        throw std::runtime_error("Деление на ноль!");
    }
    return a / b;
}{}
    

🟠Юнит-тестирование (Unit Testing) Тесты проверяют каждую функцию отдельно, чтобы убедиться, что она работает правильно. В C++ используют Google Test (gtest), Catch2 или Boost.Test.

    
        #include <gtest/gtest.h>
#include "math_utils.h"

TEST(DivideFunctionTest, HandlesZeroDenominator) {
    EXPECT_THROW(divide(10, 0), std::runtime_error);
}

TEST(DivideFunctionTest, NormalCase) {
    EXPECT_EQ(divide(10, 2), 5);
}{}
    

🟠Отладка (Debugging) Если код работает не так, как ожидалось, используют отладчики (GDB, LLDB, Visual Studio Debugger). Они позволяют пошагово исполнять код и смотреть, где происходит ошибка.

    
        g++ -g main.cpp -o program  # Компилируем с отладочной информацией
gdb ./program  # Запускаем отладчик{}
    

🟠Статический анализ кода Используются специальные инструменты, которые автоматически ищут ошибки в коде: Clang-Tidy Cppcheck SonarQube

    
        cppcheck --enable=all my_code.cpp{}
    

🟠Динамический анализ (Sanitizers, Valgrind) Эти инструменты помогают находить утечки памяти, переполнения буфера и другие ошибки.

    
        g++ -fsanitize=address -g main.cpp -o program
./program  # Если есть проблемы, они будут найдены{}
    

🟠Интеграционное и системное тестирование Когда код протестирован отдельно, его проверяют в реальной среде. Это включает тестирование работы программы с базами данных, сетевыми запросами и другими модулями. Ставь 👍 и забирай 📚 Базу знаний

🤔 Как проверять равенство двух float? Равенство двух float проверяется с учётом допустимой разницы (эпсилон), чтобы избежать ошибок из-за неточности представления: ∣a−b∣<ϵ, где ϵ — небольшое значение, например 10−610^{-6}. Такой подход помогает корректно сравнивать близкие числа, которые могут отличаться в пределах допустимой погрешности. Ставь 👍 если знал ответ, 🔥 если нет Забирай 📚Базу знаний

🤔 Какая есть оптимизация в строках С++? Стандартный класс std::string в C++ имеет несколько механизмов оптимизации для повышения производительности и уменьшения расхода памяти. Рассмотрим основные из них. 🟠Small String Optimization (SSO) – Оптимизация малых строк Если строка маленькая (обычно до 15-23 байт, зависит от реализации), std::string не выделяет динамическую память, а хранит символы прямо внутри объекта std::string. Обычно std::string содержит: - Указатель на динамическую память - Размер строки - Вместимость (capacity) Но если строка короткая, память не выделяется в куче (heap), а данные хранятся прямо внутри объекта std::string.

    
        #include <iostream>
#include <string>

int main() {
    std::string small = "Hello"; // Использует SSO
    std::string large = "This is a very long string that will not fit SSO"; // Динамическая память

    std::cout << "Small string: " << small << "\n";
    std::cout << "Large string: " << large << "\n";
}{}
    

🟠Copy-on-Write (COW) – Оптимизация копирования (устарела) Раньше (до C++11) std::string использовал технику Copy-on-Write (COW), где несколько строк могли разделять одну и ту же память, пока одна из них не изменялась. Почему отказались? Не потокобезопасно (если один поток меняет строку, другой может получить неожиданные данные). В C++11 было добавлено std::move, которое делает копирование дешевле. SSO делает COW менее нужной.

    
        std::string a = "Hello";
std::string b = a; // Копия не создается, оба указывают на одну память
b[0] = 'X'; // Теперь создаётся отдельная копия{}
    

🟠Move Semantics – Семантика перемещения (C++11) Вместо дорогостоящего копирования std::string теперь можно перемещать с помощью std::move(), передавая владение ресурсом без копирования.

    
        #include <iostream>
#include <string>

int main() {
    std::string a = "Hello, world!";
    std::string b = std::move(a); // Перемещение, a становится пустой
    std::cout << "b: " << b << "\n"; // "Hello, world!"
}{}
    

🟠Reserve() – Избегание частых выделений памяти Если заранее известно, сколько символов потребуется, можно использовать .reserve(size), чтобы избежать многократных перевыделений памяти.

    
        std::string str;
str.reserve(100); // Сразу выделяет память на 100 символов
for (int i = 0; i < 100; i++) {
    str += 'a'; // Не перевыделяет память 100 раз
}{}
    

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