Топ вопросов по Computer Science

Одной из самых популярных парадигм программирование является объектно-ориентированное программирование (ООП).

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

ООП широко использует классы. Классы - это способ создания новых объектов с помощью макета или шаблона, который задает программист. Объекты, которые были созданы с помощью класса, называются экземплярами.

Вернемся к примеру с приготовлением пищи на псевдокоде. Предположим, что в нашей пекарне у нас есть главный повар (по имени Иван) и помощник повара (по имени Антон). У каждого из них есть определенные обязанности. Если бы мы использовали ООП, то наша программа бы выглядеть следующим образом:

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

Принципы SOLID – это набор правил, способствующих проектированию гибких, расширяемых и поддерживаемых программ. К ним относятся Single Responsibility, Open/Closed, Liskov Substitution, Interface Segregation и Dependency Inversion.

1. Single Responsibility Principle (Принцип единственной ответственности) гласит, что каждый класс должен отвечать только за одну функцию в программе. Это помогает обеспечить легкость поддержки кода, его расширения и понимания. Применяя этот принцип, следует разбивать программу на отдельные компоненты с четко определенными задачами.
2. Open/Closed Principle (Принцип открытости/закрытости) означает, что классы должны быть открыты для расширения, но закрыты для изменения. Это достигается путем использования абстракций и интерфейсов для работы с классами. Примером может служить использование виртуальных функций в C++ для создания абстракции над различными реализациями.
3. Liskov Substitution Principle (Принцип подстановки Барбары Лисков) утверждает, что объекты базового класса могут быть заменены объектами любого из его подклассов без нарушения работы программы. Это требует строгое соблюдение контрактов и интерфейсов, определенных в базовом классе, во всех его производных классах.
4. Interface Segregation Principle (Принцип разделения интерфейсов) предполагает, что интерфейсы классов должны быть маленькими и специфическими для клиентов. Это позволяет избежать создания «толстых» интерфейсов, которые содержат методы, не нужные клиентам.
5. Dependency Inversion Principle (Принцип инверсии зависимостей) утверждает, что модули верхнего уровня не должны зависеть от модулей нижнего уровня. Зависимости должны строиться на абстракциях, а не на деталях. Это достигается через использование интерфейсов и внедрение зависимостей (dependency injection).

Применяя принципы SOLID, разработчики могут создавать гибкие, масштабируемые и легко поддерживаемые программы, которые легко изменять и расширять по мере развития требований

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

Выделают три типа полиморфизма с примерами кода на C#:

1. Ad-hoc полиморфизм - это способность функции обрабатывать аргументы разных типов, предоставляя различную реализацию в зависимости от типа аргументов.

По моему мнению не заслуживает носить гордое имя полиморфизма, достаточно называть это перегрузкой методов/операторов. А в C++ даже без ООП такой механизм работает.

2. Параметрический полиморфизм - это способность обрабатывать аргументы одного или более типов без привязки к конкретному типу. Это достигается с помощью шаблонов, обобщений или дженериков.

3. Полиморфизм подтипов - это способность объекта производного класса использоваться вместо объекта базового класса. Это возможно благодаря наследованию и переопределению методов.

Вот это истинное проявление полиморфизма, которое даже трудновато понять, если использовать апкасты, даункасты, приведения типов и остальное.

Но пример легкий:

Важно отметить, что полиморфизм это самое важное в ООП. Без понимания полиморфизма нет смысла изучать SOLID и паттерны проектирования.

И ещё, столь же важно отметить, что понять всю силу полиморфизма можно только на языке со статической типизацией, просто потому что с динамической типизацией полиморфизм становится незаметным, но вездесущим. :)

Модули верхних уровней не должны зависеть от модулей нижних уровней. Оба типа модулей должны зависеть от абстракций. Абстракции не должны зависеть от реализации. Реализация должна зависеть от абстракции.

Пример нарушения принципа:

Что плохо?:

UserService зависит от конкретного класса Database, что делает его менее гибким и более зависимым от изменений в Database. Если пользователя нужно будет еще записывать в файл, отправлять на другой сервис в определенном виде, то придется переписывать и изменять много кода. Модуль верхнего уровня тесно связан с модулем нижнего уровня, а нужно, чтобы оба они зависели от абстракции.

Исправленный код:

Используем абстракцию (интерфейс) для БД:

Здесь UserService слабо связан с базой данных, он зависит от абстракции в виде интерфейса. Не важно, какая база данных будет использоваться и как она внутри работает (обрабатывает пользователя), написанный код меняться не будет.

Граф — это более общий случай дерева. Иногда деревья называют ациклическими графами.

Отличий у этих структур данных два:

