Собеседование в Facebook - Разбор Для Начинающих

Рет қаралды 45,712

Күн бұрын

Разбираем очень популярную задачу из собеседования в Facebook на позицию разработчика ПО. Она решается с помощью хитрого приема, который поможет при решении не только этой, но и многих других задач из собеседований в топовые зарубежные айти компании.
Эта задача на Leetcode: leetcode.com/problems/subarra...
Освойте основы Python-разработки на бесплатном курсе от Яндекс Практикума - ya.cc/t/GQ2vmtGU4Ham8U
Токен: LdtCKNm4k
00:00 О задаче
00:43 Условие задачи
01:54 Первое решение
03:18 Код первого решения
04:23 Второе решение
07:40 Код второго решения
08:21 Яндекс Практикум
09:51 Самое быстрое решение
14:44 Код финального решения

Пікірлер: 210

@sashalukin Ай бұрын

Создал Telegram канал, в котором рассказываю о жизни в Лондоне, работе в Google и подготовке к собеседованиям. Подписывайтесь: t.me/saschalukin

@sb9185 9 ай бұрын

Блин какой приятный парень! Можно целыми дня смотреть его уроки про задачи на собеседовании)

@IvanYugov 11 ай бұрын

Так, погодите... Да ведь это одна из тем задания №27 на ЕГЭ по информатике. Формулировки задания очень похожие, и на 2 первичных балла нужно написать решение как раз за O(N).

@runneso 11 ай бұрын

Там нет отрицательных чисел, однако меня тоже взяла гордость, когда я увидел, что задача похожа на экзамиционную.

@IvanYugov 11 ай бұрын

@@runneso Да, наличие отрицательных чисел существенно влияет на способ решения. Задания с отрицательными числами пока официально не встречались, но во всяких тренировочных сборниках изредка попадаются. Зато можно почти серьёзно говорить старшеклассникам: осилите 27-е - получите задел на FAANG.

@user-jp8jl5mg3v 11 ай бұрын

@@IvanYugovтак 27 часто сложнее этой задачи. Она придумывается за минуту (не преувеличение). Такие подарки в 27 редкость. Обычно что-то посложнее. В этом году например (я писал ИГЭЭЭ) была задачка на префиксы, нужно было максимизировать сумму трёх чисел, разность индексов у любых двух из них хотя бы k. Делается за линию, но идейно сложнее, чем это. Так что да, алгоритмическая база в последних двух задачах нужна нормальная, больше, чем для этой задачи.

@nixxik__ 11 ай бұрын

@@user-jp8jl5mg3v то что ты назвал тоже очень легко, это прямо база информатики 27

@user-jp8jl5mg3v 11 ай бұрын

@@nixxik__ Ну да, просто первое в голову пришло - пример 27, который похож по теме задачи, но сложнее идейно. Понятно, это не сложнейший из типов.

@dark.960 11 ай бұрын

Видно как растёт качество видео. Спасибо за твою работу, очень помогаешь!

@kazarovroman 11 ай бұрын

Супер подробно объяснил. Спасибо. Побольше таких разжеванных задач!

@habib_sultan 11 ай бұрын

Класс! Спасибо за полезные видео. Снимай плиз пару выпусков про то, кто ты и как "докатился" до такой жизни, про свой опыт в бигтехе и фишечки, которые ты рекомендовал бы себе- младшему.

@Lammax2012 11 ай бұрын

Классно! Всё предельно ясно-понятно! Спасибо!

@saveekglushchenko6903 11 ай бұрын

Очень круто! Спасибо, футболки отличные)

@hopelesssuprem1867 11 ай бұрын

Очень интересная задача. Спасибо большое

@sudo_ku 10 ай бұрын

Топ🔥 Спасибо за работу!

@vacsa 11 ай бұрын

Спасибо за труды!

@Baha996 11 ай бұрын

Классный ролик, продолжай 🔥🔥🔥

@blitz_kiy5104 11 ай бұрын

