Computer Science

Коллизия

После размещения данных в хеш-таблице в соответствии по их хешам. Если у каких-то двух данных совпали хеши, то это называется коллизией. Существует несколько методов разрешения.

Методы разрешения коллизий

Метод открытой адресации — запись в другую ячейку. Часто можем перепрыгивать через ячейки или применять хеш-функцию к полученному числу.

Пробирование (поиск) — набор преобразований, когда пытаемся, чтобы наше значение попало в свободную ячейку. Виды:

• линейное пробивание
• квадратичное пробивание
• двойное хеширование

[–] эффективность сильно зависит от способа обхода и от размера внутреннего массива [+] быстрый обход, меньший расход памяти.

Метод цепочек — создание цепочки-списка, где один элемент хранит в себе ссылку на другой элемент. Каждая ячейка массива является указателем на связный список (цепочку) пар ключ-значение, соответствующих одному и тому же хеш-значению ключа.

[–] расход памяти на ссылку, медленный обход [+] простота реализации

Переменные окружения

Переменные окружения — это переменные, которые определены для текущей оболочки. Их можно создать с помощью команды export

Параллельность, потоки, scheduler

Многозадачность и её виды

Многозадачность (англ. multitasking) — свойство операционной системы или среды выполнения обеспечивать возможность параллельной (или псевдопараллельной) обработки нескольких задач.

Вытесняющая

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

Преимущества:

• возможность полной реализации многозадачного ввода-вывода в ядре ОС, когда ожидание завершения ввода-вывода одной программой позволяет процессору тем временем исполнять другую программу;
• cильное повышение надежности системы в целом, в сочетании с использованием защиты памяти — идеал в виде «ни одна программа пользовательского режима не может нарушить работу ОС в целом» становится достижимым хотя бы теоретически, вне вытесняющей многозадачности он не достижим даже в теории.
• возможность полного использования многопроцессорных и многоядерных систем.

Недостатки:

• необходимость особой дисциплины при написании кода, особые требования к его реентерабельности, к защите всех разделяемых и глобальных данных объектами типа критических секций и мьютексов.

Кооперативная

Тип многозадачности, при котором следующая задача выполняется только после того, как текущая задача явно объявит себя готовой отдать процессорное время другим задачам.

Преимущество:

• отсутствие необходимости защищать все разделяемые структуры данных объектами типа критических секций и мьютексов, что упрощает программирование, особенно перенос кода из однозадачных сред в многозадачные.

Недостаток:

• неспособность всех приложений работать в случае ошибки в одном из них, приводящей к отсутствию вызова операции «отдать процессорное время».
• крайне затрудненная возможность реализации многозадачной архитектуры ввода-вывода в ядре ОС, позволяющей процессору исполнять одну задачу, в то время как другая задача инициировала операцию ввода-вывода и ждет её завершения.

Проблемы многозадачных программ

Starvation

Ситуация, когда определенный процесс или задача не получает необходимых ресурсов или внимания, что приводит к тому, что она не может продвигаться вперед или завершиться. В результате этого другие задачи или процессы могут получать приоритет, и голодание может вызвать несправедливость в распределении ресурсов.

Race condition

Race condition возникает, когда результат выполнения программы зависит от того, в каком порядке выполняются операции несколькими потоками или процессами. Это может привести к неправильным или неожиданным результатам, так как разные потоки могут изменять общее состояние программы параллельно без должной синхронизации. Race condition может быть одной из причин возникновения data race.

Data race

Data race возникает, когда два или более потока (или процесса) одновременно обращаются к одному и тому же общему ресурсу (например, переменной) и хотя бы одна из этих операций является записью. При этом отсутствует явная синхронизация между потоками, и результаты выполнения становятся непредсказуемыми.

Переключение контекста

Переключение контекста — в многозадачных ОС и средах – процесс прекращения выполнения процессором одной задачи с сохранением всей необходимой информации и состояния, необходимых для последующего продолжения с прерванного места, и восстановления и загрузки состояния задачи, к выполнению которой переходит процессор.