● В графе возможны циклы, то есть «ребёнок» может быть «родителем» для того же элемента.

● Рёбра тоже могут нести смысловую нагрузку, то есть нужно сохранять их значения.

Графы бывают ориентированные и неориентированные. У первых рёбра между узлами имеют направление, так что порядок элементов важен. У вторых направлений нет, и элементы можно читать и обходить в любом порядке.

У ориентированных графов важен порядок элементов, у неориентированных ― элементы можно менять местами

Графы часто представляют в виде матрицы смежности.

Здесь каждая строка или столбец — узел. 1 в ячейке означает, что между узлами есть связь, 0 — что связи нет. Если у связей, то есть рёбер графа, есть вес, он как раз может быть помещён в ячейку

Как применяют графы:

● Для хранения информации, связанной друг с другом сложными соотношениями.

● Для анализа соотносящейся друг с другом информации.

● Для построения маршрута из точки А в точку Б.

Структуру данных для работы выбирают в зависимости от задачи. Если нужно что-то простое, подойдёт обычный массив. Когда требуется создать очередь или историю запросов, выбирают связный список или очередь. Если нужен поиск и сортировка, поможет двоичное дерево. Именно поэтому важно знать все типы данных в программировании, чтобы подбирать оптимальный в любой ситуации.

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

Инкапсуляция - это принцип объектно-ориентированного программирования, который позволяет объединить данные (переменные) и методы (функции), работающие с этими данными, в единый компонент, называемый объектом. Он предполагает скрытие внутренней реализации объекта от внешнего мира и предоставление только необходимого интерфейса для взаимодействия с ним.

Рассматривая инкапсуляцию, обычно обращают внимание на следующие аспекты:

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

Интерфейс доступа: Разработчик определяет, какие методы и свойства объекта будут доступны для использования извне. Это создает четкий интерфейс, который скрывает сложности внутренней реализации и упрощает взаимодействие с объектом.

Безопасность и надежность: Инкапсуляция способствует созданию более надежных и безопасных программ. Поскольку внутренние детали объекта скрыты, изменения в реализации могут быть внесены без влияния на внешний код, предоставляющий доступ к объекту.

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

Модульность и управление сложностью: Инкапсуляция помогает разделить большие программы на более мелкие, легко управляемые модули. Это способствует улучшению структуры кода и облегчает поддержку и разработку.

Если в коде программы Базовый класс заменить на его Наследника, то программа должна работать, так как в Наследнике есть все операции, которые были в Базовом. В Базовый класс нужно выносить только общую логику, которую наследники будут реализовывать. Наследников создаем только тогда, когда они правильно собираются реализовать логику Базового класса без проблем.

Пусть есть человек, который умеет только есть и спать

И есть студент, который наследуется от Person. Он, помимо есть и спать, может еще учиться

И он умеет делать все то, что умеет человек. Потому что студент — это человек, кто бы что не говорил.

Пример нарушения всех мыслимых и немыслимых норм мог бы быть таким:

Тут студента уже нельзя назвать человеком. Потому что он не делает все то же, что и человек, плюс что-то дополнительно. Ну и ведет себя как не будем говорить кто.

Наследник ведь расширяет интерфейс. Значит, только добавляет дополнительный функционал (говорили про это в Open-Closed). Значит, он не должен ломать то, что написано раньше.

Определение

• Хранит элементы данных на основе последовательного индекса, чаще всего с нулевой базой
• В его основе лежат кортежи из теории множеств
• Массив — одна из старейших и наиболее используемых структур данных

Что вам нужно знать

• Массив оптимален для индексирования; плох для поиска, вставки и удаления (если не делать этого в самом конце массива)
• Основная разновидность — линейные массивы, или одноразмерные
• Их размер статичен, то есть при объявлении линейного массива задаётся фиксированный размер
• Динамические массивы подобны линейным, но в них зарезервировано пространство для дополнительных элементов
• При заполнении динамического массива его содержимое копируется в массив большего размера
• Двумерные массивы имеют два индекса x и y, как сетки или вложенные массивы

Эффективность («О» большое)

• Индексирование: линейный массив — O(1), динамический массив — O(1)
• Поиск: линейный массив — O(n), динамический массив — O(n)
• Оптимизированный поиск: линейный массив — O(log n), динамический массив — O(log n)
• Вставка: линейный массив — недопустимо, динамический массив — O(n)

Основными компонентами микропроцессора являются

• Адресные строки для ссылки на адрес блока
• Линии передачи данных
• Микросхемы для обработки данных