Вот жаль, что такое разом не приходит в голову. Сначала о втором способе подумал. Но логично ведь, что можно просто концы обрезать до 5. Мне в голову пришла идея где мы по массиву змейкой вперёд и назад идём постоянно сокращая на один шаг с каждой сменой направления, при этом, меняя направление, мы обнуляем сумму цифр и так пока числа не встретятся, вроде O(n), но скорее всего медленнее, правда и памяти лишней не затронет. Все варианты как раз высчитывает, ведь нет разницы с какой стороны подмассивы считать. Надо бы алгоритмы прокачать

@danilas2206 11 ай бұрын

Спасибо за видео!

@user-yr3ub5gp3t 11 ай бұрын

Спасибо за контент!

@leomysky 10 ай бұрын

Очень крутое видео Большое спасибо

@flyingdinosaur8871 6 ай бұрын

Круто! Спасибо!

@alexandersuvorov5465 7 ай бұрын

Огромное. Спасибо.

@glukh0v_d1ma 11 ай бұрын

спасибо, доходчиво

@dimasbka Ай бұрын

ох где же это видео раньше пряталось, если до первого и второго решения я додуатся сумел то третьего варианта мне явно не хватало

@user-lk8n0fgjk 11 ай бұрын

Отличное видео! Спасибо за твой труд! И возвращайся к джаве плизззз)

@v.demchenko 13 күн бұрын

Я бы хотел поправить автора видео. Дело в том, что приобьяснении он говорит про итерацию по числам справа. Но по делу, скрипт работает с нулевым и последующими елементами. Для того, что бы реализовать процесс как было обьясненно. Нужно ко второму циклу накинуть +1 и в сумму в первом цикле обьявить как елемент по которому итерируемся.. плюс условия по проверке так же изменить на начало.

@mavn-code 11 ай бұрын

я от тембра голоса и манере преподавания автора восхищаюсь. Молодец!

@daitedve1984 11 ай бұрын

Тоже восхищён - усыпить меня буквально за минуту - это талант! 😆

@flybenazer8572 2 ай бұрын

спасибо

@user-ym2ci7sf3l 11 ай бұрын

Балдеж!

@vladsssl 6 ай бұрын

привет, а что у тебя за монитор, подключенный к маку?

@DasBosch 11 ай бұрын

Кхъ, у меня как раз на этой неделе собес в Яндекс. Напишу, если попадется что-то интересное)

@alexanderzaretskiy4188 11 ай бұрын

Класс)

@Arkham_nine 9 ай бұрын

Спасибо! Разбери что-нибудь с Деревом Фенвика плз!

@overskam2699 11 ай бұрын

Sliding window не сработает, потому что есть отрицательные значения? или сработает?

@kotikGGG Ай бұрын

А проходы по хэшмэпу не увеличивают сложность до n^2?

@hoopengo2289 11 ай бұрын

остановил видева. Я думаю можно отсортировать массив. Потом решить с помощью two pointers. Но там много заморочек, поэтому я бы еще подумал.

@user-jy3hn5oq1g 11 ай бұрын

Саш, привет. Посоветуй литературу для прокачки алгоритмического мышления. Какие книги тебе помогали готовиться к собеседованиям?

@makige1378 11 ай бұрын

Адитья Бхаргава "Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих"

@MaruiInfantry 11 ай бұрын

Алгоритмы это 3-4 вопроса из пары десятков на онсайте.

@konstantin1648 11 ай бұрын

Роберт Лафоре "Структуры данных и алгоритмы"

@naneri 11 ай бұрын

leetcode

@roman_je_rkoff 11 ай бұрын

@@MaruiInfantry только для некоторых компаний это основной критерий и от алгоритмов зависит скорость работы программ, не важно на каком языке. Собесился в яндекс, рассказал хорошо теорию и свой опыт, но с задачей долго ковырялся и из за этого не взяли

@edmond-dantes-1796 9 ай бұрын

Если нет опыта решения подобных задач (недавнего причем) то придумать самое быстро решение на собесе за 20 мин это какая то фантастика. IQ 150+ надо иметь наверн. Если дома посидеть спокойно, то за часик-2 конечно можно ну или с набитой рукой врываться на собесы. Контент в кайф кнчн)

@gggppp228 Ай бұрын

Чтобы хорошо щёлкать алгоритмические, надо просто руку набивать. Мне первое решение для этой задачи сразу в голову пришло

@edmond-dantes-1796 Ай бұрын

