Задача из Собеседования на 160,000 Евро в Год

Разбираем популярную задачу, которую спросили у моего знакомого на собеседовании на позицию Senior Software Developer в Берлине.
После успешного прохождения нескольких собеседований, ему предложили зарплату в 160.000 евро в год.
Задача состоит в поиске двух чисел из отсортированного массива, в сумме дающих заданное число.
00:00 Вступление
00:54 Условие задачи
02:09 Перебор всех пар
03:38 HashSet
06:11 Бинарный поиск
09:49 Два указателя

[@sashalukin]

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

[@user-tp8ku2hp9u]

-1 и 8 тоже дадут 7 :)

[@sashalukin]

Хехе, точно, не заметил :)

[@semchic888]

@@sashalukin а я увидел, но так как профан, подумал что не все условия увидел)))

[@sashalukin]

Так, закреплю коммент, чтобы все увидели) В начале в первом примере тоже два ответа и тоже можно вернуть любой из них. Круто, что заметили :)

[@FariusFriends]

ток хотел написать

[@user-qm7pl3ez4s]

@@sashalukin я конечно не программист, но почему нельзя например из непосредственно результата "К" начать вычитать числа и сравнивать их с предложенными?

[@user-lu9gz7yf2v]

Надо в собеседовании ввести задание, чтоб и пытуемый посчитал пальцы на правой руке, затем на левой, а затем назвал общее количество пальцев на обеих руках.

[@pontypilat_0338]

Ппфф легко же. 5 на левой, 5 на правой, значит общее количество 25

[@Bartolph]

@@pontypilat_0338 разве не 30?

[@carbonara_13]

изи, 55

[@MiroSlave1]

@@carbonara_13 ты меня опередил

[@SmihoTvor_lite]

@@carbonara_13 а разве не жолтый?

[@fedot0ff]

Комментарий в поддержку канала. Автор, ты молодец, спасибо за труд!

[@dashkarandash4217]

очень интересный материал, спасибо =) хотелось бы больше подобных видео

[@vladnykytenko8394]

Очень рад, что вы вернулись.

[@user-qz3kw1xd6v]

Хорошее объяснение и понятный код, спасибо. Ждём ещё, удачи в развитии!

[@Wild6-8]

Здравствуйте, давно увидел ваше видео в рекомендациях и жалею что не посмотрел ранее. Спасибо за контент👍

[@kriguitar4753]

8:44 - тут лучше определить, что является входом и что является выходом нашей части, отвечающей за бинарный поиск и вынести наш бинарный поиск в отдельный компонент. Это как упростит чтение и понимание кода, так и сделает код более модульным. По сути тут происходит тоже самое что и в "HashSet"

[@user-hj2es2vj6p]

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

[@user-sp5fv4kw2n]

Почитай Вирта: Структуры и Алгоритмы, целый мир откроешь

[@ruslanabishev]

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

[@grbak]

Топ-видос! Посмотрел и сохранил в один из своих плейлистов еще в феврале, но вернулся и разобрался в последнем варианте решения только сейчас, когда твердо решил апнуть скилл в решении задачек (наткнулся на эту задачу на leetcode). Оказывается, лучшее решение не такое уж нетривиальное, как показалось на первый взгляд

[@Coralinerbx]

Снимай пожалуйста ещё ролики. У тебя очень хорошо получается. Очень познавательно!!! Спасибо!!

[@akella512]

Рад, что появилось свежее видео. Интересная задача и подходы к ее решению, доступное объяснение👍💪

[@Gremelka9]

С возвращением) спасибо за ролик)

[@andreipopov2700]

Классное видео. Автор все очень доступно и понятно объясняет. Саше спасибо большое за труд и терпение к "диванным ворчунам" )))

[@jury2753]

Супер!!! Спасибо огромное, за классное видео. 👍👍👍

[@kovsaw]

Очень круто, спасибо за видео!

[@Rewsbt]

Наконец то вы вернулисссссьььььььь

[@igorratnik2357]

Спасибо. Доходчиво:) Подписка однозначно за годный контент:)

[@alexeybubakov6885]

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