Есть много команд, которые отображают свободную или использованную память в Linux. Самый простой способ отслеживать использование памяти в Linux — использовать команду «free». Linux и другие операционные системы на основе Unix обычно показывают меньше свободной памяти, чем может быть доступно. Вот почему Swap (special type of memory) доступен для использования, когда ОЗУ заполнена.

Алгоритм бинарного поиска - это эффективный метод поиска элемента в отсортированном массиве данных. Он основан на принципе разделяй и властвуй и работает за логарифмическое время.

Вот как он работает:

• Инициализация: Начинается с того, что алгоритм определяет диапазон, в котором будет осуществляться поиск. Обычно это весь массив данных.
• Середина диапазона: Алгоритм выбирает середину диапазона и сравнивает значение в этой середине с искомым значением.
• Сужение диапазона: Если значение в середине равно искомому значению, поиск завершается. Если искомое значение меньше значения в середине, то поиск продолжается только в левой половине диапазона. Если больше, то только в правой.
• Повторение: Шаги 2 и 3 повторяются, пока искомый элемент не будет найден или пока диапазон поиска не сократится до одного элемента.
• Бинарный поиск используется для эффективного поиска элементов в упорядоченных массивах данных. Он обеспечивает быстрое время выполнения, особенно при работе с большими объемами данных, поскольку его сложность составляет O(log n), где n - количество элементов в массиве.

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

Основное отличие хаба (концентратора) от свитча (коммутатора) заключается в способе передачи данных в сети. Хаб принимает данные на одном порту и передаёт их на все остальные порты без учёта назначения, что приводит к большему числу коллизий и снижает общую производительность сети. Свитч же направляет данные только к целевому устройству, используя таблицу MAC-адресов для определения нужного порта, что минимизирует коллизии и повышает эффективность и скорость передачи данных.

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

Динамическое программирование применяют в тех случаях, когда задача имеет определённую структуру, которая допускает разбиение на подзадачи, и когда решение каждой подзадачи может быть повторно использовано для решения других подзадач. Оно особенно эффективно в случаях, когда решение полной задачи содержит в себе оптимальные решения её подзадач.

Примеры задач, которые часто решаются с использованием динамического программирования, включают в себя:

• Задача о рюкзаке: Найти оптимальный способ упаковать предметы в рюкзак с ограниченной вместимостью, чтобы максимизировать суммарную стоимость упакованных предметов.
• Задача о наибольшей общей подпоследовательности (LCS): Найти самую длинную общую подпоследовательность элементов в двух последовательностях.
• Задача о нахождении кратчайшего пути в графе: Найти кратчайший путь от начальной вершины до конечной в графе с весами на рёбрах.
• Задача о разделении матрицы для умножения: Найти оптимальный порядок умножения матриц, чтобы минимизировать количество операций умножения скалярных элементов.

Определение:

Поиск в глубину — это алгоритм, ищущий по дереву (или графу) сначала в глубину начиная с корня.

• Алгоритм идёт по дереву, переходя между уровнями по левым дочерним узлам, пока не дойдёт до самого низа.
• Завершив проход по ветви, алгоритм возвращается обратно, просматривая правые дочерние узлы этой ветви. Причём, если возможно, выбирает самые левые из узлов, расположенных справа от предыдущего маршрута.
• Завершив просмотр всей ветви, алгоритм переходит к узлу, расположенному справа от корня, и снова идёт по левым дочерним узлам до самого дна.
• Последним анализируется крайний правый узел (расположенный справа от всех своих предшественников).

Что вам нужно знать:

• Алгоритм оптимален для поиска по дереву, чья глубина превышает ширину.
• Для работы алгоритма используется стек.
• Поскольку стек является LIFO-структурой, ему не нужно отслеживать указатели узлов, поэтому потребляется меньше памяти, чем в случае с поиском в ширину.
• Когда алгоритм не может дальше идти по левой стороне, он начинает анализировать стек.

Эффективность («О» большое):

• Поиск: поиск в глубину — O(|E| + |V|).
• E — количество рёбер (граней?).
• V — количество вершин.

Аутентификация возможна при помощи следующих методов: что человек знает (пароль), что у человека есть (токен) и кто человек есть (биометрия). При двухфакторной аутентификации часто используется пароль и токен, в некоторых случаях – ПИН и отпечаток большого пальца.

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

Архитектура компьютера делится на три категории.

• Проектирование системы: включает в себя все аппаратные компоненты системы, включая процессор данных, помимо ЦП, например, прямой доступ к памяти и графический процессор.
• Архитектура набора команд (ISA): Это встроенный язык программирования центрального процессора. Он определяет функции и возможности ЦП на основе программ, которые он может обрабатывать.
• Микроархитектура: определяет путь к данным, элемент хранения и обработку данных, а также то, как они должны быть реализованы в ISA.