@@gggppp228 согласен, надо готовиться к такому. Изниоткуда такой скил не появится

@SoulPervert 10 ай бұрын

13:16 а если бы между теми двумя подмассивами с суммой 8 был еще один какой-то?

@galo4kin 10 ай бұрын

Вот у меня тоже возник вопрос, если я правильно понял, похожий, что будет, если после того, как мы взяли в ответ количество подмассивов с суммой 4, например, а потом снова плавится подмассив с такой же суммой и он нам снова потребуется. Тогда в ответе появится лишний +1 в ответе.

@user-qm5fv5by5z 9 ай бұрын

да вот ничего подобного, первым в голову не такая дичь пришла), просто складываю все подряд слева направа в цикле и когда сложение выдает 5 то в счетчике +1, потом новый цикл со следующего индекса, и так 8 циклов с перебором (сложением) (длинна массива 8 - 8 циклов, с 1 элемента, потом со второго и т.д.). досмотрел ролик и подумал что мое решение получше будет)...

@Igorkornilovspb 8 ай бұрын

Привет! Спасибо за твои видео! Очень интересно. Да и вообще классно знать что где-то есть люди, которые хорошо зарабатывают (предполагаю что в Лондоне программисту хорошо платят) но при этом они могут адекватно и доброжелательно излагать мысли. У меня только вопрос, а лично тебе какая польза от этого? Особенно вызывает удивление что рассказываешь на русском.

@Baha996 11 ай бұрын

класс

@a1dwow 9 ай бұрын

Я сразу сделал через 1 решение и ввел переменную accumulator для накопление

@antonmuzeev 10 ай бұрын

Саша, а сделай, плиз, объяснение на английском языке. Хочется набраться слов и фраз именно на английском языке.

@WildRhinocerosDriver 9 ай бұрын

А куда делось множество {7, 2, 1, -5}? Или речь шла только о подряд идущих числах?

@hello_world_zz 10 ай бұрын

если вы не знаете что делать - то воспользуйся Hash. Золотые слова!

@ventice11o Ай бұрын

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

@hopelesssuprem1867 11 ай бұрын

В питоне хэш-мап - это словарь, а то так сразу можно и столку сбить)

@nicholasspezza9449 10 ай бұрын

не очень понимаю зачем третий цикл for, когда первые два уже покроют все возможные варианты. Все что написано в третьем цикле можно написать во втором, а по выходу из второго цикла обнулять подсумму. Получится сложность О(n^2). А да посмотрел дальше ролик, это его второе решение. Ну тогда зачем вообще было говорить о первом решении, оно вообще искусственное, придуманное ради того, чтоб было, так можно и 10 циклов друг в друга вложить ради кол-ва.

@znsoft 10 ай бұрын

По жд едут 70 вагонов с насыпными грузами, каждый взвешен с точностью до килограма и значения не повторяются. От ржд приходит документ что во всем поезде едет 4 груза: зерно 940000 кг, пшено 800000 кг ,яблоки 250000 кг, картошка . Вагоны на станциях перецеплялись все опломбировано и вскрывать нельзя, вам нужно найти только яблоки .... если интересно расскажу решение )

@101picofarad 11 ай бұрын

десятилетия использую подыбный прием в матлабе и в голову не приходило, что это это так называется ;)

@rubbbik 9 ай бұрын

Очень познавательно, но почему бы не использовать вместо конструкции range(len()), enumerate

@KostyaRUS72 11 ай бұрын

идти от каждого числа с подсуммировкой пока сумма массима не даст K. Когда k = массиву, удалять его из переменной возвращать массив в ruturn

@KostyaRUS72 11 ай бұрын

эт специальо мысли вслух тк видос на задаче поставил на паузе, и я не программист

@luckyiam3532 11 ай бұрын

Are you switched to Python from Java??

@lidersh.2360 11 ай бұрын

Спасибо за ролик, классно! Но хочу уточнить что при пояснении первого примера границы левая и правая могут совпасть и тогда это будет подмассив из 1 элемента Просто по объяснению создаётся впечатление что длина подмассива начинается с двух элементов, хотя в самом примере было указано что длина может быть и 1 элемент

@dimitro.cardellini 10 ай бұрын

