Добро пожаловать в этот Jupyter Notebook! Если вы готовитесь к собеседованиям на роль Data Scientist, этот материал может быть для вас полезным.
Цель этого ноутбука - помочь вам лучше подготовиться к собеседованиям с live coding, дать понимание типов задач, которые могут быть заданы, и предложить эффективные методы их решения. Независимо от того, являетесь ли вы начинающим или опытным специалистом, я надеюсь, что найдете здесь что-то полезное для себя.
Удачи в подготовке и на собеседованиях!
Необходимо разработать класс RandomizedSet
, который обладает следующими характеристиками:
add
) и его удаление (delete
) должны выполняться за время O(1).get_random
) из множества за время O(1).class RandomizedSet:
def __init__(self) -> None:
# Конструктор класса
def add(self, element: int) -> None:
# Метод для добавления элемента в множество
def delete(self, element: int) -> None:
# Метод для удаления элемента из множества
def get_random(self) -> int:
# Метод для получения случайного элемента из множества
randomized_set = RandomizedSet()
randomized_set.add(1)
randomized_set.add(2)
randomized_set.add(1)
assert randomized_set.get_random() in [1, 2] # Должен вернуть 1 или 2 с равной вероятностью
assert randomized_set.get_random() in [1, 2] # Должен вернуть 1 или 2 с равной вероятностью
randomized_set.delete(1)
assert randomized_set.get_random() == 2 # Должен вернуть 2, так как 1 был удален
*задача с собеса X5*
Решение задачи 1:
import random
class RandomizedSet:
def __init__(self) -> None:
self.indexes = {} # Словарь для хранения элементов и их индексов
self.items = [] # Список для хранения элементов
def add(self, item: int) -> None: # O(1)
if item not in self.indexes: # Проверяем, что элемента еще нет в множестве
# O(1) <= Операция проверки наличия элемента в хэш-таблице,
# каковой является словарь в Python (self.dict в данном случае),
# в среднем выполняется за время O(1)
self.indexes[item] = len(self.items)
self.items.append(item)
def delete(self, item: int) -> None: # O(1)
if item in self.indexes: # Проверяем, что элемент существует
index = self.indexes.pop(item) # Удаляем элемент из словаря и получаем его индекс
# Заменяем удаляемый элемент последним элементом в списке
last_item = self.items[-1]
self.items[index] = last_item
self.indexes[last_item] = index
self.items.pop() # Удаляем последний элемент
def get_random(self) -> int:
return random.choice(self.items) # Возвращаем случайный элемент из списка
randomized_set = RandomizedSet()
randomized_set.add(1)
randomized_set.add(2)
randomized_set.add(1)
randomized_set.get_random() # Должен вернуть 1 или 2 с равной вероятностью
2
randomized_set.get_random() # Должен вернуть 1 или 2 с равной вероятностью
2
randomized_set.delete(1)
randomized_set.get_random() # Должен вернуть 2, так как 1 был удален
2
Необходимо доработать класс DummyModel
, который обладает следующими характеристиками:
fit
, который получает на вход X_train
и y_train
predict
, который по X_test
возвращает векторclass DummyModel:
def __init__(self, function):
...
def fit(self, X_train, y_train):
...
def predict(self, X_test):
...
# Пример использования
X_train = np.array([[1, 2], [3, 4], [5, 6], [7, 8]])
y_train = np.array([1, 2, 3, 40])
# Инициализация модели с функцией np.median
model = DummyModel(function=np.mean)
model.fit(X_train, y_train)
# Тестовые данные
X_test = np.array([[9, 10], [11, 12]])
# Предсказание
predictions = model.predict(X_test)
assert np.array_equal(predictions, np.array([11.5, 11.5]))
*Задание с собеседования ГК Самолет (в задании это не указано, но задавая вопросы можно узнать библиотеки которые можно использовать - например numpy, также дали дополнительное задание - написать аннотацию типов)*
Решение задачи 2:
init, инициализирует объект класса следующими атрибутами:
Метод fit: Принимает два аргумента: X_train и y_train, которые представляют собой обучающий набор признаков и целевые значения соответственно. В этом методе вы вычисляете агрегированное значение y_train с помощью предоставленной функции агрегации и сохраняете это значение в переменной экземпляра self.value
Метод predict: Принимает один аргумент: X_test, который представляет собой набор признаков, для которого вы хотите сделать предсказания. В этом методе вы создаете массив NumPy, который заполняете повторяющимися значениями self.value (рассчитанными в методе fit) в количестве, равном длине X_test. Таким образом, для каждого элемента в X_test вы предсказываете одно и то же значение, рассчитанное на основе y_train
import numpy as np
class DummyModel:
def __init__(self, func) -> None:
self.func = func
self.value = None
def fit(self, X_train: np.ndarray, y_train: np.ndarray) -> None:
self.value = self.func(y_train)
def predict(self, X_test: np.ndarray) -> np.ndarray:
return np.array([self.value] * len(X_test))
X_train = np.array([[1, 2], [3, 4], [5, 6], [7, 8]])
y_train = np.array([1, 2, 3, 40])
# Инициализация модели с функцией np.median
model = DummyModel(np.mean)
model.fit(X_train, y_train)
# Тестовые данные
X_test = np.array([[9, 10], [11, 12]])
predictions = model.predict(X_test)
assert np.array_equal(predictions, np.array([11.5, 11.5]))
# Вывод результатов
print("Predictions:", predictions)
Predictions: [11.5 11.5]
Далее последовал вопрос как можно отпимизировать код чтобы он быстрее выполнялся на больших массивов
class DummyModel_optimized:
def __init__(self, func) -> None:
self.func = func
self.value = None
def fit(self, X_train: np.ndarray, y_train: np.ndarray) -> None:
self.value = self.func(y_train)
def predict(self, X_test: np.ndarray) -> np.ndarray:
return np.full(len(X_test), self.value)
Тестирование решения для задачи 2:
# Задаем размеры массивов
size = int(10e6)
num_features = 4
# Создаем X_train и X_test
X_train = np.ones((size, num_features)) # Массив size x num_features, заполненный единицами
X_test = np.ones((int(size * 0.2), num_features)) # 20% от X_train
# Создаем y_train
y_train = np.ones(size) # Вектор длиной size, заполненный единицами
y_train[-1] = 2*size # Заменяем последний элемент большим значением
# Проверяем размерности
print(f"X_train shape: {X_train.shape}")
print(f"X_test shape: {X_test.shape}")
print(f"y_train shape: {y_train.shape}")
print(f"y_train median: {np.median(y_train)}")
print(f"y_train mean: {y_train.mean()}")
X_train shape: (10000000, 4) X_test shape: (2000000, 4) y_train shape: (10000000,) y_train median: 1.0 y_train mean: 2.9999999
model1 = DummyModel(np.mean)
model1.fit(X_train, y_train)
model2 = DummyModel_optimized(np.mean)
model2.fit(X_train, y_train)
%timeit -n 10 model1.predict(X_test)
135 ms ± 14.2 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit -n 100 model2.predict(X_test)
2.9 ms ± 266 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
в принципе этого следовало ожидать, нампай обычно быстрее делает процессы
progress_fit_predict
для отслеживания времени обучения и предсказания моделей¶Необходимо разработать декоратор progress_fit_predict
, который можно применить к классам моделей. Декоратор должен отслеживать время, затраченное на методы fit
и predict
модели, и выводить это время в консоль.
fit
модели должно выводиться сообщение в формате: "Обучение модели {название_класса} заняло: {время} секунд".predict
модели должно выводиться сообщение в формате: "Предсказание модели {название_класса} заняло: {время} секунд".def progress_fit_predict(...):
...
@progress_fit_predict
class LinearRegression:
...
def fit(self, X_train: np.ndarray, y_train: np.ndarray) -> None:
...
def predict(self, X_test: np.ndarray) -> np.ndarray:
...
# Создание экземпляра модели и тестирование
model = LinearRegression()
model.fit(X_train, y_train)
predictions = model.predict(X_test)
Вывод:
Обучение модели LinearRegression заняло: 1.73 секунд
Предсказание модели LinearRegression заняло: 0.02 секунд
*Задание с собеседования Rubbles*
Решение задачи 3:
import time
import numpy as np
def progress_fit_predict(cls):
class Wrapped(cls):
def fit(self, X, y):
start_time = time.time()
super().fit(X, y)
print(f"Обучение модели {cls.__name__} заняло: {time.time() - start_time:.2f} секунд")
def predict(self, X):
start_time = time.time()
predict = super().predict(X)
print(f"Предсказание модели {cls.__name__} заняло: {time.time() - start_time:.2f} секунд")
return predict
return Wrapped
Тестирование решения для задачи 3:
@progress_fit_predict
class DummyModel: # приведу пример на DummyModel модели которая была описана выше для проверки кода
def __init__(self, func) -> None:
self.func = func
self.value = None
def fit(self, X_train: np.ndarray, y_train: np.ndarray) -> None:
self.value = self.func(y_train)
def predict(self, X_test: np.ndarray) -> np.ndarray:
return np.full(len(X_test), self.value)
# Создание экземпляра модели и тестирование
model = DummyModel(np.mean)
model.fit(X_train, y_train)
predictions = model.predict(X_test)
Обучение модели DummyModel заняло: 0.02 секунд Предсказание модели DummyModel заняло: 0.00 секунд
дальше последовал вопрос, а можно ли применить этот декоратор к моделям из sklearn. Если да то как? И будут ли какие-нибудь ошибки?
Решения для задачи 3 для встроенных классов моделей sklearn:
from sklearn.linear_model import LinearRegression
@progress_fit_predict
class MyLinearRegression(LinearRegression):
pass
from sklearn.datasets import make_regression
from sklearn.model_selection import train_test_split
# Задаем размеры массивов
size = int(10e6)
num_features = 4
# Генерация синтетических данных
X, y = make_regression(n_samples=size, n_features=num_features, noise=10)
# Разделение данных на обучающую и тестовую выборку (80% обучающих, 20% тестовых)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)
X_train.shape, X_test.shape, y_train.shape, y_test.shape
((8000000, 4), (2000000, 4), (8000000,), (2000000,))
Тестирование решения для задачи 3 для встроенных классов моделей sklearn:
# Создание экземпляра модели и тестирование
model = MyLinearRegression()
model.fit(X_train, y_train)
predictions = model.predict(X_test)
Обучение модели MyLinearRegression заняло: 1.68 секунд Предсказание модели MyLinearRegression заняло: 0.02 секунд
Описание:
Необходимо создать функцию, которая анализирует строку на предмет правильности расстановки круглых скобок. Функция возвращает True
, если все открытые скобки закрыты корректно в соответствии с правилами скобочных последовательностей, и False
в противном случае.
Функция:
def is_valid_brackets(expression: str) -> bool:
...
Примечания:
*Задание с собеседования Rubbles*
Решение задачи 4:
def is_valid_brackets(expression: str) -> bool:
count = 0
for char in expression:
if char == '(':
count += 1
elif char == ')':
if count == 0:
return False
count -= 1
return not count
is_valid_brackets('()')
True
is_valid_brackets(')(')
False
Примечания:
assert
. Меня спросили, сколько таких assert
будет, где и как я буду хранить тесты и правильные варианты. А если тестов много и они генерируются где-то в другом месте? Просто миллионы тестов правильных выражений и много тестов для неправильных выражений — я сразу сообразил, что нужно использовать специальную библиотеку unittest
.unittest
тоже не подошло, потому что тесты реализованы так, что они локализованы. Можно, конечно, внутри класса создать переменные и снаружи передать туда кортежи, но лучше так не делать. Тесты должны содержать в себе все, что нужно, и добавление туда чего-либо нежелательно.False
или True
, чтобы не хранить их в каждом тесте.*Задание с собеседования в Rubbles*
Решение задачи 5:
# Функция для тестирования без использования unittest
def test_is_valid_brackets(expressions, expected_value):
all_passed = True
for i, expression in enumerate(expressions):
result = is_valid_brackets(expression)
if result != expected_value:
print(f"Тест не пройден в {i}. для выражения \"{expression}\" : ожидалось {expected_value}, получено {result}")
all_passed = False
if all_passed:
print("Все тесты пройдены успешно.")
valid_expressions = ("()", "()()", "(())")
invalid_expressions = (")(", "(()", "())")
# Запуск функции тестирования
test_is_valid_brackets(valid_expressions, True)
test_is_valid_brackets(invalid_expressions, False)
Все тесты пройдены успешно. Все тесты пройдены успешно.
Дополнительные условия озвученные после уточнения:
def search(arr:List, value:int) -> bool:
...
Ввод | Вывод |
---|---|
[], 0 | False |
[1, 4, 9], 1 | True |
[1, 4, 9], 7 | False |
*Задание с собеседования Avito (похожую задачу я видел на собесе в Яндесе, но эта задача была лишь частью большой матрешки, остальные задачи и вопросы уже строились над ней)*
Решение задачи 6:
from typing import List
def search(arr: List[int], value: int) -> bool:
def check(m, param):
return arr[m] >= param
def lbinsearch(l, r, check, param):
while l < r:
m = (l + r) // 2
if check(m, param):
r = m
else:
l = m + 1
return l
index = lbinsearch(0, len(arr) - 1, check, value)
if index < len(arr) and arr[index] == value:
return True
else:
return False
search([], 0)
False
search([1, 4, 9], 1)
True
search([1, 4, 9], 7)
False
# дополним тесты случаем когда искомое значение крайнее справа
search([1, 4, 9], 9)
True
Далее задали вопрос о том, как реализовать поиск с помощью правого бинарного поиска.
def search(arr: List[int], value: int) -> bool:
def check(m, param):
return arr[m] <= param
def rbinsearch(l, r, check, param):
while l < r:
m = (l + r + 1) // 2
if check(m, param):
l = m
else:
r = m - 1
return l
index = rbinsearch(0, len(arr) - 1, check, value)
if index < len(arr) and arr[index] == value:
return True
else:
return False
search([], 0)
False
search([1, 4, 9], 1)
True
search([1, 4, 9], 7)
False
search([1, 4, 9], 9)
True
Самые частые ошибки, которые я видел у кандидатов, — это реализация в while l < r
нестрогого неравенства, ошибки с зацикливанием при реализации шагов (m = (l + r) // 2
и m = (l + r + 1) // 2
), а также выполнение условия не в виде отдельной функции def check(m, param)
с разными дополнительными условиями для избежания двойных проверок при строгом сравнении, и вопросы о том, как будет работать алгоритм, если массив имеет определенные особенности.
!!!дополнение к задаче!!! вот некоторые примеры задач-матрёшек которые могут быть заданы после решения этой задачи без встроенных функций:
Ниже решение к одной из возможных таких задач:
def search(arr: List[int], value: int) -> bool:
def check(m, param):
# Проверяем, чтобы индекс не выходил за пределы массива
if m + 1 >= len(arr):
return False
# Возвращаем True, если сумма элемента m и следующего не меньше искомого значения
return arr[m] + arr[m + 1] >= param
def lbinsearch(l, r, check, param):
while l < r:
m = (l + r) // 2
if check(m, param):
r = m
else:
l = m + 1
return l
index = lbinsearch(0, len(arr) - 1, check, value)
if index < len(arr) - 1:
return f'индексы пары:({index}, {index + 1}) пара: ({arr[index]}, {arr[index + 1]})' # Возвращаем пару элементов
else:
return False
search([0, 1, 4, 2, 1, 4, 3, 5], 2)
'индексы пары:(1, 2) пара: (1, 4)'
search([0, 1, 4, 2, 1, 4, 3, 5], 5)
'индексы пары:(4, 5) пара: (1, 4)'
search([0, 1, 4, 2, 1, 4, 3, 5], 8)
'индексы пары:(6, 7) пара: (3, 5)'
search([0, 1, 4, 2, 1, 4, 3, 5], 6)
'индексы пары:(5, 6) пара: (4, 3)'
search([0, 1, 4, 2, 1, 4, 3, 5], 10)
False