Вопрос №1

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

Пример:

def isEven(value):
    return value % 2 == 0

Ответ:

def isEven(value):
    return value & 1 == 0

Или

def isEven(value):
    if value == 0:
        return True
    if value > 1:
        return isEven(value - 2)
    if value < -1:
        return isEven(value + 2)
    return False

Объяснение:

1. Реализация из примера использует оператор остатка от деления (%) для определения остатка от деления числа на 2. Если остаток равен 0, то число является четным.
2. Вторая реализация использует битовую операцию побитового ИЛИ для определения четности числа. Если число является четным, то его младший бит равен 0.
3. Третья реализация использует рекурсию. Результатом рекурсии в итоге станет 1 или -1, то есть нечетное или 0, то есть четное.

• value % 2 == 0: Наиболее простая и понятная реализация; O (1); Не позволяет использовать отрицательные числа.

• value & 1 == 0: Менее понятная реализация, но так же простая; O (1); Позволяет использовать отрицательные числа; Самая высокая скорость выполнения.

• Рекурсия: Понятная реализация; O (n); Позволяет использовать отрицательные числа; Может вызвать переполнение стека.

Вопрос №2

На языке Python написать минимум по 2 класса реализовывающих циклический буфер FIFO. Объяснить плюсы и минусы каждой реализации.

Ответ:

1:

class RingBuffer:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = []

    def add(self, data):
        if len(self.data) < self.capacity:
            self.data.append(data)
        else:
            raise Exception("The buffer is full")

    def get(self):
        try:
            return self.data.pop(0)
        except IndexError:
            raise Exception("The buffer is empty")

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

2:

class RingBuffer:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = [None for i in range(capacity)]
        self.add_to = 0
        self.get_from = 0
    def _inc(self, inx):
        return (inx + 1) % self.capacity
    def add(self, data):
        if self.add_to == self.get_from and self.data[self.add_to] is not None:
            self.get_from = self._inc(self.get_from)
        self.data[self.add_to] = data
        self.add_to = self._inc(self.add_to)
    def get(self):
        data = self.data[self.get_from]
        if data is None:
            raise Exception("The buffer is empty")
        self.data[self.get_from] = None
        self.get_from = self._inc(self.get_from)
        return data
    def __str__(self):
        return self.data.__str__()

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

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

2 вариант: Эффективна для любых размеров буфера. Добавление и извлечение элементов не требуют перемещения данных; Устойчива к переполнению. Добавляет элемент только когда есть свободное место, благодаря циклическим индексам; Более сложная реализация; Использует больше памяти. Хранит все ячейки буфера, даже пустые.

Вопрос №3

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

Ответ:

Быстрая сортировка является одним из самых эффективных алгоритмов сортировки для массивов любого размера и порядка.

def quick_sort(nums):
    l = len(nums)
    if l <= 1:
        return nums
    else:
        q = nums[l//2]
        s_nums = []
        m_nums = []
        e_nums = []
        for n in nums:
            if n < q:
                s_nums.append(n)
            elif n > q:
                m_nums.append(n)
            else:
                e_nums.append(n)
        return quick_sort(s_nums) + e_nums + quick_sort(m_nums)

Плюсы: Быстрая сортировка имеет асимптотическую сложность O(n log n), что делает ее одним из самых быстрых алгоритмов сортировки; Подходит для сортировки массивов любого размера и порядка; Эта реализация быстрой сортировки относительно проста для понимания;

Минусы: Не сохраняет исходный порядок элементов, равных опорному; В некоторых случаях (например, уже отсортированный массив) может работать медленнее других алгоритмов.

Сравнение с другими алгоритмами:

1. Сортировка слиянием: имеет схожую сложность O(n log n), но может быть менее эффективной due to additional space requirements.
2. Сортировка пузырьком: простая, но медленная (O(n^2)) сортировка.
3. Сортировка выбором: еще один простой алгоритм сортировки O(n^2).

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

def unique_elements(input_list):

    # Реализация через цикл for:
    unique_list = []
    for elem in input_list:
        if elem not in unique_list:
            unique_list.append(elem)
    return unique_list

    # Реализация через преобразование в множество:
    unique_set = set(input_list)
    unique_list = list(unique_set)
    return unique_list

    # Реализация через преобразование в ключи словаря:
    return list(dict.fromkeys(input_list))

2. Написать функцию, которая принимает на вход два целых числа (минимум и максимум) и возвращает список всех простых чисел в заданном диапазоне.

def prime_numbers_range(minimum, maximum):
    primes = []
    for num in range(max(2, minimum), maximum + 1):
        is_prime = True
        for i in range(2, int(num ** 0.5) + 1):
            if num % i == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(num)
    return primes

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

class Point:
    def __init__(self, x=0, y=0):
        # Инициализация.
        self.x = x
        self.y = y

    def distance_to(self, other):
        # Вычисление расстояния до другой точки.
        return ((self.x - other.x) ** 2 + (self.y - other.y) ** 2) ** 0.5

    def get_coordinates(self):
        # Получение координат точки в виде кортежа (x, y).
        return self.x, self.y

    def set_coordinates(self, x, y):
        # Установка новых координат точки.
        self.x = x
        self.y = y

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

def sort_strings_by_length(strings):

    # Сортировка по возрастанию длины строки
    sorted_strings_asc = sorted(strings, key=len)

    # Сортировка по убыванию длины строки
    sorted_strings_desc = sorted(strings, key=len, reverse=True)

    return sorted_strings_asc, sorted_strings_desc