Або ми по гіршому варіанту оцініюємо, або по середньому ) Чого б це хеш-мапа в гіршому випадку працювала, як O(1)? Вона буде працювати, як O(n) То ж, загальна склпжність за часом буде O(n^2) + пам'яті O(n)

@Insidepointg 11 ай бұрын

крутое решение, правда пока не прогнал через дебагер не понял. на пальцах сложно)

@AToPAt 11 ай бұрын

Сколько времени дается на выполнение подобной задачи на собеседовании?

@denisgluk431 11 ай бұрын

у нас скорее всего на бумажке попросят прикинуть.. т.е. как-то так не ходу.. я на одном просто рогом упёрся и какие-то вещи на пальцах объяснял, чтобы каракули долго не писать

@MyTradePro 9 ай бұрын

Он же сказал в видео - 20 минут

@iintersergey 10 ай бұрын

Из неприятного для таких задач, самостоятельно придумать финальное решение довольно сложно, те после объяснения то понятно, но сам с ходу можешь придумать только второй вариант за N^2

@dmitrymikheev121 11 ай бұрын

а тут разве не надо обнулять значения мапы после того как к answer плюсуем?

@SS-io3lb 11 ай бұрын

Попробуй в коде перед тем, как задавать вопрос. Может оказаться, что вопрос бессмысленный.

@user-jp8jl5mg3v 11 ай бұрын

Конечно нет, мы в мапе по ключу храним число подмассивов, которые начинаются в 0, заканчиваются где-то до текущего элемента и имеют сумму равную ключу. Её обнулять нет смысла.

@rathmines4979 11 ай бұрын

у меня есть вопросы к последнему алгоритму, как там вышло 5, если считать вручную, то у меня вышло 13, может и больше было бы, но лень все перебирать

@SayXaNow 11 ай бұрын

надо считать все числа подмассива, а вы видимо считали выборочно. для K=5 и массива [4,2,1] ответ 0, а не 1, нельзя складывать 4 и 1 без двойки. проще всего это проверить квадратичным алгоритмом с полным перебором. он дает ответ 5.

@kitsiv 10 ай бұрын

мда, это конечно обычным людям нереально достичь. Пойду дальше писать калькуляторы

@nikolay2263 11 ай бұрын

Еще есть способ решить через префиксную сумму, также o(n) по времени и памяти

@holy-del 11 ай бұрын

А он через что решил?

@solarine-7354 11 ай бұрын

Имеется ввиду что можно не использовать хэш мапу

@MegaBeshka 11 ай бұрын

у меня какие то ноунеймы попросили вернуть из такого массива все возможные варианты элементов этого массива, которые в сумме дают число к

@ivanovchin 11 ай бұрын

ого, ты начал показывать код на python, а не на java, неожиданно

@aleksandr_t 7 ай бұрын

Кстати, мне давали такую задачу в Яндексе

@LockMyClock 3 ай бұрын

Почему быстрое решение имеет код в два раза больше ,чес обычное?

@bitowner 11 ай бұрын

Кажись баг в реализации, даже 2 бага... Если subarray_sum будет 0, то в хэш запишется {0:2}, а в answer добавится то, что по ключу -5 (зачем от 0 отрезать кусок с суммой -5, чтобы получить 5?) Может случится ситуация, когда to_remove будет 0 и тогда к answer добавится 2, вместо 1 Не проверял, надо тесты погонять

@SayXaNow 11 ай бұрын

[-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

@bitowner 11 ай бұрын

@@SayXaNow спасибо за подробное объяснение! Действительно, даже если {0: 1} увеличивается, то всё правильно работает, и эти отрезки с 0 суммой учитываются в ответе

@bjj1423 6 ай бұрын

Без отладчика пока не особо понимаю как работает код)

@user-iz2mo2gr8j 6 ай бұрын

Почему тут не было бинарного поиска😢?По моему,это было бы самое оптимальное и рациональное решение!

@lyanochka65473 11 ай бұрын

наконец то пример решения на Python!!! (единстыенный язык, который я идеально понимаю...)

@Deletedeletedelete 11 ай бұрын

Код на питоне понятен даже если впервые видишь язык. Собственно его популярность отчасти обусловлена простотой

