Python developer собеседование с задачей уровня хард из Яндекса . Ян Желанов
HTML-код
- Опубликовано: 18 окт 2024
- t.me/RUclipsPr...
Чат для общения 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,то тебя спросят: а как улучшить?
Задача 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)
Такое решение получилось - вроде работает
А где задача уровня хард?)))
Почему у интервьюируемого губы не накрашены? Непорядок, не труъ девелопер.
Пох. Лишь бы реально давали годный контент по разбору всей этой зоологии.
@@Самара-з6б Чувак, вайтишники должны видеть до чего ИТ доводит)
Решение первой задачки со сложностью 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]
спасибо за троллинг баянистого переворота строки, это было хорошо :)
Интересный формат. Осваиваю потихоньку базу на бэкендера. Подобные задачки решаемы, но сижу над ними долго. Не представляю, как в лайв-формате можно быстро придумать решение. Для меня слишком стрессово)
@@slava_zxz Скоро будет 6 месяцев. Сейчас заканчиваю продвинутый синтаксис Питона, прошел основы SQL (Postgre, ещё хочу другую реализацию), основы html+css, и теоретическое введение в ООП. Сейчас хочу переходить к практике ООП и Джанге.
@@slava_zxz удачи нам в этом деле! Главное не терять мотивации
@@davgf438 а вы делали какие-то пет проекты?
@@heybeachMIN ещё нет. Первый будет параллельно с изучением джанги. Ориентировочно через месяц. Ну и несколько ботов ещё хотел сделать, однако для них тоже нужно вникать в библиотеку.
@@davgf438 А кроме ботов, какие Вы планируете делать пет проекты? Я слышал, что создание какой-нибудь соц сети очень хороший может дать плюс при трудоустройстве... Но, наверно, это чертовски сложно и долго плюс знания фронтеда нужно, скорее всего.
Вообще, я только почти закончил курс на степике Поколение python: начинающие, так что мне далеко до Вашего уровня, но всё равно заранее интересно знать, какие люди делают пет проекты.
Если что, в 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"
Очень надеюсь, что эта переписка будет кому-то полезна, и время на нее было потрачено не зря)
Вторая задача Hard на leetcode: Sliding Window Maximum
Решение на С++ с декой, которое я использовал.
Я проверил пустой ли массив, если да, то вернуть пустой массив. Иначе я добавил в очередь квадрат нулевого элемента массива
Потом по циклу проходил с первого элемента до конца. Если квадрат 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;
}
Это решение получилось компактнее, чем первое, но по памяти заняло больше
@@Гычпукхеровое решение
Задача 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 здесь вообще ничего не дает, элементы и так расположены в порядке возрастания. Просто попробуйте в уме прогнать этот код и поймете
Уровня хард литкода последняя задача ) на открытии Яндекс.Тренировок по алгосам сказали, что задачки «с легким налётом мидл» попадаются на собесах)))
медиум, не выше
@@novoidx4322 вторая задача хард
В первой задаче похоже ошибка. Если в массиве нет отрицательных чисел, то в первом цикле 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
Первую как-то сложно решали. Можно было 2 указателя: один с начала идет, второй с конца и результирующий массив заполнять с конца.
Вторая интересная. С ходу придумал только за О(k*log + n*logk) + O(k) место.. Когда упомянули деки, то дошёл до O(n) + О(k) место.
И вопрос: а как можно на такое жесткое собеседование попробоваться подопытным кроликом? =)
Если студент практикума - то через трудоустройство. Если нет - будет розыгрышь среди подписчиков в телеге t.me/RUclipsPronin
Брат, где ты учился? Я даже после того как он решил еле как понял😭
@@tahirrasuljanov7770 мне кажется он не понял условие задачи и решил слишком сложно когда можно было сделать гораздо проще. Может я чего-то не понимаю, но у меня всё решение заняло буквально 6 строчек....
@@frogsfrogsx скинь решение
@@frogsfrogsx my_list = [3, 4, 5, 8, 2, 3, 1]
for i in sorted(my_list):
print(i ** 2)
Интервьюер очень косноязычен. Он отвратительно формулирует задачу, а потом, когда испытуемый выполнил ровно то, что услышал, вдруг оказывается, что есть еще вводные, и он якобы недостаточно полно понял условие. Я бы извинился и прекратил бы собеседование.
абсолютно согласен. "Надо вывести квадраты всех чисел отсортированного массива". Потом его фраза "в отсортированном порядке", когда интервьювер пишет вводные, ничего не говорит о том, к чему он это добавил. Очень плохо, Яндекс
@@AlexeiGoncharov-gq8dmВ начале видео говорилось, что приглашённый - программист в Яндйексе а не интервьюер. Конечно с вами сюсюкатьая никто на собесе в яндекс не будет. Не пойму почему вы придрались к формулировке первой задачи. Человек нормально разъяснил условие, а добавил некоторые фразы так как сразу понял что кандидат не слишком умный (что собственно так и есть)
@@silentlyow у Яндекса собез слабый, если что) собственно оттуда и такие сотрудники, которые сформулировать таск не в состоянии)
Да, он фиговый
Мало того, на 29 минуте он неправильно определил сложность предложенного алгоритма как n*k. На самом деле там число сочетаний по k из n умноженное на k.
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 строку
Добрый день, решение по сортировка показалось мне слишком мудреным, решил вроде как проще и понятней, тоже 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 отошлётся в си на котором питон держится, но если взять огромный массив, то разница будет заметна
задача 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))
Решение второй задачи с помощью очереди - О(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
По первой задаче пришла такая идея
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)
немного покомпактнее
Слишком много кода
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)
А так не легче?
В таком решении не учитывается отсортированность массива. Такое решение будет работать медленнее на больших объёмах данных.
Доброго дня всем! Вопросик по первой задачке) Почему её нельзя решить простой строчкой типа:
sorted([i*i for i in list_test])
Или пользоваться данной функцией в решении запрещено?
Можно, но тогда получится сложность nlogn + n, а хочется решить просто за n (благо исходный массив уже отсортирован)
@@denisbalyasnikov7185 благодарю за ответ! 🙏
К тому же i*i вернет положительное число в случае входящего отрицательного
@@denisbalyasnikov7185 зато sort отработает в любом случае быстрее, чем любой велосипед на питоне, т.к. у него плюсы под капотом
@@denisbalyasnikov7185 так у тебя сложность алгоритма будет меньше, но на практике, у компьютера уходит больше времени на само создание функции. Проверено!😊
Берём 1 элемент массива, умножаем на самого себя. Есть до операции умножения он был меньше 0, то полученый результат - умножаем на - 1.
В первой задаче можно же было использовать sorted([x**2 for x in numbers])? Или нет?
Нет
Они это обговаривали в самом начале, там сложность O(n log n) не подошла, да и интервьюеру часто интересно как мыслит интервьюируемый
попробовал решить вторую задачу через деку и с минимальным обращением к мах(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) т.к. будешь каждый раз максимум пересчитывать
Прикольное собеседование, погоняли по классическим алгосам) В последней, кстати, я подумал, нужно как-то извернуться, и придумал пару решений через рекурсию. "Разделяй и влавствуй", типо) Но не факт, что они в среднем сильно эффективнее обычного "в лоб" за O(n)
Жестко, но интересно, Ян молодец.
вторая:
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]))
первая кст - Squares of a Sorted Array на LC
не знаю что по сложности, не разбирался еще в этом но решения такие получились:
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
максимум на окне можно решить двумя стеками из пар.
Я заполняю первый стек, пока он не размера k, заполняю скмим числом, и минимумом на префиксе . Далее я все элементы этого стека перекидываю во второй, пересчитывая новые минимумы от обратной стороны, теперь элементы в обратном порядке,, т. е сверху-первый(0) элемент массива.
Теперь я начинаю опять заполнять первый стек, удаляя при этом элемент из второгг, я легко могу вычислить минмум на окне, это будет минимум из двух минимумов сверху стеков. Ну и повторяю это, пока не пройдусь по всему массиву
решал вторую задачу на литкод 3 года назад, даже уже и забыл что решал. сначала придумал решение с мультесетом, прошло прям на грани, потом придумал решение на очереди на стеках с максимумом хехехехе, а финальный вариант тоже с очередью и монотонно невозрастающей последовательностью)))
я решал где-то полгода назад, сделал с помощью стека максимумов, это прям первое что приходит в голову, если знать про очередь на двух стеках.
Ребята, извините, а по первой задачке так сделать нельзя было:
arr = [-5, 1, 2, 3]
squared_arr = [x**2 for x in arr]
sorted_numbers = sorted(squared_arr, reverse=False)
?
Сложность будет O(nlogn)
Когда прошёл курс по программированию на питон от скиллбокс
первая простая очень если делать линейку по памяти, если на собесе попросят сделать константу, то это гроб с 4 указателями)
Константа по памяти - в смысле с записью ответа во входной массив?
Ну да, неприятно выходит
Задача 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 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)
почему так? потому что входные данные могут быть большими и не помещаться в память.
Вторая задача
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
В первой задаче не проще ли было:
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) решить
Отличный собес с ушками =) очень позитивно, не хватает такого, а то все(большинство) как люди роботы сидят, жестко)))
Ян, вообще, аеселый
Ещё юбочку добавить и губки накрасить. Тьфу, что становится с мужиками...
@@Kirill_rus_ много бы я тебе ответил на это да думаю без толку это будет, определение по внешности это крайний призрак узкости так назову это. И да в кремневой долине таких как ты выразился не мужиков полно и они двигают мир и индустрию и это факт.
@@Kirill_rus_ На качество кода это не влияет, надеюсь. Я бы так одеваться не стал, но это дело каждого
@@mementomori6005 Да что ты мне про кремневою долину поёшь, я знаю, что на западе таких гей модников пруд пруди. Если мужики начнут красить волосики, надевать серёжки, косить под котиков надевая ушки, красить ноготки, то в мире будет хаос. Так и до гей парадов недалеко. Мужчина должен быть мужественным и опрятным, а не миловидной сюсей с ушками на бошке. И ладно если это ребёнок или девушка, но чтобы парень... Не, мир сходит сума. А такие как ты, кричат УРА на гей парадах ). Когда у тебя появится сын, и в 25 лет он подойдёт к тебе в латексных, обтягивающих штанишках с вырезом на попе, с волосами цвета радуги, накрашенными ресничками, напудренным носиком, и в розовой футболке с блёстками, и скажет: "папууууль, хаюхааай, зацени миникююююр" я представляю как ты в глубине души будешь "рад" своему мужскому воспитаннику))) . Ты скорее всего молодой ещё и на тиктоках и тупых блогерах поехал не в то русло. Но это моё мнение, ты можешь красить губы и не обращать на меня внимание )
Нравятся такие курсы и собесы, где учат алгоритмам, а не работать) Питонистов много, но нужных нет)
Добавьте таймкоды.
Где первая задачка, где вторая.
И готовые решения.
Простите, но по факту, стоит некая задача прогеру. Он сортировкой не будет пользоваться? Будет тратить время? Ни ужели на конечном продукте есть время и желание скорость расчитывать? Я про массовые задачи!
Тупо проверяют как ты мыслишь и может в определеных ситуациях не будешь сортировкой пользоваться, так как это сильно замедлит работу сервиса или программы
Если высоконагруженный сервис, то будет и время, и желание.
задача на монотонность, где не надо смотреть возрастает, убывает или вообще из одного числа состоит, идем с 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
@Константин а первый элемент тоже надо проверять, так что с нуля
@Константин вы не поняли идею алгоритма, мне кажется)
@Константин =)
Это не сложные задачи. Первая - простая, если не считать, засады с отрицательными числами. Вторая - скорее средней сложности. Сразу на ум приходит max heap, O((n-k)*log(n)) ? Надо больше решать литкод. А с деком, да, это по моему monotonic stack называется на литкоде или что то близко
Если знак минус убрать. Допустим массив [-5, 1, 4, 5] . То получится 5, 1, 4, и снова 5?
Скользящее окно пишется в пяток строк на islice, потом йелдишь max от него, и всё.
сложность n*k
да сразу ясно что в первой задаче подвох в том что отсортированный ввод может содержать отрицательние, ну и квадраты уже не будут отсортированы по умолчанию.. Роль дающего таски - это как маг 189 уровня: когда ты эту таску уже во сне видишь а испытуемый как молодой бобик - аж трясется от адреналина
Классный собекс.
Когда человек вот так вот пишет код и продумывает свои действия - это прям бальзам на душу такое смотреть.
Однако я так и не понял: он на какой грейд претендует?
А то Руслан сказал, мол, "...на джуна подумают" - т.е. он на мидла и выше претендовал по собесу?
Вроде нет, я немного неправильно выразился, такую задачку и на стажировку могут дать :)
@@ruslansitdikov7145, в общем, в Яндекс можно даже не пытаться попасть. :D
@Константин, ну, хз.
Если требование для прохождения - вот такие вот задачи, которую нужно решить оптимально за час - то вообще хз.
Я бы еще понял, если бы было все из разряда "не важно - решил или нет, нужно было просто посмотреть на то, как мозги работают", но Руслан сказал, что нужно именно решить.
И я вот вообще хз, насколько реально решить такую задачу за час, если видишь ее впервые.
Да, если уже решал - другое дело.
Но тем не менее.
@Константин, так-то никаого другого смысла, кроме того, что твои племянники шарят в алгосах, тут речи не идет.
Тут уровень стажера даже не тянет 😁
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
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 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
По моему его решение с квадратами не работает правильно и работает дольше sorted(...)
Второе задание вариант с deque:
from collections import deque
def max_in_frame(sequence, k):
res = []
if k > 0:
queue = deque()
for i in sequence:
queue.append(i)
if len(queue) == k:
res.append(max(queue))
queue.popleft()
if not res and queue:
res.append(max(queue))
return res
Решение первой задачи не рабочее. Думаю люди это чувствовали поэтому проверять не стали. По производительности лучшего решения чем 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 -- не является отсортированным массивом
А chat gpt 4 уже проходил собес ?
Вторую я так сделал:
def sectorwise(sequence, sector=2):
if not sequence or sector
Сложность O(n*k). Можно О(n).
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
А такое решение второй задачи как воспринимается?)
Если 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
Первое, что пришло в голову
Решение первой задачки
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
Всем здравствуйте. Почему нельзя было в первой задаче использовать sort() списка после возведения в квадрат ?
Потому что таким образом сложность высокая
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]
Первая задача решается просто, нет?
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а для чего намеренно усложнять? Главное - решить задачу так, чтобы код работал
А lambda использовать и map пройтись , как вариант во второй задаче, если конечно нужен Python
Так что там за проблема с GIL? Почему её нельзя решить?
Ссылки тут не дает ютуб вставить. Погуглите про Бизли и ГИЛ.
@@Bibliophilos нашел большую статью на Хабре. Но можно простыми словами, для человека, который ещё даже на джуна не претендует?
@@NoNoNo_Name GIL отпускает блокировку и отдает ОС операции ввода/вывода, плюс может некоторые функции на С языке выполнять в многопоточном режиме без блокировки. Вычисления компьютерные в основном распараллелить с джилом нельзя, потоки начинают ждать переключения поочередно и в итоге последовательный однопоточный код быстрее выполнит вычисления.
Я не профи здесь, лучше почитать статейки.
@@NoNoNo_Name Сборщик мусора автоматом убирает ненужные данные, у данных есть ссылки, и без gil может случиться такое, что нужные данные удалятся, потому что не будет никто ссылаться в одном из потоков, вроде из-за этого
Почему решающий не в колготках? Не по канону как-то
Вы считаете сложность алгоритма и пытаетесь найти самый быстрый, но при этом в каждой задаче создаёте функцию.
Алгоритм то может и будет работать быстрее, но сама программа медленнее. Почему нельзя работать сразу с массивом?
Каким образом создание функции влияет на скорость работы программы?
первая:
def pops(nums):
for i in range(len(nums)):
nums[i] **= 2
return sorted(nums)
print(pops([]))
print(pops([1, 2, 3, 4, 5, 6]))
print(pops([-5, -3, 0, 2, 10]))
или так:
def pops(nums):
return sorted([i ** 2 for i in nums])
я не знаю что такое 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)
норм же сделал? 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
}
чайник, утюг... С ДЕРЕВЯННЫХ СЧЕТОВ!
мб я не эксперт или что-то прослушал, но в первой задаче говорилось заранее, что список отсортированный, то есть на выходе ты вернешь такой же отсортированный список, если будешь просто по массиву циклом идти, но тогда вопрос, почему нельзя просто проверить каждый элемент на то, что он меньше нуля? Допустим :
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 уже формулировку задачи не помню) что там требуется?
Может я не понимаю условие, но почему нельзя быстро решить 1-ю задачу, просто добавив sorted к return.
Тоесть: return sorted([number * number for number in array])
Будет сложность n*log n (так как сортировка столько работает)
А надо за n сделать
Понял что ни на одно подобное собеседование я не пойду )А программирование будет моим хобби)
Ну, тут офк речь про очень сильных программистов, поэтому без опыта так с маху конечно очень трудно попасть, нужно быть либо книжным червём с невероятной выдержкой, либо просто иметь талант
@@inexoudi9z167 Талант тут не нужен. Здесь нужна практика чем больше ты чем то занимаешься тем легче. На должном уровне ты уже не боишься задачи,если она сложная и ты с ней не сталкивался то просто предётся больше времени на это посвятить.Как говорится глаза боятся а руки делают.
@@flurixoww по такой логике каждый второй был бы программистом. Талант к изучению одной из самых умственно затратных сфер в мире нужно иметь, если не хватает упорства или еще чего
@@inexoudi9z167 Каждый второй может быть программистом но человек просто не выдерживает. Человек не выдерживает того что вся информация и тд не лежит на поверхности . Не знаю к чему тут самая умственно затратная сфера, да может человек который занимается машинным обучением,крипто графий и тд вот там да тебе нужно будет хорошенько подумать . Но большенство задач которые тебе будут давать это что то по типу вот сделай программу которая будет отслеживать автобус по гпс , для этого не надо иметь много ума для этого требуется только время.
Ну и правильно, чтобы проходить такие собесы, нужно постоянно ходить на такие собесы и выдрачивать литкод.
Если самого не вставляет решение подобных задач, не стоит тратить кучу времени на них, лучше вложить его в выполнение каких-то прикладных задач.
Далеко не все программисты любят этот дроч с алгоритмами, и попасть на собес большая вероятность именно к такому.
def foo(numbers: list[int], k: int) -> list[int]:
return list(map(max, [numbers[i:i + k] for i in range(len(numbers) - k + 1)]))
Очень неприятный собеседующий Руслан, не хотел бы я к такому попасть на интервью, только если бы оффер был стоящий и не пришлось с ним работать в одной команде
Замечание по самому собеседованию. Если чел не вытягивает первую задачу, то он либо перенервничал, либо не знает базы. В любом случае надо было настоять на доп вопросе - написать все тесты для массива из int.
А это: все "-", переход через 0 с нолем, переход через 0 без ноля, все "+", и эти варианты с четным и нечетным массивом.
Если не вспомнить базу - дальнейший кодинг бесполезен (а как я представляю, его код тесты не пройдёт).
Ну и без указания, что квадрат от int в ряде случаев дает выход за пределы, задачу нельзя считать полностью решенной.
В питоне при выходе за пределы машинного слова число преобразуется в большое. То есть внутри питона из коробки есть длинная арифметика
Первая задачка на 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;
}
from random import randint
# для первой задачи изменить массив а, включив в него отрицательные числа (randint(-10, 10)) например
a = [(randint(1, 100)) for x in range(20)]
print(sorted([i**2 for i in a if i > 0] + [(i*(-1))*(i*(-1)) for i in a if i < 0]))
# первое решение
for i in range(len(a) - 2):
print(max(a[i:i+3]))
# второе решение
while len(a) != 3:
print(max(a[:3]))
del a[0]
def mass(resh):
nums = []
for num in resh:
if num % 2 == 0:
nums.append(num**2)
else:
nums.append(num**2)
return sorted(nums)
x = [1,2,3,4,5,6]
print(mass(x))
норм вариант
Всем привет! Подскажите первую задачу можно было бы решить в одну строку по типу (return sorted([abs(num) ** 2 for num in array])? Это было бы правильным алгоритмом?
Это был бы рабочий алгоритм, но временная сложность у него O(N^2). На больших данных можно не уложиться по времени выполнения программы. Оптимальный алгоритм у этой задачи имеет сложность O(N)
@@brossen392 а можете подсказать, почему N**2?
Насколько я вижу - сложность сортировки NlogN ну и сложность формирования самого массива N - Итого 2N * LogN - отбрасываем константы выходит N LogN
Можете подсказать как получилось N**2?
@@ПавелТаранов-э1ч я просто не был уверен какая сложность у встроенной сортировки, ошибся
Еще abs() убрать, там же квадрат
Смотрю на решение первой задачи - очень кривая простыня с кучей ветвлений. Думаю, что там полюбому ошибка будет, запускайте, а в итоге "ок, по коду будет работать" оО))
Судя по коду он будет работать и будет работать правильно.
А нельзя его запустить, чтобы проверить?😂😂😂
Ну первая задачка прям изи. Я про список
а о какой версии вообще речь идет? а то будет больно и хейта горы.))
for item in array : if item>0 : array1.append(item*item) else array2.append(item*item); array1.append(array2[::-1])
Что-то парень растерялся со второй задачей. Самый простой вариант имхо найти максимум и его индекс в первом окне и потом сравнивать новый элемент с максимумом и проверить индекс на попадание в окно. Если индекс за пределами окна - искать максимум в срезе.
ваше решение O(n^2)
@@absent6322 только если список отсортирован по убыванию. В остальных случаях где-то между On и On**2
@@yauhent671 ты же понимаешь что такое О-notation, это про худший случай, если вкратце.
@@absent6322 Da, znaju
Перед этим алгоритмом нужно проверить список на монотонность. Если он монотонно возрастающий, то ответ это сам список начиная с k. Если он монотонно убывающий, то ответ это сам список до len-k.
Если ни то ни другое, то тогда уже юзать алгоритм.
Поэтому и был вопрос про проверку на монотонность, которую, как я понимаю, можно осуществить просто путем вычитания из каждого значения списка его предыдущего значения с последующей проверкой на больше / меньше 0.
а как можно попасть на такой собес?
хард))) лайк от СЕООНЛИ!
Код первого задания у пацана не работает и не увидивитиьно но я типо не осуждаю самого пацана, но вот чел типо с яндекса или откуда он там, просто видно что когда пацан начал слишком громоздить, он перестал понимать что он делает и сделал вид что решение норм (хотя оно time limit ) да и какой O(n) approach это смешно, ощущение что тип пришел не из it сферы даже а с помойки.
Хахах я смотрю Андрей уже смеётся с задачки типо про sliding window ) What is going on ?
Я первую задачу так решил
def func(list: list) -> list:
res = []
for i in list:
res.append(i ** 2)
res.sort()
return res
Не оптимально
a = [1,2,3,4,5]
temp = []
for i in range(len(a)-2):
temp.append(max(a[i:i+3]))
print(temp) подойдет ли на 2-ой задаче?
Сложность O(n*k) , поэтому не подойдёт
@@runneso а вот такой ответ для 2 задачи подойдёт
a=[2,5,1,3,8,9]
k = 3
g = 0
while g < 4:
print(max(a[g:k+g]))
g+=1
@@runneso и что это вообще за сложности как понять какая сложность?
@@Lippaaa7596 та же самая сложность O(n*k), поэтому нет
@@Lippaaa7596 читайте про Big O notation
вы вообще о чем ???
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)
Идея решении второй задачи очень проста. О(N)
1. Для первого окна находим максимальное и предмаксимальное число
2. Начинаем итерацию по массиву с k до N (где N длина массива)
3. В каждой итерации проверяем равен ли первый элемент окна к максимальному числу
Если да - находим максимальное число из (предмаксимальное число, текущее число) и добавляем максимальное число в результативный массив и обновляем максимальное и предмаксимальное число
Если нет - находим максимальное число из (максимальное число и текущее число) и добавляем в результативный массив и не забываем обновить максимальное число и предмаксимальное число
Если правильно понял вторую задачу, то вроде как она у меня решилась следующим кодом(При условии, что k натуральное число и длинна массива больше k):
def solution(array: list[int]) -> list[int]:
nums = [random.randint(0, 20) for i in range(10)] # рандомно генерирующийся список
k = random.randint(2, 6) # рандомный размер окна
step = 0
res = []
while len(nums) >= k:
res.append(max(nums[step:k]))
step += 1
k += 1
return res
n*k, не допустимое время работы
2 задача
def bar(arr, k):
for i in range(0, len(arr) - k + 1):
indexes = (arr[x] for x in range(i, i + k))
print(max(indexes))
здесь сложность опять же n*k
1 элементарная задача
Делаем итератор который шагает сначала и с конца. o(n) по памяти o(1)
сравниваем элементы по молулю
2 задача тоже простая, берем ринг буфер от k и sortedMap
Ну и бежим по коллекции. В итоге сложномть NlogK и по памчти O(k)
Надо на литкоде будет закодить
Обе задачи решал первый раз
Где у тебя в питоне есть sortedMap?
К тому же, для второй "простой" задачи есть решение за линейное время: очередь с поддержкой максимума в левом элементе