[@sinsinegobaffa7321]

Довольно простое задание, как мне показалось, наверное потому, что во многих заданиях, даже простых( на строки, например ) нужно идти с двух сторон.

[@user-er9hm1vg6f]

Браво! Ваши видео просто замечательные! Продолжайте в том же духе! Хотелось бы узнать больше «инсайдерской» информации, как человеку, которому только предстоит работать :)

[@nikolaifaist]

Ещё не работаешь в этой сфере?

[@withotsoul7252]

Спасибо за видео! Очень интересная задача 👍👍🔥🔥🔥🔥

[@denismerigold486]

Cпасибо за интересную задачу! хочу ещё!)

[@user-hn3mq8dp5r]

Спасибо, так просто о сложном. Вы талант. Надо клон сделать и учителем в школу.

[@justfairytale5722]

Решал такую на литкоде методом двух указателей left, right как раз. Спасибо за видео

[@alarmolord]

Я даже не поленился и нашёл. Может кому-то интересно будет порешать такую задачу на leetcode. Задача с уровнем easy (на вход дан неотсортированный массив) "1. Two Sum". И ещё одна похожая задача уровня medium "167. Two Sum II - Input Array Is Sorted" (на вход дан отсортированный массив).

[@staspanyukov4822]

Отлично объясняешь! Выпускай почаще видео)

[@usernamer519]

очень интересное и понятное объяснение, топ. спасибо!

[@tomysmit5386]

Очень круто, ждем еще интересных и реальных задачек)

[@COOKIEMONSTER90]

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

[@gitarre_spielen]

Впервые столкнулся с вашим каналом. Смотрю на обложку, на название ролика и совсем не понимаю: а что тут сложного, это ведь решит даже ребёнок! Стал смотреть, а здесь оказалось программирование, тогда понятно стало. Забавно. Ролик интересный, подача грамотная, успехов!

[@user-us9os1gp5y]

Ураа,ждал твоих роликов давно)

[@bigtreeSSS]

Круто и интересно, обязательно продолжай.

[@lestwa4265]

Я сначала не поняла решение с двумя указателями, а потом по коду как всё поняла. Очень интересно и хорошо рассказано, пасеба!

[@Gypuk]

Бинарный поиск требует проверки на размер массива, так как при маленьком размере у нас время процессора уходит на математические вычисления середины и проверки (просто пометка от ноунейма). Спасибо за видео. Люблю искать возможности для оптимизации. Пока с такими задачами не сталкивался, но если столкнусь, то буду знать, как сделать код быстрым, да ещё и красивым.

[@user-nb3gw2zf8n]

Прекрасная подача. Так держать!

[@titanovsky]

Спасибо большое, скоро приступлю к таким задачам)

[@AlexZvukov]

Просто очередной комментарий про то, что надо микрофон-петличку 😉 В целом огонь-пулемёт, продолжай обязательно у тебя отлично получается 💪 12к подписчиков за год на 4 видосах говорит о том, что ты всё делаешь правильно, материал актуальный! Подтяни качество, сделай выпуски регулярными и будет круто. Если это тебе надо конечно 😜

[@ps-037]

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

[@slavamobile3733]

Задача элементарная, двигаем окно и смотрим если сумма меньше, двигаем правую часть, если сумма больше двигаем левую часть. На статистике данных по распределению чисел мин, Макс и n можно эмпирически вывести функцию которая весьма точно будет попадать в индекс массива, да ещё давать длинну окна. Плюс для отриц и положит, будет два окна

[@kriguitar4753]

9:49 - оно и есть. Только одно окно для любых элементов и любого результата суммы А вот что делать если 3 слагаемых - пока непонятно.

[@WillsherT]

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

[@webblyy]

@@kriguitar4753 два указателя + хешсет

[@KKZ_5000_RUB]

Отрицательные числа крайне редко в реальных задачах встречаются. Задачи эти теоретики диванные создают.

[@user-tk7nh1jw3y]

@@webblyy 2 указателя уже не нужны если есть хэш-сет

[@rinat_nur]

Приятно слушать - классная подача