@ivormacky5078 11 ай бұрын

@@Deletedeletedelete Не преувеличивайте, там достаточно фишек в синтаксисе, вопрос в другом используются они или нет!

@LonelyRiderStonerBand 11 ай бұрын

Являюсь front end разработчиком порядка 6 лет, за все время, как ни пытался, так и не понимаю, вообще ни в какую все алгоритмы, задачи решать не умею, пересмотрел уже миллиард ресурсов и обучающих видео, все равно ничего не понятно, на сегодня спасает chatGpt. Буду рад совету что делать в такой ситуации, может какую-то литературу или курсы.

@mityaoreh 11 ай бұрын

Привет! Тоже фронтендер, но поменьше) Решать задачи, просто решать задачи, тренировать мозг и глаза, формировать насмотренность. имхо такая микросфера, где опыт очень сильно решает. Я открываю Литкод - делаю простые - усложняю, пока не сломаюсь - изучаю решения, записываю/учусь применять/решаю подобные. В алгосах главное уметь в пространные концепции, «Грокаем Алгоритмы» очень мне помогло в свое время с освоением и пониманием что вообще в таких задачах происходит, у тебя на самом деле есть небольшое количество концепций, которые надо изучить и, самое важно, понять, чтобы уметь применять

@LonelyRiderStonerBand 11 ай бұрын

@@mityaoreh привет. Благодарен за совет, буду наверстывать упущенное хоть это и очень тяжело мне дается

@mityaoreh 11 ай бұрын

@@LonelyRiderStonerBand отлично понимаю) удачи, сил и терпения, всё обязательно получится :)

@LonelyRiderStonerBand 11 ай бұрын

@@mityaoreh Thanks mate ;)

@user-hu8ls1rb3c 11 ай бұрын

27б)))))

@user-gq5lt7ew6k 11 ай бұрын

Как ты это решаешь?

@kingsman9354 11 ай бұрын

Так надо сказать, или нет?

@andreiantonov7303 11 ай бұрын

надо

@mrxDots 11 ай бұрын

Надо говорить. 99% что задачу не поменяют, «видеть», «знать как решать» это еще не«решить», плюс 80% успеха прохождения алгоритмической сессии - много говорить, объяснять логику и трейдоффы

@korniienkooleh5547 10 ай бұрын

разве второй вариант это не O(n^2 / 2)

@101picofarad 11 ай бұрын

А для чего может быть полезен результат такого решения?

@user-vo2fq6my8x 11 ай бұрын

Для развития алгоритмического мышления.

@101picofarad 11 ай бұрын

@@user-vo2fq6my8x Т.е. этот алгоритм ни где не используется ;)?

@bazilval 11 ай бұрын

@@101picofarad можно представить, например, что вы ищете временной период, когда денежный баланс на счёте был равен определенной сумме

@user-yp7xd9tk5i 11 ай бұрын

а это же ещё и префиксные суммы?

@user-yp7xd9tk5i 11 ай бұрын

а, позже в видео сказали)

@vladimirpek 11 ай бұрын

Поставил на паузу: Sliding window

@mrxDots 11 ай бұрын

Sliding window сработает только если все числа >= 0

@d0paminer 11 ай бұрын

@@mrxDotsсработает в любом случае, просто он медленный

@coderunner1462 11 ай бұрын

Саша, у тебя грубая ошибка в видео где 1млн просмотров. В части про бинарный поиск ты показываешь на доске не правильно левую границу поиска и соотв. середину поиска тоже. Это сбивает с толку. Хотя код потом правильно описан. Странно что в комментариях никто этого не упомянул.

@user-nm1ld5bb8l Ай бұрын

как человек который живет в Лондоне вместа сам говорит сум?

@TTTuTTT 5 ай бұрын

привет меня зовут саша лукин и я работаю в компании Гугл в ЛОНДОНЕ! Слышишь с..а, в ЛОНДОНЕ!!! Не то что ты. А я в ЛОНДОНЕ! саша лукин и в ЛОНДОНЕ! Вот я какой! Ахахаха охохохо я неипически крут!

@Denisko123 9 ай бұрын

