t.me/RUclipsPronin Чат для общения pyhton разработчиков и им сочуствующих. Свободное общение, тестовые и вопросы с собесов и прочее. Заходите, там вам рады. Поддержать канал: www.tinkoff.ru/rm/pronin.andr... Обычно денежка идёт на книжки про питончик. Но иногда на светлое и тёмное.
Мужик и вправду молодец. А вот собеседующий, если и первоклассный программист, но никак не первоклассный собеседующий. Все интервью чувствовалось напряжение между участниками. Ощущение, что мужика расстреляют в конце, если что-то не сделает. Но в целом, полезное видео. Оно не только про программирование, но и про напряжение во время собеседования к которому всегда нужно быть готовым.
Целочисленное деление на 16:50 все еще надо, не все хорошо. Нас попросили вернуть пропущенный int, а мы отдаем float. Надо либо в инт откастить, либо действительно // использовать
Считаю что Максим отлично справился, еще и формулы умудрялся вспоминать ) Я сам недавно на первом лайв кодинге сидел тупил над простой задачей, потом после интервью решил за 30 сек .
А задача реально интересная оказалась. Я свел ее решение к 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))
@@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 больше займет ;-)
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) Вот пример кода который короче и может считать пропущенные числа, я только начал программировать, и знаю что можно и лучше сделать этот код, не судите строго.
Мужик очень бодро начал, вспомнил математическую формулу, понял как применить (пусть и некая мешанина в голове была). Потом понял как использовать предыдущее решение с новой задачей и попытался написать код. В то же время интервьюер почему-то сказал, что править(хотя, скорее, было бы правильнее добавить аргумент) старую функцию не имеет смысла, а потом банально но, очевидно, неправильно написанный код давал какие-то советы, когда человек уже допустил ошибки. Интервьюер, может, и опытный разработчик, но сидеть и столько времени смотреть в цикл где будет 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 Ладно, не надо ранним утром код писать и позориться, править код не буду что б видели что я тоже облажался =)
немного не согласен с замечанием в сторону собеседующего. В яндексе на собесах решение задач выглядит так: 1. дают задачу 2. обсуждаете условие, задаете вопросы по нему 3. дальше обсуждается решение, нужно словесно описать идею оптимального алгоритма, после чего предлагается написать код 4. код пишется самостоятельно, собеседующий не подсказывает, естественно можно задать уточняющие вопросы, но скорее по идее, а не по коду 5. после того как код написан, очень важно посидеть и подебажить в голове, посмотреть на краевые случаи, найти какие-то ошибки 6. потом надо сказать волшебное слово типа "готов сдавать" и собеседующий либо говорит, что все верно, либо, что есть ошибка (без указания где) 7. если ошибку найти не удается, то только тогда интервьюер обращает внимание на конкретные места
@@stepan_chousНу это как бы и не собеседование в Яндекс, а просто задача с Яндекса. Ориентируюсь на название видео, потому что пересматривать его не хочется, так что если в видео говорили что полностью промоделируют собес с Яндекса, то неправ. 4. "Код пишется самостоятельно" и, судя по тому что я написал в своем комменте, то собеседующий увел от собственных размышлений собеседуемого. Так что этот пункт уже не соблюден. Опять же, опираясь только на свои слова, пересматривать не хочу, если я не врал в комменте (а такой привычки за собой не имею), то ... Просто факт - пункт не соблюден. 5. "Подебажить в голове". А чем дебаггер не подходит? Если в Яндексе не разрешают дебажить, пусть даже на собесах только, то у меня большие вопросы к таким собесам. Может мне ещё в нотпаде код писать? И лсп вообще выключить? В общем, их контора, пускай делают как хотят. Просто выглядит это как хреновое собеседование, вот и все, имхо.
Совершенно нерабочий код. Во-первых, выход за границы массива. Во-вторых, если эту ошибку устранить, то все равно получим неверные значения 1, 2 вместо 2, 4.
Собеседуемый парень - молодец. И все равно, решил правильно или нет. Главное, что он понимает,, о чемговорит..Это важнее, чем знать... .. Если кандидат все знает, но ничего не понмает, значит это уже не кандидат, ищем другого... Малаец парень...
Верно - тесты на leetcode float ответ вместо int вообще не примут - интервьюер тут опять куда-то не туда увел. С другой стороны испытуемый должен был отстоять свое решение - видится, что здесь оба поднамутили
@@mikhail286 Интервьюер должен был понимать что делает формула, а не заучивать ее наизусть. Он явно формулу зазубрил, а когда его спросили зачем целочисленное , начал троить. вместо того что бы объяснить зачем
Временная сложность этой строчки 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 Это не чистый O(n), потому что поиск в множестве, п офакту произойдет n раз, и хоть он и реализован лучше простого прохода, он все равно зависит от размера множества.
Прикольная задача, я первый вариант долго решал, а второй чет быстро подошло, а потом еще и обратносовместил (еще не досмотрел видос мб он также сделал) # k - это сколько эл-тов мы удалили def findMissedNums(nums, k): st = set(nums) prevLen = len(st) mx = max(st) ans = "" if mx != len(nums) + k: return mx + k for n in range(1, mx): st.add(mx - n) if len(st) > prevLen: ans += str(mx - n) + " " prevLen = len(st) return ans lst = [1,2,4,6,7] k = 2 print(l) print(findMissedNums(lst, k))
Не уверен, что кто-то предложил в комментариях это решение, поэтому предложу его я. Задача, найти два числа, отсутствующие в перемешанном массиве натуральных чисел в количестве 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) - это уже ничего не изменит.
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]
Почему нельзя было просто создать два множества, первой из того массива, который есть, второе из всех чисел, которые должны быть, а потом из одного множества вычесть другое
Но решение второй задачи ведь не будет работать если пропущена единица Почему тогда Данила сказал что оно рабочее? А у Максима интересное мышление - он сразу предлагает сложные варианты а простые не может дать
Я новичек, подскажите на сколько гуд мое решение? Суть такая что в сортированном списке каждое следующее число больше предыдущего на 1,значит если число больше предыдущего больше чем на 1 то между ними как раз и прячется потерянное число . def found_num(chisla): j = 0 for i in sorted(chisla): if i > j + 1: return (i-1) j = i
Нашел самое сложное (и по времени, и по памяти) решение этой задачи в истории: 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))))
А где можно почитать про формулы в первой задачке? Воспроизвел пример, в итоге функция всего лишь находит элемент n+1, больший n на 1. А если не последний элемент удалится, тогда это решение не подходит.
Я новичок, не особо понимаю, зачем усложнять, какие-то уровни. Если создать список со всеми числами и их сравнить, такое решение пройдёт, если нет почему?
Тут проверяют знания алгоритмов, а не то как ты будешь писать код который будут поддерживать джуны после курсов. Если заморочится и порешать задачки алгоритмические, хотя бы базовые, набить руку, то можно сильно увеличить производительность своего приложения. Но как показывает практика, когда в код залетают алгоритмы, а у того кто его потом сапортит нет базы, хотя бы математической, то часто летит нытье уровня - что за идиот это писал, ничего не понятно. вот я бы сейчас тут дернул filter().sort().reduce() и все станет супер просто и понятно. а по факту все было просто и понятно, но незнайка сделал по свойму и положил фпс счетчик своего приложения
Первая задача ксорами решается понятно, как. Про вторую не понял, за линейную скорость как найти. Пока решил "в лоб" def find_one_lost(ar): x = len(ar) ^ (len(ar) + 1) for i in range(len(ar)): x ^= ar[i] x ^= i return x def find_two_lost(ar): one, two = 1, 1 for i in range(len(ar)): if i in ar: continue one = i two = find_one_lost(ar + [one]) return one, two
Прямо сейчас попасть можно только через акселерацию ЯндексПрактикума для студентов (Максим, например, так попал). . Если буду искать людей со стороны -- то тут t.me/RUclipsPronin Недавно отбирал в пет-проект людей. Собесы с ними пока под замком, но открою
Как насчет такого решения второй задачи? Я так понимаю, оно 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 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]
Оцените мое решение первой задачи 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
Мои решения для одного и для двух (и более) чисел: 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 или как там нашу называет, то придется принять правила игры. Это объективная реальность. или ты принимаешь правила игры, или создаешь свою реальность
Я предполагаю, что так в принципе оценивается возможность человека мыслить и мыслить быстро. Потому что какой-то инструмент рано или поздно выучит любой, но будет ли этот человек достаточно быстро ориентироваться в чем-то новом, выходящим за рамки его знаний трудный вопрос. Который возможно так и оценивают+сразу проверяют знание языка
Судя по последним действиям Яндекс, то им отрастить нужно не только нейронные связи. А еще у этих умников уходит код в общий доступ, ну прям супер гении, зато человека мучают со знанием суммы арифметической прогрессии. У них код из под носа увели, а они умничают.
Нут так вроде и не было задано решать через формулу Гаусса. Я бы, например, не догадался и решал бы в лоб "вычеркиваниями". А тут человек заработал плюс.
делюсь своим решением 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)
Не вижу антирекламы. Алгоритмы нужно знать, или хотя бы понимать как к ним логически прийти. Вряд ли какой-либо общий курс может впихнуть в голову кучу алгоритмов и логическое мышление. Это должно приходить в процессе самообразования
@@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) - нечетное, и наоборот, то есть всегда умножаем четное на нечетное.. в таком случае всегда четное будет
t.me/RUclipsPronin Чат для общения pyhton разработчиков и им сочуствующих. Свободное общение, тестовые и вопросы с собесов и прочее. Заходите, там вам рады.
Поддержать канал: www.tinkoff.ru/rm/pronin.andr...
Обычно денежка идёт на книжки про питончик. Но иногда на светлое и тёмное.
В == внимательность
Мужик и вправду молодец. А вот собеседующий, если и первоклассный программист, но никак не первоклассный собеседующий. Все интервью чувствовалось напряжение между участниками. Ощущение, что мужика расстреляют в конце, если что-то не сделает. Но в целом, полезное видео. Оно не только про программирование, но и про напряжение во время собеседования к которому всегда нужно быть готовым.
Комент в поддержку Максима! С боевым крещением!😉
Спасибо
Целочисленное деление на 16:50 все еще надо, не все хорошо. Нас попросили вернуть пропущенный int, а мы отдаем float. Надо либо в инт откастить, либо действительно // использовать
Считаю что Максим отлично справился, еще и формулы умудрялся вспоминать ) Я сам недавно на первом лайв кодинге сидел тупил над простой задачей, потом после интервью решил за 30 сек .
А задача реально интересная оказалась.
Я свел ее решение к 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 больше займет ;-)
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)
Вот пример кода который короче и может считать пропущенные числа, я только начал программировать, и знаю что можно и лучше сделать этот код, не судите строго.
Мужик очень бодро начал, вспомнил математическую формулу, понял как применить (пусть и некая мешанина в голове была). Потом понял как использовать предыдущее решение с новой задачей и попытался написать код. В то же время интервьюер почему-то сказал, что править(хотя, скорее, было бы правильнее добавить аргумент) старую функцию не имеет смысла, а потом банально но, очевидно, неправильно написанный код давал какие-то советы, когда человек уже допустил ошибки.
Интервьюер, может, и опытный разработчик, но сидеть и столько времени смотреть в цикл где будет 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 Ладно, не надо ранним утром код писать и позориться, править код не буду что б видели что я тоже облажался =)
Если испытуемому простительно из-за нехватки опыта, то интервьюер, принявший код с несколькими ошибками, выглядел невовлеченным
немного не согласен с замечанием в сторону собеседующего. В яндексе на собесах решение задач выглядит так:
1. дают задачу
2. обсуждаете условие, задаете вопросы по нему
3. дальше обсуждается решение, нужно словесно описать идею оптимального алгоритма, после чего предлагается написать код
4. код пишется самостоятельно, собеседующий не подсказывает, естественно можно задать уточняющие вопросы, но скорее по идее, а не по коду
5. после того как код написан, очень важно посидеть и подебажить в голове, посмотреть на краевые случаи, найти какие-то ошибки
6. потом надо сказать волшебное слово типа "готов сдавать" и собеседующий либо говорит, что все верно, либо, что есть ошибка (без указания где)
7. если ошибку найти не удается, то только тогда интервьюер обращает внимание на конкретные места
@@stepan_chousНу это как бы и не собеседование в Яндекс, а просто задача с Яндекса. Ориентируюсь на название видео, потому что пересматривать его не хочется, так что если в видео говорили что полностью промоделируют собес с Яндекса, то неправ.
4. "Код пишется самостоятельно" и, судя по тому что я написал в своем комменте, то собеседующий увел от собственных размышлений собеседуемого. Так что этот пункт уже не соблюден. Опять же, опираясь только на свои слова, пересматривать не хочу, если я не врал в комменте (а такой привычки за собой не имею), то ... Просто факт - пункт не соблюден.
5. "Подебажить в голове". А чем дебаггер не подходит? Если в Яндексе не разрешают дебажить, пусть даже на собесах только, то у меня большие вопросы к таким собесам. Может мне ещё в нотпаде код писать? И лсп вообще выключить?
В общем, их контора, пускай делают как хотят. Просто выглядит это как хреновое собеседование, вот и все, имхо.
Совершенно нерабочий код. Во-первых, выход за границы массива. Во-вторых, если эту ошибку устранить, то все равно получим неверные значения 1, 2 вместо 2, 4.
Никогда бы не взял типа в красном на работу по софт скилам
Лайк, лимонад «Колокольчик» и сыр «Дружба».
А если два числа подрят потеряли?
Данила такой неприятный :( не знаю почему, такой крутой мужик, а Данила какой-то неприятный
Не рекрутер, мб поэтому)
А что - не перебивал, не третировал...
Собеседуемый парень - молодец. И все равно, решил правильно или нет. Главное, что он понимает,, о чемговорит..Это важнее, чем знать... .. Если кандидат все знает, но ничего не понмает, значит это уже не кандидат, ищем другого... Малаец парень...
Целочисленное деление нужно, чтобы ответ был int. Если "/" то ответ будет float
Верно - тесты на leetcode float ответ вместо int вообще не примут - интервьюер тут опять куда-то не туда увел. С другой стороны испытуемый должен был отстоять свое решение - видится, что здесь оба поднамутили
@@mikhail286 Интервьюер должен был понимать что делает формула, а не заучивать ее наизусть. Он явно формулу зазубрил, а когда его спросили зачем целочисленное , начал троить. вместо того что бы объяснить зачем
Первая задача в одну строку
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)) Если решать как в видео
Прикольная задача, я первый вариант долго решал, а второй чет быстро подошло, а потом еще и обратносовместил (еще не досмотрел видос мб он также сделал)
# k - это сколько эл-тов мы удалили
def findMissedNums(nums, k):
st = set(nums)
prevLen = len(st)
mx = max(st)
ans = ""
if mx != len(nums) + k:
return mx + k
for n in range(1, mx):
st.add(mx - n)
if len(st) > prevLen:
ans += str(mx - n) + " "
prevLen = len(st)
return ans
lst = [1,2,4,6,7]
k = 2
print(l)
print(findMissedNums(lst, k))
память 0(n)
скорость 0(n)
Не уверен, что кто-то предложил в комментариях это решение, поэтому предложу его я. Задача, найти два числа, отсутствующие в перемешанном массиве натуральных чисел в количестве 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) - это уже ничего не изменит.
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)
Почему нельзя было просто создать два множества, первой из того массива, который есть, второе из всех чисел, которые должны быть, а потом из одного множества вычесть другое
А ограничение по памяти?
@@AndyPronin ах вон оно как, понял
Но решение второй задачи ведь не будет работать если пропущена единица Почему тогда Данила сказал что оно рабочее? А у Максима интересное мышление - он сразу предлагает сложные варианты а простые не может дать
If I+1dic[i] then miss1=I+1 break if I+1+miss1dic[i+miss1] then miss2=miss1+I+1 break. Все. В один проход.
Я новичек, подскажите на сколько гуд мое решение? Суть такая что в сортированном списке каждое следующее число больше предыдущего на 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_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))))
лайк от СЕООНЛИ
Не расмотрели если одно или оба числа в начале: 1 и 2
А можно мидловский собес по алго секции?😇 Хотя может и там будут задачки на применение хэшмап или xor🤔
Можно и мидловый)
прочитал, как алко секции😁
А где можно почитать про формулы в первой задачке? Воспроизвел пример, в итоге функция всего лишь находит элемент n+1, больший n на 1. А если не последний элемент удалится, тогда это решение не подходит.
Попробуй сначала с помощью sum решить. Потом принцип Гаусса погугли. Очень прикольная история, как он придумал суммировать числа в последовательности
Поправьте меня, если я неправ, но похоже в собесе разговор о Натуральных числах, а не о Целых?
Любое натуральное число является целым, так что противоречий нет
Я новичок, не особо понимаю, зачем усложнять, какие-то уровни. Если создать список со всеми числами и их сравнить, такое решение пройдёт, если нет почему?
Тут проверяют знания алгоритмов, а не то как ты будешь писать код который будут поддерживать джуны после курсов.
Если заморочится и порешать задачки алгоритмические, хотя бы базовые, набить руку, то можно сильно увеличить производительность своего приложения.
Но как показывает практика, когда в код залетают алгоритмы, а у того кто его потом сапортит нет базы, хотя бы математической, то часто летит нытье уровня - что за идиот это писал, ничего не понятно. вот я бы сейчас тут дернул filter().sort().reduce() и все станет супер просто и понятно. а по факту все было просто и понятно, но незнайка сделал по свойму и положил фпс счетчик своего приложения
Первая задача ксорами решается понятно, как. Про вторую не понял, за линейную скорость как найти. Пока решил "в лоб"
def find_one_lost(ar):
x = len(ar) ^ (len(ar) + 1)
for i in range(len(ar)):
x ^= ar[i]
x ^= i
return x
def find_two_lost(ar):
one, two = 1, 1
for i in range(len(ar)):
if i in ar:
continue
one = i
two = find_one_lost(ar + [one])
return one, two
Ну у меня что-то такое получилось:
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
Здравствуйте, Андрей. Подскажите, можно ли попасть к вам на интервью. Если да, то куда написать?
Прямо сейчас попасть можно только через акселерацию ЯндексПрактикума для студентов (Максим, например, так попал).
. Если буду искать людей со стороны -- то тут t.me/RUclipsPronin Недавно отбирал в пет-проект людей. Собесы с ними пока под замком, но открою
А если просто массив в сет перегнать и по нему циклом пройтись , сложность О(n)
А по памяти?
@@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 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]
множества не подходят?
Нет
Оцените мое решение первой задачи
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 в квадрате
Может dig2 = i + 2 ??
Добрый и злой полицейский-рекрутер 😂
Они оба добрые
@@maxnmx4544 да, Андрей забавно сыграл просто, когда разрядил обстановку.
Мои решения для одного и для двух (и более) чисел:
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
Вторая задачкас временным ограничением классная, спасибо!
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
Без Данилы пожалуйста в след раз
почему?
@@AndyPronin токсик
def find_miss_number(arr, n):
expected_sum = sum(range(1, n+1))
actual_sum = sum(arr)
return expected_sum - actual_sum
Чел в красном возомнил себя непонятно кем. лЛежал всё интервью и непрерывно говорил что это запускаться или работать не будет.
я я так ее решил .
def miss(arr):
return sum(range(1,len(arr)+2))-sum(arr)
Вот смотришь, думаешь, ну как так можно тупить. А когда там оказываешься, тупишь ещё хлеще))
Есть какие-нибудь таблетки от этого?)
Нет.. это я я как пример
Да. Постигается упражнениями. Первый раз адреналин и не можешь вспомнить своё имя. Потом проще. Для этого такие собесы и делаем. Танк. Граната. Новобранец.
а если хочешь как лучше. А в итоге тупишь как перед как перед экзаменом. Я честно все учил, но сейчас не помню? Хотя бы есть такие примеры что отлично. Хорошие видео чтобы показать и порешать те вопросы которые возникают. Спасибо.
А теперь вопросы к Яндексу и тем кто любит такие алгоритмические вопросы 1) где в жизни, а точнее в приложении может понадобиться знание суммы арифметической прогрессии 2) как часто в работе разработчика он будет использовать это знание с нуля, без библиотеки.
Пригодиться для прокачки твоих нейронных связей. Для прокачки твоих скилов. И, если ты хочешь в FANG или MANG или как там нашу называет, то придется принять правила игры. Это объективная реальность. или ты принимаешь правила игры, или создаешь свою реальность
Я предполагаю, что так в принципе оценивается возможность человека мыслить и мыслить быстро. Потому что какой-то инструмент рано или поздно выучит любой, но будет ли этот человек достаточно быстро ориентироваться в чем-то новом, выходящим за рамки его знаний трудный вопрос. Который возможно так и оценивают+сразу проверяют знание языка
Судя по последним действиям Яндекс, то им отрастить нужно не только нейронные связи. А еще у этих умников уходит код в общий доступ, ну прям супер гении, зато человека мучают со знанием суммы арифметической прогрессии. У них код из под носа увели, а они умничают.
Нут так вроде и не было задано решать через формулу Гаусса. Я бы, например, не догадался и решал бы в лоб "вычеркиваниями". А тут человек заработал плюс.
делюсь своим решением
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)
множества отдыхают…..
А почему вариант с for - это квадратичная сложность? Вложенного же подцикла нет😮
Поиск элемента в массиве == линейное время. Вложенный цикл есть по сути, если понимать, как работает in в вашей структуре данных
Тяжело в учении, легко в бою, волнение берет свое .. , задача то лёгкая, на 7 8 киу
Сам не ожидал
очередная антиреклама яндекс практикуму
Не вижу антирекламы.
Алгоритмы нужно знать, или хотя бы понимать как к ним логически прийти.
Вряд ли какой-либо общий курс может впихнуть в голову кучу алгоритмов и логическое мышление. Это должно приходить в процессе самообразования
@@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
def find_miss(lst: list):
cur_lst = sorted(lst).copy()
ret_lst = []
for i in range(1, len(cur_lst)):
if cur_lst[i-1]+1 != cur_lst[i]:
ret_lst.append(cur_lst[i-1]+1)
return ret_lst