Python developer собеседование с задачей уровня хард из Яндекса . Ян Желанов
ฝัง
- เผยแพร่เมื่อ 10 ก.พ. 2025
- t.me/TH-camPr...
Чат для общения pyhton разработчиков и им сочуствующих. Свободное общение, тестовые и вопросы с собесов и прочее. Заходите, там вам рады.
Поддержать канал: www.tinkoff.ru...
Обычно денежка идёт на книжки про питончик. Но иногда на светлое и тёмное.
Виш лист
Хорошие книги по Питончику, которые могу рекомендовать (и хочу купить с вашей помощью).
Знакомство с Python | Бейдер Дэн (2023) - выглядит приятно для новичка
Чистый Python. Тонкости программирования для профи | Бейдер Дэн (2022) - хорошо для продолжения
Высоконагруженные приложения. Программирование, масштабирование, поддержка | Клеппман Мартин
Изучаем Python. Двухтомник. Марк Лутц. Очень подробно и структурно (Хочу дождаться 6го издания.. )
• Изучаем Python с Марко...
Читаем и разбираем ее тут
Куплено (огромное спасибо зрителям)
Python. К вершинам мастерства | Рамальо Лучано - 2е издание - сложно для новичка, но интересно
Паттерны разработки на Python: TDD, DDD и событийно-ориентированная архитектура -- хорошо про то, когда какой фреймворк применять
Видимо, дальше появтся еще нескромные желания. Но пока - так
Моя тележка andpronin -- стучите, если что.
Мой канал про обучению python с нуля и до мидла Андрей+=Пронин
/ @pypronin
Я в других сетях
🔗Вконтакте: CaptPronin
🔗Дзен: zen.yandex.ru/...
#python #питон #программирование #Андрей_Пронин #собеседование #ЯнЖеланов
За день до собеса посмотрел это видео, попалась задачка с квадратами. Так что спасибо за контент=)
затянул?
@@AndyPronin надо спрашивать: задонатил? 🤣
@@rrrrr5042 то дело добровольное)
@@user-tg4pb7uy5dскорее всего как первая
Задача 1:
def solution(array: list[int]) -> list[int]:
right = len(array) - 1
left = 0
result = []
while left array[right]:
result.append(array[left] ** 2)
left += 1
else:
result.append(array[right] ** 2)
right -= 1
return result[::-1]
У вас ошибка при сравнении. Сравнивать квадрат с обычным числом справа. Так же в конце идёт reverse, что добавляет сложности. Я бы делал через deque с appendleft.
А где задача уровня хард?)))
В первом решении нужно перед поиском индексов left и right первоначально присвоить их в 0 и len-1 соответственно, иначе в случае массивов, состоящих либо только из положительных чисел, либо отрицательных, эти индексы не присвоятся и всё будет плохо.
В первой задаче можно было отрицательные числа в stack (LIFO) засунуть и сравнивать модуль или квадрат числа с числом или квадратом числа исходного массива, если число в стеке меньше то его выводить, а потом число исходного массива.
а че не так с sorted?
@@devpops3393 Вычислительная сложность алгоритма будет выше, чем методом двух указателей
@@freesx1306 а никто же задачу такую не ставил. Поэтому сначала можно sorted выходной список вернуть. Зачем на этом этапе усложнять?
@@alexkochevnicke5122 ну все задачи на собеседовании в Яндекс требуют оптимального решения. Поэтому и надо усложнять. Даже если ты напишешь с sorted,то тебя спросят: а как улучшить?
Интервьюер очень косноязычен. Он отвратительно формулирует задачу, а потом, когда испытуемый выполнил ровно то, что услышал, вдруг оказывается, что есть еще вводные, и он якобы недостаточно полно понял условие. Я бы извинился и прекратил бы собеседование.
абсолютно согласен. "Надо вывести квадраты всех чисел отсортированного массива". Потом его фраза "в отсортированном порядке", когда интервьювер пишет вводные, ничего не говорит о том, к чему он это добавил. Очень плохо, Яндекс
@@AlexeiGoncharov-gq8dmВ начале видео говорилось, что приглашённый - программист в Яндйексе а не интервьюер. Конечно с вами сюсюкатьая никто на собесе в яндекс не будет. Не пойму почему вы придрались к формулировке первой задачи. Человек нормально разъяснил условие, а добавил некоторые фразы так как сразу понял что кандидат не слишком умный (что собственно так и есть)
@@silentlyow у Яндекса собез слабый, если что) собственно оттуда и такие сотрудники, которые сформулировать таск не в состоянии)
Да, он фиговый
Мало того, на 29 минуте он неправильно определил сложность предложенного алгоритма как n*k. На самом деле там число сочетаний по k из n умноженное на k.
Задача 1 :
def sorted_squares(arr):
n = len(arr)
result = [0] * n
left, right = 0, n - 1
for i in range(n - 1, -1, -1):
if abs(arr[left]) > abs(arr[right]):
result[i] = arr[left] ** 2
left += 1
else:
result[i] = arr[right] ** 2
right -= 1
return result
input_array = [-81, -9, 1, 2, 3]
output = sorted_squares(input_array)
print(output)
Такое решение получилось - вроде работает
В первой задаче похоже ошибка. Если в массиве нет отрицательных чисел, то в первом цикле for границы (left и right) не получат никакого значения, поэтому в следующем же цикле while появится ошибка: local variable 'left' referenced before assignment.
Например в самом начале функции можно обозначить границы для таких краевых случаев :
length = len(arr)
plus = 0
minus = 0
for i in arr:
if i >= 0:
plus += 1
else:
minus +=1
if plus == length:
left = -1
right = 0
elif minus == length:
left = length -1
right = length
спасибо за троллинг баянистого переворота строки, это было хорошо :)
Решение первой задачки со сложностью O(n)
arr := []int{-11, -10, 3, 4, 5, 6, 7, 8, 9}
result := make([]int, len(arr), len(arr))
count := 0
for i := 0; i < len(arr); i++ {
if arr[i] < 0 {
result[len(arr)-1-i] = arr[i] * arr[i]
count++
} else {
result[i-count] = arr[i] * arr[i]
}
}
fmt.Println(result)
Решение неправильное. Например, если заменить -10 на -2, итоговый массив будет [9, 16, 25, 36, 49, 64, 81, 4, 121]
Почему у интервьюируемого губы не накрашены? Непорядок, не труъ девелопер.
Пох. Лишь бы реально давали годный контент по разбору всей этой зоологии.
@@Самара-з6б Чувак, вайтишники должны видеть до чего ИТ доводит)
Задача 1:
Def func(arr):
Res = []
For i in arr:
If i < 0:
Res.append(int(f'-{i**2}')
Else:
Res.append(i**2)
Return res
@@Slay-.- 0_о про метод abc() не слыхал? :)
Неправильно
Просто идёте подряд с самого начала и до конца и добавляете в res квадраты пройденных элементов. Условие if здесь вообще ничего не дает, элементы и так расположены в порядке возрастания. Просто попробуйте в уме прогнать этот код и поймете
Решение на С++ с декой, которое я использовал.
Я проверил пустой ли массив, если да, то вернуть пустой массив. Иначе я добавил в очередь квадрат нулевого элемента массива
Потом по циклу проходил с первого элемента до конца. Если квадрат i больше элемента в конце очереди, то я добавлял его в конец. Иначе я добавлял в начало. Потом скопировал элементы деки в массив и вернул его
vector array_squares(vector& nums)
{
deque qe;
vector result;
if (!nums.empty())
qe.push_back(pow(nums[0], 2));
else
return {};
for (auto i = nums.begin()+1; i != nums.end(); i++)
{
if (pow(*i, 2) > qe.back())
qe.push_back(pow(*i, 2));
else
qe.push_front(pow(*i, 2));
}
copy(qe.begin(), qe.end(), back_inserter(result));
return result;
}
Это решение получилось компактнее, чем первое, но по памяти заняло больше
@@Гычпукхеровое решение
Если что, в Python GIL - это и есть, по сути своей, mutex, который контролирует доступ к состоянию процесса интерпретатора.
Многопоточный код писать на Python еще как можно, если он касается задач ввода/вывода.
Оба героя плавают в этой теме, только один уверенно, а второй нет)
цикл событий выполняется в одном потоке поэтому можно поподробнее о том как написать многопоточный код для задач ввода вывода?)))а то создатели питона не в курсе еще что оказывается есть такой гений который может))
Вы написали многопоточных кол на питоне писать ещё как можно если он касается ввода вывода) 1.какой смысла писать ввод вывод с использованием многопоточности впринципе если асинхронщина в один поток отработает быстрее, далее он все равно не будет истинно многопоточным потому что gil)))
@@eurodoo
Ещё рекомендую все же разобраться как работают потоки в Python.
Там создаются настоящие такие posix потоки ОС, которые успешно будут работать параллельно в случае ввода/вывода, потому что будут "отпускать" GIL.
Что имеет смысл делать, а что нет - это вопрос другой. В технологиях все-таки нужно разбираться, однажды это спасает жизнь)
@@denisbalyasnikov7185 что что они отпускают Гил, когда они его отпускают они не работают, а "ждут" загуглите эффект конвоя, у вас будет реальная многопоточность только если библиотека си которая используется написана питоном не блокирующуя например sha256))
@@eurodoo
Даже не представляю как бы мы жили, если бы поток после освобождения GIL больше ничего не делал, кроме как ждал.
Эффект конвоя относится только к моменту, когда поток пытается снова захватить GIL, чтобы получить доступ к состоянию интерпретатора.
Вы путаете много понятий.
Обсуждение есть смысл продолжать после четкого понимания:
1. cpu-bound vs io-bound operations;
2. blocking vs non-blocking operations;
3. cooperative vs preemptive multitasking;
4. greenlets vs threads;
5. Раздел документации "Thread State and the Global Interpreter Lock"
Очень надеюсь, что эта переписка будет кому-то полезна, и время на нее было потрачено не зря)
задача 2 def window(ar,k):
dlin, s, int_qw_val,max_values = len(ar), 0, float('-inf'),[]
while s < dlin - k + 1:
for a in ar[s:s + k]:
if a > int_qw_val:
int_qw_val = a
max_values.append(int_qw_val)
s += 1
return max_values
l = [7,15,1,3,20,10,16,17]
k=3
print(window(l,k))
Первую как-то сложно решали. Можно было 2 указателя: один с начала идет, второй с конца и результирующий массив заполнять с конца.
Вторая интересная. С ходу придумал только за О(k*log + n*logk) + O(k) место.. Когда упомянули деки, то дошёл до O(n) + О(k) место.
И вопрос: а как можно на такое жесткое собеседование попробоваться подопытным кроликом? =)
Если студент практикума - то через трудоустройство. Если нет - будет розыгрышь среди подписчиков в телеге t.me/TH-camPronin
Брат, где ты учился? Я даже после того как он решил еле как понял😭
@@tahirrasuljanov7770 мне кажется он не понял условие задачи и решил слишком сложно когда можно было сделать гораздо проще. Может я чего-то не понимаю, но у меня всё решение заняло буквально 6 строчек....
@@frogsfrogsx скинь решение
@@frogsfrogsx my_list = [3, 4, 5, 8, 2, 3, 1]
for i in sorted(my_list):
print(i ** 2)
Вторая задача Hard на leetcode: Sliding Window Maximum
Уровня хард литкода последняя задача ) на открытии Яндекс.Тренировок по алгосам сказали, что задачки «с легким налётом мидл» попадаются на собесах)))
медиум, не выше
@@novoidx4322 вторая задача хард
почему в первой задаче не сделать ещё одну сортировку по key=abs ?
почему во второй задаче не пройтись по срезам?
for i in range(len(nums)-1-k):
max(nums[i:i+k])
Добрый день, решение по сортировка показалось мне слишком мудреным, решил вроде как проще и понятней, тоже o(n):
left_index = 0 #Индекс первого элемента
right_index = len(array)-1 # 0 #Индекс последнего элемента
result = []
while left_index right_number: #Если левое число больше правого
result.append(left_number**2) # то добавляем в результат его квадрат
left_index+=1 # Увеличиваем левый индекс
else:
result.append(right_number**2) #Иначе берем правое число
right_index-=1 # И уменьшаем его индекс
result[::-1] # Инвертируем
Однако вариант sorted([number**2 for number in array]) все равно быстрее, можете объяснить почему?
асимтотически он не быстрее. если говорить о маленьких массивах то он будет физически быстрее просто потому что sort отошлётся в си на котором питон держится, но если взять огромный массив, то разница будет заметна
да сразу ясно что в первой задаче подвох в том что отсортированный ввод может содержать отрицательние, ну и квадраты уже не будут отсортированы по умолчанию.. Роль дающего таски - это как маг 189 уровня: когда ты эту таску уже во сне видишь а испытуемый как молодой бобик - аж трясется от адреналина
Когда прошёл курс по программированию на питон от скиллбокс
Доброго дня всем! Вопросик по первой задачке) Почему её нельзя решить простой строчкой типа:
sorted([i*i for i in list_test])
Или пользоваться данной функцией в решении запрещено?
Можно, но тогда получится сложность nlogn + n, а хочется решить просто за n (благо исходный массив уже отсортирован)
@@denisbalyasnikov7185 благодарю за ответ! 🙏
К тому же i*i вернет положительное число в случае входящего отрицательного
@@denisbalyasnikov7185 зато sort отработает в любом случае быстрее, чем любой велосипед на питоне, т.к. у него плюсы под капотом
@@denisbalyasnikov7185 так у тебя сложность алгоритма будет меньше, но на практике, у компьютера уходит больше времени на само создание функции. Проверено!😊
Добавьте таймкоды.
Где первая задачка, где вторая.
И готовые решения.
Отличный собес с ушками =) очень позитивно, не хватает такого, а то все(большинство) как люди роботы сидят, жестко)))
Ян, вообще, аеселый
Ещё юбочку добавить и губки накрасить. Тьфу, что становится с мужиками...
@@Kirill_rus_ много бы я тебе ответил на это да думаю без толку это будет, определение по внешности это крайний призрак узкости так назову это. И да в кремневой долине таких как ты выразился не мужиков полно и они двигают мир и индустрию и это факт.
@@Kirill_rus_ На качество кода это не влияет, надеюсь. Я бы так одеваться не стал, но это дело каждого
@@mementomori6005 Да что ты мне про кремневою долину поёшь, я знаю, что на западе таких гей модников пруд пруди. Если мужики начнут красить волосики, надевать серёжки, косить под котиков надевая ушки, красить ноготки, то в мире будет хаос. Так и до гей парадов недалеко. Мужчина должен быть мужественным и опрятным, а не миловидной сюсей с ушками на бошке. И ладно если это ребёнок или девушка, но чтобы парень... Не, мир сходит сума. А такие как ты, кричат УРА на гей парадах ). Когда у тебя появится сын, и в 25 лет он подойдёт к тебе в латексных, обтягивающих штанишках с вырезом на попе, с волосами цвета радуги, накрашенными ресничками, напудренным носиком, и в розовой футболке с блёстками, и скажет: "папууууль, хаюхааай, зацени миникююююр" я представляю как ты в глубине души будешь "рад" своему мужскому воспитаннику))) . Ты скорее всего молодой ещё и на тиктоках и тупых блогерах поехал не в то русло. Но это моё мнение, ты можешь красить губы и не обращать на меня внимание )
Простите, но по факту, стоит некая задача прогеру. Он сортировкой не будет пользоваться? Будет тратить время? Ни ужели на конечном продукте есть время и желание скорость расчитывать? Я про массовые задачи!
Тупо проверяют как ты мыслишь и может в определеных ситуациях не будешь сортировкой пользоваться, так как это сильно замедлит работу сервиса или программы
Если высоконагруженный сервис, то будет и время, и желание.
Жестко, но интересно, Ян молодец.
По первой задаче пришла такая идея
arr = [-5, -3, 0, 0, 2, 2, 6, 9]
arr_res = []
i = len(arr)-1
j = 0
while len(arr) != len(arr_res):
if (arr[i] ** 2) >= (arr[j] ** 2):
arr_res.append(arr[i] ** 2)
i -= 1
else:
arr_res.append(arr[j] ** 2)
j += 1
print(arr_res)
немного покомпактнее
Слишком много кода
максимум на окне можно решить двумя стеками из пар.
Я заполняю первый стек, пока он не размера k, заполняю скмим числом, и минимумом на префиксе . Далее я все элементы этого стека перекидываю во второй, пересчитывая новые минимумы от обратной стороны, теперь элементы в обратном порядке,, т. е сверху-первый(0) элемент массива.
Теперь я начинаю опять заполнять первый стек, удаляя при этом элемент из второгг, я легко могу вычислить минмум на окне, это будет минимум из двух минимумов сверху стеков. Ну и повторяю это, пока не пройдусь по всему массиву
Очень неприятный собеседующий Руслан, не хотел бы я к такому попасть на интервью, только если бы оффер был стоящий и не пришлось с ним работать в одной команде
не знаю что по сложности, не разбирался еще в этом но решения такие получились:
def square(array: list[int]) -> list[int]:
return sorted([n**2 for n in array])
def func(array: list[int], k: int) -> list[int]:
return [max(array[i:i+k]) for i in list(range(0, len(array)))[::k]]
буду рад услышать мнение опытных людей)
Если не ошибаюсь, в задаче нужно было пройтись по всем числам с окном k, а не через k - поэтому решение с шагом [::k] пропустит 2/3 возможных вариантов
Оба решения не верны. В первом - полностью игнорируется момент с тем, что исходный массив уже отсортирован и использовать встроенную функцию сортировки в задачке на алгоритмы явно запрещается (использование sorted после возведения всех значений в квадрат). Во втором - неверный шаг И, что важнее, ты проходишь по каждому элементу и считаешь результат для каждого субмассива. Представь, что к = 10000, а массив длинной в миллионы элементов, тогда ты должен посчитать миллионы раз подмассивы длиной 10000. Смысл в том что подмассивы отличаются друг от друга только на 1 элемент и этим нужно воспользоваться.
Первое збс, второе не рабочее так как пропустит кучу чисел)
def solution(arr: list[int], window: int) -> list[int]:
if len(arr) < window or window
Нравятся такие курсы и собесы, где учат алгоритмам, а не работать) Питонистов много, но нужных нет)
Это не сложные задачи. Первая - простая, если не считать, засады с отрицательными числами. Вторая - скорее средней сложности. Сразу на ум приходит max heap, O((n-k)*log(n)) ? Надо больше решать литкод. А с деком, да, это по моему monotonic stack называется на литкоде или что то близко
Решение второй задачи с помощью очереди - О(n) - идея в том, чтобы при движении окна постоянно поддерживать максимум в начале очереди
if k == 1:
return nums
queue, ans = deque(), []
for i in range(len(nums)):
if queue and queue[0] < i-k+1:
queue.popleft()
while queue and nums[i] > nums[queue[-1]]:
queue.pop()
queue.append(i)
if i >= k-1:
ans.append(nums[queue[0]])
return ans
А с каких пор добавление и удаление из очереди стало работать за 1?
@@nikolayveselovwp793оно всегда было за O(1). Очередь сама по себе урезанный двусвязанный список. А в связанном списке добавление и удаление всегда работает за константное время. Так как в списке не нужно реаллочить память из одного участка памяти в другой, чтобы расширить или уменьшить список. Добавление в очередь происходит за счёт создания новой ссылки на новый элемент и связывание его с первым или последним элементом. Удаление работает точно также, но наоборот. Единственное, когда в списке(в очереди) происходит добавление за О(n) - это добавление или удаление в диапазоне от 1(не включительно) до последнего(не включительно)
@@Гычпук да, извиняюсь, я почему то вместо очереди прочитал куча…
А что если array = (90, 89, 87, 86, 85 etc)
numbers = [0, 2, 4, 6, 8, 10, 1, 3, 5, 7]
k = 3
b = []
c = 0
d = []
for i in range(len(numbers)):
b = numbers[i:k + i]
c = max(b)
d.append(c)
if numbers[i:] == numbers[-3:]:
break
print(d)
я так сделал, правда занимаюсь программированием недели 3-4
первая простая очень если делать линейку по памяти, если на собесе попросят сделать константу, то это гроб с 4 указателями)
Константа по памяти - в смысле с записью ответа во входной массив?
Ну да, неприятно выходит
Скользящее окно пишется в пяток строк на islice, потом йелдишь max от него, и всё.
сложность n*k
По моему его решение с квадратами не работает правильно и работает дольше sorted(...)
Классный собекс.
Когда человек вот так вот пишет код и продумывает свои действия - это прям бальзам на душу такое смотреть.
Однако я так и не понял: он на какой грейд претендует?
А то Руслан сказал, мол, "...на джуна подумают" - т.е. он на мидла и выше претендовал по собесу?
Вроде нет, я немного неправильно выразился, такую задачку и на стажировку могут дать :)
@@ruslansitdikov7145, в общем, в Яндекс можно даже не пытаться попасть. :D
@Константин, ну, хз.
Если требование для прохождения - вот такие вот задачи, которую нужно решить оптимально за час - то вообще хз.
Я бы еще понял, если бы было все из разряда "не важно - решил или нет, нужно было просто посмотреть на то, как мозги работают", но Руслан сказал, что нужно именно решить.
И я вот вообще хз, насколько реально решить такую задачу за час, если видишь ее впервые.
Да, если уже решал - другое дело.
Но тем не менее.
@Константин, так-то никаого другого смысла, кроме того, что твои племянники шарят в алгосах, тут речи не идет.
Тут уровень стажера даже не тянет 😁
Вы считаете сложность алгоритма и пытаетесь найти самый быстрый, но при этом в каждой задаче создаёте функцию.
Алгоритм то может и будет работать быстрее, но сама программа медленнее. Почему нельзя работать сразу с массивом?
Каким образом создание функции влияет на скорость работы программы?
Что-то парень растерялся со второй задачей. Самый простой вариант имхо найти максимум и его индекс в первом окне и потом сравнивать новый элемент с максимумом и проверить индекс на попадание в окно. Если индекс за пределами окна - искать максимум в срезе.
ваше решение O(n^2)
@@absent6322 только если список отсортирован по убыванию. В остальных случаях где-то между On и On**2
@@yauhent671 ты же понимаешь что такое О-notation, это про худший случай, если вкратце.
@@absent6322 Da, znaju
Перед этим алгоритмом нужно проверить список на монотонность. Если он монотонно возрастающий, то ответ это сам список начиная с k. Если он монотонно убывающий, то ответ это сам список до len-k.
Если ни то ни другое, то тогда уже юзать алгоритм.
Поэтому и был вопрос про проверку на монотонность, которую, как я понимаю, можно осуществить просто путем вычитания из каждого значения списка его предыдущего значения с последующей проверкой на больше / меньше 0.
Прикольное собеседование, погоняли по классическим алгосам) В последней, кстати, я подумал, нужно как-то извернуться, и придумал пару решений через рекурсию. "Разделяй и влавствуй", типо) Но не факт, что они в среднем сильно эффективнее обычного "в лоб" за O(n)
Опозорился, как только появился в кадре 😮
Почему решающий не в колготках? Не по канону как-то
Понял что ни на одно подобное собеседование я не пойду )А программирование будет моим хобби)
Ну, тут офк речь про очень сильных программистов, поэтому без опыта так с маху конечно очень трудно попасть, нужно быть либо книжным червём с невероятной выдержкой, либо просто иметь талант
@@inexoudi9z167 Талант тут не нужен. Здесь нужна практика чем больше ты чем то занимаешься тем легче. На должном уровне ты уже не боишься задачи,если она сложная и ты с ней не сталкивался то просто предётся больше времени на это посвятить.Как говорится глаза боятся а руки делают.
@@flurixoww по такой логике каждый второй был бы программистом. Талант к изучению одной из самых умственно затратных сфер в мире нужно иметь, если не хватает упорства или еще чего
@@inexoudi9z167 Каждый второй может быть программистом но человек просто не выдерживает. Человек не выдерживает того что вся информация и тд не лежит на поверхности . Не знаю к чему тут самая умственно затратная сфера, да может человек который занимается машинным обучением,крипто графий и тд вот там да тебе нужно будет хорошенько подумать . Но большенство задач которые тебе будут давать это что то по типу вот сделай программу которая будет отслеживать автобус по гпс , для этого не надо иметь много ума для этого требуется только время.
Ну и правильно, чтобы проходить такие собесы, нужно постоянно ходить на такие собесы и выдрачивать литкод.
Если самого не вставляет решение подобных задач, не стоит тратить кучу времени на них, лучше вложить его в выполнение каких-то прикладных задач.
Далеко не все программисты любят этот дроч с алгоритмами, и попасть на собес большая вероятность именно к такому.
Задача 2:
def solution(array: list[int], k: int) -> list[int]:
from collections import deque
dq = deque()
ret = []
for i in range(len(array)):
while dq and dq[0] = k - 1:
ret.append(array[dq[0]])
return ret
def square(lst):
c = []
for i in range(len(lst)):
b = lst[i]**2
c.append(b)
c.sort()
return c
a = [-5,4,2,3]
b = square(a)
print(b)
А так не легче?
В таком решении не учитывается отсортированность массива. Такое решение будет работать медленнее на больших объёмах данных.
Берём 1 элемент массива, умножаем на самого себя. Есть до операции умножения он был меньше 0, то полученый результат - умножаем на - 1.
В первой задаче не проще ли было:
sorted_list = [-5, -3, -2, -1, 0, 2, 3, 4, 5]
squared_sorted_list = sorted([x**2 for x in sorted_list])
print(squared_sorted_list)
сложность твоего решения получается O(nlogn) а можно за О(n) решить
первая кст - Squares of a Sorted Array на LC
Эта отсылка к сыну и кружкам - чушь собачья. Абстрактные школьные математические задачи и олимпиады на то и пишутся, чтобы подловить на чём-нибудь, типа ааааа, ты похоже забыл в чём разница между целыми и натуральными числами! Здесь чувак даже уточняет перед кодированием, а правильно ли он понял, что вы ему всего 10 секунд назад задали, может тест на элегантность и лаконичность кода, уж больно он просто выглядит. И вы такие - да, да, ОК. Ну подловили, супер, однако в реальной жизни возможность отрицательных чисел была бы 100% обговорена и задана, а не скромно замята.
Ну и задачу с максимумами не мешало бы рассказать в конце, а не просто посоветовать "условно хранить индексы максимальных элементов по порядку", что блин не добавляет ну вообще никакой ясности, лишь сомнений в том, что сам экзаменатор может внятно об'яснить решение.
решал вторую задачу на литкод 3 года назад, даже уже и забыл что решал. сначала придумал решение с мультесетом, прошло прям на грани, потом придумал решение на очереди на стеках с максимумом хехехехе, а финальный вариант тоже с очередью и монотонно невозрастающей последовательностью)))
я решал где-то полгода назад, сделал с помощью стека максимумов, это прям первое что приходит в голову, если знать про очередь на двух стеках.
Решение первой задачки
def func(arr: list) -> list:
stack = []
result = []
if len(arr) == 0:
return arr
else:
for i in arr:
if len(stack) == 0 or i**2 stack[-1] or len(stack) == 0:
result.append(stack.pop())
while len(stack) != 0 and i ** 2 > stack[-1]:
result.append(stack.pop())
continue
stack.append(i ** 2)
while len(stack) > 0:
result.append(stack.pop())
return result
Решение первой задачи я отказалсь понимать, что-то он там намудрил.)))
вот мое решение:
def solution(array):
left_pointer = 0
right_pointer = len(array) - 1
result = [0] * len(array)
while left_pointer < right_pointer:
left_square = array[left_pointer] ** 2
right_square = array[right_pointer] ** 2
if left_square > right_square:
result[right_pointer - left_pointer] = left_square
left_pointer += 1
else:
result[right_pointer - left_pointer] = right_square
right_pointer -= 1
return result
Жостко
Первая задачка на Dart:
void main() {
List numbers = [-6, -4, -2, 1, 3, 4, 6];
print(function(numbers));
}
List function(List numbers) {
List results = [];
for (var each in numbers) {
int ok = each * each;
results.insert(index(results, ok), ok);
}
return results;
}
int index(List numbers, int number) {
if (numbers.isEmpty) return 0;
for (int i = numbers.length - 1; i >= 0; i--) {
if (number > numbers[i]) return i + 1;
}
return 0;
}
Ребята, извините, а по первой задачке так сделать нельзя было:
arr = [-5, 1, 2, 3]
squared_arr = [x**2 for x in arr]
sorted_numbers = sorted(squared_arr, reverse=False)
?
Сложность будет O(nlogn)
Решение первой задачи не рабочее. Думаю люди это чувствовали поэтому проверять не стали. По производительности лучшего решения чем sorted([num * num for num in arr]) На следующих входных данных я не нашёл. solution([-5000, -3, -2, -1, 0, 1, 2, 3, 4, 5000] * 50000)
[-5000, -3, -2, -1, 0, 1, 2, 3, 4, 5000] * 50000 -- не является отсортированным массивом
Если знак минус убрать. Допустим массив [-5, 1, 4, 5] . То получится 5, 1, 4, и снова 5?
а о какой версии вообще речь идет? а то будет больно и хейта горы.))
Судя по коду он будет работать и будет работать правильно.
А нельзя его запустить, чтобы проверить?😂😂😂
for item in array : if item>0 : array1.append(item*item) else array2.append(item*item); array1.append(array2[::-1])
Смотрю на решение первой задачи - очень кривая простыня с кучей ветвлений. Думаю, что там полюбому ошибка будет, запускайте, а в итоге "ок, по коду будет работать" оО))
А lambda использовать и map пройтись , как вариант во второй задаче, если конечно нужен Python
А python можно сделать копию массива но по модулю и просто вывод массива в квадрате по индексам?
original_list = [1, -2, 3, -4, 5]
copy_list = original_list.copy()
modulus_list = [abs(x) for x in copy_list]
for index, value in enumerate(modulus_list):
squared_value = value ** 2
print(f"zhopka {index}: {squared_value}")
задача на монотонность, где не надо смотреть возрастает, убывает или вообще из одного числа состоит, идем с 1 по предпоследнее число и сравниваем разницу(вычитание) с некст числом, если есть вычитание больше и меньше нуля то не монотонна
pozitive = negative = False
for i in range(n-1):
dif = array[i] - array[i-1]
if dif > 0:
pozitive = True
elif dif < 0:
negative = True
if pozitive and negative:
print(' ne monotona')
break
@Константин а первый элемент тоже надо проверять, так что с нуля
@Константин вы не поняли идею алгоритма, мне кажется)
@Константин =)
попробовал решить вторую задачу через деку и с минимальным обращением к мах(deq) в случае с большим k. пересчитывать max() по всей деке придется только в 1 случае из k.
def frame(lst, k):
from collections import deque
result = []
de = deque(lst[0:k])
max_v = max(de)
result.append(max_v)
for i in range(k, len(lst)):
val_l, val_r = de.popleft(), lst[i]
de.append(val_r)
result.append(max_v := max(de) if val_l == max_v else max_v :=max(max_v, val_r))
return result
а первую задачу решал так
def quad(lst):
n = len(lst)
l, r, result = 0, n-1, [0]*n
lval, rval = lst[0]**2, lst[n-1]**2
for i in range(n-1, 0, -1):
if rval > lval:
result[i] = rval; r -= 1; rval = lst[r]**2
else:
result[i] = lval; l += 1; lval = lst[l]**2
result[0] = rval
return result
Во второй задаче, если будет массив из одинаковых/убывающий, например [2, 2, 2, 2, 2, ... , 2] или [5, 4, 3, 2, 1, ..., -100000] -- будет O(n*k) т.к. будешь каждый раз максимум пересчитывать
Первая задача решается просто, нет?
a = [-25,2,3,5,6]
x = [number * number for number in a]
x.sort()
print(x) = [4, 9, 25, 36, 625]
Интересно, для кого были все эти рассуждения про O(N) и O(NlogN)?
@@eaf2kа для чего намеренно усложнять? Главное - решить задачу так, чтобы код работал
вторую решил оч быстро так:
def solution(nums: list[int], k: int) -> list[int]:
res = []
it = iter(nums)
try:
frame = [next(it) for _ in range(k)]
while True:
mv = max(frame)
res.append(mv)
new_element = next(it)
frame = frame[1:]
frame.append(new_element)
except StopIteration:
pass
return res
nums = [6, 2, 3, 7, 0, 1, 3, 4, 13, -2, -5, 12]
res = solution(nums, 3)
print(res)
почему так? потому что входные данные могут быть большими и не помещаться в память.
6:50 Если при поиске работы программистом придётся конкурировать с такими дарованиями, то шансы есть 👍 спасибо за мотивацию😁
Замечание по самому собеседованию. Если чел не вытягивает первую задачу, то он либо перенервничал, либо не знает базы. В любом случае надо было настоять на доп вопросе - написать все тесты для массива из int.
А это: все "-", переход через 0 с нолем, переход через 0 без ноля, все "+", и эти варианты с четным и нечетным массивом.
Если не вспомнить базу - дальнейший кодинг бесполезен (а как я представляю, его код тесты не пройдёт).
Ну и без указания, что квадрат от int в ряде случаев дает выход за пределы, задачу нельзя считать полностью решенной.
В питоне при выходе за пределы машинного слова число преобразуется в большое. То есть внутри питона из коробки есть длинная арифметика
1 задача
def foo(arr):
return list(map(lambda x: x**2, filter(lambda x: (type(x) is int) if x > 0 else False, arr)))
ох уж этот синдром питониста, решать все в 1 строку
А такое решение второй задачи как воспринимается?)
Если 1 элемент в окне, то возвращает сам входной массив. Если 2 и более чисел, то возвращает максимум из окна, оставшийся кусок массива отдает на функцию через рекурсию, пока не останется 1 элемент.
def max_in_scope(array, k):
if len(array) < 2:
return array
else:
res = []
res.append(max(array[:k]))
res.extend(max_in_scope(array[k:], k))
return res
Первое, что пришло в голову
вы вообще о чем ???
arr = [3, 9, 5, 12, 4, 8, 7, 15, 1, 6, 10, 11, 14, 2]
max_values = []
for i in range(len(arr) - 2):
max_value = max(arr[i], arr[i+1], arr[i+2])
max_values.append(max_value)
print(max_values)
хард))) лайк от СЕООНЛИ!
2 задача - не благодарите
from collections import deque
def solution(arr, window):
result = []
max_queue = deque() # Очередь для хранения индексов с текущим максимальным элементом
for index, num in enumerate(arr):
# Удаляем индексы из очереди, которые находятся за пределами текущего окна
while max_queue and max_queue[0] = window - 1:
result.append(arr[max_queue[0]]) # Добавляем максимальный элемент текущего окна в результат
return result
В первой задаче можно же было использовать sorted([x**2 for x in numbers])? Или нет?
Нет
Они это обговаривали в самом начале, там сложность O(n log n) не подошла, да и интервьюеру часто интересно как мыслит интервьюируемый
Код первого задания у пацана не работает и не увидивитиьно но я типо не осуждаю самого пацана, но вот чел типо с яндекса или откуда он там, просто видно что когда пацан начал слишком громоздить, он перестал понимать что он делает и сделал вид что решение норм (хотя оно time limit ) да и какой O(n) approach это смешно, ощущение что тип пришел не из it сферы даже а с помойки.
Хахах я смотрю Андрей уже смеётся с задачки типо про sliding window ) What is going on ?
яндекс.блокнот
яндекс.сервитор в лице "сотрудника яндекс", который у себя в уме код и запускает, и компилит, и дебажит.
какое же днище! и вот с этим приходится на рынке конкурировать...
вторая:
l = [6, 2, 3, 7, 0, 1]
k = 3
for i in range(len(l)):
print(max(l[i:k+i]))
if i + k == len(l):
break
ну или
for i in range(len(l)-k+1):
print(max(l[i:k+i]))
я не знаю что такое deck в питоне, но вот решение задачи на языке, который не умеет в списки по умолчанию
```
class Max {
var idx: Int = 0
var next: Max?
}
var n: [Int] = [6,2,3,7,0,1]
var k = 3
var result = [Int](repeating: 0, count: n.count-k+1)
var maxHead: Max? = nil
var currentMax: Max? = nil
var isIncreasing: Bool = true
for i in 1..= currentMax!.idx {
currentMax = currentMax!.next
}
}
}
```
print(result)
мб я не эксперт или что-то прослушал, но в первой задаче говорилось заранее, что список отсортированный, то есть на выходе ты вернешь такой же отсортированный список, если будешь просто по массиву циклом идти, но тогда вопрос, почему нельзя просто проверить каждый элемент на то, что он меньше нуля? Допустим :
nums = [-9, -5, -2, 1, 2, 3, 4]
arr = []
for i in nums:
if i < 0:
arr.append(-(i*i))
else:
arr.append(i*i)
print(arr)
результат у вас будет не верно отсортирован, да еще и квадраты с минусом. попробуйте прогнать ваш код в ide
@@SparePant уже формулировку задачи не помню) что там требуется?
чайник, утюг... С ДЕРЕВЯННЫХ СЧЕТОВ!
Идея решении второй задачи очень проста. О(N)
1. Для первого окна находим максимальное и предмаксимальное число
2. Начинаем итерацию по массиву с k до N (где N длина массива)
3. В каждой итерации проверяем равен ли первый элемент окна к максимальному числу
Если да - находим максимальное число из (предмаксимальное число, текущее число) и добавляем максимальное число в результативный массив и обновляем максимальное и предмаксимальное число
Если нет - находим максимальное число из (максимальное число и текущее число) и добавляем в результативный массив и не забываем обновить максимальное число и предмаксимальное число
А chat gpt 4 уже проходил собес ?
Task 1:
Как я понимаю это О(n) + O(n)
def main(_array: list[int]) -> list[int]:
_array = copy.deepcopy(_array)
return sorted(x*x for x in _array)
Сортировка занимает nlog(n) и обход по списку n. В итоге n+nlog(n)
Вторую задачу задачу можно решить без deque за O(n)
Я тут из мира Java залетел, мне кажется первую задачку можно решить намного проще:
int[] input = new int[]{-10, -7, -6, -4, -3, -2, 0, -1, 1, 2, 3, 4, 5, 6, 7};
LinkedList result = new LinkedList();
int lIndex = input.length - 1;
int rIndex = 0;
while (rIndex = rightNum) {
result.addFirst(leftNum * leftNum);
rIndex++;
} else {
result.addFirst(rightNum * rightNum);
lIndex--;
}
}
че то собеседующий взбесил, не может нормально сформулировать ни нормально подтолкнуть, чистая пытка, еще и вертится на стуле как с шилом в жопе, чисто рандомного прогера позвали с яндекса а он пришел чсв повысить свое
первая задач с оптимизацией - это deque
def square_sort(sorted_array: list[int]) -> list[int]:
if sorted_array[0] >= 0:
return [x**2 for x in sorted_array]
result = []
sorted_deque = deque(sorted_array)
while sorted_deque:
if abs(sorted_deque[0]) > abs(sorted_deque[-1]):
append_item = sorted_deque.popleft()
else:
append_item = sorted_deque.pop()
result = [append_item**2] + result
return list(result)
Вторая задача
def find_max_num_in_group(nums: list[int], k: int) -> list[int]:
result = []
groups = (len(nums) - k) + 1
for index in range(groups):
result.append(max(nums[index:index + k]))
return result
def solution(arr: list[int], k: int) -> list[int]:
return [max(arr[i:i + k]) for i in range(len(arr)) if len(arr[i:i + k]) == k]
Всем здравствуйте. Почему нельзя было в первой задаче использовать sort() списка после возведения в квадрат ?
Потому что таким образом сложность высокая
норм же сделал? 2 задача, Swift, сложность O(n)
func solution(numbers: [Int], step: Int) -> [Int] {
guard numbers.count >= step else { return numbers }
var answer = [Int]()
var deque = [Int]()
for i in 0..= step - 1 {
answer.append(numbers[deque.first!])
}
}
return answer
}
Ничего не понимаю, а зачем этот бред то нужен? Первая задача решается конечной сортировкой листа sorted и это будет намного быстрее, чем он тут пыжится.
это не будет быстрее
Может я не понимаю условие, но почему нельзя быстро решить 1-ю задачу, просто добавив sorted к return.
Тоесть: return sorted([number * number for number in array])
Будет сложность n*log n (так как сортировка столько работает)
А надо за n сделать
Вроде айтишники крутого уровня должны много зарабатывать. Но что у вас за обстановка за спинами, парни?
а что не так? У них обычные комнаты
А почему в первой задаче нельзя отсортировать массив прям перед ретюрном?
можно, но времени много займет
Как же течет кровь из глаз от solution - это даже хуже чем a, b, c = 1, 2, 3 т.к претенциозное, но при этом ноль бит инфы. Я бы даже сказал, что близко к True = False... Это не к джуну предъява, а к тем, кто одного за другим их учат этому 80lvl naming, не первое видео уже смотрю...
Я первую задачу так решил
def func(list: list) -> list:
res = []
for i in list:
res.append(i ** 2)
res.sort()
return res
Не оптимально
Так что там за проблема с GIL? Почему её нельзя решить?
Ссылки тут не дает ютуб вставить. Погуглите про Бизли и ГИЛ.
@@Bibliophilos нашел большую статью на Хабре. Но можно простыми словами, для человека, который ещё даже на джуна не претендует?
@@NoNoNo_Name GIL отпускает блокировку и отдает ОС операции ввода/вывода, плюс может некоторые функции на С языке выполнять в многопоточном режиме без блокировки. Вычисления компьютерные в основном распараллелить с джилом нельзя, потоки начинают ждать переключения поочередно и в итоге последовательный однопоточный код быстрее выполнит вычисления.
Я не профи здесь, лучше почитать статейки.
@@NoNoNo_Name Сборщик мусора автоматом убирает ненужные данные, у данных есть ссылки, и без gil может случиться такое, что нужные данные удалятся, потому что не будет никто ссылаться в одном из потоков, вроде из-за этого
а у меня литкод захавал и решение с мультисетом за логарифм, писаное на коленке