Сначала подумал, что это задачка, которую я вчера решал на Литкоде. Аж охренел ))) Но там попроще, там просто надо найти ключи двух элементов, дающих в сумме ту же 5 (здесь нет решений). Решается элементарно через два for. Тут посложнее задачка.

@kotikkoty6649 5 ай бұрын

Может быть, я лох, но покажите, кто до хтой задачи додумается сам за 20 минут, не зная типового решения? Или вопрос в том, что это прям базовое типовое решение, которое и так все знают?

@Sergey-Primak 11 ай бұрын

14:17 - "но при этом мы тратим O(n) памяти" и еще мы тратим время на поиск в этой памяти "отрезаемых кусков" - O(n) в итоге время алгоритма примерно равно O(2*n)

@asethone 11 ай бұрын

В терминах Big O (O-большое), константы не учитываются при рассчете алгоритмической сложности, поэтому итоговая сложность записывается именно как O(n). Рекомендую подробнее почитать про оценку сложности алгоритмов.

@Sergey-Primak 11 ай бұрын

@@asethone согласен;-) но алгоритм с O(n) используемый в цикле m раз, всегда будет быстрее, чем тот же цикл с алгоритмом с неправильной оценкой сложности O(3*n). сложности у алгоритмов одинаковы - скорости разные

@asethone 11 ай бұрын

@@Sergey-Primak Ну вопрос оптимизации - это уже отдельная тема. Уменьшить количество проходов по циклу после того, как ты придумал быстрое решение всегда можно успеть. Главное, и самое сложное на собеседованиях - это как раз придумать такое решение, которое именно в терминах Big O будет наиболее оптимальным. А то, что ты там лишний раз добавишь O(n) вне цикла - это никого даже не смутит, ведь O(n) + O(n) все еще O(n).

@surrrogatehuman7653 11 ай бұрын

Так надо говорить, что знаешь решение или нет....

@inex550 11 ай бұрын

Блетб. Гениально

@user-vz5pe6yo2n 11 ай бұрын

Работник гугла рекламирует яндекс?

@salawat007 11 ай бұрын

Да.

@xz8928 11 ай бұрын

я думал сначала отсортировать массив и использовать метод двух индексов

@user-qp9tg5pn5e 11 ай бұрын

тогда вообще ответ поменяется

@xz8928 11 ай бұрын

@@user-qp9tg5pn5e да я это уже понял )

@richlance 11 ай бұрын

С двумя индексами, кажется, можно и без хеш-мап решить

@MrKOHKyPEHT 11 ай бұрын

Что за пайтон? Где джава? )

@karelalex 11 ай бұрын

Петухон, Жава, какя разница?

@helgisnezhin7928 8 ай бұрын