[@user-xp8zi5bs1d]

Спасибо! Очень интересно и полезно🎉

[@alxndrnz]

Ура, вернулся :)

[@marksreider7645]

Спасибо, круто!

[@yanazork]

Это было очень интересно!)

[@Pavlo_Synytsia]

спасибо, интересно и познавательно

[@user-xw8ur4sc6t]

лукас не глядя. давно ждал возвращения))

[@cathello2900]

Интересно 👍 Палец и т.п. за этот видос! По больше пожалуйста таких задача ! С разжевыванием и примером. Можно и не только на Алгоритмы. Но и более простые на возвраты. На операции логики сравнения и т.п и т.д. Вообще Очевидные цифры в особенности по условию - сразу бросаются в глаза. Как пример из первого пункта: 8 + (-1) Т.е крайние цифры к условию и цифры с отрицательным значением. Опять же надо смотреть и на контекст условия.. Но учитывая последние примеры то как раз таки отрицательные цифры используются.

[@Coralinerbx]

Спасибо большое!! Вы молодец!

[@nurlybekmardanov5486]

Рад, что ты вернулся!

[@VPmagicshow]

Оооочень круто!

[@iloginu]

Вначале подумал и придумал вариант такой: берем первый и суммируем с последним. Если больше К, то берем предпоследний и тд. Ползем назад сравнивая с первым. Потом берем второй и опять сравниваем с последним, идя навстречу второму. О том, что последний можно не сбрасывать почему-то не додумался )

[@EliJahMCI]

Интересно, спасибо за контент

[@user-rj2pq9jk5w]

Спасибо большое за информацию)

[@user-eg7od8nu1u]

Я давно забросил программировать но первая мысль была от от 7 вычитать по одному и искать равные ! Последнее решение просто наикрасивейшее!!!

[@user-kh9rp6tu2b]

Можно так же идти с позиции I+1, чтобы не проверять уже пройденное число

[@xelnagamex]

последнее решение не работает

[@ntvisigoth]

Саша Лукин, спасибо за твой труд! Крайне хорошо поясняешь. Уметь пояснять сложное простыми словами это очень важный и полезный навык. В будущем, мы, люди, все чаще и чаще будем коммуницировать. Хотел бы тебя спросить вот о чем: Как ВИДЕТЬ более эффективный вариант чаще? Ведь до этого же надо додуматься! Вот ты привел разные решения, но ведь про них надо было сообразить . Как развивать соображалку то? ;) Пока, развитие сооражалки в алгоритмах вижу такой: Ты смотришь как решают другие. В голове откладываются разные подходы. А потом методом брутфорса при решении той или иной задачи пишешь код. Либо ты видишь такую задачу, которая очень похожа на ту, которую ты уже видел ранее и применяешь то, что ты помнишь. Но все это цепляется на знание и на способность мозга вспомнить и увидеть схожие черты с ранее решенной задаче. Есть ли другие способы ?

[@Dimarious.G]

Чтобы развивать навык решения задач, нужно решать задачи. Чтобы развивать навык решать задачи эффективно, нужно решать задачи эффективно. Итого. Берёшь задачу, САМ решаешь её в лоб, то есть самым примитивным и очевидным способом. Пытаешься найти другие способы (да, сам). Сравниваешь полученные варианты, анализируешь их плюсы и минусы, ищешь слабые места, места, которые можно улучшить и т.д. и т.п. Смотришь, как другие люди решают другие задачи (да-да, именно другие) в поисках вдохновения. Смотришь, не появились ли ещё идеи, которые можно применить к своей задаче. Когда ты уже сдедал всё, что мог сделать сам, тогда и только тогда можно смотреть, как другие решают такие же задачи. Тогда будет развитие, а если просто смотреть на других, хоть и на лучших, ну хз... Сильно ли накачаешься, наблюдая за тем, как сильные силачи тягают железо? Вопрос риторический. Можешь не благодарить 😌

[@byesedd]

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

[@byesedd]

@@Dimarious.Gа так думаю ты прав в остальном

[@user-wq4fc8zv9i]

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

