Python разработчик | Собеседование с задачей из Яндекса. Максим Никулин
ฝัง
- เผยแพร่เมื่อ 6 ก.พ. 2023
- t.me/TH-camPronin
Чат для общения pyhton разработчиков и им сочуствующих. Свободное общение, тестовые и вопросы с собесов и прочее. Заходите, там вам рады.
Поддержать канал: www.tinkoff.ru/rm/pronin.andr...
Обычно денежка идёт на книжки про питончик. Но иногда на светлое и тёмное.
Виш лист
Хорошие книги по Питончику, которые могу рекомендовать (и хочу купить с вашей помощью).
Знакомство с Python | Бейдер Дэн (2023) - выглядит приятно для новичка
Чистый Python. Тонкости программирования для профи | Бейдер Дэн (2022) - хорошо для продолжения
Высоконагруженные приложения. Программирование, масштабирование, поддержка | Клеппман Мартин
Изучаем Python. Двухтомник. Марк Лутц. Очень подробно и структурно (Хочу дождаться 6го издания.. )
• Изучаем Python с Марко...
Читаем и разбираем ее тут
Куплено (огромное спасибо зрителям)
Python. К вершинам мастерства | Рамальо Лучано - 2е издание - сложно для новичка, но интересно
Паттерны разработки на Python: TDD, DDD и событийно-ориентированная архитектура -- хорошо про то, когда какой фреймворк применять
Видимо, дальше появтся еще нескромные желания. Но пока - так
Моя тележка andpronin -- стучите, если что.
Мой канал про обучению python с нуля и до мидла Андрей+=Пронин
/ @pypronin
Я в других сетях
🔗Вконтакте: CaptPronin
🔗Дзен: zen.yandex.ru/id/5fbd33919412...
#python #питон #программирование #Андрей_Пронин #собеседование #ДанилаЕрёмин #МаксимНикулин
t.me/TH-camPronin Чат для общения pyhton разработчиков и им сочуствующих. Свободное общение, тестовые и вопросы с собесов и прочее. Заходите, там вам рады.
Поддержать канал: www.tinkoff.ru/rm/pronin.andr...
Обычно денежка идёт на книжки про питончик. Но иногда на светлое и тёмное.
В == внимательность
Мужик и вправду молодец. А вот собеседующий, если и первоклассный программист, но никак не первоклассный собеседующий. Все интервью чувствовалось напряжение между участниками. Ощущение, что мужика расстреляют в конце, если что-то не сделает. Но в целом, полезное видео. Оно не только про программирование, но и про напряжение во время собеседования к которому всегда нужно быть готовым.
Комент в поддержку Максима! С боевым крещением!😉
Спасибо
Считаю что Максим отлично справился, еще и формулы умудрялся вспоминать ) Я сам недавно на первом лайв кодинге сидел тупил над простой задачей, потом после интервью решил за 30 сек .
Данила такой неприятный :( не знаю почему, такой крутой мужик, а Данила какой-то неприятный
Не рекрутер, мб поэтому)
А что - не перебивал, не третировал...
Целочисленное деление на 16:50 все еще надо, не все хорошо. Нас попросили вернуть пропущенный int, а мы отдаем float. Надо либо в инт откастить, либо действительно // использовать
Мужик очень бодро начал, вспомнил математическую формулу, понял как применить (пусть и некая мешанина в голове была). Потом понял как использовать предыдущее решение с новой задачей и попытался написать код. В то же время интервьюер почему-то сказал, что править(хотя, скорее, было бы правильнее добавить аргумент) старую функцию не имеет смысла, а потом банально но, очевидно, неправильно написанный код давал какие-то советы, когда человек уже допустил ошибки.
Интервьюер, может, и опытный разработчик, но сидеть и столько времени смотреть в цикл где будет IndexError и просто банально даже не задать наводящий вопрос... Сорри, но мне кажется, ему было просто пофиг на собеседуемого. Второй код написан просто неправильно от слова совсем (даже если не учитывать IndexError), а ведь мужик, используя первоначальную идею (найти первое число, а потом от недостающей суммы отнять его и получить второе), мог добиться правильного результата. Да, интервьюер мог потом попросить найти N пропущенных, и вернулись бы к сортировке, использованию enumerate, но в целом, он бы решил второе задание.
жееесть, я сидел и думал - как бы я это сделал. В голову пришло применить enumerate, потом поставил паузу и полез в комментарии - а тут ты! Неужели я начинаю немножко понимать?
@@donnydarko5345 Ну там с enumerate тоже есть траблы... Там не тривиально, но примерно так (только тут табуляция в 2 пробела):
def find_n_missed_numbers(arr, n_missed):
arr = sorted(arr)
result, tmp_number = [], 1
for idx, number in enumerate(arr):
delta = arr[idx] - tmp_number
if delta:
for i in range(delta, 0, -1):
result.append(arr[idx] - i)
tmp_number += delta + 1
result += [arr[-1] + i for i in range(1, n_missed - len(result) + 1)]
return result
На разных случаях потестил (что если числа пропущены подряд, что если числа пропущены только в начале, что если числа пропущены только в конце и разные комбинации), вроде правильно.
P.S. Тут даже enumerate не нужен по сути, я просто сел, думая написать код используя его, но по сути написал код где idx не используется xDD Ладно, не надо ранним утром код писать и позориться, править код не буду что б видели что я тоже облажался =)
Если испытуемому простительно из-за нехватки опыта, то интервьюер, принявший код с несколькими ошибками, выглядел невовлеченным
А задача реально интересная оказалась.
Я свел ее решение к 3 случаям: 1) 2 числа за пределами (1, max) - тут сразу return, 2) 1 число за пределами - тут все сведется к вычислению числа за пределами + к поиску 1 пропущенного числа в массиве(т.е. к предыдущей задаче), 3) оба числа в массиве. Вот тут я решал через произведение последовательностей(правильной и текущей) и смотрел на остатки от деления/результат умножения на определенное число.
Чисто технически, сложность тут будет О(N) по времени и О(1) по памяти.
Ну и сортировку подсчетом никто не отменял, но это + О(N) памяти.
А по поводу собеса: в целом, весьма и весьма не дурно. Да, по факту, код не рабочий(там IndexError будет), задачу он решил не за О(n), было много ошибок, в том числе выход за границы массива, а корнеркейсы и тесты только после подсказок начал искать, но: у него сразу чувствуется алгоритмическая подготовка и то, что мозг работает и пытается обдумывать свои действия.
Не уверен, что это уровень Яндекса(если такой уровень есть вообще), но это был достойный собес, как по мне.
P.S. Нужно больше алгоритмических собесов.
будет)
а разве нельзя посмотреть пересечение двух списков? просто одной командой. список 1 и список 2 и различия между ними?
result = list(set(lst1) ^ set(lst2))
или
result = list(set(lst1) - set(lst2))
@@stepfpv а память?
@@AndyPronin а память я пока не знаю ))) я три дня смотрю ролики про питон )))
@@AndyPronin Зато сложность O(n)
source_set = set(arr)
pattern_set = set(i for i in range(max(arr) + 1))
result_set = pattern_set - source_set
Сложность, грубо - O(5n) ... ну, памяти раза в 2 больше займет ;-)
Лайк, лимонад «Колокольчик» и сыр «Дружба».
Совершенно нерабочий код. Во-первых, выход за границы массива. Во-вторых, если эту ошибку устранить, то все равно получим неверные значения 1, 2 вместо 2, 4.
Первая задача в одну строку
def find(cisla):
return print([i for i in range(1,max(cisla)+1) if i not in cisla])
Временная сложность этой строчки O(n2). А если пропущено последнее число, то вообще работать не будет. Возвращать print - это, пожалуй, тоже лишнее).
Тогда уж так:
def find(cisla):
return [i for i in range(1, len(cisla)+2) if i not in set(cisla)]
Время O(n), память O(n)
@@mikhail286 спасибо, буду знать
@@mikhail286 Это не чистый O(n), потому что поиск в множестве, п офакту произойдет n раз, и хоть он и реализован лучше простого прохода, он все равно зависит от размера множества.
def find(cisla):
cisla = set(cisla)
return [i for i in range(1, len(cisla)+2) if i not in cisla]
return int((((len(list) + 1) * ((len(list) + 1) + 1)) / 2) - sum(list)) Если решать как в видео
Не уверен, что кто-то предложил в комментариях это решение, поэтому предложу его я. Задача, найти два числа, отсутствующие в перемешанном массиве натуральных чисел в количестве n.
1) Сортируем массив (сложность O(nLog n))
2) С помощью алгоритма бинарного поиска ищем первое число, на каждой итерации проверяем if arr[i] - i == 1 and arr[i-1] == i - 1 - тогда arr[i] и будет искомым числом. Здесь следует добавить условие для избежания выхода за пределы массива или чуть получше продумать этот пункт. (сложность O(log n))
3) Теперь, когда нам известно первое число, вычисляем сумму чисел от 1 до n + 2 и вычитаем из нее первое число.
Судя по всему, это решение также не самое эффективное, в интернете можно найти решение с помощью XOR за О(n).
Во-первых, раз нашли первое число бинарным поиском, второе число тоже ничего не мешает найти так же - зачем скатываться до O(n) при поиске второго?
Во-вторых, общая сложность алгоритма считается по наихудшему его шагу, поэтому, если мы имеем O(nlog(n)) после сортировки, то уже без разницы, что мы используем дальше O(log(n)) или O(n) - это уже ничего не изменит.
Целочисленное деление нужно, чтобы ответ был int. Если "/" то ответ будет float
Верно - тесты на leetcode float ответ вместо int вообще не примут - интервьюер тут опять куда-то не туда увел. С другой стороны испытуемый должен был отстоять свое решение - видится, что здесь оба поднамутили
@@mikhail286 Интервьюер должен был понимать что делает формула, а не заучивать ее наизусть. Он явно формулу зазубрил, а когда его спросили зачем целочисленное , начал троить. вместо того что бы объяснить зачем
А где можно почитать про формулы в первой задачке? Воспроизвел пример, в итоге функция всего лишь находит элемент n+1, больший n на 1. А если не последний элемент удалится, тогда это решение не подходит.
Попробуй сначала с помощью sum решить. Потом принцип Гаусса погугли. Очень прикольная история, как он придумал суммировать числа в последовательности
А можно мидловский собес по алго секции?😇 Хотя может и там будут задачки на применение хэшмап или xor🤔
Можно и мидловый)
прочитал, как алко секции😁
2я задача в оптимальном решении o(n) рантайма + o(1)- это гроб уровня hard, который не алгоритмическая, а математическая задача. Данила решил просто потешить свое чсв.
А если два числа подрят потеряли?
def find_missing_numbers(nums, n):
all_numbers = set(range(1, n + 1))
existing_numbers = set(nums)
missing_numbers = all_numbers - existing_numbers
return list(missing_numbers)
nums = [2, 3, 7, 8, 10, 12, 18, 20, 28,]
n = max(nums)
missing = find_missing_numbers(nums, n)
print("Недостающие числа:", missing)
Вот пример кода который короче и может считать пропущенные числа, я только начал программировать, и знаю что можно и лучше сделать этот код, не судите строго.
Я новичек, подскажите на сколько гуд мое решение? Суть такая что в сортированном списке каждое следующее число больше предыдущего на 1,значит если число больше предыдущего больше чем на 1 то между ними как раз и прячется потерянное число .
def found_num(chisla):
j = 0
for i in sorted(chisla):
if i > j + 1:
return (i-1)
j = i
какие chisla? это питон или кумир?
Ну у меня что-то такое получилось:
def find_miss_int(array: List[int]):
true_len = len(array)
final_len = true_len + 1
s = final_len * (final_len + 1) // 2
return s - sum(array)
def find_miss_two_int(array: List[int]):
first_miss = 0
sorted_array = sorted(array)
for i in range(len(sorted_array)):
number = i + 1
number_in_array = sorted_array[i]
if number_in_array != number:
first_miss = number
array.append(first_miss)
break
second_miss = find_miss_int(array)
return first_miss, second_miss
Нашел самое сложное (и по времени, и по памяти) решение этой задачи в истории:
def find_missing_numbers(arr):
lenarr = len(arr) + 2
realarr = []
for i in range(1, lenarr + 1):
realarr.append(i)
return sorted(list(set(realarr).difference(set(arr))))
Здравствуйте, Андрей. Подскажите, можно ли попасть к вам на интервью. Если да, то куда написать?
Прямо сейчас попасть можно только через акселерацию ЯндексПрактикума для студентов (Максим, например, так попал).
. Если буду искать людей со стороны -- то тут t.me/TH-camPronin Недавно отбирал в пет-проект людей. Собесы с ними пока под замком, но открою
Добрый и злой полицейский-рекрутер 😂
Они оба добрые
@@maxnmx4544 да, Андрей забавно сыграл просто, когда разрядил обстановку.
def finder(x):
max_n = max(x) + 1
res = [i for i in range(1, max_n) if i not in x]
if not res:
return [max_n, max_n + 1]
elif len(res) >= 2:
return res
return res + [max_n]
Нада вернуть 2 числа, + тот кто дал задание не указал рвзмер массива, может перкбор O(n) не сработать
Усложняешь.
@@cristianglodeanu2329 Хз, я дальше 11 минуты не смотрел, он там сказал, что надо найти пропущенное число, я нашел
@@cristianglodeanu2329 Не, это не работает
Это О(n*n)
def lost_number(sequence: list[int]) -> int:
sortseq = [None]*(len(sequence)+1)
for i in sequence:
sortseq[i-1] = i
res = [i for i, val in enumerate(sortseq, 1) if val is None]
return res[0]
Поправьте меня, если я неправ, но похоже в собесе разговор о Натуральных числах, а не о Целых?
Любое натуральное число является целым, так что противоречий нет
Не расмотрели если одно или оба числа в начале: 1 и 2
Я новичок, не особо понимаю, зачем усложнять, какие-то уровни. Если создать список со всеми числами и их сравнить, такое решение пройдёт, если нет почему?
Тут проверяют знания алгоритмов, а не то как ты будешь писать код который будут поддерживать джуны после курсов.
Если заморочится и порешать задачки алгоритмические, хотя бы базовые, набить руку, то можно сильно увеличить производительность своего приложения.
Но как показывает практика, когда в код залетают алгоритмы, а у того кто его потом сапортит нет базы, хотя бы математической, то часто летит нытье уровня - что за идиот это писал, ничего не понятно. вот я бы сейчас тут дернул filter().sort().reduce() и все станет супер просто и понятно. а по факту все было просто и понятно, но незнайка сделал по свойму и положил фпс счетчик своего приложения
Никогда бы не взял типа в красном на работу по софт скилам
Тут даже если не 1 и не 2 числа а k пропущено - всё равно линия по времени. Правда если k не фиксировано то это ещё и по памати линия, но комон, мы всё равно массив храним, нам не пофиг?
Заводим массив a длинны n, изначально все числа нули
for num in arr:
a[num - 1] = 1
ans = []
for i in range(n):
if a[i] == 0:
ans.append(i + 1)
Типа a[i] 1 если число встретилось и 0 иначе. Ищем все нули и всё. Всё линия.
Почему нельзя было просто создать два множества, первой из того массива, который есть, второе из всех чисел, которые должны быть, а потом из одного множества вычесть другое
А ограничение по памяти?
@@AndyPronin ах вон оно как, понял
лайк от СЕООНЛИ
Как насчет такого решения второй задачи? Я так понимаю, оно O(n). Не ошибся ли где-то я?
__________________________________
def two_are_missed(arr):
ln = len(arr) + 2
diff = ln*(ln+1)/2 - sum(arr)
for i in range(1, len(arr) + 1):
if i not in arr:
return i, diff - i
return i + 1, i + 2
print(two_are_missed([1,2,4])) # ---> (3, 5)
Или даже так, в худшем случае придется проитерироваться n/2 раз. В предыдущем варианте было n раз.
___________________
def two_are_missed(arr):
ln = len(arr) + 2
diff = ln*(ln+1)/2 - sum(arr)
for i in range(1, round(diff/2)+1):
if i not in arr:
return i, diff-i
Каждый раз когда ты пишешь value {in | not in} array помни, что ты запускаешь цикл-поиск по всему массиву, который, собственно O(n). Поэтому, если ты пользуешься данной конструкцией внутри другого O(n) цикла, то твой алгоритм превращается в O(n^2). Но в целом, да, код правильный, обидно что собеседуемый хотел точно такую же идею использовать, но интервьюер почему-то сказал что это бессмысленно .......
Вторая задачкас временным ограничением классная, спасибо!
def missing_two_nums(nums: list) -> (int, int):
"""
O(n) time complexity.
O(1) memory complexity.
"""
all_gen = range(1, len(nums) + 3)
sum_two = sum(all_gen) - sum(nums)
xsum_two = reduce(lambda x, y: x ^ y, all_gen) ^ reduce(lambda x, y: x ^ y, nums)
for num in all_gen:
if num ^ xsum_two == sum_two - num:
return num, sum_two - num
Может dig2 = i + 2 ??
def find_miss_number(arr, n):
expected_sum = sum(range(1, n+1))
actual_sum = sum(arr)
return expected_sum - actual_sum
Мои решения для одного и для двух (и более) чисел:
def lost_number(sequence: list[int]) -> int:
mx = 0
res = set()
for s in sequence:
mx = s if s > mx else mx
res.add(s)
res = set(range(1, mx + 1)) - res
return list(res)[0] if len(res) == 1 else None
def lost_number2(sequence: list[int]) -> int:
res = []
diff = 1
for key, val in enumerate(sorted(sequence)):
if val - key != diff:
res.append(val-1)
diff = val - key
return res
А теперь вопросы к Яндексу и тем кто любит такие алгоритмические вопросы 1) где в жизни, а точнее в приложении может понадобиться знание суммы арифметической прогрессии 2) как часто в работе разработчика он будет использовать это знание с нуля, без библиотеки.
Пригодиться для прокачки твоих нейронных связей. Для прокачки твоих скилов. И, если ты хочешь в FANG или MANG или как там нашу называет, то придется принять правила игры. Это объективная реальность. или ты принимаешь правила игры, или создаешь свою реальность
Я предполагаю, что так в принципе оценивается возможность человека мыслить и мыслить быстро. Потому что какой-то инструмент рано или поздно выучит любой, но будет ли этот человек достаточно быстро ориентироваться в чем-то новом, выходящим за рамки его знаний трудный вопрос. Который возможно так и оценивают+сразу проверяют знание языка
Судя по последним действиям Яндекс, то им отрастить нужно не только нейронные связи. А еще у этих умников уходит код в общий доступ, ну прям супер гении, зато человека мучают со знанием суммы арифметической прогрессии. У них код из под носа увели, а они умничают.
Нут так вроде и не было задано решать через формулу Гаусса. Я бы, например, не догадался и решал бы в лоб "вычеркиваниями". А тут человек заработал плюс.
Без Данилы пожалуйста в след раз
почему?
@@AndyPronin токсик
If I+1dic[i] then miss1=I+1 break if I+1+miss1dic[i+miss1] then miss2=miss1+I+1 break. Все. В один проход.
Оцените мое решение первой задачи
def find(list: list) -> int:
c = 0
for i in range(1, len(list) + 1):
for num in list:
if i == num:
c = 1
break
if c == 0:
return i
return len(list) + 1
n в квадрате
А если просто массив в сет перегнать и по нему циклом пройтись , сложность О(n)
А по памяти?
@@AndyPronin понял
Вот смотришь, думаешь, ну как так можно тупить. А когда там оказываешься, тупишь ещё хлеще))
Есть какие-нибудь таблетки от этого?)
Нет.. это я я как пример
Да. Постигается упражнениями. Первый раз адреналин и не можешь вспомнить своё имя. Потом проще. Для этого такие собесы и делаем. Танк. Граната. Новобранец.
а если хочешь как лучше. А в итоге тупишь как перед как перед экзаменом. Я честно все учил, но сейчас не помню? Хотя бы есть такие примеры что отлично. Хорошие видео чтобы показать и порешать те вопросы которые возникают. Спасибо.
множества не подходят?
Нет
я я так ее решил .
def miss(arr):
return sum(range(1,len(arr)+2))-sum(arr)
делюсь своим решением
arr= [1, 2, 5,6,7, ]
z2=[]
def find(arr):
n=10
z=1
for i in arr:
while i!=z:
z2.append(z)
z+=1
z += 1
while n > z:
z2.append(z)
z+=1
find(arr)
print(z2)
Тяжело в учении, легко в бою, волнение берет свое .. , задача то лёгкая, на 7 8 киу
Сам не ожидал
множества отдыхают…..
А почему вариант с for - это квадратичная сложность? Вложенного же подцикла нет😮
Поиск элемента в массиве == линейное время. Вложенный цикл есть по сути, если понимать, как работает in в вашей структуре данных
очередная антиреклама яндекс практикуму
Не вижу антирекламы.
Алгоритмы нужно знать, или хотя бы понимать как к ним логически прийти.
Вряд ли какой-либо общий курс может впихнуть в голову кучу алгоритмов и логическое мышление. Это должно приходить в процессе самообразования
@@archimg1221 скорее, нарешенность нужна
@@archimg1221 Чувак, ты хотя бы проверял второй код? А стоило бы...
@@archimg1221 Только у меня претензия была не к алгоритмам, а то что он с самого начала высчитывал сумму значений исходного массива, а использует при этом длину массива, которая названа real_arr, что вообще неочевидно, плюс код пришлось бы переписывать если бы массив начинался не с единицы (в отсортированном виде)
Как я понял он имел ввиду что-то типа такого: раз в ряду 1,2,3,4 1-ый + последний = 2-ой + предпоследний, то чтобы узнать сумму элементов можно поделить кол-во элементов на 2 и умножить на такое значение, т.е. на сумму первого и последнего, последний элемент как раз и будет равен real_arr, то есть длине массива, получается:(first+last)*(length/2) но учитывая что first = 1 a last = length Он записал: (1+length)*length/2 что вооооообще непоняяяятно
@@archimg1221 И в четности поэтому запуатался, потому что может быть 1,2,3,4,5 только вот он оперирует длиной массива и строка у него a * (a + 1) которая не может быть нечетной по причине того что если a - четное, то (a + 1) - нечетное, и наоборот, то есть всегда умножаем четное на нечетное.. в таком случае всегда четное будет
def find_num(arr):
s = 0
for i in range(1, len(arr) + 1):
s += i - arr[i - 1]
s += i + 1
return s