Как это можно понимать??? Ну почему я такой тупой(((((

@user-qd2tm8gh7l 10 ай бұрын

верните, пожалуйста, видео про хеш-сеты, я не досмотрел

@user-qd2tm8gh7l 10 ай бұрын

благодарю

@acthanger7420 11 ай бұрын

Разреши задать один вопрос - почему ты рекламу в ролики вставляешь? Это просто средство доп. заработка или может ты кайфуешь от того факта, что твой канал на Ютубе приносит деньги? P.S. Я ни в коему случае, не осуждаю и не придераюсь. Мне очень нравится твой контент, а этот вопрос чисто от любопытства. Так что братан, хорош, контент в кайф, вот такого бы побольше)

@asethone 11 ай бұрын

Я тоже обратил внимание. Интересно, какая должна быть сумма за рекламу, чтобы даже чел, работающий мидлом в лондоне, согласился ее опубликовать у себя на канале) Без негатива. Просто тоже любопытно.

@voropai4k 11 ай бұрын

Занимался долго спортпрогой, задача супербаза, не думал, что такое простенькое может где-то попасться

@syavorskiy 11 ай бұрын

Это не совсем O(n): решение использует функции работы с массивами, у которых неизвестно, что внутри. В отсутствие индекса тому же get'у понадобится в самом плохом случае пробежать весь массив. Кроме того, операции добавления элементов в массив и изменения их значений тоже не бесплатны. Это очень хорошо видно при работе с базами данных, на десятках и сотнях тысяч записей. Так что было бы интересно сравнить производительность второго и третьего решения на большом массиве. Скажем, в 1000 элементов.

@syavorskiy 11 ай бұрын

@@SayXaNow да, я прочитал вашу дискуссию ) жаль, что после того, как свой коммент написал. Отличный тест, спасибо!

@denisgluk431 11 ай бұрын

глупости какие-то.. опираться на то что в языке массивы не честные.. ну представь что они нормальные, что ты сам их делал.. или хеш можно выкинуть, представить у тебя конечные суммы и тупо массивом заменить, достаточного размера.. можно вон дополнительный проход по массиву сделать и максимальный размер суммы определить заранее

@asinas302 11 ай бұрын

Первое, что пришло в голову - решить через Segment Tree

@HopeOfMankind_ 11 ай бұрын

Это как

@asinas302 11 ай бұрын

@@HopeOfMankind_ почему-то мой комментарий был удален. Почитайте про дерево отрезков для суммы. Оно позволяет достаточно быстро, за logN отвечать на запрос от нахождении суммы на любом отрезке tree[l;r] , хотя в данном случае префиксы будут эффективнее, потому что у нас же не один отрезок.

@pika4u380 11 ай бұрын

Ничего себе, Саша начал писать на Python. Java такой: Ну да ну да, пошёл я😹

@ivanserg6393 11 ай бұрын

Почему-то нет инофрмации по типам данных. Если это int, то можно и красивее через гистограмму, без хэшмэпы, если же это float - то могут быть близкие числа по типу 1.000002, 1.000001, 1.999997 для которых вычитание работать не будет в силу двоичности данных. И хэшмап тоже работать не будет при некоторых хэшированиях, т.к. все хэши совпадут, что приведет к o(n^2)

@sergeev_oleg 11 ай бұрын

По условию, видимо, массив из целых чисел. Алгоритмические задачи обычно решаются с помощью базовых типов данных.

@ivormacky5078 11 ай бұрын

Это как это через гистограмму?

@user-jp8jl5mg3v 11 ай бұрын

N квадрата по памяти не будет, мы в целом что-то меняем в хеш мапе n раз . Мы там храним информацию только о тех подмассивах, которые начинаются с нулевого элемента.

@ivanserg6393 11 ай бұрын

@@user-jp8jl5mg3v n шагов, на каждом шаге n проверок, если хэш совпадает

@ivanserg6393 11 ай бұрын

@@sergeev_oleg вообще в алгоритмических задачах всегда обговаривают тип, если это важно для решения.

@user-vo2fq6my8x 11 ай бұрын

Не рекомендую брать ЯндекПрактикум Python (личный опыт). Он чуть-чуть дает знания и денег своих не стоит, цена сильно завышено. Порядка 70% материалов, вам придется искать самостоятельно в интернете (Да, Яндекс просит денег, за то что бы он вам написал, то что нужно понгуглить). Ну а про баги самой платформы вы можете почитать отзывы в интернете, они впринципе все одинаковые. Если вам кто-то оплатит 100% курса (или около того), то смело можно идти, но приготовьтесь страдать!

@mrxDots 11 ай бұрын

Я учился и потом работал в практикуме. Это правда, что всей информации на курсе в материалах недостаточно, Яндекс дает каркас, это цель курса - научиться самостоятельно изучать недостающую информацию (ее на самом деле не так много). + у вас есть вебинары, где можете задавать вопросы + код ревью где ревьюер тоже подскажет как делать лучше и комьюнити для обмена информацией. Если что-то не нравится (бывают разные менторы), можно обратиться к куратору. Надо понимать, что практикум это для тех кто хочет учиться, а не чтобы знания положили в голову. На финале вы сделаете несколько проектов, без понимания вы их сделать не сможете, так что уйдете со знаниями и опытом. Конечно это не уровень «сразу идти работать», если курс вам это обещает - не верьте. практикум хорош для переквалификации и понятного старта. Я нанимал людей после практикума и других курсов, у первых в голове хорошее понимание «что и зачем», а не «потому что я так прочитал»

@user-vo2fq6my8x 11 ай бұрын

@@mrxDots Яндекс просит от 50 000 до 250 000 р. (скидки не рассматриваем) за то что, ...Яндекс дает каркас, это цель курса - научиться САМОСТОЯТЕЛЬНО изучать недостающую информацию... Повторюсь, ищите материалы самостоятельно, но платите за это деньги и не малые - именно в этом у меня основная претензия. На одно из Финальных Заданий - нужно было использовать HTML страницу, которую предоставлял ЯП. И именно из-за этой страницы, часть проекта не работало. Причина, которой она не работала, не расскрывалась в материалах ЯП. (собственно для решения того Финального задания матреиалы ЯП вообще не нужны были, так как в них не содержалась информация нужная для написания требуемого кода в ФЗ.)

@denisgluk431 11 ай бұрын

и чего там питон дают или что ещё?

@user-mo8zi6uc4d 11 ай бұрын

Я бы сказал, что сложность n*log(n), если используем map и от n до n^2 для unordered_map (из-за возможных колизий).

@h00per12 11 ай бұрын

Так тут int используется, то коллизий вообще нет, то есть get(key) будет работать за константу

@user-cu4pd6qk5w 11 ай бұрын

@@h00per12 Коллизии могут быть, даже если хранятся обычные инты, хэш-функция будет вычисляться по модулю от длины массива

@user-mo8zi6uc4d 11 ай бұрын

@@h00per12 коллизии появляются из-за того, что хеш функции для бесконечного кол-ва ключей дают ограниченное кол-во хешей и тут не важно инт или нет. Нужно будет либо растить мапу до более чем n^2 памяти (ведь парадокс дней рождение root(n)) либо будут коллизии

@denisgluk431 11 ай бұрын

если числа небольшие то мапа небольшая будет, хоть вообще без мапы это делай.. даже тупо массивом достаточного размера замени, где ячейка под каждую сумму предусмотрена..

@asethone 11 ай бұрын

Ох, уже столько дискуссий на эту тему в комментариях развели. Это довольно странно. Так как Саша сказал про хеш-мапы, то речь именно про unordered_map, а не map. В *_среднем_* время извлечения и вставки нового элемента в хеш-таблицу именно O(1) - тут не может быть каких-то споров. Да, в случае большого количества коллизий, и в случае добавления нового элемента при превышении коэффициента загрузки, что в свою очередь ведет к рехешированию всего содержимого хеш-мапы, это время может быть близко к O(n). Но, опять таки, в подобных задачках тебя, как правило, должна интересовать именно *_средняя_* сложность алгоритма, поэтому тут все корректно оценено. Мораль: не нужно быть *пессимистом* и всегда смотреть на _худший_ случай. Будьте *программистом* и смотрите на _усредненный_ 😉

@user-fz7jx9uv9y 11 ай бұрын

Предполагаю, что последний алгоритм решается не за O(n), а за O(n * log2n), мы же не знаем, как извлекаются значения из словаря, скорее всего там бинарный поиск с логарифмической сложностью, либо необходимо делать массив количеств, и извлекать значения за O(1) и тогда общая сложность алгоритма будет O(n), но памяти может быть израсходовано значительно больше

@mityaoreh 11 ай бұрын

значения из словаря всегда за О(1) же

@asethone 11 ай бұрын

Реализация конкретного словаря зависит от библиотеки, но в основном - это хеш-таблицы. К примеру, стандартная библиотека шаблонов STL в C++ предлагает unordered_map, в документации, к которой, можно увидеть, что средняя скорость извлечения, удаления и добавления нового элемента O(1). Аналоги: HashMap в Java, dict в Python. Возвращаясь к STL в C++, там есть и обычный контейнер map, который реализован как раз на красно-черном двоичном дереве - в нем-то, все аналогичные действия и занимают O(log n). В основном, когда говорят про словари, имеются в виду именно хеш-мапы, о чем как раз Саша и говорит на 10:05. Поэтому алгоритмическая сложность последнего решения действительно O(n), и ошибки здесь нет.

@Lammax2012 11 ай бұрын

под капотом обычно массив

@vshcherb 11 ай бұрын

@@asethone Добавление нового элемента в хеш-таблицы не o(1), необходимо добавлять сложность увеличения и ребалансировки хеш-таблиц, так что *среднняя сложность* равна все той-же o(log n). В общих условиях, где не выделяется 2 ГБ память на все int hashtable.