[@user-yd2wm6gt5k]

Удачи тебе,юный подаван.

[@NikolayMishin]

была такая задача в Яндексе)) спасибо за разбор, супер!

[@olafk2628]

Спасибо! Мне кажется, не лишним будет упомянуть, что сортировка это в среднем еще плюс O(n log n) по времени к оценке сложности, если изначально массив не отсортирован.

[@sashalukin]

Ага, и часто эту задачу дают в виде неотсортированного массива, где нужно найти 3 числа, в сумме дающих k. В таком случае просто в начале сортируем массив, потом пишем цикл прохода по массиву (это будет первое число из 3), а второе и третье каждый раз пытаемся найти методом двух указателей как в видео. Тогда время будет O(n^2) и O(n log n) от сортировки не влияет на итоговую сложность.

[@dimapimenov6807]

Нет, в таком случае алгоритм работать не будет Пример: [0, 3, 2], к=3 Тогда начальная пара (0, 2) в сумме даст меньше, чем надо, и следующая пара для рассмотрения будет (3, 2)

[@Boosty931]

@@dimapimenov6807 у тебя не сортирован массив. После сортировки все будет ок.

[@dimapimenov6807]

Ну так и вопрос был про несортированный массив и алгоритм на нем

[@dimapimenov6807]

Если я вообще правильно понял вопрос... Я решил что вопрос про метод 2х указателей

[@russellstar]

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

[@realvall]

Только из-за того, что задачки порешал, платить конечно не будут. Это условие обязательное, но не достаточное. А вот если задачки не порешал, то деньги ТОЧНО не будут платить.

[@sovaz1997]

@@realvall и тем не менее, данная задача не скажет ничего от слова совсем (т. е. 0%) по поводу уровня программиста. Соответственно, самый правильный способ - убрать эту задачу из собеседования и оставить олимпиадникам

[@anti_middle_ages]

@@sovaz1997 Ну тебе виднее)

[@realvall]

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

[@QuickCube]

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

[@andrewteterin975]

Приятно слушать. Да ещё и Java)) спасибо

[@el_dorado]

Спасибо, я только начал подступаться к программированию. Ничего еще не знаю, но все равно интересно.

[@infomail8550]

Классно все объяснил. Казалось бы просто решается, но как послушаешь, сколько есть вариантов, голова идет кругом. Да еще и на Джаве, красавчик!

[@user-bx5ze4jw5p]

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

[@kselnaag2482]

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

[@sashalukin]

Спасибо :) С опытом придет, если до этого решил 10 задач на два указателя, то и в 11 увидишь. Если хочешь потренить, то вот сайт, на нем все к собесам готовятся: leetcode.com/problemset/all/?topicSlugs=two-pointers Решай easy задачи, и если не можешь придумать решение (а так в начале всегда будет), то смотри в комментах (секция Discuss). Удачи!

[@hacamadahimichiru6110]

Подскажите, пожалуйста, по алгоритмам годные источники. И по структурные данным, если можно

[@kselnaag2482]

@@hacamadahimichiru6110 Сам сейчас прохожу направление CS от Принстона на Курсере (от профессора Седжвика). Еще хвалят курс CS50 от Гарварда, но сам не пробовал. Все бесплатно и в интернете. Гуглите.

[@hacamadahimichiru6110]

@@kselnaag2482 спасибо!

[@user-hd9hw7nl1n]

