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

Условие: Даны 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

💡Задача: Быки и коровы

Условие задачи: разыгрывается партия, в которой мы просим оппонента угадать число. После первой попытки мы мы говорим другу количество отданных цифр и неотгаданных.

Быки - правильные цифры, находящиеся на нужных позициях.

Коровы - правильные числа, но находящиеся на соответствующих позициях.

Задача - выдать подсказку в формате "xAyB", где x - количество быков, y - количество коров.

Пример:

Ввод: secret = "1807", guess = "7810"
Вывод: "1A3B"

Объяснение:

Ввод: secret = "1123", guess = "0111"
Вывод: "1A1B"

Решение:

class Solution:
def getHint(self, se: str, gu: str) -> str:
dcse=defaultdict(lambda:0)
dcgu=defaultdict(lambda:0)
a=0
b=0
for i in range(len(se)):
if(se[i]==gu[i]):
a+=1
else:
dcse[se[i]]+=1
dcgu[gu[i]]+=1
for x in dcse:
if(dcgu[x]>=dcse[x]):
b+=dcse[x]
else:
b+=dcgu[x]
return(str(a)+"A"+str(b)+"B")

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

@python_job_interview

Задача Junior. Собеседование.

Напишите функцию для перемножения всех элементов в списке.

Например,
print(multiply((8, 2, 3, -1, 7))) #-336

Ваши ответы пишите в комментариях, а свой вариант мы опубликуем позже.

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

@python_job_interview

💡Задача: Doodle Jump

Условие: Дан целочисленный массив nums. Изначально вы находитесь в первом элементе массива, и каждый элемент массива представляет максимальную длину прыжка в этой позиции.

Верните true, если вы можете добраться до последнего индекса, или false в противном случае.

Пример:
Ввод: nums = [1,3,1,1,4]
Вывод: true
Объяснение: Переходим на 1 шаг от индекса 0 к 1, затем на 3 шага к последнему индексу.

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

Решение:

def canJump(self, nums: List[int]) -> bool:
j=0
k=nums[j]
while(k and j<len(nums)-1):
j+=1
# if j>=len(nums)-1:
# return True
k-=1
if nums[j]>k:
k=nums[j]
if j>=len(nums)-1:
return True
else:
return False

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

@python_job_interview

💡Задача: "Матрица спирали"

Условие задачи: дан двумерный массив, надо вернуть все его элементы в "спиральном" порядке по часовой стрелке.

Пример:
Ввод: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Вывод: [1,2,3,6,9,8,7,4,5]

Ввод: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Вывод: [1,2,3,4,8,12,11,10,9,5,6,7]

📌Решение

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

@python_job_interview

💡Задача: Сортировочный список

Условие: дан односвязный список, необходимо отсортировать узлы списка по значению в порядке возрастания

Пример:

Ввод: head = [4,2,1,3]
Вывод: [1,2,3,4]

Ввод: head = [-1,5,3,4,0]
Вывод: [-1,0,3,4,5]

Можете ли вы отсортировать связанный список за O (n logn) времени и O(1) памяти (т.е. постоянного пространства)?

Решение:

class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
arr, itr = [], head

while itr:
arr.append(itr.val)
itr = itr.next
arr.sort() # sort it
itr, i = head, 0
while itr:

itr.val = arr[i]
i += 1
itr = itr.next
return head

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

@python_job_interview

📌 Проверка: является ли строка палиндромом?

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

Условие: палиндромом является фраза, которая после перевода в нижний регистр всех символов, а также удаления всех знаков препинания, читается одинаково как слева направо, так и справа налево.

Задача - вернуть true, если строка палиндром, false - в противном случае.

Пример:

Ввод: s = "A man, a plan, a canal: Panama"
Вывод: true
Объяснение: "amanaplanacanalpanama" является палиндромом.

Ввод: s = "race a car"
Вывод: false
Объяснение: "raceacar" не является палиндромом.

