Так, погодите... Да ведь это одна из тем задания №27 на ЕГЭ по информатике. Формулировки задания очень похожие, и на 2 первичных балла нужно написать решение как раз за O(N).
@@runneso Да, наличие отрицательных чисел существенно влияет на способ решения. Задания с отрицательными числами пока официально не встречались, но во всяких тренировочных сборниках изредка попадаются. Зато можно почти серьёзно говорить старшеклассникам: осилите 27-е - получите задел на FAANG.
Ребят, я 5 лет работаю разрабом, у меня два высших, но я сейчас егэ по информатике глянула и не смогла там почти ничего решить😅 современные выпускники, похоже, гении))
Класс! Спасибо за полезные видео. Снимай плиз пару выпусков про то, кто ты и как "докатился" до такой жизни, про свой опыт в бигтехе и фишечки, которые ты рекомендовал бы себе- младшему.
Вот жаль, что такое разом не приходит в голову. Сначала о втором способе подумал. Но логично ведь, что можно просто концы обрезать до 5. Мне в голову пришла идея где мы по массиву змейкой вперёд и назад идём постоянно сокращая на один шаг с каждой сменой направления, при этом, меняя направление, мы обнуляем сумму цифр и так пока числа не встретятся, вроде O(n), но скорее всего медленнее, правда и памяти лишней не затронет. Все варианты как раз высчитывает, ведь нет разницы с какой стороны подмассивы считать. Надо бы алгоритмы прокачать
Если нет опыта решения подобных задач (недавнего причем) то придумать самое быстро решение на собесе за 20 мин это какая то фантастика. IQ 150+ надо иметь наверн. Если дома посидеть спокойно, то за часик-2 конечно можно ну или с набитой рукой врываться на собесы. Контент в кайф кнчн)
Я бы хотел поправить автора видео. Дело в том, что приобьяснении он говорит про итерацию по числам справа. Но по делу, скрипт работает с нулевым и последующими елементами. Для того, что бы реализовать процесс как было обьясненно. Нужно ко второму циклу накинуть +1 и в сумму в первом цикле обьявить как елемент по которому итерируемся.. плюс условия по проверке так же изменить на начало.
мой способ менее эффективный, потому что я использовал поиск в массиве, а не в хэш таблице создаём массив префиксных сумм, потом проходимся по нему и ищем есть ли в нём (текущий элемент-5)
@@MaruiInfantry только для некоторых компаний это основной критерий и от алгоритмов зависит скорость работы программ, не важно на каком языке. Собесился в яндекс, рассказал хорошо теорию и свой опыт, но с задачей долго ковырялся и из за этого не взяли
да вот ничего подобного, первым в голову не такая дичь пришла), просто складываю все подряд слева направа в цикле и когда сложение выдает 5 то в счетчике +1, потом новый цикл со следующего индекса, и так 8 циклов с перебором (сложением) (длинна массива 8 - 8 циклов, с 1 элемента, потом со второго и т.д.). досмотрел ролик и подумал что мое решение получше будет)...
По жд едут 70 вагонов с насыпными грузами, каждый взвешен с точностью до килограма и значения не повторяются. От ржд приходит документ что во всем поезде едет 4 груза: зерно 940000 кг, пшено 800000 кг ,яблоки 250000 кг, картошка . Вагоны на станциях перецеплялись все опломбировано и вскрывать нельзя, вам нужно найти только яблоки .... если интересно расскажу решение )
Привет! Спасибо за твои видео! Очень интересно. Да и вообще классно знать что где-то есть люди, которые хорошо зарабатывают (предполагаю что в Лондоне программисту хорошо платят) но при этом они могут адекватно и доброжелательно излагать мысли. У меня только вопрос, а лично тебе какая польза от этого? Особенно вызывает удивление что рассказываешь на русском.
Вот у меня тоже возник вопрос, если я правильно понял, похожий, что будет, если после того, как мы взяли в ответ количество подмассивов с суммой 4, например, а потом снова плавится подмассив с такой же суммой и он нам снова потребуется. Тогда в ответе появится лишний +1 в ответе.
не очень понимаю зачем третий цикл for, когда первые два уже покроют все возможные варианты. Все что написано в третьем цикле можно написать во втором, а по выходу из второго цикла обнулять подсумму. Получится сложность О(n^2). А да посмотрел дальше ролик, это его второе решение. Ну тогда зачем вообще было говорить о первом решении, оно вообще искусственное, придуманное ради того, чтоб было, так можно и 10 циклов друг в друга вложить ради кол-ва.
Из неприятного для таких задач, самостоятельно придумать финальное решение довольно сложно, те после объяснения то понятно, но сам с ходу можешь придумать только второй вариант за N^2
from collections import defaultdict ... prefix_sum_count = defaultdict(int, {0: 1}) for num in nums: subarray_sum += num answer += prefix_sum_count(subarray_sum - k) prefix_sum_count[subarray_sum] += 1
Або ми по гіршому варіанту оцініюємо, або по середньому ) Чого б це хеш-мапа в гіршому випадку працювала, як O(1)? Вона буде працювати, як O(n) То ж, загальна склпжність за часом буде O(n^2) + пам'яті O(n)
Сначала подумал, что это задачка, которую я вчера решал на Литкоде. Аж охренел ))) Но там попроще, там просто надо найти ключи двух элементов, дающих в сумме ту же 5 (здесь нет решений). Решается элементарно через два for. Тут посложнее задачка.
Являюсь front end разработчиком порядка 6 лет, за все время, как ни пытался, так и не понимаю, вообще ни в какую все алгоритмы, задачи решать не умею, пересмотрел уже миллиард ресурсов и обучающих видео, все равно ничего не понятно, на сегодня спасает chatGpt. Буду рад совету что делать в такой ситуации, может какую-то литературу или курсы.
Привет! Тоже фронтендер, но поменьше) Решать задачи, просто решать задачи, тренировать мозг и глаза, формировать насмотренность. имхо такая микросфера, где опыт очень сильно решает. Я открываю Литкод - делаю простые - усложняю, пока не сломаюсь - изучаю решения, записываю/учусь применять/решаю подобные. В алгосах главное уметь в пространные концепции, «Грокаем Алгоритмы» очень мне помогло в свое время с освоением и пониманием что вообще в таких задачах происходит, у тебя на самом деле есть небольшое количество концепций, которые надо изучить и, самое важно, понять, чтобы уметь применять
Кажись баг в реализации, даже 2 бага... Если subarray_sum будет 0, то в хэш запишется {0:2}, а в answer добавится то, что по ключу -5 (зачем от 0 отрезать кусок с суммой -5, чтобы получить 5?) Может случится ситуация, когда to_remove будет 0 и тогда к answer добавится 2, вместо 1 Не проверял, надо тесты погонять
[-5, 5, -5, 5] на втором шаге сумма = 0, в ансвер добавится по ключу [-5], т.е. 1, записанная на первом шаге. т.к. второй элемент [5] нам подходит как подмассив. на 4м шаге опять 0, по ключу [-5] уже значение 2, записанное туда на третьем шаге. ансвер = 1+2 = 3. это потому, то на четвертом шаге подходят два подмассива: последний элемент [5] и [5,-5,5] "зачем от 0 отрезать кусок с суммой -5, чтобы получить 5?": 0 - (-5) = 5, вот поэтому "Может случится ситуация, когда to_remove будет 0 и тогда к answer добавится 2, вместо 1": нет, в ансвер плюсуется по ключу [ту_ремув], но счетчик увеличивается по ключу [субаррай_сум] [5, 0, 0, 0, 0] начиная со второго шага ту_ремув всегда ноль, но по ключу ноль находится единица, т.к. увеличиваться постоянно значение по ключу [5]. в итоге ансвер = 1+1+1+1+1 = 5
@@SayXaNow спасибо за подробное объяснение! Действительно, даже если {0: 1} увеличивается, то всё правильно работает, и эти отрезки с 0 суммой учитываются в ответе
надо считать все числа подмассива, а вы видимо считали выборочно. для K=5 и массива [4,2,1] ответ 0, а не 1, нельзя складывать 4 и 1 без двойки. проще всего это проверить квадратичным алгоритмом с полным перебором. он дает ответ 5.
Надо говорить. 99% что задачу не поменяют, «видеть», «знать как решать» это еще не«решить», плюс 80% успеха прохождения алгоритмической сессии - много говорить, объяснять логику и трейдоффы
привет меня зовут саша лукин и я работаю в компании Гугл в ЛОНДОНЕ! Слышишь с..а, в ЛОНДОНЕ!!! Не то что ты. А я в ЛОНДОНЕ! саша лукин и в ЛОНДОНЕ! Вот я какой! Ахахаха охохохо я неипически крут!
14:17 - "но при этом мы тратим O(n) памяти" и еще мы тратим время на поиск в этой памяти "отрезаемых кусков" - O(n) в итоге время алгоритма примерно равно O(2*n)
В терминах Big O (O-большое), константы не учитываются при рассчете алгоритмической сложности, поэтому итоговая сложность записывается именно как O(n). Рекомендую подробнее почитать про оценку сложности алгоритмов.
@@asethone согласен;-) но алгоритм с O(n) используемый в цикле m раз, всегда будет быстрее, чем тот же цикл с алгоритмом с неправильной оценкой сложности O(3*n). сложности у алгоритмов одинаковы - скорости разные
@@Sergey-Primak Ну вопрос оптимизации - это уже отдельная тема. Уменьшить количество проходов по циклу после того, как ты придумал быстрое решение всегда можно успеть. Главное, и самое сложное на собеседованиях - это как раз придумать такое решение, которое именно в терминах Big O будет наиболее оптимальным. А то, что ты там лишний раз добавишь O(n) вне цикла - это никого даже не смутит, ведь O(n) + O(n) все еще O(n).
Может быть, я лох, но покажите, кто до хтой задачи додумается сам за 20 минут, не зная типового решения? Или вопрос в том, что это прям базовое типовое решение, которое и так все знают?
Разреши задать один вопрос - почему ты рекламу в ролики вставляешь? Это просто средство доп. заработка или может ты кайфуешь от того факта, что твой канал на Ютубе приносит деньги? P.S. Я ни в коему случае, не осуждаю и не придераюсь. Мне очень нравится твой контент, а этот вопрос чисто от любопытства. Так что братан, хорош, контент в кайф, вот такого бы побольше)
Я тоже обратил внимание. Интересно, какая должна быть сумма за рекламу, чтобы даже чел, работающий мидлом в лондоне, согласился ее опубликовать у себя на канале) Без негатива. Просто тоже любопытно.
Саша, у тебя грубая ошибка в видео где 1млн просмотров. В части про бинарный поиск ты показываешь на доске не правильно левую границу поиска и соотв. середину поиска тоже. Это сбивает с толку. Хотя код потом правильно описан. Странно что в комментариях никто этого не упомянул.
Предполагаю, что последний алгоритм решается не за O(n), а за O(n * log2n), мы же не знаем, как извлекаются значения из словаря, скорее всего там бинарный поиск с логарифмической сложностью, либо необходимо делать массив количеств, и извлекать значения за O(1) и тогда общая сложность алгоритма будет O(n), но памяти может быть израсходовано значительно больше
Реализация конкретного словаря зависит от библиотеки, но в основном - это хеш-таблицы. К примеру, стандартная библиотека шаблонов STL в C++ предлагает unordered_map, в документации, к которой, можно увидеть, что средняя скорость извлечения, удаления и добавления нового элемента O(1). Аналоги: HashMap в Java, dict в Python. Возвращаясь к STL в C++, там есть и обычный контейнер map, который реализован как раз на красно-черном двоичном дереве - в нем-то, все аналогичные действия и занимают O(log n). В основном, когда говорят про словари, имеются в виду именно хеш-мапы, о чем как раз Саша и говорит на 10:05. Поэтому алгоритмическая сложность последнего решения действительно O(n), и ошибки здесь нет.
@@asethone Добавление нового элемента в хеш-таблицы не o(1), необходимо добавлять сложность увеличения и ребалансировки хеш-таблиц, так что *среднняя сложность* равна все той-же o(log n). В общих условиях, где не выделяется 2 ГБ память на все int hashtable.
у нас скорее всего на бумажке попросят прикинуть.. т.е. как-то так не ходу.. я на одном просто рогом упёрся и какие-то вещи на пальцах объяснял, чтобы каракули долго не писать
Не рекомендую брать ЯндекПрактикум Python (личный опыт). Он чуть-чуть дает знания и денег своих не стоит, цена сильно завышено. Порядка 70% материалов, вам придется искать самостоятельно в интернете (Да, Яндекс просит денег, за то что бы он вам написал, то что нужно понгуглить). Ну а про баги самой платформы вы можете почитать отзывы в интернете, они впринципе все одинаковые. Если вам кто-то оплатит 100% курса (или около того), то смело можно идти, но приготовьтесь страдать!
Я учился и потом работал в практикуме. Это правда, что всей информации на курсе в материалах недостаточно, Яндекс дает каркас, это цель курса - научиться самостоятельно изучать недостающую информацию (ее на самом деле не так много). + у вас есть вебинары, где можете задавать вопросы + код ревью где ревьюер тоже подскажет как делать лучше и комьюнити для обмена информацией. Если что-то не нравится (бывают разные менторы), можно обратиться к куратору. Надо понимать, что практикум это для тех кто хочет учиться, а не чтобы знания положили в голову. На финале вы сделаете несколько проектов, без понимания вы их сделать не сможете, так что уйдете со знаниями и опытом. Конечно это не уровень «сразу идти работать», если курс вам это обещает - не верьте. практикум хорош для переквалификации и понятного старта. Я нанимал людей после практикума и других курсов, у первых в голове хорошее понимание «что и зачем», а не «потому что я так прочитал»
@@mrxDots Яндекс просит от 50 000 до 250 000 р. (скидки не рассматриваем) за то что, ...Яндекс дает каркас, это цель курса - научиться САМОСТОЯТЕЛЬНО изучать недостающую информацию... Повторюсь, ищите материалы самостоятельно, но платите за это деньги и не малые - именно в этом у меня основная претензия. На одно из Финальных Заданий - нужно было использовать HTML страницу, которую предоставлял ЯП. И именно из-за этой страницы, часть проекта не работало. Причина, которой она не работала, не расскрывалась в материалах ЯП. (собственно для решения того Финального задания матреиалы ЯП вообще не нужны были, так как в них не содержалась информация нужная для написания требуемого кода в ФЗ.)
Это не совсем O(n): решение использует функции работы с массивами, у которых неизвестно, что внутри. В отсутствие индекса тому же get'у понадобится в самом плохом случае пробежать весь массив. Кроме того, операции добавления элементов в массив и изменения их значений тоже не бесплатны. Это очень хорошо видно при работе с базами данных, на десятках и сотнях тысяч записей. Так что было бы интересно сравнить производительность второго и третьего решения на большом массиве. Скажем, в 1000 элементов.
глупости какие-то.. опираться на то что в языке массивы не честные.. ну представь что они нормальные, что ты сам их делал.. или хеш можно выкинуть, представить у тебя конечные суммы и тупо массивом заменить, достаточного размера.. можно вон дополнительный проход по массиву сделать и максимальный размер суммы определить заранее
@@h00per12 коллизии появляются из-за того, что хеш функции для бесконечного кол-ва ключей дают ограниченное кол-во хешей и тут не важно инт или нет. Нужно будет либо растить мапу до более чем n^2 памяти (ведь парадокс дней рождение root(n)) либо будут коллизии
если числа небольшие то мапа небольшая будет, хоть вообще без мапы это делай.. даже тупо массивом достаточного размера замени, где ячейка под каждую сумму предусмотрена..
Ох, уже столько дискуссий на эту тему в комментариях развели. Это довольно странно. Так как Саша сказал про хеш-мапы, то речь именно про unordered_map, а не map. В *_среднем_* время извлечения и вставки нового элемента в хеш-таблицу именно O(1) - тут не может быть каких-то споров. Да, в случае большого количества коллизий, и в случае добавления нового элемента при превышении коэффициента загрузки, что в свою очередь ведет к рехешированию всего содержимого хеш-мапы, это время может быть близко к O(n). Но, опять таки, в подобных задачках тебя, как правило, должна интересовать именно *_средняя_* сложность алгоритма, поэтому тут все корректно оценено. Мораль: не нужно быть *пессимистом* и всегда смотреть на _худший_ случай. Будьте *программистом* и смотрите на _усредненный_ 😉
@@HopeOfMankind_ почему-то мой комментарий был удален. Почитайте про дерево отрезков для суммы. Оно позволяет достаточно быстро, за logN отвечать на запрос от нахождении суммы на любом отрезке tree[l;r] , хотя в данном случае префиксы будут эффективнее, потому что у нас же не один отрезок.
Почему-то нет инофрмации по типам данных. Если это int, то можно и красивее через гистограмму, без хэшмэпы, если же это float - то могут быть близкие числа по типу 1.000002, 1.000001, 1.999997 для которых вычитание работать не будет в силу двоичности данных. И хэшмап тоже работать не будет при некоторых хэшированиях, т.к. все хэши совпадут, что приведет к o(n^2)
Но оценка O(N) не учитывает ни построение хешмапа, ни поиск по нему. ОК, поиском можно пренебречь, т.к. он упорядочен, но как быть с тем, что на каждой итерации перестраивается либо сам хешмап, либо его индекс?
О(5*N)==O(N), т.е. речь о решении задачи за время сопоставимое с количеством данных, когда N стремится к бесконечности. Поэтому особо разницы нет, конечный пользователь зачастую не заметит разницу в обработке чего-либо за 1мс или 5мс, но если функция уйдет в степени, то дело плохо
@@sidhott если ты за конкретное конечное количество шагов его достраиваешь, а не собственно строишь с нуля, то ответ напрашивается сам собой. Да за каждый новый сегмент тебе приходится по сути делать много действий, но по итогу то ты прошел по массиву чисел раз и получил ответ
@@alfagamma2499 а какая разница достраиваю я хеш или строю с нуля, если мне память двигать? n раз передвинуть n/2 ячеек памяти -- это O(n)? "много действий" -- это сколько конкретно, О(индекса)? P.S. прошёл по массиву чисел раз -- только звучит красиво, т.к. O(n) + O(n2) = O(n2).
Создал Telegram канал, в котором рассказываю о жизни в Лондоне, работе в Google и подготовке к собеседованиям. Подписывайтесь: t.me/saschalukin
Блин какой приятный парень! Можно целыми дня смотреть его уроки про задачи на собеседовании)
Так, погодите... Да ведь это одна из тем задания №27 на ЕГЭ по информатике. Формулировки задания очень похожие, и на 2 первичных балла нужно написать решение как раз за O(N).
Там нет отрицательных чисел, однако меня тоже взяла гордость, когда я увидел, что задача похожа на экзамиционную.
@@runneso Да, наличие отрицательных чисел существенно влияет на способ решения. Задания с отрицательными числами пока официально не встречались, но во всяких тренировочных сборниках изредка попадаются.
Зато можно почти серьёзно говорить старшеклассникам: осилите 27-е - получите задел на FAANG.
@user-jp8jl5mg3v то что ты назвал тоже очень легко, это прямо база информатики 27
Гораздо сложнее 27
Ребят, я 5 лет работаю разрабом, у меня два высших, но я сейчас егэ по информатике глянула и не смогла там почти ничего решить😅 современные выпускники, похоже, гении))
Видно как растёт качество видео. Спасибо за твою работу, очень помогаешь!
Класс! Спасибо за полезные видео.
Снимай плиз пару выпусков про то, кто ты и как "докатился" до такой жизни, про свой опыт в бигтехе и фишечки, которые ты рекомендовал бы себе- младшему.
я от тембра голоса и манере преподавания автора восхищаюсь. Молодец!
Тоже восхищён - усыпить меня буквально за минуту - это талант! 😆
Вот жаль, что такое разом не приходит в голову. Сначала о втором способе подумал. Но логично ведь, что можно просто концы обрезать до 5. Мне в голову пришла идея где мы по массиву змейкой вперёд и назад идём постоянно сокращая на один шаг с каждой сменой направления, при этом, меняя направление, мы обнуляем сумму цифр и так пока числа не встретятся, вроде O(n), но скорее всего медленнее, правда и памяти лишней не затронет. Все варианты как раз высчитывает, ведь нет разницы с какой стороны подмассивы считать. Надо бы алгоритмы прокачать
Супер подробно объяснил. Спасибо. Побольше таких разжеванных задач!
Если нет опыта решения подобных задач (недавнего причем) то придумать самое быстро решение на собесе за 20 мин это какая то фантастика. IQ 150+ надо иметь наверн. Если дома посидеть спокойно, то за часик-2 конечно можно ну или с набитой рукой врываться на собесы.
Контент в кайф кнчн)
Чтобы хорошо щёлкать алгоритмические, надо просто руку набивать. Мне первое решение для этой задачи сразу в голову пришло
@@gggppp228 согласен, надо готовиться к такому. Изниоткуда такой скил не появится
Классно! Всё предельно ясно-понятно! Спасибо!
Последнее решение на доске верно объяснено, но код не корректный.
Для массива 1 2 3 4 1 и k = 10, выдаст 3, хотя верный ответ 2
Я бы хотел поправить автора видео.
Дело в том, что приобьяснении он говорит про итерацию по числам справа. Но по делу, скрипт работает с нулевым и последующими елементами.
Для того, что бы реализовать процесс как было обьясненно. Нужно ко второму циклу накинуть +1 и в сумму в первом цикле обьявить как елемент по которому итерируемся.. плюс условия по проверке так же изменить на начало.
Очень круто! Спасибо, футболки отличные)
Очень интересная задача. Спасибо большое
Топ🔥 Спасибо за работу!
ох где же это видео раньше пряталось, если до первого и второго решения я додуатся сумел то третьего варианта мне явно не хватало
мой способ менее эффективный, потому что я использовал поиск в массиве, а не в хэш таблице
создаём массив префиксных сумм, потом проходимся по нему и ищем есть ли в нём (текущий элемент-5)
Саш, привет. Посоветуй литературу для прокачки алгоритмического мышления. Какие книги тебе помогали готовиться к собеседованиям?
Адитья Бхаргава "Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих"
Алгоритмы это 3-4 вопроса из пары десятков на онсайте.
Роберт Лафоре "Структуры данных и алгоритмы"
leetcode
@@MaruiInfantry только для некоторых компаний это основной критерий и от алгоритмов зависит скорость работы программ, не важно на каком языке. Собесился в яндекс, рассказал хорошо теорию и свой опыт, но с задачей долго ковырялся и из за этого не взяли
если вы не знаете что делать - то воспользуйся Hash. Золотые слова!
Классный ролик, продолжай 🔥🔥🔥
да вот ничего подобного, первым в голову не такая дичь пришла), просто складываю все подряд слева направа в цикле и когда сложение выдает 5 то в счетчике +1, потом новый цикл со следующего индекса, и так 8 циклов с перебором (сложением) (длинна массива 8 - 8 циклов, с 1 элемента, потом со второго и т.д.). досмотрел ролик и подумал что мое решение получше будет)...
По жд едут 70 вагонов с насыпными грузами, каждый взвешен с точностью до килограма и значения не повторяются. От ржд приходит документ что во всем поезде едет 4 груза: зерно 940000 кг, пшено 800000 кг ,яблоки 250000 кг, картошка . Вагоны на станциях перецеплялись все опломбировано и вскрывать нельзя, вам нужно найти только яблоки .... если интересно расскажу решение )
Очень крутое видео
Большое спасибо
Спасибо за труды!
Привет! Спасибо за твои видео! Очень интересно. Да и вообще классно знать что где-то есть люди, которые хорошо зарабатывают (предполагаю что в Лондоне программисту хорошо платят) но при этом они могут адекватно и доброжелательно излагать мысли.
У меня только вопрос, а лично тебе какая польза от этого? Особенно вызывает удивление что рассказываешь на русском.
Саша, а сделай, плиз, объяснение на английском языке. Хочется набраться слов и фраз именно на английском языке.
Круто! Спасибо!
13:16 а если бы между теми двумя подмассивами с суммой 8 был еще один какой-то?
Вот у меня тоже возник вопрос, если я правильно понял, похожий, что будет, если после того, как мы взяли в ответ количество подмассивов с суммой 4, например, а потом снова плавится подмассив с такой же суммой и он нам снова потребуется. Тогда в ответе появится лишний +1 в ответе.
Отличное видео! Спасибо за твой труд! И возвращайся к джаве плизззз)
остановил видева. Я думаю можно отсортировать массив. Потом решить с помощью two pointers. Но там много заморочек, поэтому я бы еще подумал.
Огромное. Спасибо.
Спасибо за контент!
не очень понимаю зачем третий цикл for, когда первые два уже покроют все возможные варианты. Все что написано в третьем цикле можно написать во втором, а по выходу из второго цикла обнулять подсумму. Получится сложность О(n^2). А да посмотрел дальше ролик, это его второе решение. Ну тогда зачем вообще было говорить о первом решении, оно вообще искусственное, придуманное ради того, чтоб было, так можно и 10 циклов друг в друга вложить ради кол-ва.
Кхъ, у меня как раз на этой неделе собес в Яндекс. Напишу, если попадется что-то интересное)
десятилетия использую подыбный прием в матлабе и в голову не приходило, что это это так называется ;)
В питоне хэш-мап - это словарь, а то так сразу можно и столку сбить)
Спасибо за видео!
Я сразу сделал через 1 решение и ввел переменную accumulator для накопление
Из неприятного для таких задач, самостоятельно придумать финальное решение довольно сложно, те после объяснения то понятно, но сам с ходу можешь придумать только второй вариант за N^2
from collections import defaultdict
...
prefix_sum_count = defaultdict(int, {0: 1})
for num in nums:
subarray_sum += num
answer += prefix_sum_count(subarray_sum - k)
prefix_sum_count[subarray_sum] += 1
идти от каждого числа с подсуммировкой пока сумма массима не даст K. Когда k = массиву, удалять его из переменной возвращать массив в ruturn
эт специальо мысли вслух тк видос на задаче поставил на паузе, и я не программист
наконец то пример решения на Python!!! (единстыенный язык, который я идеально понимаю...)
Код на питоне понятен даже если впервые видишь язык. Собственно его популярность отчасти обусловлена простотой
@@Deletedeletedelete Не преувеличивайте, там достаточно фишек в синтаксисе, вопрос в другом используются они или нет!
спасибо, доходчиво
Спасибо! Разбери что-нибудь с Деревом Фенвика плз!
Здравствуйте, разве использование хэш мапы не даёт нам асимпотику O(n log n) ?
Або ми по гіршому варіанту оцініюємо, або по середньому )
Чого б це хеш-мапа в гіршому випадку працювала, як O(1)?
Вона буде працювати, як O(n)
То ж, загальна склпжність за часом буде O(n^2) + пам'яті O(n)
А проходы по хэшмэпу не увеличивают сложность до n^2?
Очень познавательно, но почему бы не использовать вместо конструкции range(len()), enumerate
Балдеж!
спасибо
мда, это конечно обычным людям нереально достичь. Пойду дальше писать калькуляторы
Кстати, мне давали такую задачу в Яндексе
Класс)
Сначала подумал, что это задачка, которую я вчера решал на Литкоде. Аж охренел ))) Но там попроще, там просто надо найти ключи двух элементов, дающих в сумме ту же 5 (здесь нет решений). Решается элементарно через два for. Тут посложнее задачка.
Почему быстрое решение имеет код в два раза больше ,чес обычное?
Являюсь front end разработчиком порядка 6 лет, за все время, как ни пытался, так и не понимаю, вообще ни в какую все алгоритмы, задачи решать не умею, пересмотрел уже миллиард ресурсов и обучающих видео, все равно ничего не понятно, на сегодня спасает chatGpt. Буду рад совету что делать в такой ситуации, может какую-то литературу или курсы.
Привет! Тоже фронтендер, но поменьше)
Решать задачи, просто решать задачи, тренировать мозг и глаза, формировать насмотренность. имхо такая микросфера, где опыт очень сильно решает. Я открываю Литкод - делаю простые - усложняю, пока не сломаюсь - изучаю решения, записываю/учусь применять/решаю подобные.
В алгосах главное уметь в пространные концепции, «Грокаем Алгоритмы» очень мне помогло в свое время с освоением и пониманием что вообще в таких задачах происходит, у тебя на самом деле есть небольшое количество концепций, которые надо изучить и, самое важно, понять, чтобы уметь применять
@@mityaoreh привет. Благодарен за совет, буду наверстывать упущенное хоть это и очень тяжело мне дается
@@LonelyRiderStonerBand отлично понимаю)
удачи, сил и терпения, всё обязательно получится :)
@@mityaoreh Thanks mate ;)
Кажись баг в реализации, даже 2 бага... Если subarray_sum будет 0, то в хэш запишется {0:2}, а в answer добавится то, что по ключу -5 (зачем от 0 отрезать кусок с суммой -5, чтобы получить 5?)
Может случится ситуация, когда to_remove будет 0 и тогда к answer добавится 2, вместо 1
Не проверял, надо тесты погонять
[-5, 5, -5, 5]
на втором шаге сумма = 0, в ансвер добавится по ключу [-5], т.е. 1, записанная на первом шаге. т.к. второй элемент [5] нам подходит как подмассив.
на 4м шаге опять 0, по ключу [-5] уже значение 2, записанное туда на третьем шаге. ансвер = 1+2 = 3. это потому, то на четвертом шаге подходят два подмассива: последний элемент [5] и [5,-5,5]
"зачем от 0 отрезать кусок с суммой -5, чтобы получить 5?": 0 - (-5) = 5, вот поэтому
"Может случится ситуация, когда to_remove будет 0 и тогда к answer добавится 2, вместо 1": нет, в ансвер плюсуется по ключу [ту_ремув], но счетчик увеличивается по ключу [субаррай_сум]
[5, 0, 0, 0, 0]
начиная со второго шага ту_ремув всегда ноль, но по ключу ноль находится единица, т.к. увеличиваться постоянно значение по ключу [5]. в итоге ансвер = 1+1+1+1+1 = 5
@@SayXaNow спасибо за подробное объяснение! Действительно, даже если {0: 1} увеличивается, то всё правильно работает, и эти отрезки с 0 суммой учитываются в ответе
класс
крутое решение, правда пока не прогнал через дебагер не понял. на пальцах сложно)
А куда делось множество {7, 2, 1, -5}? Или речь шла только о подряд идущих числах?
у меня есть вопросы к последнему алгоритму, как там вышло 5, если считать вручную, то у меня вышло 13, может и больше было бы, но лень все перебирать
надо считать все числа подмассива, а вы видимо считали выборочно. для K=5 и массива [4,2,1] ответ 0, а не 1, нельзя складывать 4 и 1 без двойки.
проще всего это проверить квадратичным алгоритмом с полным перебором. он дает ответ 5.
Так надо сказать, или нет?
надо
Надо говорить. 99% что задачу не поменяют, «видеть», «знать как решать» это еще не«решить», плюс 80% успеха прохождения алгоритмической сессии - много говорить, объяснять логику и трейдоффы
у меня какие то ноунеймы попросили вернуть из такого массива все возможные варианты элементов этого массива, которые в сумме дают число к
привет меня зовут саша лукин и я работаю в компании Гугл в ЛОНДОНЕ! Слышишь с..а, в ЛОНДОНЕ!!! Не то что ты. А я в ЛОНДОНЕ! саша лукин и в ЛОНДОНЕ! Вот я какой! Ахахаха охохохо я неипически крут!
14:17 - "но при этом мы тратим O(n) памяти"
и еще мы тратим время на поиск в этой памяти "отрезаемых кусков" - O(n)
в итоге время алгоритма примерно равно O(2*n)
В терминах Big O (O-большое), константы не учитываются при рассчете алгоритмической сложности, поэтому итоговая сложность записывается именно как O(n). Рекомендую подробнее почитать про оценку сложности алгоритмов.
@@asethone согласен;-)
но алгоритм с O(n) используемый в цикле m раз, всегда будет быстрее, чем тот же цикл с алгоритмом с неправильной оценкой сложности O(3*n).
сложности у алгоритмов одинаковы - скорости разные
@@Sergey-Primak Ну вопрос оптимизации - это уже отдельная тема. Уменьшить количество проходов по циклу после того, как ты придумал быстрое решение всегда можно успеть.
Главное, и самое сложное на собеседованиях - это как раз придумать такое решение, которое именно в терминах Big O будет наиболее оптимальным. А то, что ты там лишний раз добавишь O(n) вне цикла - это никого даже не смутит, ведь O(n) + O(n) все еще O(n).
привет, а что у тебя за монитор, подключенный к маку?
Sliding window не сработает, потому что есть отрицательные значения? или сработает?
ого, ты начал показывать код на python, а не на java, неожиданно
Почему тут не было бинарного поиска😢?По моему,это было бы самое оптимальное и рациональное решение!
Еще есть способ решить через префиксную сумму, также o(n) по времени и памяти
А он через что решил?
Имеется ввиду что можно не использовать хэш мапу
Может быть, я лох, но покажите, кто до хтой задачи додумается сам за 20 минут, не зная типового решения? Или вопрос в том, что это прям базовое типовое решение, которое и так все знают?
Без отладчика пока не особо понимаю как работает код)
Are you switched to Python from Java??
Поставил на паузу: Sliding window
Sliding window сработает только если все числа >= 0
@@mrxDotsсработает в любом случае, просто он медленный
Разреши задать один вопрос -
почему ты рекламу в ролики вставляешь? Это просто средство доп. заработка или может ты кайфуешь от того факта, что твой канал на Ютубе приносит деньги?
P.S. Я ни в коему случае, не осуждаю и не придераюсь. Мне очень нравится твой контент, а этот вопрос чисто от любопытства.
Так что братан, хорош, контент в кайф, вот такого бы побольше)
Я тоже обратил внимание.
Интересно, какая должна быть сумма за рекламу, чтобы даже чел, работающий мидлом в лондоне, согласился ее опубликовать у себя на канале)
Без негатива. Просто тоже любопытно.
а тут разве не надо обнулять значения мапы после того как к answer плюсуем?
Попробуй в коде перед тем, как задавать вопрос. Может оказаться, что вопрос бессмысленный.
Саша, у тебя грубая ошибка в видео где 1млн просмотров.
В части про бинарный поиск ты показываешь на доске не правильно левую границу поиска и соотв. середину поиска тоже. Это сбивает с толку. Хотя код потом правильно описан. Странно что в комментариях никто этого не упомянул.
разве второй вариант это не O(n^2 / 2)
как человек который живет в Лондоне вместа сам говорит сум?
Предполагаю, что последний алгоритм решается не за O(n), а за O(n * log2n), мы же не знаем, как извлекаются значения из словаря, скорее всего там бинарный поиск с логарифмической сложностью, либо необходимо делать массив количеств, и извлекать значения за O(1) и тогда общая сложность алгоритма будет O(n), но памяти может быть израсходовано значительно больше
значения из словаря всегда за О(1) же
Реализация конкретного словаря зависит от библиотеки, но в основном - это хеш-таблицы. К примеру, стандартная библиотека шаблонов STL в C++ предлагает unordered_map, в документации, к которой, можно увидеть, что средняя скорость извлечения, удаления и добавления нового элемента O(1). Аналоги: HashMap в Java, dict в Python.
Возвращаясь к STL в C++, там есть и обычный контейнер map, который реализован как раз на красно-черном двоичном дереве - в нем-то, все аналогичные действия и занимают O(log n).
В основном, когда говорят про словари, имеются в виду именно хеш-мапы, о чем как раз Саша и говорит на 10:05. Поэтому алгоритмическая сложность последнего решения действительно O(n), и ошибки здесь нет.
под капотом обычно массив
@@asethone Добавление нового элемента в хеш-таблицы не o(1), необходимо добавлять сложность увеличения и ребалансировки хеш-таблиц, так что *среднняя сложность* равна все той-же o(log n). В общих условиях, где не выделяется 2 ГБ память на все int hashtable.
Занимался долго спортпрогой, задача супербаза, не думал, что такое простенькое может где-то попасться
Сколько времени дается на выполнение подобной задачи на собеседовании?
у нас скорее всего на бумажке попросят прикинуть.. т.е. как-то так не ходу.. я на одном просто рогом упёрся и какие-то вещи на пальцах объяснял, чтобы каракули долго не писать
Он же сказал в видео - 20 минут
Не рекомендую брать ЯндекПрактикум Python (личный опыт). Он чуть-чуть дает знания и денег своих не стоит, цена сильно завышено. Порядка 70% материалов, вам придется искать самостоятельно в интернете (Да, Яндекс просит денег, за то что бы он вам написал, то что нужно понгуглить).
Ну а про баги самой платформы вы можете почитать отзывы в интернете, они впринципе все одинаковые.
Если вам кто-то оплатит 100% курса (или около того), то смело можно идти, но приготовьтесь страдать!
Я учился и потом работал в практикуме. Это правда, что всей информации на курсе в материалах недостаточно, Яндекс дает каркас, это цель курса - научиться самостоятельно изучать недостающую информацию (ее на самом деле не так много). + у вас есть вебинары, где можете задавать вопросы + код ревью где ревьюер тоже подскажет как делать лучше и комьюнити для обмена информацией. Если что-то не нравится (бывают разные менторы), можно обратиться к куратору. Надо понимать, что практикум это для тех кто хочет учиться, а не чтобы знания положили в голову. На финале вы сделаете несколько проектов, без понимания вы их сделать не сможете, так что уйдете со знаниями и опытом. Конечно это не уровень «сразу идти работать», если курс вам это обещает - не верьте. практикум хорош для переквалификации и понятного старта. Я нанимал людей после практикума и других курсов, у первых в голове хорошее понимание «что и зачем», а не «потому что я так прочитал»
@@mrxDots Яндекс просит от 50 000 до 250 000 р. (скидки не рассматриваем) за то что, ...Яндекс дает каркас, это цель курса - научиться САМОСТОЯТЕЛЬНО изучать недостающую информацию...
Повторюсь, ищите материалы самостоятельно, но платите за это деньги и не малые - именно в этом у меня основная претензия.
На одно из Финальных Заданий - нужно было использовать HTML страницу, которую предоставлял ЯП. И именно из-за этой страницы, часть проекта не работало. Причина, которой она не работала, не расскрывалась в материалах ЯП. (собственно для решения того Финального задания матреиалы ЯП вообще не нужны были, так как в них не содержалась информация нужная для написания требуемого кода в ФЗ.)
и чего там питон дают или что ещё?
верните, пожалуйста, видео про хеш-сеты, я не досмотрел
благодарю
а это же ещё и префиксные суммы?
а, позже в видео сказали)
А для чего может быть полезен результат такого решения?
Для развития алгоритмического мышления.
@@ЕвгенийИзотов-н7п Т.е. этот алгоритм ни где не используется ;)?
@@101picofarad можно представить, например, что вы ищете временной период, когда денежный баланс на счёте был равен определенной сумме
Так надо говорить, что знаешь решение или нет....
Это не совсем O(n): решение использует функции работы с массивами, у которых неизвестно, что внутри.
В отсутствие индекса тому же get'у понадобится в самом плохом случае пробежать весь массив.
Кроме того, операции добавления элементов в массив и изменения их значений тоже не бесплатны.
Это очень хорошо видно при работе с базами данных, на десятках и сотнях тысяч записей.
Так что было бы интересно сравнить производительность второго и третьего решения на большом массиве. Скажем, в 1000 элементов.
@@SayXaNow да, я прочитал вашу дискуссию ) жаль, что после того, как свой коммент написал. Отличный тест, спасибо!
глупости какие-то.. опираться на то что в языке массивы не честные.. ну представь что они нормальные, что ты сам их делал.. или хеш можно выкинуть, представить у тебя конечные суммы и тупо массивом заменить, достаточного размера.. можно вон дополнительный проход по массиву сделать и максимальный размер суммы определить заранее
Как ты это решаешь?
Блетб. Гениально
Ничего себе, Саша начал писать на Python. Java такой: Ну да ну да, пошёл я😹
27б)))))
Работник гугла рекламирует яндекс?
Да.
Я бы сказал, что сложность n*log(n), если используем map и от n до n^2 для unordered_map (из-за возможных колизий).
Так тут int используется, то коллизий вообще нет, то есть get(key) будет работать за константу
@@h00per12 Коллизии могут быть, даже если хранятся обычные инты, хэш-функция будет вычисляться по модулю от длины массива
@@h00per12 коллизии появляются из-за того, что хеш функции для бесконечного кол-ва ключей дают ограниченное кол-во хешей и тут не важно инт или нет. Нужно будет либо растить мапу до более чем n^2 памяти (ведь парадокс дней рождение root(n)) либо будут коллизии
если числа небольшие то мапа небольшая будет, хоть вообще без мапы это делай.. даже тупо массивом достаточного размера замени, где ячейка под каждую сумму предусмотрена..
Ох, уже столько дискуссий на эту тему в комментариях развели. Это довольно странно.
Так как Саша сказал про хеш-мапы, то речь именно про unordered_map, а не map. В *_среднем_* время извлечения и вставки нового элемента в хеш-таблицу именно O(1) - тут не может быть каких-то споров. Да, в случае большого количества коллизий, и в случае добавления нового элемента при превышении коэффициента загрузки, что в свою очередь ведет к рехешированию всего содержимого хеш-мапы, это время может быть близко к O(n). Но, опять таки, в подобных задачках тебя, как правило, должна интересовать именно *_средняя_* сложность алгоритма, поэтому тут все корректно оценено.
Мораль: не нужно быть *пессимистом* и всегда смотреть на _худший_ случай. Будьте *программистом* и смотрите на _усредненный_ 😉
Разве map не имеет сложность всех операций log(n)? Тогда получается O(n*log(n))
я думал сначала отсортировать массив и использовать метод двух индексов
тогда вообще ответ поменяется
@@Гэтсби-ь6ю да я это уже понял )
С двумя индексами, кажется, можно и без хеш-мап решить
Первое, что пришло в голову - решить через Segment Tree
Это как
@@HopeOfMankind_ почему-то мой комментарий был удален. Почитайте про дерево отрезков для суммы. Оно позволяет достаточно быстро, за logN отвечать на запрос от нахождении суммы на любом отрезке tree[l;r] , хотя в данном случае префиксы будут эффективнее, потому что у нас же не один отрезок.
Почему-то нет инофрмации по типам данных. Если это int, то можно и красивее через гистограмму, без хэшмэпы, если же это float - то могут быть близкие числа по типу 1.000002, 1.000001, 1.999997 для которых вычитание работать не будет в силу двоичности данных. И хэшмап тоже работать не будет при некоторых хэшированиях, т.к. все хэши совпадут, что приведет к o(n^2)
По условию, видимо, массив из целых чисел.
Алгоритмические задачи обычно решаются с помощью базовых типов данных.
Это как это через гистограмму?
@user-jp8jl5mg3v n шагов, на каждом шаге n проверок, если хэш совпадает
@@sergeev_oleg вообще в алгоритмических задачах всегда обговаривают тип, если это важно для решения.
Что за пайтон? Где джава? )
Петухон, Жава, какя разница?
Но оценка O(N) не учитывает ни построение хешмапа, ни поиск по нему. ОК, поиском можно пренебречь, т.к. он упорядочен, но как быть с тем, что на каждой итерации перестраивается либо сам хешмап, либо его индекс?
О(5*N)==O(N), т.е. речь о решении задачи за время сопоставимое с количеством данных, когда N стремится к бесконечности.
Поэтому особо разницы нет, конечный пользователь зачастую не заметит разницу в обработке чего-либо за 1мс или 5мс, но если функция уйдет в степени, то дело плохо
@@alfagamma2499 а откуда Вы взяли 5х, почему время построения хешмапа сопоставимо с его размером, а не, скажем, квадратом его размера?
@@sidhott если ты за конкретное конечное количество шагов его достраиваешь, а не собственно строишь с нуля, то ответ напрашивается сам собой. Да за каждый новый сегмент тебе приходится по сути делать много действий, но по итогу то ты прошел по массиву чисел раз и получил ответ
@@alfagamma2499 а какая разница достраиваю я хеш или строю с нуля, если мне память двигать? n раз передвинуть n/2 ячеек памяти -- это O(n)? "много действий" -- это сколько конкретно, О(индекса)?
P.S. прошёл по массиву чисел раз -- только звучит красиво, т.к. O(n) + O(n2) = O(n2).
@@sidhottможно родить массив с упреждением и удваивать его при переполнении чтобы не перекидывать его в памяти при каждой записи.