отличный контент и подача материала !! единственное упущение, мало роликов ((

[@leomysky]

Круто и очень понятно, спасибо

[@eugen7965]

В втором решении тоже два цикла. Второй скрыт - это поиск в хешсете (скрытый перебор по нему)

[@Z3rgatul]

Чего??? Поиск в хешсете О(1)

[@sergeifomin3225]

@@Z3rgatul sets (аналог C++ std::unordered_map), Dictionary и Tuple (аналог std::map в C++) контейнеры для хранения списка ключей реализованы на базе бинарного дерева (сложность поиска log(n)). Хз. Почему во всех мануалах python написано O(1). Может кто объяснит?

[@Z3rgatul]

@@sergeifomin3225 кто сказал что set в python это бинарное дерево? там hashtable

[@rasimbot]

@@sergeifomin3225 | Нет, unordered_set и unordered_map это хэш-таблицы с O(1). Не дерево

[@user-wi4fg7xm2p]

очень полезный алгоритм

[@CoS1NuS1]

Большое спасибо! Очень интересно )

[@user-qy7vv5yx3b]

Я бы сказал формализовать вообще всё.

[@Sam240793]

Спасибо за видео, очень полезно и понятно) А если задача состоит в том, чтобы не два числа найти из массива, а сколько угодно чисел, но чтобы в итоге получилось k, то какой алгоритм лучше использовать в такой задаче? И можно ли ее назвать подобной? 🤔

[@user-pv1ol1vc8k]

Любопытно, что некоторые задания из ЕГЭ сложнее, чем реальная задача с собеседования )

[@vladislavbaranovskii4133]

это же хорошо, подготовился к проф ЕГЭ, и можешь идти в гугл

[@Grim_J0nes]

Да, если не учитывать бэкграунд кандидата(опыт работы с платформами, модулями и тд), выпускник ЕГЭ подходит)

[@dmitry7464]

Задания из ЕГЭ по информатике?

[@abcdefghi1489]

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

[@Whitestarwhitestar]

​@@abcdefghi1489 на ЕГЭ тоже стресс не маленький)

[@user-ri4rk3hn8g]

Круто!

[@user-iq2nq7cj6l]

Спасибо, очень интересно!

[@maksigors]

отличное видео, спасибо)

[@viacheslavmatveichev4039]

Здравствуйте! Спасибо большое за разбор. Задача интересная и довольно популярная. Но отдельный интерес вызывает именно математическое обоснование данного алгоритма. А именно: доказать, что решение найдется при движении именно левого поинтера, когда сумма меньше и правого, когда сумма больше. Не сможете помочь разобрать? Обоснование порой спрашивают чаще, чем сам алгоритм. Спасибо!

[@bpht618]

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

[@viacheslavmatveichev4039]

@@bpht618 , здравствуйте. Да, я согласен, интуитивно и логически алгоритм полностью понятен. Но хочется именно математически обоснование/доказать в более менее лаконичной форме. Возможно надо просто действовать от противного и на каком-то шаге N показать, что иной суммы нет, потому что иначе бы мы ее точно встретили на шаге К

[@sashalukin]

Я бы доказывал через инвариант (условие, которое выполняется изначально и сохраняется после каждой итерации цикла). Инвариант: все элементы массива с индексами < l, а также с индексами > r точно нам не подходят. Изначально это условие выполняется, потому что элементов массива с индексами меньше 0 или больше nums.length-1 нет. При каждой итерации мы считаем сумму элементов. Так как массив отсортирован, то по нашему инварианту arr[r] - максимальный по значению элемент среди всех тех, которые потенциально могут быть в ответе. Если arr[l] + arr[r] < k, то arr[l] + arr[i

[@sashalukin]

Но в Гуглах-Амазонах крайне редко спрашивают доказательства. Там все очень структурированно, т.е. есть четкие правила, по которым идут собеседования и правила, по которым они оцениваются. Грубо говоря, это решил/не решил задачу, придумал оптимальное/не оптимальное решение, написал код без багов/с багами, и.т.д. Но объяснить простыми словами, почему решение работает, конечно, нужно. А в наших компаниях это любят, согласен. Меня несколько раз просили доказать какие-то штуки, самым популярным было, что добавление элемента в динамический массив работает в среднем за О(1). www.quora.com/Do-I-need-to-study-mathematical-proofs-in-algorithms-for-a-software-engineer-interview-with-Facebook-Google

[@viacheslavmatveichev4039]

@@sashalukin спасибо! Да, Вы правы, такие вопросы на математические доказательства/обоснования мы получали именно в наших компаниях… интересно :) всего доброго, с нетерпением ждём новых выпусков! :)

[@hotKorzhik]