Ввод: s = " "
Вывод: true
Объяснение: s - пустая строка "" после удаления всех знаков препинания и пробелов.
Так как пустая строка читается одинаково в обоих направлениях, то она является палиндромом.

Решение с использвоанием регулярного выражения

import re

class Solution(object):
def isPalindrome(self, s):
new_s = re.sub(r"[^a-zA-Z0-9\\s+]", "", s).lower()
return new_s == new_s[::-1]

re.sub(pattern, replaceString): все совпадающие вхождения указанного шаблона заменяются, указанной строкой (здесь пустая строка, так как мы хотим удалить).

Давайте объясним шаблон:

[^ ]: Сопоставляет один символ, не присутствующий в списке ниже.
a-zA-Z: Сопоставляет все буквы верхнего и нижнего регистров.
0-9: совпадает с цифрами.
\s+: Сопоставляет строку символов, не являющихся пробелами.
Добавляем \, первый из которых "просит" Python не интерпретировать последующие.
Наконец, шаблон совпадает со всеми неалфавитными символами, а re.sub() позволяет нам удалить все встречающиеся символы из строки.

new_s[::-1] используется для переворачивания строки.

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

@python_job_interview

🔢 Задача на теорию чисел

Для того чтобы проверить, как её ученики умеют считать, Мария Ивановна каждый год задаёт им на дом одну и ту же задачу — для заданного натурального A найти минимальное натуральное N такое, что N в степени N (N, умноженное на себя N раз) делится на A.

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

Решение:
def decomp(n):
ans = []
d = 2
while d * d <= n:
if n % d == 0:
ans.append(d)
n //= d
else:
d += 1
if n > 1:
ans.append(n)
return ans



x = int(input())
if x == 1:
print(1)
else:
a = list(set(decomp(x)))
b = decomp(x)

y = 1
for i in range(len(a)):
y *= a[i]
k = 1
n = k*y

if a[0] != x:
for i in range(40):
t = (i+1)*y
if pow(t, t, x) == 0:
print((i+1) * y)
break
else:
print(a[0])

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

@python_job_interview

Найти максимальный подмассив

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

Условие задачи: дан целочисленный массив, необходимо найти в нем такой подмассив, сумма элементов в котором будет максимальной.

Подмассивом называется последовательная часть исходного массива.

Пример:

Ввод: nums = [-2,1,-3,4,-1,2,1,-5,4]
Вывод: 6

Объяснение: 4,-1,2,1] имеет наибольшую сумму 6.

Ввод: nums = [5,4,-1,7,8]
Вывод: 23

Решение:

class Solution:
def maxSubArray(self, nums: List[int]) -> int:
Max = nums[0]
Sum = 0
for num in nums:
Sum += num
Max = max(Max, Sum)
if Sum<0:
Sum = 0
return Max

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

@python_job_interview

📌 Задача палиндром наибольшей длины, полученный с помощью соединений из слов, состоящих из двух букв.

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

Условие задачи: дан массив строк, каждый элемент которого состоит из двух букв английского алфавита в нижнем регистре.

Необходимо создать палиндром наибольшей длины путем выбора некоторых элементов из массива строк и компаниовки их в любом порядке. Каждый элемент массива можно использовать не более одного раза.

В ответе надо вернуть длину такого палидрома.

Палиндром - строка, которая одинаково читаются слева направо и справа налево.

Пример:

Ввод: words = ["lc","cl","gg"]
Вывод: 6
Объяснение: lc" + "gg" + "cl" = "lcggcl" или же "clgglc", но оба имеют максимальную длину 6.

Ввод: words = ["ab","ty","yt","lc","cl","ab"]
Вывод: 8
Объяснение: "ty" + "lc" + "cl" + "yt" = "tylcclyt" или "lcyttycl"

Ввод: words = ["cc","ll","xx"]
Вывод: 2

Решение

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

@python_job_interview