{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Примеры заданий по live coding c решениями с собеседований\n", "\n", "Добро пожаловать в этот Jupyter Notebook! Если вы готовитесь к собеседованиям на роль Data Scientist, этот материал может быть для вас полезным.\n", "\n", "## Что вы найдете в этом ноутбуке:\n", "\n", "1. **Реальные задачи с собеседований:** Все задачи, представленные здесь, были собраны с реальных собеседований. \n", "2. **Подробные решения и объяснения:** Для каждой задачи предоставлены подробные решения с объяснениями. Я делюсь своим процессом мышления и почему был выбран именно этот подход или метод.\n", "3. **Главные отличия от задач в разделах algo и leetcode:** Все задачи в этих разделах больше на знание Python, для реализации стандартных задач, актуальных в повседневной работе в области Data Science. То есть знание алгоритмов не требуется, как и предварительное решение задач с LeetCode. Также на собеседованиях мне встречались технические специалисты, которые открыто признавались, что сами не любят задачи аля литкод и говорили, что все равно требуется проверить знание кодирования и анонсировали, анонсировали, что задача будет простая или сильно прикладная, например, подобная задаче, которую мы вчера решали с джуном).\n", "\n", "Цель этого ноутбука - помочь вам лучше подготовиться к собеседованиям с live coding, дать понимание типов задач, которые могут быть заданы, и предложить эффективные методы их решения. Независимо от того, являетесь ли вы начинающим или опытным специалистом, я надеюсь, что найдете здесь что-то полезное для себя.\n", "\n", "Удачи в подготовке и на собеседованиях!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Задача 1. Разработка класса аналог множества, только с генерацией случайного элемента\n", "\n", "Необходимо разработать класс `RandomizedSet`, который обладает следующими характеристиками:\n", "\n", "- Добавление элемента (`add`) и его удаление (`delete`) должны выполняться за время O(1).\n", "- Возможность генерации случайного элемента (`get_random`) из множества за время O(1).\n", "\n", "#### Структура класса:\n", "\n", "```python\n", "class RandomizedSet:\n", " def __init__(self) -> None:\n", " # Конструктор класса\n", "\n", " def add(self, element: int) -> None:\n", " # Метод для добавления элемента в множество\n", "\n", " def delete(self, element: int) -> None:\n", " # Метод для удаления элемента из множества\n", "\n", " def get_random(self) -> int:\n", " # Метод для получения случайного элемента из множества\n", "\n", "\n", "randomized_set = RandomizedSet()\n", "randomized_set.add(1)\n", "randomized_set.add(2)\n", "randomized_set.add(1)\n", "assert randomized_set.get_random() in [1, 2] # Должен вернуть 1 или 2 с равной вероятностью\n", "assert randomized_set.get_random() in [1, 2] # Должен вернуть 1 или 2 с равной вероятностью\n", "randomized_set.delete(1)\n", "assert randomized_set.get_random() == 2 # Должен вернуть 2, так как 1 был удален\n", "```\n", "\n", "***задача с собеса X5***" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Решение задачи 1**:" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "import random\n", "\n", "class RandomizedSet:\n", " def __init__(self) -> None:\n", " self.indexes = {} # Словарь для хранения элементов и их индексов\n", " self.items = [] # Список для хранения элементов\n", "\n", " def add(self, item: int) -> None: # O(1)\n", " if item not in self.indexes: # Проверяем, что элемента еще нет в множестве\n", " # O(1) <= Операция проверки наличия элемента в хэш-таблице, \n", " # каковой является словарь в Python (self.dict в данном случае), \n", " # в среднем выполняется за время O(1)\n", " self.indexes[item] = len(self.items)\n", " self.items.append(item)\n", "\n", " def delete(self, item: int) -> None: # O(1)\n", " if item in self.indexes: # Проверяем, что элемент существует\n", " index = self.indexes.pop(item) # Удаляем элемент из словаря и получаем его индекс\n", " # Заменяем удаляемый элемент последним элементом в списке\n", " last_item = self.items[-1] \n", " self.items[index] = last_item\n", " self.indexes[last_item] = index\n", " self.items.pop() # Удаляем последний элемент\n", "\n", " def get_random(self) -> int:\n", " return random.choice(self.items) # Возвращаем случайный элемент из списка" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "randomized_set = RandomizedSet()\n", "randomized_set.add(1)\n", "randomized_set.add(2)\n", "randomized_set.add(1)\n", "randomized_set.get_random() # Должен вернуть 1 или 2 с равной вероятностью\n", "\n" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "randomized_set.get_random() # Должен вернуть 1 или 2 с равной вероятностью" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "randomized_set.delete(1)\n", "randomized_set.get_random() # Должен вернуть 2, так как 1 был удален" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Задача 2. Разработка класса DummyModel для предсказания на основе статистической функции\n", "\n", "Необходимо доработать класс `DummyModel`, который обладает следующими характеристиками:\n", "\n", "- Инициализация модели с выбранной статистической функцией (например, медиана, среднее, максимум).\n", "- Метод `fit`, который получает на вход `X_train` и `y_train`\n", "- Метод `predict`, который по `X_test` возвращает вектор\n", "\n", "#### Структура класса:\n", "\n", "```python\n", "\n", "class DummyModel:\n", " def __init__(self, function):\n", " ...\n", "\n", " def fit(self, X_train, y_train):\n", " ...\n", "\n", " def predict(self, X_test):\n", " ...\n", "\n", "# Пример использования\n", "X_train = np.array([[1, 2], [3, 4], [5, 6], [7, 8]])\n", "y_train = np.array([1, 2, 3, 40])\n", "\n", "# Инициализация модели с функцией np.median\n", "model = DummyModel(function=np.mean)\n", "model.fit(X_train, y_train)\n", "\n", "# Тестовые данные\n", "X_test = np.array([[9, 10], [11, 12]])\n", "\n", "# Предсказание\n", "predictions = model.predict(X_test)\n", "assert np.array_equal(predictions, np.array([11.5, 11.5])) \n", "```\n", "\n", "***Задание с собеседования ГК Самолет (в задании это не указано, но задавая вопросы можно узнать библиотеки которые можно использовать - например numpy, также дали дополнительное задание - написать аннотацию типов)***" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Решение задачи 2**:\n", "- __init__, инициализирует объект класса следующими атрибутами:\n", " - self.func - функция агрегации, передаваемая при создании объекта класса. Она определяет метод агрегации (например, среднее значение, медиана, максимум и т.д.), который будет использоваться для вычисления одного предсказываемого значения на основе целевых значений (y_train) в методе fit\n", " - self.value - атрибут для хранения рассчитанного агрегированного значения после вызова метода fit. Изначально он устанавливается в None, так как до вызова метода fit у нас нет рассчитанного значения\n", "\n", "\n", "- Метод fit: Принимает два аргумента: X_train и y_train, которые представляют собой обучающий набор признаков и целевые значения соответственно. В этом методе вы вычисляете агрегированное значение y_train с помощью предоставленной функции агрегации и сохраняете это значение в переменной экземпляра self.value\n", "\n", "- Метод predict: Принимает один аргумент: X_test, который представляет собой набор признаков, для которого вы хотите сделать предсказания. В этом методе вы создаете массив NumPy, который заполняете повторяющимися значениями self.value (рассчитанными в методе fit) в количестве, равном длине X_test. Таким образом, для каждого элемента в X_test вы предсказываете одно и то же значение, рассчитанное на основе y_train\n" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "\n", "class DummyModel:\n", " def __init__(self, func) -> None:\n", " self.func = func\n", " self.value = None\n", "\n", " def fit(self, X_train: np.ndarray, y_train: np.ndarray) -> None:\n", " self.value = self.func(y_train)\n", "\n", " def predict(self, X_test: np.ndarray) -> np.ndarray:\n", " return np.array([self.value] * len(X_test))" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Predictions: [11.5 11.5]\n" ] } ], "source": [ "X_train = np.array([[1, 2], [3, 4], [5, 6], [7, 8]])\n", "y_train = np.array([1, 2, 3, 40])\n", "\n", "# Инициализация модели с функцией np.median\n", "model = DummyModel(np.mean)\n", "model.fit(X_train, y_train)\n", "\n", "# Тестовые данные\n", "X_test = np.array([[9, 10], [11, 12]])\n", "\n", "predictions = model.predict(X_test) \n", "assert np.array_equal(predictions, np.array([11.5, 11.5])) \n", "\n", "# Вывод результатов\n", "print(\"Predictions:\", predictions)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Далее последовал вопрос как можно отпимизировать код чтобы он быстрее выполнялся на больших массивов" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [], "source": [ "class DummyModel_optimized:\n", " def __init__(self, func) -> None:\n", " self.func = func\n", " self.value = None\n", "\n", " def fit(self, X_train: np.ndarray, y_train: np.ndarray) -> None:\n", " self.value = self.func(y_train)\n", "\n", " def predict(self, X_test: np.ndarray) -> np.ndarray:\n", " return np.full(len(X_test), self.value)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Тестирование решения для задачи 2**:" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "X_train shape: (10000000, 4)\n", "X_test shape: (2000000, 4)\n", "y_train shape: (10000000,)\n", "y_train median: 1.0\n", "y_train mean: 2.9999999\n" ] } ], "source": [ "# Задаем размеры массивов\n", "size = int(10e6)\n", "num_features = 4\n", "\n", "# Создаем X_train и X_test\n", "X_train = np.ones((size, num_features)) # Массив size x num_features, заполненный единицами\n", "X_test = np.ones((int(size * 0.2), num_features)) # 20% от X_train\n", "\n", "# Создаем y_train\n", "y_train = np.ones(size) # Вектор длиной size, заполненный единицами\n", "\n", "y_train[-1] = 2*size # Заменяем последний элемент большим значением\n", "\n", "# Проверяем размерности\n", "print(f\"X_train shape: {X_train.shape}\")\n", "print(f\"X_test shape: {X_test.shape}\")\n", "print(f\"y_train shape: {y_train.shape}\")\n", "print(f\"y_train median: {np.median(y_train)}\")\n", "print(f\"y_train mean: {y_train.mean()}\")" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [], "source": [ "model1 = DummyModel(np.mean)\n", "model1.fit(X_train, y_train)" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [], "source": [ "model2 = DummyModel_optimized(np.mean)\n", "model2.fit(X_train, y_train)" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "135 ms ± 14.2 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n" ] } ], "source": [ "%timeit -n 10 model1.predict(X_test)" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "2.9 ms ± 266 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n" ] } ], "source": [ "%timeit -n 100 model2.predict(X_test)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "в принципе этого следовало ожидать, нампай обычно быстрее делает процессы" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Задача 3: Разработка декоратора `progress_fit_predict` для отслеживания времени обучения и предсказания моделей\n", "\n", "Необходимо разработать декоратор `progress_fit_predict`, который можно применить к классам моделей. Декоратор должен отслеживать время, затраченное на методы `fit` и `predict` модели, и выводить это время в консоль.\n", "\n", "#### Требования к декоратору:\n", "\n", "1. При вызове метода `fit` модели должно выводиться сообщение в формате: \"Обучение модели {название_класса} заняло: {время} секунд\".\n", "2. При вызове метода `predict` модели должно выводиться сообщение в формате: \"Предсказание модели {название_класса} заняло: {время} секунд\".\n", "3. Декоратор не должен влиять на остальные методы класса модели.\n", "\n", "#### Структура декоратора:\n", "\n", "```python\n", "def progress_fit_predict(...):\n", " ...\n", "```\n", "#### Пример использования декоратора:\n", "```python\n", "@progress_fit_predict\n", "class LinearRegression:\n", " ...\n", "\n", " def fit(self, X_train: np.ndarray, y_train: np.ndarray) -> None:\n", " ...\n", "\n", " def predict(self, X_test: np.ndarray) -> np.ndarray:\n", " ...\n", "\n", "# Создание экземпляра модели и тестирование\n", "model = LinearRegression()\n", "model.fit(X_train, y_train)\n", "predictions = model.predict(X_test)\n", "```\n", "**Вывод:** \n", "Обучение модели LinearRegression заняло: 1.73 секунд \n", "Предсказание модели LinearRegression заняло: 0.02 секунд\n", "\n", "***Задание с собеседования Rubbles***" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Решение задачи 3**:\n", "- я ни разу до этого не писал декораторы для классов поэтому сказал про это. Меня попросили написать для функции, а потом подсказали что можно заменить def на class и название с больгой буквы и все. Оказалось что там различий нет: \n", "- декораторы функций: \n", " - Модифицируют поведение функции, \n", " - Обычно принимают функцию в качестве аргумента и возвращают новую функцию.\n", " - Могут добавлять дополнительную логику до и после выполнения оригинальной функции.\n", "- декораторы классов:\n", " - Модифицируют поведение класса.\n", " - Обычно принимают класс в качестве аргумента и возвращают новый класс или экземпляр класса.\n", " - Могут добавлять новые методы, изменять существующие, добавлять атрибуты или изменять процесс инициализации экземпляра.\n", "- super() используется для вызова методов родительского класса. Это стандартный подход в объектно-ориентированном программировании, который позволяет дочернему классу расширять или изменять функционал родительского класса." ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [], "source": [ "import time\n", "import numpy as np\n", "\n", "def progress_fit_predict(cls):\n", " class Wrapped(cls):\n", " def fit(self, X, y):\n", " start_time = time.time()\n", " super().fit(X, y)\n", " print(f\"Обучение модели {cls.__name__} заняло: {time.time() - start_time:.2f} секунд\")\n", "\n", " def predict(self, X):\n", " start_time = time.time()\n", " predict = super().predict(X)\n", " print(f\"Предсказание модели {cls.__name__} заняло: {time.time() - start_time:.2f} секунд\")\n", " return predict\n", "\n", " return Wrapped" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Тестирование решения для задачи 3**:" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Обучение модели DummyModel заняло: 0.02 секунд\n", "Предсказание модели DummyModel заняло: 0.00 секунд\n" ] } ], "source": [ "@progress_fit_predict\n", "class DummyModel: # приведу пример на DummyModel модели которая была описана выше для проверки кода\n", " def __init__(self, func) -> None:\n", " self.func = func\n", " self.value = None\n", "\n", " def fit(self, X_train: np.ndarray, y_train: np.ndarray) -> None:\n", " self.value = self.func(y_train)\n", "\n", " def predict(self, X_test: np.ndarray) -> np.ndarray:\n", " return np.full(len(X_test), self.value)\n", "\n", "# Создание экземпляра модели и тестирование\n", "model = DummyModel(np.mean)\n", "model.fit(X_train, y_train)\n", "predictions = model.predict(X_test)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "дальше последовал вопрос, а можно ли применить этот декоратор к моделям из sklearn. Если да то как? И будут ли какие-нибудь ошибки?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Решения для задачи 3 для встроенных классов моделей sklearn**:" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [], "source": [ "from sklearn.linear_model import LinearRegression\n", "\n", "@progress_fit_predict\n", "class MyLinearRegression(LinearRegression):\n", " pass" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "((8000000, 4), (2000000, 4), (8000000,), (2000000,))" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from sklearn.datasets import make_regression\n", "from sklearn.model_selection import train_test_split\n", "\n", "# Задаем размеры массивов\n", "size = int(10e6)\n", "num_features = 4\n", "\n", "# Генерация синтетических данных\n", "X, y = make_regression(n_samples=size, n_features=num_features, noise=10)\n", "\n", "# Разделение данных на обучающую и тестовую выборку (80% обучающих, 20% тестовых)\n", "X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)\n", "X_train.shape, X_test.shape, y_train.shape, y_test.shape" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Тестирование решения для задачи 3 для встроенных классов моделей sklearn**:" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Обучение модели MyLinearRegression заняло: 1.68 секунд\n", "Предсказание модели MyLinearRegression заняло: 0.02 секунд\n" ] } ], "source": [ "# Создание экземпляра модели и тестирование\n", "model = MyLinearRegression()\n", "model.fit(X_train, y_train)\n", "predictions = model.predict(X_test)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Задача 4: Валидация корректности расстановки скобок в выражении\n", "\n", "**Описание:** \n", "Необходимо создать функцию, которая анализирует строку на предмет правильности расстановки круглых скобок. Функция возвращает `True`, если все открытые скобки закрыты корректно в соответствии с правилами скобочных последовательностей, и `False` в противном случае.\n", "\n", "**Функция:**\n", "\n", "```python\n", "def is_valid_brackets(expression: str) -> bool:\n", " ...\n", "```\n", "**Примечания:**\n", "- Пустая строка считается корректной скобочной последовательностью\n", "- Скобочные последовательности без вложенных пар считаются невалидными (например, )( должно возвращать False)\n", "\n", "***Задание с собеседования Rubbles***" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Решение задачи 4**:\n", "- решение подобной задачи, обычно реализуется через стек в виде листа. Я тоже так попробовал сделать. Потом последовали вопросы зачем нам стэк? А если выражение будет содержать милионы скобок, что мы будем этот список хранить? Ведь в условии задачи нет ограничения на длину строки? А можно ли не хранить скобки. В общем ниже вы увидите оптимальное решение без стэка, просто со счетчиком. \n", "1. В начале функция инициализирует счетчик count, который отслеживает количество открытых скобок, которые ещё не были закрыты.\n", "2. Циклом проходим по всем символам в строке\n", "3. Если текущий символ является открывающей скобкой (, функция увеличивает счетчик count на единицу\n", "4. Если текущий символ является закрывающей скобкой ), функция сначала проверяет, не равен ли счетчик count нулю. Если count равен нулю, это значит, что нет открывающей скобки для пары, и функция возвращает False, указывая на неправильное расположение скобок\n", "5. Если же счетчик count больше нуля, это означает, что есть открывающая скобка, которая может быть закрыта, и функция уменьшает счетчик count на единицу, учитывая закрытие одной из открывающих скобок.\n", "6. После прохождения всех символов, сравниваем счетчик count с нулем. Это происходит тогда когда все открывающие скобки имеют соответствующие закрывающие. В этом случае функция возвращает True. Иначе False" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [], "source": [ "def is_valid_brackets(expression: str) -> bool:\n", " count = 0\n", " for char in expression:\n", " if char == '(':\n", " count += 1\n", " elif char == ')':\n", " if count == 0:\n", " return False\n", " count -= 1\n", " return not count" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "is_valid_brackets('()')" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "is_valid_brackets(')(')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Задача 5: Напишите тест к предыдущей функции is_valid_brackets\n", "\n", "**Примечания:**\n", "- cначала я начал писать функцию через `assert`. Меня спросили, сколько таких `assert` будет, где и как я буду хранить тесты и правильные варианты. А если тестов много и они генерируются где-то в другом месте? Просто миллионы тестов правильных выражений и много тестов для неправильных выражений — я сразу сообразил, что нужно использовать специальную библиотеку `unittest`.\n", "- реализовать решение через библиотеку `unittest` тоже не подошло, потому что тесты реализованы так, что они локализованы. Можно, конечно, внутри класса создать переменные и снаружи передать туда кортежи, но лучше так не делать. Тесты должны содержать в себе все, что нужно, и добавление туда чего-либо нежелательно.\n", "- в итоге ожидали просто реализацию функции, которая принимает кортеж и ожидаемое значение `False` или `True`, чтобы не хранить их в каждом тесте.\n", "\n", "***Задание с собеседования в Rubbles***" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Решение задачи 5**:" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [], "source": [ "# Функция для тестирования без использования unittest\n", "def test_is_valid_brackets(expressions, expected_value):\n", "\n", " all_passed = True\n", " for i, expression in enumerate(expressions):\n", " result = is_valid_brackets(expression)\n", " if result != expected_value:\n", " print(f\"Тест не пройден в {i}. для выражения \\\"{expression}\\\" : ожидалось {expected_value}, получено {result}\")\n", " all_passed = False\n", " \n", " if all_passed:\n", " print(\"Все тесты пройдены успешно.\")\n", "\n" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Все тесты пройдены успешно.\n", "Все тесты пройдены успешно.\n" ] } ], "source": [ "valid_expressions = (\"()\", \"()()\", \"(())\")\n", "invalid_expressions = (\")(\", \"(()\", \"())\")\n", "\n", "# Запуск функции тестирования\n", "test_is_valid_brackets(valid_expressions, True)\n", "test_is_valid_brackets(invalid_expressions, False)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Задача 6. Напишите функцию поиска значения в массиве\n", "\n", "**Дополнительные условия озвученные после уточнения:** \n", "- массив отсортирован\n", "\n", "```python\n", "def search(arr:List, value:int) -> bool:\n", " ...\n", "```\n", "### Примеры:\n", "| Ввод | Вывод | \n", "|-------------|-------| \n", "|[], 0 | False | \n", "|[1, 4, 9], 1 | True | \n", "|[1, 4, 9], 7 | False | \n", "\n", "***Задание с собеседования Avito (похожую задачу я видел на собесе в Яндесе, но эта задача была лишь частью большой матрешки, остальные задачи и вопросы уже строились над ней)***" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Решение задачи 6**:\n", "- решение этой задачи лучше сделать через классический универсальный код бинарного поиска, так все последующие матрешки будут более понятно реализуемы. " ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [], "source": [ "from typing import List\n", "\n", "def search(arr: List[int], value: int) -> bool:\n", " def check(m, param):\n", " return arr[m] >= param\n", "\n", " def lbinsearch(l, r, check, param):\n", " while l < r:\n", " m = (l + r) // 2\n", " if check(m, param):\n", " r = m\n", " else:\n", " l = m + 1\n", " return l\n", "\n", " index = lbinsearch(0, len(arr) - 1, check, value)\n", "\n", " if index < len(arr) and arr[index] == value:\n", " return True\n", " else:\n", " return False" ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 39, "metadata": {}, "output_type": "execute_result" } ], "source": [ "search([], 0)" ] }, { "cell_type": "code", "execution_count": 40, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 40, "metadata": {}, "output_type": "execute_result" } ], "source": [ "search([1, 4, 9], 1)" ] }, { "cell_type": "code", "execution_count": 41, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "search([1, 4, 9], 7)" ] }, { "cell_type": "code", "execution_count": 42, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 42, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# дополним тесты случаем когда искомое значение крайнее справа\n", "search([1, 4, 9], 9)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Далее задали вопрос о том, как реализовать поиск с помощью правого бинарного поиска." ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [], "source": [ "def search(arr: List[int], value: int) -> bool:\n", " def check(m, param):\n", " return arr[m] <= param\n", "\n", " def rbinsearch(l, r, check, param):\n", " while l < r:\n", " m = (l + r + 1) // 2\n", " if check(m, param):\n", " l = m\n", " else:\n", " r = m - 1\n", " return l\n", "\n", " index = rbinsearch(0, len(arr) - 1, check, value)\n", "\n", " if index < len(arr) and arr[index] == value:\n", " return True\n", " else:\n", " return False" ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" } ], "source": [ "search([], 0)" ] }, { "cell_type": "code", "execution_count": 35, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 35, "metadata": {}, "output_type": "execute_result" } ], "source": [ "search([1, 4, 9], 1)" ] }, { "cell_type": "code", "execution_count": 36, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 36, "metadata": {}, "output_type": "execute_result" } ], "source": [ "search([1, 4, 9], 7)" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "source": [ "search([1, 4, 9], 9)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Самые частые ошибки, которые я видел у кандидатов, — это реализация в `while l < r` нестрогого неравенства, ошибки с зацикливанием при реализации шагов (`m = (l + r) // 2` и `m = (l + r + 1) // 2`), а также выполнение условия не в виде отдельной функции `def check(m, param)` с разными дополнительными условиями для избежания двойных проверок при строгом сравнении, и вопросы о том, как будет работать алгоритм, если массив имеет определенные особенности. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**!!!дополнение к задаче!!!** вот некоторые примеры задач-матрёшек которые могут быть заданы после решения этой задачи без встроенных функций:\n", "- если значение не найдено выведи левый элемент, если его нет, то верни False\n", "- если значение не найдено выведи правый элемент, если его нет, то верни False\n", "- а если на входе будет строка из латинских прописных символов\n", "- также могут спросить, почему я не использовал встроенную функцию бинарного поиска? после того как я привел пример синтаксиса встроенной функции, пошли вопросы какой поиск реализован во встроенном методе левый или правый? какую из вышеперечисленных задач нельзя решить встроенной функцией без дополнительной проверки, что найденный элемент соответствует условию" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ниже решение к одной из возможных таких задач:\n", "- найти два соседних элемента в сумме дающих больше заданного значения, если нет верни False" ] }, { "cell_type": "code", "execution_count": 43, "metadata": {}, "outputs": [], "source": [ "def search(arr: List[int], value: int) -> bool:\n", " def check(m, param):\n", " # Проверяем, чтобы индекс не выходил за пределы массива\n", " if m + 1 >= len(arr):\n", " return False\n", " # Возвращаем True, если сумма элемента m и следующего не меньше искомого значения\n", " return arr[m] + arr[m + 1] >= param\n", "\n", " def lbinsearch(l, r, check, param):\n", " while l < r:\n", " m = (l + r) // 2\n", " if check(m, param):\n", " r = m\n", " else:\n", " l = m + 1\n", " return l\n", "\n", " index = lbinsearch(0, len(arr) - 1, check, value)\n", " if index < len(arr) - 1:\n", " return f'индексы пары:({index}, {index + 1}) пара: ({arr[index]}, {arr[index + 1]})' # Возвращаем пару элементов\n", " else:\n", " return False" ] }, { "cell_type": "code", "execution_count": 44, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'индексы пары:(1, 2) пара: (1, 4)'" ] }, "execution_count": 44, "metadata": {}, "output_type": "execute_result" } ], "source": [ "search([0, 1, 4, 2, 1, 4, 3, 5], 2)" ] }, { "cell_type": "code", "execution_count": 45, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'индексы пары:(4, 5) пара: (1, 4)'" ] }, "execution_count": 45, "metadata": {}, "output_type": "execute_result" } ], "source": [ "search([0, 1, 4, 2, 1, 4, 3, 5], 5)" ] }, { "cell_type": "code", "execution_count": 46, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'индексы пары:(6, 7) пара: (3, 5)'" ] }, "execution_count": 46, "metadata": {}, "output_type": "execute_result" } ], "source": [ "search([0, 1, 4, 2, 1, 4, 3, 5], 8)" ] }, { "cell_type": "code", "execution_count": 47, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'индексы пары:(5, 6) пара: (4, 3)'" ] }, "execution_count": 47, "metadata": {}, "output_type": "execute_result" } ], "source": [ "search([0, 1, 4, 2, 1, 4, 3, 5], 6)" ] }, { "cell_type": "code", "execution_count": 48, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 48, "metadata": {}, "output_type": "execute_result" } ], "source": [ "search([0, 1, 4, 2, 1, 4, 3, 5], 10)" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.9.12" } }, "nbformat": 4, "nbformat_minor": 2 }