Саша, привет! Большое спасибо за разборы задач. То, что ты делаешь - круто. Успехов тебе и каналу, продолжай. У меня вопрос: у тебя есть контактная почта или другие каналы связи? Хотелось бы написать: узнать и задать буквально пару вопросов про твой опыт переезда айтишника в Индонезию. Успехов!

[@romanbykov5922]

сочувствую вам, если вы считаете, что ЭТО - круто...

[@AAzamdjon]

Это работает если нужно найти лишь одну пару чисел. Но больше спасибо за объяснение. Очень легко воспринимается такая подача!)

[@AlexanderBogachuk]

А. Бал. Деть. Узнал много нового. Спасибо!

[@digimax1288]

Здорово, не занимаюсь программированием, никак не решаюсь начать, но настолько четкое объяснение, что понял даже я. Спасибо!

[@sashalukin]

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

[@digimax1288]

@@sashalukin спасибо большое за совет и напутствие

[@AVS11176]

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

[@digimax1288]

@@AVS11176 я вообще в банке работаю на данный момент, ну и как везде, 70% работы это эксель и какое-то статистическое ПО (типо R, у нас САС). То когда я залезал в VBA или в SAS все смотрели как на мага-чародея

[@yury497]

Последнее решение даже не пришло в голову, пока не зашла речь про указатели, но чёрт возьми, оно такое простое и офигенное!

[@NikolayMishin]

согласен

[@egorlazuka770]

Гениальное решение, спасибо)

[@user-lb2bw8xc2y]

Спасибо, очень помогло!

[@enternickhere]

Здравствуйте! Спасибо за видео). Вопрос не совсем по теме: какая основная разница между массивом и коллекцией, которая позволяет "одновременно" перебирать все ее элементы?

[@user-yf8jf3fo2x]

Не совсем понятно что значит "одновременно" перебирать все ее элементы. Collection наследуется от Iterable т.е. все коллекции позволяют перебирать, если речь об этом. Могу предположить что речь идет о том что массивы фиксированной длины, а реализации интерфейса Collection динамической, т.е. увеличиваются по мере добавления элементов. Массив также используется под капотом некоторых реализаций интерфейса Collection например ArrayList и частично HashSet. Ну т.е. более простой базовый объект для более сложных структур данных. В контексте задачи наверное речь про то что поиск по HashSet за О1 а не за On как у массива отсюда и ускорение.

[@enternickhere]

Да, меня заинтересовало то, что сложность использования коллекции - О(1), а не О(n). То есть коллекция способна перебирать элементы настолько быстро, что время, затраченное на перебор, считается постоянным?

[@user-yf8jf3fo2x]

@@enternickhere почитайте "как работает HashMap в джава". элементы там хранятся в массиве связанных списков или массиве бинарных деревьев. Индекс массива вычисляется(а не перебирается) в зависимости от содержимого элемента при его помещении. И также потом при его поиске и извлечении.

[@enternickhere]

Почитал, понял)

[@blushingpie]

(Во втором примере) Разве проверка наличия элемента а массиве равна O(1)? Мне кажется, что больше на O(n) похоже, тогда алгоритм будет О(n^2)?

[@user-fu7ox7ml2u]

Тож заметил) set.contains написал и радуется)

[@user-gt5st3wh2p]

Спасибо за видео) Можно попросить выпускать видео по чаще чем раз в год?) Пока в России еще ютуб работает..

[@user-tn5ik8tb3k]

Я смог сам дойти до последнего решения в видео) Спасибо автору за контент

[@user-wh5mg4fh4k]

Видимо действительно с программистами вообще напряг последнее время, раз такие задачи на собеседовании дают.

[@lsentinell]

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

[@mijlenium]

