Python вопросы с собеседований

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

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

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

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

Пример:

Ввод: 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

8 крутых способов свести функции Python в одну строку

▪Видео

@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

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

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

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

Задача - вернуть 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

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

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

Пример:

Ввод: 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

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

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

Пример:
Ввод: 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

💡Задача: 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

🖥 Задача с leetcode. Max Area of Island

Максимальная площадь острова

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

Условие задачи: Условие задачи:

Дан двумерный массив размера m x n. "1" отвечает за сушу, "0" - за океан. Необходимо опеределить максмимальную площадь острова из островов, расположенных на карте.

Островом считается территория, образованная из "1", расположенных сверху, справа, снизу и слева относительно друг друга.


Пример:

Ввод: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]

Вывод: 6

Ввод: grid = [[0,0,0,0,0,0,0,0]]

Вывод: 0

Решение

Сlass Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
rows,cols = len(grid),len(grid[0])
visited = [[False for j in range(cols)] for i in range(rows)]
def dfs(i,j):
if i<0 or i>= rows or j<0 or j>= cols or grid[i][j]==0 or visited[i][j]:
return 0
visited[i][j] = True
count = 1
count += dfs(i+1,j)
count += dfs(i-1,j)
count += dfs(i,j+1)
count += dfs(i,j-1)
return count

ans = 0
for i in range(rows):
for j in range(cols):
if grid[i][j]==1:
count = dfs(i,j)
ans = max(count,ans)
return ans


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

@python_job_interview

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

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

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

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

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

@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

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

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

Условие задачи: дан массив из целых чисел и число 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

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

Сложность задачи: 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

🧮 Задача: 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

🖥 Задача. Как упорядочить массив по возрастанию питон?

При работе со списками в Python существует два подхода. Первый – это изменить имеющийся список. Говорят, отсортировать по месту:

>>> nums = [5, 3, 4, 1, 2]
>>> nums.sort()
>>> nums
[1, 2, 3, 4, 5]
>>>

Второй способ – создать новый массив с упорядоченными элементами:

>>> nums = [5, 3, 4, 1, 2]
>>> sorted(nums)
[1, 2, 3, 4, 5]
>>> nums # в исходном списке порядок элементов сохранился
[5, 3, 4, 1, 2]
>>>

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

#junior

@python_job_interview

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

▪Книга

@python_job_interview

🖥 Вопросы для собеседования Python Junior

🖥 Github

@python_job_interview

🖥 Практическая задача. Первый вторник месяца

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

Напишите функцию, которая будет принимать год и номер месяца и возвращать строку с датой, когда станут доступны новые игры.

Примечание: месяцы считаем по порядку, 1 = январь.

Примеры:

first_tuesday_of_the_month(1997, 1) ➞
"1997-01-07"

first_tuesday_of_the_month(2021, 2) ➞
"2021-02-02"

first_tuesday_of_the_month(2023, 3) ➞
"2023-03-03"

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

@python_job_interview

🖥 Задача. Как проверить строки на соответствие шаблону python?

Проверить строки на шаблон можно с помощью модуля re

# re.findall() ищет все вхождения в строке
text = "He was carefully disguised but captured quickly by police."
re.findall(r"\w+ly\b", text) # ['carefully', 'quickly']

# re.match() позволяет объединять в групыы
m = re.match(r"(\d+)\.(\d+)", "24.1632")
m.groups() # ('24', '1632')

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

@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?

Для генерации случайных чисел нужно импортировать модуль random, в котором есть несколько подходящих функций:

random() возвращает случайно число (class 'float') в диапазоне от 0.0 до 1.0 (верхняя граница не входит в диапазон).

from random import random

random() # 0.3380967837329142
random() # 0.07200652051529788

randint(start, stop) возвращает случайное число (class 'int') в диапазоне от start до stop (обе границы включены в диапазон).

from random import randint

randint(1, 7) # 4
randint(1, 7) # 2

randrange(start, stop, step) возвращает случайное число (class 'int') из последовательности от start до stop (верхняя граница не входит в диапазон) с шагом = step. Параметры start и step необязательные, по умолчанию start = 0, step = 1.

from random import randrange

randrange(4) # 1
randrange(4) # 3

random.randrange(4, 10) # 6
random.randrange(4, 10) # 9

random.randrange(4, 10, 2) # 4
random.randrange(4, 10, 2) # 8

#junior

@python_job_interview