Тестовое задание на позицию код-ревьюера Яндекс.Практикум

Дано
▪В файле main.py находится пример реального кода, который сдал студент к заданию.
Текст задания находится по ссылке
▪Общие требования к коду, с которыми ознакамливаются студенты, находятся по ссылке

Что нужно сделать
▪Нужно провести ревью этого кода. Найти в нем ошибки, неточности, неэффективные места, или дать какие-то необязательные рекомендации по улучшению.
▪Можно сделать форк репозитория или gist (не делайте Pull Request в этот репозиторий) и расставить комментарии над проблемными строками в main.py.
▪Учтите, что вы "ревьюите" студента, то есть не надо просто исправлять ошибки, нужно оставлять комментарии и рекомендации.

Как сдавать
▪В форме прикрепите ссылку на ваш репозиторий или на gist с комментариями.

▪Github

@python_job_interview

Задача с leetcode. Контейнер с наибольшим количеством воды

Дан целочисленный массив height длины n. Нарисовано n вертикальных линий, две конечные точки i-й линии равны (i, 0) и (i, height[i]). Найдите две линии, которые вместе с осью абсцисс образуют контейнер, содержащий наибольшее количество воды.

Верните максимальное количество воды, которое может храниться в контейнере. Обратите внимание, что вы не можете наклонять контейнер.

Пример 1 (картинка):
Ввод: height = [1,8,6,2,5,4,8,3,7]
Вывод: 49
Объяснение: Вышеуказанные вертикальные линии представлены массивом [1,8,6,2,5,4,8,3,7]. В этом случае максимальная площадь воды (синяя секция), которую может содержать контейнер, составляет 49.

Пример 2:
Ввод: height = [1,1]
Вывод: 1

Решение:

def maxWater(height):
first = 0
end = len(height) -1
ans = 0

while first < end: //condition applied
ans = max(ans, min(height[first], height[end]) * (first - end))
if height[first] < height[end]:
first += 1
else:
end -= 1
return ans

# Working Part
height=[5,1,3,4,6]
print(maxWater(height))

Пишите свое решение в комментариях👇

@python_job_interview

📌 Задача. Поиск в повернутом отсортированном массиве

Условие задачи: дан массив, сдвинутый относительно опорного элемента, который неизвестен ( массив после сдвига относительно опорного элемента имеет следующий вид: [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]])

Массив [0,1,2,4,5,6,7], имея опорный элемент 3, будет выглядеть следующим образом: [4,5,6,7,0,1,2].

Необходимо осуществить поиск целевого элемента в сдвинутом массиве, определив его индекс, или же вывести -1 при его отсутствии.

Решение должно быть за O(log n) по времени.

Пример:

Ввод: nums = [4,5,6,7,0,1,2], target = 0

Вывод: 4

Ввод: nums = [4,5,6,7,0,1,2], target = 3

Вывод: -1

Решение:

class Solution:
def search(self, nums: List[int], target: int) -> int:
if target in nums :
return nums.index(target)
else :
return -1

Пишите свое мнение в комментариях👇

@python_job_interview

Задача. Слияние двух бинарных деревьев

Сложность: Лёгкая

Условие задачи: Даны два бинарных дерева, необходимо осуществить их наложение друг на друга и вывод результатов в новом дереве.

Примечание: Наложение представляет из себя суммирование соответствующих значений из узлов двух деревьев.

Пример:

Ввод: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Вывод:[3,4,5,5,4,null,7]

Ввод: root1 = [1], root2 = [1,2]
Вывод: [2,2]

Решение

Напишем простую рекурсию с функцией constructTree.
▪Если один из двух узлов не определен, мы можем просто вернуть другой узел.
▪Если 2 узла не определены, мы можем завершить рекурсию.

class Solution(object):
def mergeTrees(self, root1, root2):

def constructTree(root1, root2):
if not root1 and not root2:
return None
if not root2:
return root1
if not root1:
return root2
head = TreeNode(root1.val + root2.val)
head.left = constructTree(root1.left, root2.left)
head.right = constructTree(root1.right, root2.right)

return head

return constructTree(root1, root2)

Пишите свое мнение в комментариях👇

@python_job_interview

🔑 Задача Ключи и комнаты

Условие: Даны n комнат проиндексированных с 0, все они закрыты кроме комнаты с номером 0. Необходимо посетить все комнаты, однако этого нельзя сдеать не имея ключа от соответствующей закрытой двери.

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

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

Сложность: Средняя

Пример:

Ввод: rooms = [[1],[2],[3],[]]
Вывод: true
Объяснение: из 0 комнаты можно попасть в 1, из 1 во 2, из 2 в 3.

Ввод: rooms = [[1,3],[3,0,1],[2],[0]]
Вывод: false

Пишите свое решение в комментариях👇

📌 Решение

@python_job_interview

📚 Книга с разбором популярных вопросов и ответов при собеседовании на позицию Python-developera.

▪Книга

@python_job_interview

🧮 Задача: Abelian sandpiles

Смоделируйте гравитацию, действующую на кучу песка.

Напишите функцию apply_gravity, которая, учитывая двумерный массив numpy, представляющий песок, будет "применять гравитацию" к нему (и ничего не вернет):

1. Каждый элемент массива представляет собой целое число, отражающее высоту кучи песка.

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

Решение:

>>> import numpy as np
>>> sandpile = np.zeros((5, 5), dtype=np.uint32)
>>> sandpile[2, 2] = 16
>>> apply_gravity(sandpile)
>>> print(sandpile)
[[0 0 1 0 0]
[0 2 1 2 0]
[1 1 0 1 1]
[0 2 1 2 0]
[0 0 1 0 0]]

Ресурсы

Бонус!

Используйте matplotlib для отображения результата в виде изображения:

apply_gravity(sandpile)
plt.imshow(sandpile)
plt.show()

Чтобы продемонстрировать результаты, вычислите кучу песка размером 2 ** 24 песчинки

Ваше мнение пишите в комментариях 👇

@python_job_interview

🎯Задача. Уникальные тропы

Сложность задачи: Medium.

Условие задачи: дано поле размером m x n. Изначально робот находится в левом верхнем углу. Необходимо посчитать сколькими возможными уникальными путями робот может добраться в правый нижний угол.

Робот может двигаться лишь вправо и вниз.

Пример:

Ввод: m = 3, n = 7
Вывод: 28.

Решение:

class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# Purpose: find # ways to go from top-left to bottom-right
# Formula: res[i][j] += res[all i][j - 1]

# build
dp = [0] * n
dp[0] = 1

# find
for i in range(m):
for j in range(n):
if j >= 1:
dp[j] += dp[j - 1]

# return
return dp[-1]

Ваше мнение пишите в комментариях 👇

@python_job_interview

📌 Задача. Наличие дубликатов

Сложность: Лёгкая

Условие задачи: дан массив из целых чисел и число k. Необходимо вернуть true, если существуют два уникальных индекса, которые удовлетворяют условиям:

- nums[i] == nums[j];
- abs(i - j) <= k.

Пример:

Ввод: nums = [1,2,3,1], k = 3
Вывод: true

Ввод: nums = [1,0,1,1], k = 1
Вывод: true

Решение:

def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
dic = {}
for i in range(len(nums)):
if nums[i] in dic and i - dic[nums[i]] <= k:
return True
dic[nums[i]] = i
return False


Пишите свое решение в комментариях👇

@python_job_interview