@@lsentinell Меня на собеседование на 440к рублей в месяц попросили вычислить координаты дрона, уже активно движущегося по заданной траектории, которая стабилизируется с использоваием фази логики с коэффициентом упреждения 0.4 относительно параллельной связки формации, изображающих некую геометрическую фигуру. Из доступных данных - координаты в текущий и следующий момент ведущего дрона из 2й формации, координаты предыдущей секунды "оператора" во 2й формации и текущая позиция на общем маршруте (геометрическая фигура задаётся в виде csv документе в виде уравнений) 2й формаци Т.е. По факту дано всё, но ничего )00)) И даже источника сигнала нет, чтобы с помощью драйвера выяснить что там творит отдельно взятый дрон. Его нужно подстроить под параллельно движущуюся формацию. А проектным заданием, которым я сейчас занимаюсь - нужно научить дроны вовремя разлетаться, чтобы впускать в свой строй новую единицу, которая не сломает всю картину И это на зп всего за 7 тысяч вечнозелёных )) Собираю манатки, еду в амазон в гл офис )0))

[@user-pp6zi7lz7s]

В первом варианте нужно добавить проверку: если сумма двух чисел больше К, то вернуться в начало первого цикла, потому что дальнейшие суммы будут также больше К, т.к. массив отсортирован. В варианте с бинарным поиском при делении на две части нужно использовать целочисленное деление на 2, потому что в какой-то момент программа будет пытаться найти элемент с не целым номером индекса, например, 6,5.

[@user-wn2vu9jb3x]

Делится тип Integer. Он при делении дает целочисленное значение без остатка. Пример: 13/2 = 6;

[@Rameronos]

Java, в отличии от всяких питонов и js, строго типизированный язык и в нём исключено получить дробное значение при делении целых чисел, если явно это не указывать. При этом, результат деления всегда округляется до меньшего числа. То есть даже если провести операцию, к примеру, 59 / 10, то результат будет 5. Однако, если хотя бы одно из делимых чисел привести к дробному типу, вроде (float)59 / 10 или 59.0 / 10, то результат вычисления уже будет 5.9.

[@XEL234234234234]

@@Rameronos не округляется до меньшего, а отбрасывается дробная часть - разницу хорошо видно если делить на 10 не 59, а минус 59

[@DadundddaD]

Зачем целочисленное деление, если есть битовый сдвиг? Или в джава он под запретом?

[@DadundddaD]

​@@Rameronosпитон тоже строго типизирован, но динамически.

[@fahrenheit1863]

В книге алгоритмы Т.Кормена(упражнение 2.3.7) эта задачка в самом начале дается. Там по условию нужно написать алгоритм с O(n lg n). Я сам додумался только до варианта с бинарным поиском. Здорово, из этого видео я узнал что такое хешсеты и метод двойных указателей.

[@aleks3954]

шикарный разбор

[@johnmurdoch8368]

Та что уж там.. на миллион евро год

[@kisoonx]

Во втором варианте все равно время работы O(n^2), так как поиск в хэшсете - тоже представляет из себя внутренний цикл еще и со сравнением входящего значения..., отличие лишь в том, что количество пар теперь образуется реверсивно на увеличение лесенки, а не на уменьшение как с двумя циклами, так еще и больше на одну пару становится: -3 и пусто, а уж потом 0 и -3, 1 и -3, 1 и 0. Явой не занимаюсь, могу лишь предположить, что просто поиск в хэшсете работает быстрее, чем функция for, но не забываем про время обращения к памяти , если работать с большим объемом + постоянное пополнение хэшсета - это тоже еще одно действие, на которое тратится время. Вообще плохо считать время выполнения по формуле, которая опирается только на количество данных)

[@OdinKG]

>>"Во втором варианте все равно время работы O(n^2)" Именно так, но видимо автор является очень "современным" программистом, т.е. о том, что внутри происходит особо не задумывается.

[@ruslibertarian]

Логарифмическое время там должно быть на поиск. Пополнение за константу. Те сложность должна быть n + log(n)

[@Mukhinroman]

Как же круто он объясняет!!!

[@YKupriyanov_]

Саша главное твоя подача! Красавчик

[@user-eb2kh4df6r]

Во втором варианте, все же, оценка не совсем верная. O() -оценка в ХУДШЕМ случае, а не в среднем. В ХУДШЕМ случае (если хеш-функция - хреновая), сложность будет O(n log n). Другое дело, что для int хэш известен. И в конкретном случае с int - все будет верно - O(n), но стоит заменить тип (самое простое обобщение), как все станет совсем не очевидно

