Задача 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) засунуть и сравнивать модуль или квадрат числа с числом или квадратом числа исходного массива, если число в стеке меньше то его выводить, а потом число исходного массива.
@@alexkochevnicke5122 ну все задачи на собеседовании в Яндекс требуют оптимального решения. Поэтому и надо усложнять. Даже если ты напишешь с sorted,то тебя спросят: а как улучшить?
Интервьюер очень косноязычен. Он отвратительно формулирует задачу, а потом, когда испытуемый выполнил ровно то, что услышал, вдруг оказывается, что есть еще вводные, и он якобы недостаточно полно понял условие. Я бы извинился и прекратил бы собеседование.
абсолютно согласен. "Надо вывести квадраты всех чисел отсортированного массива". Потом его фраза "в отсортированном порядке", когда интервьювер пишет вводные, ничего не говорит о том, к чему он это добавил. Очень плохо, Яндекс
@@AlexeiGoncharov-gq8dmВ начале видео говорилось, что приглашённый - программист в Яндйексе а не интервьюер. Конечно с вами сюсюкатьая никто на собесе в яндекс не будет. Не пойму почему вы придрались к формулировке первой задачи. Человек нормально разъяснил условие, а добавил некоторые фразы так как сразу понял что кандидат не слишком умный (что собственно так и есть)
Мало того, на 29 минуте он неправильно определил сложность предложенного алгоритма как n*k. На самом деле там число сочетаний по k из n умноженное на k.
Интересный формат. Осваиваю потихоньку базу на бэкендера. Подобные задачки решаемы, но сижу над ними долго. Не представляю, как в лайв-формате можно быстро придумать решение. Для меня слишком стрессово)
@@slava_zxz Скоро будет 6 месяцев. Сейчас заканчиваю продвинутый синтаксис Питона, прошел основы SQL (Postgre, ещё хочу другую реализацию), основы html+css, и теоретическое введение в ООП. Сейчас хочу переходить к практике ООП и Джанге.
@@heybeachMIN ещё нет. Первый будет параллельно с изучением джанги. Ориентировочно через месяц. Ну и несколько ботов ещё хотел сделать, однако для них тоже нужно вникать в библиотеку.
@@davgf438 А кроме ботов, какие Вы планируете делать пет проекты? Я слышал, что создание какой-нибудь соц сети очень хороший может дать плюс при трудоустройстве... Но, наверно, это чертовски сложно и долго плюс знания фронтеда нужно, скорее всего. Вообще, я только почти закончил курс на степике Поколение python: начинающие, так что мне далеко до Вашего уровня, но всё равно заранее интересно знать, какие люди делают пет проекты.
Первую как-то сложно решали. Можно было 2 указателя: один с начала идет, второй с конца и результирующий массив заполнять с конца. Вторая интересная. С ходу придумал только за О(k*log + n*logk) + O(k) место.. Когда упомянули деки, то дошёл до O(n) + О(k) место. И вопрос: а как можно на такое жесткое собеседование попробоваться подопытным кроликом? =)
@@tahirrasuljanov7770 мне кажется он не понял условие задачи и решил слишком сложно когда можно было сделать гораздо проще. Может я чего-то не понимаю, но у меня всё решение заняло буквально 6 строчек....
Неправильно Просто идёте подряд с самого начала и до конца и добавляете в res квадраты пройденных элементов. Условие if здесь вообще ничего не дает, элементы и так расположены в порядке возрастания. Просто попробуйте в уме прогнать этот код и поймете
Если что, в 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" Очень надеюсь, что эта переписка будет кому-то полезна, и время на нее было потрачено не зря)
Решение на С++ с декой, которое я использовал. Я проверил пустой ли массив, если да, то вернуть пустой массив. Иначе я добавил в очередь квадрат нулевого элемента массива Потом по циклу проходил с первого элемента до конца. Если квадрат 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; }
В первой задаче похоже ошибка. Если в массиве нет отрицательных чисел, то в первом цикле 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 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))
Доброго дня всем! Вопросик по первой задачке) Почему её нельзя решить простой строчкой типа: sorted([i*i for i in list_test]) Или пользоваться данной функцией в решении запрещено?
@@denisbalyasnikov7185 так у тебя сложность алгоритма будет меньше, но на практике, у компьютера уходит больше времени на само создание функции. Проверено!😊
Добрый день, решение по сортировка показалось мне слишком мудреным, решил вроде как проще и понятней, тоже 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 отошлётся в си на котором питон держится, но если взять огромный массив, то разница будет заметна
Прикольное собеседование, погоняли по классическим алгосам) В последней, кстати, я подумал, нужно как-то извернуться, и придумал пару решений через рекурсию. "Разделяй и влавствуй", типо) Но не факт, что они в среднем сильно эффективнее обычного "в лоб" за O(n)
Решение второй задачи с помощью очереди - О(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
@@nikolayveselovwp793оно всегда было за O(1). Очередь сама по себе урезанный двусвязанный список. А в связанном списке добавление и удаление всегда работает за константное время. Так как в списке не нужно реаллочить память из одного участка памяти в другой, чтобы расширить или уменьшить список. Добавление в очередь происходит за счёт создания новой ссылки на новый элемент и связывание его с первым или последним элементом. Удаление работает точно также, но наоборот. Единственное, когда в списке(в очереди) происходит добавление за О(n) - это добавление или удаление в диапазоне от 1(не включительно) до последнего(не включительно)
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
@@Kirill_rus_ много бы я тебе ответил на это да думаю без толку это будет, определение по внешности это крайний призрак узкости так назову это. И да в кремневой долине таких как ты выразился не мужиков полно и они двигают мир и индустрию и это факт.
@@mementomori6005 Да что ты мне про кремневою долину поёшь, я знаю, что на западе таких гей модников пруд пруди. Если мужики начнут красить волосики, надевать серёжки, косить под котиков надевая ушки, красить ноготки, то в мире будет хаос. Так и до гей парадов недалеко. Мужчина должен быть мужественным и опрятным, а не миловидной сюсей с ушками на бошке. И ладно если это ребёнок или девушка, но чтобы парень... Не, мир сходит сума. А такие как ты, кричат УРА на гей парадах ). Когда у тебя появится сын, и в 25 лет он подойдёт к тебе в латексных, обтягивающих штанишках с вырезом на попе, с волосами цвета радуги, накрашенными ресничками, напудренным носиком, и в розовой футболке с блёстками, и скажет: "папууууль, хаюхааай, зацени миникююююр" я представляю как ты в глубине души будешь "рад" своему мужскому воспитаннику))) . Ты скорее всего молодой ещё и на тиктоках и тупых блогерах поехал не в то русло. Но это моё мнение, ты можешь красить губы и не обращать на меня внимание )
первая задач с оптимизацией - это 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)
попробовал решить вторую задачу через деку и с минимальным обращением к мах(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) т.к. будешь каждый раз максимум пересчитывать
Может я не понимаю условие, но почему нельзя быстро решить 1-ю задачу, просто добавив sorted к return. Тоесть: return sorted([number * number for number in array])
не знаю что по сложности, не разбирался еще в этом но решения такие получились: 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 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
@@NoNoNo_Name GIL отпускает блокировку и отдает ОС операции ввода/вывода, плюс может некоторые функции на С языке выполнять в многопоточном режиме без блокировки. Вычисления компьютерные в основном распараллелить с джилом нельзя, потоки начинают ждать переключения поочередно и в итоге последовательный однопоточный код быстрее выполнит вычисления. Я не профи здесь, лучше почитать статейки.
@@NoNoNo_Name Сборщик мусора автоматом убирает ненужные данные, у данных есть ссылки, и без gil может случиться такое, что нужные данные удалятся, потому что не будет никто ссылаться в одном из потоков, вроде из-за этого
решал вторую задачу на литкод 3 года назад, даже уже и забыл что решал. сначала придумал решение с мультесетом, прошло прям на грани, потом придумал решение на очереди на стеках с максимумом хехехехе, а финальный вариант тоже с очередью и монотонно невозрастающей последовательностью)))
максимум на окне можно решить двумя стеками из пар. Я заполняю первый стек, пока он не размера k, заполняю скмим числом, и минимумом на префиксе . Далее я все элементы этого стека перекидываю во второй, пересчитывая новые минимумы от обратной стороны, теперь элементы в обратном порядке,, т. е сверху-первый(0) элемент массива. Теперь я начинаю опять заполнять первый стек, удаляя при этом элемент из второгг, я легко могу вычислить минмум на окне, это будет минимум из двух минимумов сверху стеков. Ну и повторяю это, пока не пройдусь по всему массиву
Ну, тут офк речь про очень сильных программистов, поэтому без опыта так с маху конечно очень трудно попасть, нужно быть либо книжным червём с невероятной выдержкой, либо просто иметь талант
@@inexoudi9z167 Талант тут не нужен. Здесь нужна практика чем больше ты чем то занимаешься тем легче. На должном уровне ты уже не боишься задачи,если она сложная и ты с ней не сталкивался то просто предётся больше времени на это посвятить.Как говорится глаза боятся а руки делают.
@@flurixoww по такой логике каждый второй был бы программистом. Талант к изучению одной из самых умственно затратных сфер в мире нужно иметь, если не хватает упорства или еще чего
@@inexoudi9z167 Каждый второй может быть программистом но человек просто не выдерживает. Человек не выдерживает того что вся информация и тд не лежит на поверхности . Не знаю к чему тут самая умственно затратная сфера, да может человек который занимается машинным обучением,крипто графий и тд вот там да тебе нужно будет хорошенько подумать . Но большенство задач которые тебе будут давать это что то по типу вот сделай программу которая будет отслеживать автобус по гпс , для этого не надо иметь много ума для этого требуется только время.
Ну и правильно, чтобы проходить такие собесы, нужно постоянно ходить на такие собесы и выдрачивать литкод. Если самого не вставляет решение подобных задач, не стоит тратить кучу времени на них, лучше вложить его в выполнение каких-то прикладных задач. Далеко не все программисты любят этот дроч с алгоритмами, и попасть на собес большая вероятность именно к такому.
Всем привет! Подскажите первую задачу можно было бы решить в одну строку по типу (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?
Простите, но по факту, стоит некая задача прогеру. Он сортировкой не будет пользоваться? Будет тратить время? Ни ужели на конечном продукте есть время и желание скорость расчитывать? Я про массовые задачи!
Тупо проверяют как ты мыслишь и может в определеных ситуациях не будешь сортировкой пользоваться, так как это сильно замедлит работу сервиса или программы
Задача 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
Второе задание вариант с 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
да сразу ясно что в первой задаче подвох в том что отсортированный ввод может содержать отрицательние, ну и квадраты уже не будут отсортированы по умолчанию.. Роль дающего таски - это как маг 189 уровня: когда ты эту таску уже во сне видишь а испытуемый как молодой бобик - аж трясется от адреналина
Ребята, извините, а по первой задачке так сделать нельзя было: arr = [-5, 1, 2, 3] squared_arr = [x**2 for x in arr] sorted_numbers = sorted(squared_arr, reverse=False) ?
Решение первой задачи не рабочее. Думаю люди это чувствовали поэтому проверять не стали. По производительности лучшего решения чем sorted([num * num for num in arr]) На следующих входных данных я не нашёл. solution([-5000, -3, -2, -1, 0, 1, 2, 3, 4, 5000] * 50000)
мб я не эксперт или что-то прослушал, но в первой задаче говорилось заранее, что список отсортированный, то есть на выходе ты вернешь такой же отсортированный список, если будешь просто по массиву циклом идти, но тогда вопрос, почему нельзя просто проверить каждый элемент на то, что он меньше нуля? Допустим : 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)
Классный собекс. Когда человек вот так вот пишет код и продумывает свои действия - это прям бальзам на душу такое смотреть. Однако я так и не понял: он на какой грейд претендует? А то Руслан сказал, мол, "...на джуна подумают" - т.е. он на мидла и выше претендовал по собесу?
@Константин, ну, хз. Если требование для прохождения - вот такие вот задачи, которую нужно решить оптимально за час - то вообще хз. Я бы еще понял, если бы было все из разряда "не важно - решил или нет, нужно было просто посмотреть на то, как мозги работают", но Руслан сказал, что нужно именно решить. И я вот вообще хз, насколько реально решить такую задачу за час, если видишь ее впервые. Да, если уже решал - другое дело. Но тем не менее.
задача на монотонность, где не надо смотреть возрастает, убывает или вообще из одного числа состоит, идем с 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
Первая задачка на 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; }
Это не сложные задачи. Первая - простая, если не считать, засады с отрицательными числами. Вторая - скорее средней сложности. Сразу на ум приходит max heap, O((n-k)*log(n)) ? Надо больше решать литкод. А с деком, да, это по моему monotonic stack называется на литкоде или что то близко
А такое решение второй задачи как воспринимается?) Если 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 Первое, что пришло в голову
В первой задаче не проще ли было: 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)
Решение первой задачки 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
Вы считаете сложность алгоритма и пытаетесь найти самый быстрый, но при этом в каждой задаче создаёте функцию. Алгоритм то может и будет работать быстрее, но сама программа медленнее. Почему нельзя работать сразу с массивом?
1 элементарная задача Делаем итератор который шагает сначала и с конца. o(n) по памяти o(1) сравниваем элементы по молулю 2 задача тоже простая, берем ринг буфер от k и sortedMap Ну и бежим по коллекции. В итоге сложномть NlogK и по памчти O(k) Надо на литкоде будет закодить Обе задачи решал первый раз
Где у тебя в питоне есть sortedMap? К тому же, для второй "простой" задачи есть решение за линейное время: очередь с поддержкой максимума в левом элементе
Очень неприятный собеседующий Руслан, не хотел бы я к такому попасть на интервью, только если бы оффер был стоящий и не пришлось с ним работать в одной команде
def search_max(array: list[int], k) -> list[int]: n = 0 lst_real = [] lst = [] for x in array: if n == k: lst_real.append(max(lst)) lst = [] lst.append(x) n = 0 else: lst.append(x) n += 1 lst_real.append(max(lst)) return lst_real
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
Замечание по самому собеседованию. Если чел не вытягивает первую задачу, то он либо перенервничал, либо не знает базы. В любом случае надо было настоять на доп вопросе - написать все тесты для массива из int. А это: все "-", переход через 0 с нолем, переход через 0 без ноля, все "+", и эти варианты с четным и нечетным массивом. Если не вспомнить базу - дальнейший кодинг бесполезен (а как я представляю, его код тесты не пройдёт). Ну и без указания, что квадрат от int в ряде случаев дает выход за пределы, задачу нельзя считать полностью решенной.
Задача 1. 1. Проверить входной на пустоту вернуть пусто. 2. Проверить входной на все не отрицательные ответ из начала видео. 3. Проверить входной на все отрицательные либо ноль в конце, решение как во втором варианте, но берём числа с конца в начало. 4. Для варианта и минус и плюс двумя указателями с начала и конца пишем в конец выходного массива созданного заранее сдвигаясь в начало большее из чисел по модулю возведенное в квадрат и сдвигаем указатели пока они не станут равны. При равенстве указателей дописываем квадрат последнего числа.
@@igormyatlyuk503 это как и многие решения зависит от условий. Через list comprehension во втором и третьем варианте будет гораздо быстрее чем через четвертый, особенно на длинных списках. Хотя можно и без них обойтись, код станет компактнее, но всегда будет "тормозной"
@@igormyatlyuk503 понятно, что на практике, зачастую, массив данных небольшой и при его обработке используем оверхэд. Но, если добиваться максимальной производительности, то только с 2. и 3. Тем более, для проверки в 2. надо только убедиться, что первый элемент >=0, а в 3. - что последний
Что-то парень растерялся со второй задачей. Самый простой вариант имхо найти максимум и его индекс в первом окне и потом сравнивать новый элемент с максимумом и проверить индекс на попадание в окно. Если индекс за пределами окна - искать максимум в срезе.
Перед этим алгоритмом нужно проверить список на монотонность. Если он монотонно возрастающий, то ответ это сам список начиная с k. Если он монотонно убывающий, то ответ это сам список до len-k. Если ни то ни другое, то тогда уже юзать алгоритм. Поэтому и был вопрос про проверку на монотонность, которую, как я понимаю, можно осуществить просто путем вычитания из каждого значения списка его предыдущего значения с последующей проверкой на больше / меньше 0.
вторую решил оч быстро так: 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 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)) норм вариант
За день до собеса посмотрел это видео, попалась задачка с квадратами. Так что спасибо за контент=)
затянул?
@@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б Чувак, вайтишники должны видеть до чего ИТ доводит)
спасибо за троллинг баянистого переворота строки, это было хорошо :)
Интервьюер очень косноязычен. Он отвратительно формулирует задачу, а потом, когда испытуемый выполнил ровно то, что услышал, вдруг оказывается, что есть еще вводные, и он якобы недостаточно полно понял условие. Я бы извинился и прекратил бы собеседование.
абсолютно согласен. "Надо вывести квадраты всех чисел отсортированного массива". Потом его фраза "в отсортированном порядке", когда интервьювер пишет вводные, ничего не говорит о том, к чему он это добавил. Очень плохо, Яндекс
@@AlexeiGoncharov-gq8dmВ начале видео говорилось, что приглашённый - программист в Яндйексе а не интервьюер. Конечно с вами сюсюкатьая никто на собесе в яндекс не будет. Не пойму почему вы придрались к формулировке первой задачи. Человек нормально разъяснил условие, а добавил некоторые фразы так как сразу понял что кандидат не слишком умный (что собственно так и есть)
@@silentlyow у Яндекса собез слабый, если что) собственно оттуда и такие сотрудники, которые сформулировать таск не в состоянии)
Да, он фиговый
Мало того, на 29 минуте он неправильно определил сложность предложенного алгоритма как n*k. На самом деле там число сочетаний по k из n умноженное на k.
Интересный формат. Осваиваю потихоньку базу на бэкендера. Подобные задачки решаемы, но сижу над ними долго. Не представляю, как в лайв-формате можно быстро придумать решение. Для меня слишком стрессово)
@@slava_zxz Скоро будет 6 месяцев. Сейчас заканчиваю продвинутый синтаксис Питона, прошел основы SQL (Postgre, ещё хочу другую реализацию), основы html+css, и теоретическое введение в ООП. Сейчас хочу переходить к практике ООП и Джанге.
@@slava_zxz удачи нам в этом деле! Главное не терять мотивации
@@davgf438 а вы делали какие-то пет проекты?
@@heybeachMIN ещё нет. Первый будет параллельно с изучением джанги. Ориентировочно через месяц. Ну и несколько ботов ещё хотел сделать, однако для них тоже нужно вникать в библиотеку.
@@davgf438 А кроме ботов, какие Вы планируете делать пет проекты? Я слышал, что создание какой-нибудь соц сети очень хороший может дать плюс при трудоустройстве... Но, наверно, это чертовски сложно и долго плюс знания фронтеда нужно, скорее всего.
Вообще, я только почти закончил курс на степике Поколение python: начинающие, так что мне далеко до Вашего уровня, но всё равно заранее интересно знать, какие люди делают пет проекты.
Первую как-то сложно решали. Можно было 2 указателя: один с начала идет, второй с конца и результирующий массив заполнять с конца.
Вторая интересная. С ходу придумал только за О(k*log + n*logk) + O(k) место.. Когда упомянули деки, то дошёл до O(n) + О(k) место.
И вопрос: а как можно на такое жесткое собеседование попробоваться подопытным кроликом? =)
Если студент практикума - то через трудоустройство. Если нет - будет розыгрышь среди подписчиков в телеге t.me/UA-camPronin
Брат, где ты учился? Я даже после того как он решил еле как понял😭
@@tahirrasuljanov7770 мне кажется он не понял условие задачи и решил слишком сложно когда можно было сделать гораздо проще. Может я чего-то не понимаю, но у меня всё решение заняло буквально 6 строчек....
@@frogsfrogsx скинь решение
@@frogsfrogsx my_list = [3, 4, 5, 8, 2, 3, 1]
for i in sorted(my_list):
print(i ** 2)
Задача 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 здесь вообще ничего не дает, элементы и так расположены в порядке возрастания. Просто попробуйте в уме прогнать этот код и поймете
Если что, в 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"
Очень надеюсь, что эта переписка будет кому-то полезна, и время на нее было потрачено не зря)
Решение первой задачки со сложностью 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]
Уровня хард литкода последняя задача ) на открытии Яндекс.Тренировок по алгосам сказали, что задачки «с легким налётом мидл» попадаются на собесах)))
медиум, не выше
@@novoidx4322 вторая задача хард
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 строку
Решение на С++ с декой, которое я использовал.
Я проверил пустой ли массив, если да, то вернуть пустой массив. Иначе я добавил в очередь квадрат нулевого элемента массива
Потом по циклу проходил с первого элемента до конца. Если квадрат 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;
}
Это решение получилось компактнее, чем первое, но по памяти заняло больше
@@Гычпукхеровое решение
Вторая задача Hard на leetcode: Sliding Window Maximum
В первой задаче похоже ошибка. Если в массиве нет отрицательных чисел, то в первом цикле 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 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))
Жестко, но интересно, Ян молодец.
Доброго дня всем! Вопросик по первой задачке) Почему её нельзя решить простой строчкой типа:
sorted([i*i for i in list_test])
Или пользоваться данной функцией в решении запрещено?
Можно, но тогда получится сложность nlogn + n, а хочется решить просто за n (благо исходный массив уже отсортирован)
@@denisbalyasnikov7185 благодарю за ответ! 🙏
К тому же i*i вернет положительное число в случае входящего отрицательного
@@denisbalyasnikov7185 зато sort отработает в любом случае быстрее, чем любой велосипед на питоне, т.к. у него плюсы под капотом
@@denisbalyasnikov7185 так у тебя сложность алгоритма будет меньше, но на практике, у компьютера уходит больше времени на само создание функции. Проверено!😊
вторая:
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]))
Добрый день, решение по сортировка показалось мне слишком мудреным, решил вроде как проще и понятней, тоже 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 отошлётся в си на котором питон держится, но если взять огромный массив, то разница будет заметна
Берём 1 элемент массива, умножаем на самого себя. Есть до операции умножения он был меньше 0, то полученый результат - умножаем на - 1.
Прикольное собеседование, погоняли по классическим алгосам) В последней, кстати, я подумал, нужно как-то извернуться, и придумал пару решений через рекурсию. "Разделяй и влавствуй", типо) Но не факт, что они в среднем сильно эффективнее обычного "в лоб" за O(n)
Решение второй задачи с помощью очереди - О(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)
немного покомпактнее
Слишком много кода
Отличный собес с ушками =) очень позитивно, не хватает такого, а то все(большинство) как люди роботы сидят, жестко)))
Ян, вообще, аеселый
Ещё юбочку добавить и губки накрасить. Тьфу, что становится с мужиками...
@@Kirill_rus_ много бы я тебе ответил на это да думаю без толку это будет, определение по внешности это крайний призрак узкости так назову это. И да в кремневой долине таких как ты выразился не мужиков полно и они двигают мир и индустрию и это факт.
@@Kirill_rus_ На качество кода это не влияет, надеюсь. Я бы так одеваться не стал, но это дело каждого
@@mementomori6005 Да что ты мне про кремневою долину поёшь, я знаю, что на западе таких гей модников пруд пруди. Если мужики начнут красить волосики, надевать серёжки, косить под котиков надевая ушки, красить ноготки, то в мире будет хаос. Так и до гей парадов недалеко. Мужчина должен быть мужественным и опрятным, а не миловидной сюсей с ушками на бошке. И ладно если это ребёнок или девушка, но чтобы парень... Не, мир сходит сума. А такие как ты, кричат УРА на гей парадах ). Когда у тебя появится сын, и в 25 лет он подойдёт к тебе в латексных, обтягивающих штанишках с вырезом на попе, с волосами цвета радуги, накрашенными ресничками, напудренным носиком, и в розовой футболке с блёстками, и скажет: "папууууль, хаюхааай, зацени миникююююр" я представляю как ты в глубине души будешь "рад" своему мужскому воспитаннику))) . Ты скорее всего молодой ещё и на тиктоках и тупых блогерах поехал не в то русло. Но это моё мнение, ты можешь красить губы и не обращать на меня внимание )
первая задач с оптимизацией - это 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)
первая кст - Squares of a Sorted Array на LC
Добавьте таймкоды.
Где первая задачка, где вторая.
И готовые решения.
А почему в первой задаче нельзя отсортировать массив прям перед ретюрном?
попробовал решить вторую задачу через деку и с минимальным обращением к мах(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) т.к. будешь каждый раз максимум пересчитывать
Может я не понимаю условие, но почему нельзя быстро решить 1-ю задачу, просто добавив sorted к return.
Тоесть: return sorted([number * number for number in array])
Будет сложность n*log n (так как сортировка столько работает)
А надо за n сделать
не знаю что по сложности, не разбирался еще в этом но решения такие получились:
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
Вторая задача
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
Так что там за проблема с GIL? Почему её нельзя решить?
Ссылки тут не дает ютуб вставить. Погуглите про Бизли и ГИЛ.
@@Bibliophilos нашел большую статью на Хабре. Но можно простыми словами, для человека, который ещё даже на джуна не претендует?
@@NoNoNo_Name GIL отпускает блокировку и отдает ОС операции ввода/вывода, плюс может некоторые функции на С языке выполнять в многопоточном режиме без блокировки. Вычисления компьютерные в основном распараллелить с джилом нельзя, потоки начинают ждать переключения поочередно и в итоге последовательный однопоточный код быстрее выполнит вычисления.
Я не профи здесь, лучше почитать статейки.
@@NoNoNo_Name Сборщик мусора автоматом убирает ненужные данные, у данных есть ссылки, и без gil может случиться такое, что нужные данные удалятся, потому что не будет никто ссылаться в одном из потоков, вроде из-за этого
В первой задаче можно же было использовать sorted([x**2 for x in numbers])? Или нет?
Нет
Они это обговаривали в самом начале, там сложность O(n log n) не подошла, да и интервьюеру часто интересно как мыслит интервьюируемый
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(...)
первая простая очень если делать линейку по памяти, если на собесе попросят сделать константу, то это гроб с 4 указателями)
Константа по памяти - в смысле с записью ответа во входной массив?
Ну да, неприятно выходит
Если знак минус убрать. Допустим массив [-5, 1, 4, 5] . То получится 5, 1, 4, и снова 5?
Нравятся такие курсы и собесы, где учат алгоритмам, а не работать) Питонистов много, но нужных нет)
А lambda использовать и map пройтись , как вариант во второй задаче, если конечно нужен Python
Вторую я так сделал:
def sectorwise(sequence, sector=2):
if not sequence or sector
Сложность O(n*k). Можно О(n).
решал вторую задачу на литкод 3 года назад, даже уже и забыл что решал. сначала придумал решение с мультесетом, прошло прям на грани, потом придумал решение на очереди на стеках с максимумом хехехехе, а финальный вариант тоже с очередью и монотонно невозрастающей последовательностью)))
я решал где-то полгода назад, сделал с помощью стека максимумов, это прям первое что приходит в голову, если знать про очередь на двух стеках.
максимум на окне можно решить двумя стеками из пар.
Я заполняю первый стек, пока он не размера k, заполняю скмим числом, и минимумом на префиксе . Далее я все элементы этого стека перекидываю во второй, пересчитывая новые минимумы от обратной стороны, теперь элементы в обратном порядке,, т. е сверху-первый(0) элемент массива.
Теперь я начинаю опять заполнять первый стек, удаляя при этом элемент из второгг, я легко могу вычислить минмум на окне, это будет минимум из двух минимумов сверху стеков. Ну и повторяю это, пока не пройдусь по всему массиву
Понял что ни на одно подобное собеседование я не пойду )А программирование будет моим хобби)
Ну, тут офк речь про очень сильных программистов, поэтому без опыта так с маху конечно очень трудно попасть, нужно быть либо книжным червём с невероятной выдержкой, либо просто иметь талант
@@inexoudi9z167 Талант тут не нужен. Здесь нужна практика чем больше ты чем то занимаешься тем легче. На должном уровне ты уже не боишься задачи,если она сложная и ты с ней не сталкивался то просто предётся больше времени на это посвятить.Как говорится глаза боятся а руки делают.
@@flurixoww по такой логике каждый второй был бы программистом. Талант к изучению одной из самых умственно затратных сфер в мире нужно иметь, если не хватает упорства или еще чего
@@inexoudi9z167 Каждый второй может быть программистом но человек просто не выдерживает. Человек не выдерживает того что вся информация и тд не лежит на поверхности . Не знаю к чему тут самая умственно затратная сфера, да может человек который занимается машинным обучением,крипто графий и тд вот там да тебе нужно будет хорошенько подумать . Но большенство задач которые тебе будут давать это что то по типу вот сделай программу которая будет отслеживать автобус по гпс , для этого не надо иметь много ума для этого требуется только время.
Ну и правильно, чтобы проходить такие собесы, нужно постоянно ходить на такие собесы и выдрачивать литкод.
Если самого не вставляет решение подобных задач, не стоит тратить кучу времени на них, лучше вложить его в выполнение каких-то прикладных задач.
Далеко не все программисты любят этот дроч с алгоритмами, и попасть на собес большая вероятность именно к такому.
А chat gpt 4 уже проходил собес ?
Ну первая задачка прям изи. Я про список
Всем здравствуйте. Почему нельзя было в первой задаче использовать sort() списка после возведения в квадрат ?
Потому что таким образом сложность высокая
Когда прошёл курс по программированию на питон от скиллбокс
Всем привет! Подскажите первую задачу можно было бы решить в одну строку по типу (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() убрать, там же квадрат
Простите, но по факту, стоит некая задача прогеру. Он сортировкой не будет пользоваться? Будет тратить время? Ни ужели на конечном продукте есть время и желание скорость расчитывать? Я про массовые задачи!
Тупо проверяют как ты мыслишь и может в определеных ситуациях не будешь сортировкой пользоваться, так как это сильно замедлит работу сервиса или программы
Если высоконагруженный сервис, то будет и время, и желание.
Что за жесть 😱
Яндекс.
хард))) лайк от СЕООНЛИ!
Задача 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
Опозорился, как только появился в кадре 😮
Второе задание вариант с 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
первая:
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])
да сразу ясно что в первой задаче подвох в том что отсортированный ввод может содержать отрицательние, ну и квадраты уже не будут отсортированы по умолчанию.. Роль дающего таски - это как маг 189 уровня: когда ты эту таску уже во сне видишь а испытуемый как молодой бобик - аж трясется от адреналина
Скользящее окно пишется в пяток строк на islice, потом йелдишь max от него, и всё.
сложность n*k
Жостко
Ребята, извините, а по первой задачке так сделать нельзя было:
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 -- не является отсортированным массивом
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]
мб я не эксперт или что-то прослушал, но в первой задаче говорилось заранее, что список отсортированный, то есть на выходе ты вернешь такой же отсортированный список, если будешь просто по массиву циклом идти, но тогда вопрос, почему нельзя просто проверить каждый элемент на то, что он меньше нуля? Допустим :
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 уже формулировку задачи не помню) что там требуется?
Классный собекс.
Когда человек вот так вот пишет код и продумывает свои действия - это прям бальзам на душу такое смотреть.
Однако я так и не понял: он на какой грейд претендует?
А то Руслан сказал, мол, "...на джуна подумают" - т.е. он на мидла и выше претендовал по собесу?
Вроде нет, я немного неправильно выразился, такую задачку и на стажировку могут дать :)
@@ruslansitdikov7145, в общем, в Яндекс можно даже не пытаться попасть. :D
@Константин, ну, хз.
Если требование для прохождения - вот такие вот задачи, которую нужно решить оптимально за час - то вообще хз.
Я бы еще понял, если бы было все из разряда "не важно - решил или нет, нужно было просто посмотреть на то, как мозги работают", но Руслан сказал, что нужно именно решить.
И я вот вообще хз, насколько реально решить такую задачу за час, если видишь ее впервые.
Да, если уже решал - другое дело.
Но тем не менее.
@Константин, так-то никаого другого смысла, кроме того, что твои племянники шарят в алгосах, тут речи не идет.
Тут уровень стажера даже не тянет 😁
а о какой версии вообще речь идет? а то будет больно и хейта горы.))
задача на монотонность, где не надо смотреть возрастает, убывает или вообще из одного числа состоит, идем с 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
@Константин а первый элемент тоже надо проверять, так что с нуля
@Константин вы не поняли идею алгоритма, мне кажется)
@Константин =)
Первая задачка на 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;
}
Это не сложные задачи. Первая - простая, если не считать, засады с отрицательными числами. Вторая - скорее средней сложности. Сразу на ум приходит max heap, O((n-k)*log(n)) ? Надо больше решать литкод. А с деком, да, это по моему monotonic stack называется на литкоде или что то близко
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)
чайник, утюг... С ДЕРЕВЯННЫХ СЧЕТОВ!
А такое решение второй задачи как воспринимается?)
Если 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
Первое, что пришло в голову
В первой задаче не проще ли было:
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) решить
а как можно попасть на такой собес?
Решение первой задачки
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
Вы считаете сложность алгоритма и пытаетесь найти самый быстрый, но при этом в каждой задаче создаёте функцию.
Алгоритм то может и будет работать быстрее, но сама программа медленнее. Почему нельзя работать сразу с массивом?
Каким образом создание функции влияет на скорость работы программы?
Почему решающий не в колготках? Не по канону как-то
1 элементарная задача
Делаем итератор который шагает сначала и с конца. o(n) по памяти o(1)
сравниваем элементы по молулю
2 задача тоже простая, берем ринг буфер от k и sortedMap
Ну и бежим по коллекции. В итоге сложномть NlogK и по памчти O(k)
Надо на литкоде будет закодить
Обе задачи решал первый раз
Где у тебя в питоне есть sortedMap?
К тому же, для второй "простой" задачи есть решение за линейное время: очередь с поддержкой максимума в левом элементе
Очень неприятный собеседующий Руслан, не хотел бы я к такому попасть на интервью, только если бы оффер был стоящий и не пришлось с ним работать в одной команде
Решение первой задачи я отказалсь понимать, что-то он там намудрил.)))
вот мое решение:
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
Минут за 10 решил последнюю задачу , но код очень корявым у меня получился (
def search_max(array: list[int], k) -> list[int]:
n = 0
lst_real = []
lst = []
for x in array:
if n == k:
lst_real.append(max(lst))
lst = []
lst.append(x)
n = 0
else:
lst.append(x)
n += 1
lst_real.append(max(lst))
return lst_real
Огонь, если получился
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
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
Я первую задачу так решил
def func(list: list) -> list:
res = []
for i in list:
res.append(i ** 2)
res.sort()
return res
Не оптимально
Замечание по самому собеседованию. Если чел не вытягивает первую задачу, то он либо перенервничал, либо не знает базы. В любом случае надо было настоять на доп вопросе - написать все тесты для массива из int.
А это: все "-", переход через 0 с нолем, переход через 0 без ноля, все "+", и эти варианты с четным и нечетным массивом.
Если не вспомнить базу - дальнейший кодинг бесполезен (а как я представляю, его код тесты не пройдёт).
Ну и без указания, что квадрат от int в ряде случаев дает выход за пределы, задачу нельзя считать полностью решенной.
В питоне при выходе за пределы машинного слова число преобразуется в большое. То есть внутри питона из коробки есть длинная арифметика
Задача 1.
1. Проверить входной на пустоту вернуть пусто.
2. Проверить входной на все не отрицательные ответ из начала видео.
3. Проверить входной на все отрицательные либо ноль в конце, решение как во втором варианте, но берём числа с конца в начало.
4. Для варианта и минус и плюс двумя указателями с начала и конца пишем в конец выходного массива созданного заранее сдвигаясь в начало большее из чисел по модулю возведенное в квадрат и сдвигаем указатели пока они не станут равны. При равенстве указателей дописываем квадрат последнего числа.
Нужен только 4 пункт. Ну 1 можно, хотя и необязательно. 2 и 3 лишние
@@igormyatlyuk503 это как и многие решения зависит от условий. Через list comprehension во втором и третьем варианте будет гораздо быстрее чем через четвертый, особенно на длинных списках. Хотя можно и без них обойтись, код станет компактнее, но всегда будет "тормозной"
@@igormyatlyuk503 понятно, что на практике, зачастую, массив данных небольшой и при его обработке используем оверхэд. Но, если добиваться максимальной производительности, то только с 2. и 3. Тем более, для проверки в 2. надо только убедиться, что первый элемент >=0, а в 3. - что последний
Слишком много проверок. Алгоритм должен работать при люьрц длинне
Что-то парень растерялся со второй задачей. Самый простой вариант имхо найти максимум и его индекс в первом окне и потом сравнивать новый элемент с максимумом и проверить индекс на попадание в окно. Если индекс за пределами окна - искать максимум в срезе.
ваше решение O(n^2)
@@absent6322 только если список отсортирован по убыванию. В остальных случаях где-то между On и On**2
@@yauhent671 ты же понимаешь что такое О-notation, это про худший случай, если вкратце.
@@absent6322 Da, znaju
Перед этим алгоритмом нужно проверить список на монотонность. Если он монотонно возрастающий, то ответ это сам список начиная с k. Если он монотонно убывающий, то ответ это сам список до len-k.
Если ни то ни другое, то тогда уже юзать алгоритм.
Поэтому и был вопрос про проверку на монотонность, которую, как я понимаю, можно осуществить просто путем вычитания из каждого значения списка его предыдущего значения с последующей проверкой на больше / меньше 0.
Очень интересно, но ничего не понятно))
вторую решил оч быстро так:
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)
почему так? потому что входные данные могут быть большими и не помещаться в память.
Судя по коду он будет работать и будет работать правильно.
А нельзя его запустить, чтобы проверить?😂😂😂
Смотрю на решение первой задачи - очень кривая простыня с кучей ветвлений. Думаю, что там полюбому ошибка будет, запускайте, а в итоге "ок, по коду будет работать" оО))
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
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))
норм вариант
6:50 Если при поиске работы программистом придётся конкурировать с такими дарованиями, то шансы есть 👍 спасибо за мотивацию😁
Первая задача решается просто, нет?
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а для чего намеренно усложнять? Главное - решить задачу так, чтобы код работал
вы вообще о чем ???
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)
а что за онлайн редактор кода используется?
Яндекса для собесов онлайн редактор