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

[@sashalukin]

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

[@sb9185]

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

[@dark.960]

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

[@habib_sultan]

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

[@IvanYugov]

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

[@runneso]

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

[@IvanYugov]

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

[@nixxik__]

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

[@СтаниславВокеутов-ю2э]

Гораздо сложнее 27

[@violetjellyfish2089]

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

[@kazarovroman]

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

[@blitz_kiy5104]

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

[@mavn-code]

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

[@daitedve1984]

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

[@SoulPervert]

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

[@galo4kin]

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

[@edmond-dantes-1796]

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

[@gggppp228]

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

[@edmond-dantes-1796]

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

[@sudo_ku]

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

[@Lammax2012]

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

[@saveekglushchenko6903]

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

[@v.demchenko]

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

[@hopelesssuprem1867]

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

[@Baha996]

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

[@Керик-у7ю]

Последнее решение на доске верно объяснено, но код не корректный. Для массива 1 2 3 4 1 и k = 10, выдаст 3, хотя верный ответ 2

[@alexandersuvorov5465]

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

[@dimasbka]

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

[@kotikGGG]

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

[@hello_world_zz]

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

[@flyingdinosaur8871]

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

[@leomysky]

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

[@vacsa]

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

[@ПаблоЭскобар-л8щ]

Спасибо за разбор задач, очень прокачивают. Угарнул с того, что на литкод добавили тест k = 0, nums =[1]. При моей реализации ответ выходит один, думаю, как разобрать этот случай

[@ПавелКононов-м6б]

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

[@makige1378]

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

[@MaruiInfantry]

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

[@konstantin1648]

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

[@naneri]

leetcode

[@roman_je_rkoff]

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

[@hoopengo2289]

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

[@user-qm5fv5by5z]

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

[@neiro22]

Здравствуйте, разве использование хэш мапы не даёт нам асимпотику O(n log n) ?

[@glingrad7444]

дает o(1) с точки зрения времени и o(n) с точки зрения памяти

[@user-lk8n0fgjk]

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

[@danilas2206]

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

[@ЕвгенийКутовой-й6ы]

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

[@vladsssl]

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

[@Arkham_nine]

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

[@overskam2699]

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

[@ВикторМорозов-ы9ф]

Балдеж!

[@KostyaRUS72]

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

[@KostyaRUS72]

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

[@glukh0v_d1ma]

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

[@bzych8965]

мой способ менее эффективный, потому что я использовал поиск в массиве, а не в хэш таблице создаём массив префиксных сумм, потом проходимся по нему и ищем есть ли в нём (текущий элемент-5)

[@Poli.Pavlovich]

Финальное решение очень элегантное

[@znsoft]

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

[@dimitro.cardellini]

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

[@rathmines4979]

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

[@SayXaNow]

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

[@LockMyClock]

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

[@antonmuzeev]

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

[@WildRhinocerosDriver]

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

[@DasBosch]

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

[@cinemaSage_1]

Are you switched to Python from Java??

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

[@nicholasspezza9449]

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

[@rubbbik]

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

[@flybenazer-chanel]

спасибо

[@a1dwow]

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

[@bjj1423]

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

[@Sergey-Primak]

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

[@asethone]

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

[@Sergey-Primak]

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

[@asethone]

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

[@Igorkornilovspb]

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

[@dmitrymikheev121]

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

[@SS-io3lb]

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

[@lyanochka65473]

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

[@Deletedeletedelete]

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

[@ivormacky5078]

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

[@101picofarad]

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

[@alexanderzaretskiy4188]

Класс)

[@hopelesssuprem1867]

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

[@bitowner]

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

[@SayXaNow]

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

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

[@MegaBeshka]

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

[@LonelyRiderStonerBand]

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

[@mityaoreh]

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

[@LonelyRiderStonerBand]

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

[@mityaoreh]

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

[@LonelyRiderStonerBand]

