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

Условие задачи: дан массив, сдвинутый относительно опорного элемента, который неизвестен ( массив после сдвига относительно опорного элемента имеет следующий вид: [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

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

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

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

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

Задача - выдать подсказку в формате "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