[@griglog1309]

Тип не имеет значения, коллизии будут всегда. С int'ами тоже вполне можно упереться в nlogn.

[@user-hg3wh1sm8k]

Суммарно n запросов к хеш таблице будут иметь сложность O(n) И худший случая - линия, кажется, а не логарифм. Однако оценку на среднее время выполнение операции в O(1) можно доказать.

[@griglog1309]

@@user-hg3wh1sm8k Ты не понял, сложность обращения к хэш-таблице в джаве - O(log(n)) в худшем случае

[@user-hg3wh1sm8k]

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

[@user-hg3wh1sm8k]

@@griglog1309 а какой худший случай времени работы одной операции, линия или логарифм, пока что не понял. Кажется, что использование хеш таблицы обычно дает линию в худшем случае, но могу ошибаться. В любом случае, суммарное время работы будет всегда линейным, а я ответил на комментарий, где автор оценивает асимптотику как O(nlogn)

[@sibedir]

так ведь в set.contains еще один цикл есть. Причем его длина растёт. Так что в итоге проходов больше чем n.

[@vladimir2208]

Тоже не понимаю, это вроде как жадный алгоритм, у него сложность, в худшем случае, может быть и O(n*log_n), если не ошибаюсь. Но точно больше n

[@sibedir]

@@vladimir2208 n^2. Проходов будет столько же, сколько и в первом варианте. Разница только в том, что в первом второй цикл от i+1 до n, а во втором - от 0 до i-1.

[@user-hg3wh1sm8k]

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

[@sibedir]

@@user-hg3wh1sm8k ну да, каждый запрос - это O(n). Да ещё и формирование таких запросов тоже O(n). Вот и получится O(n^2).

[@user-hg3wh1sm8k]

@@sibedir не каждый запрос это O(n) Всё обращения к множеству суммарно работают за O(n) Для доказательства этого советую лекции по хешированным структурам на ютубе, или просто почитать neerc То есть, в написанной программе есть запросы к сету, работающие за линию суммарно, и остальные выче Остальные вычисления - линейны, складываем (не умножаем! Каждый запрос не работает за линию!), получаем тоже линию

[@sofiabelousova8586]

Ой, кажется, я влюбилась) Я далеко не разработчик (всего лишь МП), но было понятно и интересно) Тоже заметила в начале про две пары, дающие правильный ответ)

[@hexdragon_]

Длительность алгоритма на 4-5 минутах не равна N. В вашем примере, чтобы добраться до 4-ки, нужно 7 операций сравнения, а размер массива равен 5, поэтому это уже N+2. Сравнивается ведь каждый текущий элемент массива со всеми присутсвующими на данной итерации числами массива set. На Java это хоть и выглядит как одна операция (set.contains()), но если ее развернуть, там будут доп операции сравнения. Так эффективность алгоритмов не считается.

[@borisov4028]

при N+2 например,мы долдны пренебрегать 2

[@galogen999]

Чет не понятно, зачем делать хэшсет если есть волшебная функция которая говорит есть ли элемент с нужным значением в массиве? Почему бы эту волшебную функцию не применить к начальному массиву? По сути же эта функция заменяет цикл и все сводится к О(n2)

[@bulatton]

Так ты же сам и ответил на свой вопрос) С хэшсетом время работы будет O(n), с твоим вариантом будет O(n^2), что значительно хуже, если например данных будет очень много.

[@galogen999]

@@bulatton какая разница искать вхождение в хэшсете или в исходном массиве?

[@bulatton]

@@galogen999 поиск в хэшсете выполняется выполняется за O(1) за счет использования хэш таблиц , а в массиве поиск O(n), потому что для поиска необходимо проходить почти все элементы.

[@djangodev3191]

Недавно подписался и вот

[@coderunner1462]

Саша, в части видео с бинарным поиском ты ошибочно показываешь левую границу поиска на доске, указывая всегда на 0й элемент, а нужно на i+1й, т.е. правее текущего искомого. Из за этого и середина поиска у тебя всегда одна, а должна смещаться вправо