@@mityaoreh Thanks mate ;)

[@AToPAt]

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

[@denisgluk431]

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

[@MyTradePro]

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

[@kingsman9354]

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

[@andreiantonov7303]

надо

[@mrxDots]

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

[@nikolay2263]

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

[@holy-del]

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

[@solarine-7354]

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

[@IvannZ_Ru]

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

[@IvannZ_Ru]

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

[@iintersergey]

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

[@101picofarad]

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

[@ЕвгенийИзотов-н7п]

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

[@101picofarad]

@@ЕвгенийИзотов-н7п Т.е. этот алгоритм ни где не используется ;)?

[@bazilval]

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

[@korniienkooleh5547]

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

[@ИгорьЛукин-и7ж]

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

[@Baha996]

класс

[@kitsiv]

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

[@Матвей-ф4ч1ъ]

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

[@ivanovchin]

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

[@Insidepointg]

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

[@Denisko123]

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

[@Рома-с5д]

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

[@ivanserg6393]

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

[@sergeev_oleg]

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

[@ivormacky5078]

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

[@ivanserg6393]

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

[@ivanserg6393]

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

[@vladimirpek]

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

[@mrxDots]

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

[@d0paminer]

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

[@sinushkin]

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

[@aleksandr_t]

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

[@brilliantgame8090]

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

[@kotikkoty6649]

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

[@acthanger7420]

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

[@asethone]

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

[@sidhott]

Но оценка O(N) не учитывает ни построение хешмапа, ни поиск по нему. ОК, поиском можно пренебречь, т.к. он упорядочен, но как быть с тем, что на каждой итерации перестраивается либо сам хешмап, либо его индекс?

[@alfagamma2499]

О(5*N)==O(N), т.е. речь о решении задачи за время сопоставимое с количеством данных, когда N стремится к бесконечности. Поэтому особо разницы нет, конечный пользователь зачастую не заметит разницу в обработке чего-либо за 1мс или 5мс, но если функция уйдет в степени, то дело плохо

[@sidhott]

@@alfagamma2499 а откуда Вы взяли 5х, почему время построения хешмапа сопоставимо с его размером, а не, скажем, квадратом его размера?

[@alfagamma2499]

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

[@sidhott]

@@alfagamma2499 а какая разница достраиваю я хеш или строю с нуля, если мне память двигать? n раз передвинуть n/2 ячеек памяти -- это O(n)? "много действий" -- это сколько конкретно, О(индекса)? P.S. прошёл по массиву чисел раз -- только звучит красиво, т.к. O(n) + O(n2) = O(n2).

[@101picofarad]

​@@sidhottможно родить массив с упреждением и удваивать его при переполнении чтобы не перекидывать его в памяти при каждой записи.

[@КіріллПустовий]

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

[@h00per12]

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

[@ДмитрийВанюшкин-м2л]

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

[@КіріллПустовий]

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

[@denisgluk431]

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

[@asethone]

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

[@TTTuTTT]

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

[@МихаилЧ-д2х]

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

[@mityaoreh]

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

[@asethone]

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

[@Lammax2012]

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

[@vshcherb]

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

[@inex550]

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

[@МаксимДементьев-э5с]

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

[@МаксимДементьев-э5с]

благодарю

[@syavorskiy]

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

[@syavorskiy]

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

[@denisgluk431]

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

[@MrKOHKyPEHT]

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

[@karelalex]

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

[@surrrogatehuman7653]

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

[@НиколайРоманов-р4ф]

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

[@salawat007]

Да.

[@Тёма-ш7г]

27б)))))

[@xz8928]

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

[@Гэтсби-ь6ю]

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

[@xz8928]

@@Гэтсби-ь6ю да я это уже понял )

[@richlance]

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

[@nwn0zero0on]

Разве map не имеет сложность всех операций log(n)? Тогда получается O(n*log(n))

[@pika4u380]

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