Компилятор и интерпретатор

Компилятор переводит код в машинный. Интерпретатор же переводит промежуточный язык в машинный.

Как оценивается сложность алгоритмов? Что такое Big O?

Сложность оценивается с точки зрения Big O Notation, потому что логичнее оценивать не с точки зрения выполнения по времени, а с точки зрения Big O, то есть сложности операций. Нотация для оценки сложности кода:

• $O(n)$ - линейная зависимость
• $O(n^2)$ - цикл в цикле, например
• $O(1)$ - не зависит от размера входных данных

ООП – Зачем нужно и что это?

1. Модульность для быстрого дебага и поиска ошибок
2. Повторное использование кода
3. Масштабируемость

Это парадигма, когда мы код выстраиваем в виде объектов, которые являются объектами каких-то классов, а классы выстраивают иерархию наследования

• Абстракция Класс у которого нельзя создать объект. Позволяет работать с объектами, не вдаваясь в особенности их реализации. Абстракция — в объектно-ориентированном программировании это придание объекту характеристик, которые отличают его от всех объектов, четко определяя его концептуальные границы. raise(NotImplemenetedError) — ранее, сейчас через ABC

• Полиморфизм В функциях нам не важны тип данных, главное, чтобы при работе вне зависимости от типа функция сработала (утиная типизация). Используем одни и те же названия методов в разных классах.

• Наследование Наследование позволяет выделить общее для нескольких классов поведение и вынести его в отдельную сущность. То есть наследование является средством переиспользования кода. Наследование позволяет получить новый класс, немного отличающийся от старого.

• Инкапсуляция Инкапсуляция — объединение данных и методов работы с этими данными в один объект. Инкапсуляция — сокрытие данных через private & protected. Только тот интерфейс виден, который нужен пользователю.

Абстрактный класс и интерфейс — разница?

В интерфейсе нету реализованных методов, а в абстракции может быть.

Хеш-таблица, хеш-функция

Хеш-таблицы – это тип структуры данных, позволяющая быстро получать информацию. Получается быстро, поскольку значение индекса ведет себя как ключ к значению данных. Другими словами, в хэш-таблице хранятся пары ключ-значение, но ключ генерируется с помощью функции хеширования.

Хеш-функция — это функция, которая возвращает какой-то уникальный хеш.

Например, ключ — это строка. Мы переводим его в какую-то цифровую кодировку и используем это как id.

Хорошая функция обладает свойствами:

• детерминизм
• равномерность
• эффективность (быстро)
• ограниченность

Cryptography

PKI

PKI, или Инфраструктура открытых ключей (Public Key Infrastructure), представляет собой набор технологий и стандартов, используемых для создания, управления, распространения, использования, хранения и отзыва цифровых сертификатов. В основе PKI лежат принципы криптографии с открытым ключом, включающие использование пары ключей — открытого и закрытого.

PKI представляет собой систему, основным компонентом которой является удостоверяющий центр и пользователи, взаимодействующие между собой используя сертификаты, выданные этим удостоверяющим центром.

Шифрование и Расшифровка: Данные могут быть зашифрованы публичным ключом, но для их расшифровки потребуется соответствующий приватный ключ. Это обеспечивает конфиденциальность, так как только обладатель приватного ключа может расшифровать данные.

Цифровая Подпись: Приватный ключ используется для создания цифровой подписи, которая затем может быть проверена с использованием соответствующего публичного ключа. Это обеспечивает аутентичность и целостность данных.

Основные принципы:

• закрытый ключ (private key) известен только его владельцу;
• удостоверяющий центр (УЦ или CA — certificate authority) создает электронный документ — сертификат открытого ключа, таким образом удостоверяя факт того, что закрытый (секретный) ключ известен эксклюзивно владельцу этого сертификата, открытый ключ (public key) свободно передается;
• никто не доверяет друг другу, но все доверяют удостоверяющему центру;
• удостоверяющий центр подтверждает или опровергает принадлежность открытого ключа заданному лицу, которое владеет соответствующим закрытым ключом.