Задача из Собеседования на 160,000 Евро в Год
Vložit
- čas přidán 24. 06. 2024
- Разбираем популярную задачу, которую спросили у моего знакомого на собеседовании на позицию Senior Software Developer в Берлине.
После успешного прохождения нескольких собеседований, ему предложили зарплату в 160.000 евро в год.
Задача состоит в поиске двух чисел из отсортированного массива, в сумме дающих заданное число.
00:00 Вступление
00:54 Условие задачи
02:09 Перебор всех пар
03:38 HashSet
06:11 Бинарный поиск
09:49 Два указателя
Создал Telegram канал, в котором рассказываю о жизни в Лондоне, работе в Google и подготовке к собеседованиям. Подписывайтесь: t.me/saschalukin
-1 и 8 тоже дадут 7 :)
Хехе, точно, не заметил :)
@@sashalukin а я увидел, но так как профан, подумал что не все условия увидел)))
Так, закреплю коммент, чтобы все увидели) В начале в первом примере тоже два ответа и тоже можно вернуть любой из них.
Круто, что заметили :)
ток хотел написать
@@sashalukin я конечно не программист, но почему нельзя например из непосредственно результата "К" начать вычитать числа и сравнивать их с предложенными?
Очень рад, что вы вернулись.
Комментарий в поддержку канала. Автор, ты молодец, спасибо за труд!
Здравствуйте, давно увидел ваше видео в рекомендациях и жалею что не посмотрел ранее. Спасибо за контент👍
как здорово, что Саша вернулся на канал! спасибо и ждем новые видео!
Хорошее объяснение и понятный код, спасибо. Ждём ещё, удачи в развитии!
очень интересный материал, спасибо =) хотелось бы больше подобных видео
Надо в собеседовании ввести задание, чтоб и пытуемый посчитал пальцы на правой руке, затем на левой, а затем назвал общее количество пальцев на обеих руках.
Ппфф легко же. 5 на левой, 5 на правой, значит общее количество 25
@@pontypilat_0338 разве не 30?
изи, 55
@@carbonara_13 ты меня опередил
@@carbonara_13 а разве не жолтый?
Очень круто обьясняешь! Только учусь программировать и из роликов понял много полезных методов, алгоритмов поиска значений! Очень благодарен!
Почитай Вирта: Структуры и Алгоритмы, целый мир откроешь
С возвращением) спасибо за ролик)
Топ-видос! Посмотрел и сохранил в один из своих плейлистов еще в феврале, но вернулся и разобрался в последнем варианте решения только сейчас, когда твердо решил апнуть скилл в решении задачек (наткнулся на эту задачу на leetcode). Оказывается, лучшее решение не такое уж нетривиальное, как показалось на первый взгляд
Снимай пожалуйста ещё ролики. У тебя очень хорошо получается. Очень познавательно!!! Спасибо!!
Наконец то вы вернулисссссьььььььь
Рад, что появилось свежее видео. Интересная задача и подходы к ее решению, доступное объяснение👍💪
Супер!!! Спасибо огромное, за классное видео. 👍👍👍
Классное видео. Автор все очень доступно и понятно объясняет.
Саше спасибо большое за труд и терпение к "диванным ворчунам" )))
Очень круто, спасибо за видео!
Браво! Ваши видео просто замечательные! Продолжайте в том же духе! Хотелось бы узнать больше «инсайдерской» информации, как человеку, которому только предстоит работать :)
Ещё не работаешь в этой сфере?
Отлично объясняешь! Выпускай почаще видео)
Спасибо. Доходчиво:) Подписка однозначно за годный контент:)
Спасибо, так просто о сложном. Вы талант. Надо клон сделать и учителем в школу.
Решал такую на литкоде методом двух указателей left, right как раз. Спасибо за видео
Я даже не поленился и нашёл. Может кому-то интересно будет порешать такую задачу на leetcode. Задача с уровнем easy (на вход дан неотсортированный массив) "1. Two Sum". И ещё одна похожая задача уровня medium "167. Two Sum II - Input Array Is Sorted" (на вход дан отсортированный массив).
Спасибо! Очень интересно. Подписался. Буду ждать новых видео
Cпасибо за интересную задачу!
хочу ещё!)
Очень круто, ждем еще интересных и реальных задачек)
Мне вот эта задача по математике понравилась. Бородатая и не совсем айтишная, но может будет интересно :)
Встречаются два приятеля - математика:
- Ну как дела, как живешь?
- Все хорошо, растут два сына дошкольника.
- Сколько им лет?
- Произведение их возрастов равно количеству голубей возле этой скамейки.
- Этой информации мне недостаточно.
- Старший похож на мать.
- Теперь я знаю ответ на твой вопрос.
Сколько лет сыновьям? (Ответ логичный и однозначный)
Довольно простое задание, как мне показалось, наверное потому, что во многих заданиях, даже простых( на строки, например ) нужно идти с двух сторон.
Ураа,ждал твоих роликов давно)
Спасибо за видео! Очень интересная задача 👍👍🔥🔥🔥🔥
Ура, вернулся :)
8:44 - тут лучше определить, что является входом и что является выходом нашей части, отвечающей за бинарный поиск и вынести наш бинарный поиск в отдельный компонент. Это как упростит чтение и понимание кода, так и сделает код более модульным. По сути тут происходит тоже самое что и в "HashSet"
Прекрасная подача. Так держать!
очень интересное и понятное объяснение, топ. спасибо!
Я сначала не поняла решение с двумя указателями, а потом по коду как всё поняла. Очень интересно и хорошо рассказано, пасеба!
Впервые столкнулся с вашим каналом. Смотрю на обложку, на название ролика и совсем не понимаю: а что тут сложного, это ведь решит даже ребёнок! Стал смотреть, а здесь оказалось программирование, тогда понятно стало. Забавно.
Ролик интересный, подача грамотная, успехов!
Круто и интересно, обязательно продолжай.
Это было очень интересно!)
лукас не глядя. давно ждал возвращения))
Просто очередной комментарий про то, что надо микрофон-петличку 😉 В целом огонь-пулемёт, продолжай обязательно у тебя отлично получается 💪 12к подписчиков за год на 4 видосах говорит о том, что ты всё делаешь правильно, материал актуальный! Подтяни качество, сделай выпуски регулярными и будет круто. Если это тебе надо конечно 😜
Я думаю, что Александр это делает для общего развития - творческий порыв. Поверь мне, с такими мозгами ему доход от ютуба так... на шоколадки.
Приятно слушать - классная подача
Спасибо большое, скоро приступлю к таким задачам)
Спасибо, круто!
Бинарный поиск требует проверки на размер массива, так как при маленьком размере у нас время процессора уходит на математические вычисления середины и проверки (просто пометка от ноунейма).
Спасибо за видео. Люблю искать возможности для оптимизации. Пока с такими задачами не сталкивался, но если столкнусь, то буду знать, как сделать код быстрым, да ещё и красивым.
Мужик,твой материал на таком легке заходит,учу js,до такого уровня ещё не дошел,но о чем ты рассказываешь понятно,и заходит лайтово, спасибо за труд !
Удачи тебе,юный подаван.
Рад, что ты вернулся!
Оооочень круто!
Задача элементарная, двигаем окно и смотрим если сумма меньше, двигаем правую часть, если сумма больше двигаем левую часть.
На статистике данных по распределению чисел мин, Макс и n можно эмпирически вывести функцию которая весьма точно будет попадать в индекс массива, да ещё давать длинну окна.
Плюс для отриц и положит, будет два окна
9:49 - оно и есть. Только одно окно для любых элементов и любого результата суммы
А вот что делать если 3 слагаемых - пока непонятно.
@@kriguitar4753 воспользоваться решением примера именно из собеседования, чуть доработав, чтобы записываемый ответ слагался с оставшимися в окне элементами.
@@kriguitar4753 два указателя + хешсет
Отрицательные числа крайне редко в реальных задачах встречаются. Задачи эти теоретики диванные создают.
@@webblyy 2 указателя уже не нужны если есть хэш-сет
была такая задача в Яндексе))
спасибо за разбор, супер!
Спасибо!
Очень интересно и полезно🎉
Классно все объяснил. Казалось бы просто решается, но как послушаешь, сколько есть вариантов, голова идет кругом. Да еще и на Джаве, красавчик!
Чего такого в яве то? возможно выбран как один из хорошо читаемых языков. напиши на питоне, уже не каждый поймет.
Я давно забросил программировать но первая мысль была от от 7 вычитать по одному и искать равные ! Последнее решение просто наикрасивейшее!!!
Можно так же идти с позиции I+1, чтобы не проверять уже пройденное число
последнее решение не работает
отличный контент и подача материала !! единственное упущение, мало роликов ((
Спасибо, я только начал подступаться к программированию. Ничего еще не знаю, но все равно интересно.
Интересно 👍
Палец и т.п. за этот видос!
По больше пожалуйста таких задача ! С разжевыванием и примером. Можно и не только на Алгоритмы.
Но и более простые на возвраты. На операции логики сравнения и т.п и т.д.
Вообще Очевидные цифры в особенности по условию - сразу бросаются в глаза.
Как пример из первого пункта: 8 + (-1)
Т.е крайние цифры к условию и цифры с отрицательным значением.
Опять же надо смотреть и на контекст условия..
Но учитывая последние примеры то как раз таки отрицательные цифры используются.
Саша Лукин, спасибо за твой труд! Крайне хорошо поясняешь. Уметь пояснять сложное простыми словами это очень важный и полезный навык. В будущем, мы, люди, все чаще и чаще будем коммуницировать.
Хотел бы тебя спросить вот о чем: Как ВИДЕТЬ более эффективный вариант чаще? Ведь до этого же надо додуматься! Вот ты привел разные решения, но ведь про них надо было сообразить . Как развивать соображалку то? ;)
Пока, развитие сооражалки в алгоритмах вижу такой: Ты смотришь как решают другие. В голове откладываются разные подходы. А потом методом брутфорса при решении той или иной задачи пишешь код. Либо ты видишь такую задачу, которая очень похожа на ту, которую ты уже видел ранее и применяешь то, что ты помнишь. Но все это цепляется на знание и на способность мозга вспомнить и увидеть схожие черты с ранее решенной задаче. Есть ли другие способы ?
Чтобы развивать навык решения задач, нужно решать задачи. Чтобы развивать навык решать задачи эффективно, нужно решать задачи эффективно.
Итого. Берёшь задачу, САМ решаешь её в лоб, то есть самым примитивным и очевидным способом. Пытаешься найти другие способы (да, сам). Сравниваешь полученные варианты, анализируешь их плюсы и минусы, ищешь слабые места, места, которые можно улучшить и т.д. и т.п. Смотришь, как другие люди решают другие задачи (да-да, именно другие) в поисках вдохновения. Смотришь, не появились ли ещё идеи, которые можно применить к своей задаче. Когда ты уже сдедал всё, что мог сделать сам, тогда и только тогда можно смотреть, как другие решают такие же задачи. Тогда будет развитие, а если просто смотреть на других, хоть и на лучших, ну хз... Сильно ли накачаешься, наблюдая за тем, как сильные силачи тягают железо? Вопрос риторический.
Можешь не благодарить 😌
@@Dimarious.Gбоюсь сравнение с силачами не уместно, когда мы смотрим на силача, мы смотрим на процесс, и не применяем никаких усилий, а когда мы смотрим решение задачи, то мы смотрим на решение, а не на процесс, и применяем усилия для понимания
@@Dimarious.Gа так думаю ты прав в остальном
Приятно слушать. Да ещё и Java)) спасибо
Интересно, спасибо за контент
очень полезный алгоритм
Контент топчик. Как раз изучаю алгоритмы и структуры данных, недавно узнал о 2-х указателях. Теперь бы еще научиться все это видеть в конкретных задачах.
Спасибо :)
С опытом придет, если до этого решил 10 задач на два указателя, то и в 11 увидишь.
Если хочешь потренить, то вот сайт, на нем все к собесам готовятся:
leetcode.com/problemset/all/?topicSlugs=two-pointers
Решай easy задачи, и если не можешь придумать решение (а так в начале всегда будет), то смотри в комментах (секция Discuss). Удачи!
Подскажите, пожалуйста, по алгоритмам годные источники. И по структурные данным, если можно
@@hacamadahimichiru6110 Сам сейчас прохожу направление CS от Принстона на Курсере (от профессора Седжвика). Еще хвалят курс CS50 от Гарварда, но сам не пробовал. Все бесплатно и в интернете. Гуглите.
@@kselnaag2482 спасибо!
Спасибо большое за информацию)
спасибо, интересно и познавательно
Спасибо! Мне кажется, не лишним будет упомянуть, что сортировка это в среднем еще плюс O(n log n) по времени к оценке сложности, если изначально массив не отсортирован.
Ага, и часто эту задачу дают в виде неотсортированного массива, где нужно найти 3 числа, в сумме дающих k.
В таком случае просто в начале сортируем массив, потом пишем цикл прохода по массиву (это будет первое число из 3), а второе и третье каждый раз пытаемся найти методом двух указателей как в видео.
Тогда время будет O(n^2) и O(n log n) от сортировки не влияет на итоговую сложность.
Нет, в таком случае алгоритм работать не будет
Пример: [0, 3, 2], к=3
Тогда начальная пара (0, 2) в сумме даст меньше, чем надо, и следующая пара для рассмотрения будет (3, 2)
@@dimapimenov6807 у тебя не сортирован массив. После сортировки все будет ок.
Ну так и вопрос был про несортированный массив и алгоритм на нем
Если я вообще правильно понял вопрос... Я решил что вопрос про метод 2х указателей
Вначале подумал и придумал вариант такой: берем первый и суммируем с последним. Если больше К, то берем предпоследний и тд. Ползем назад сравнивая с первым. Потом берем второй и опять сравниваем с последним, идя навстречу второму. О том, что последний можно не сбрасывать почему-то не додумался )
Большое спасибо! Очень интересно )
Я бы сказал формализовать вообще всё.
Спасибо большое!! Вы молодец!
Круто!
Любопытно, что некоторые задания из ЕГЭ сложнее, чем реальная задача с собеседования )
это же хорошо, подготовился к проф ЕГЭ, и можешь идти в гугл
Да, если не учитывать бэкграунд кандидата(опыт работы с платформами, модулями и тд), выпускник ЕГЭ подходит)
Задания из ЕГЭ по информатике?
На егэ ты в других условиях, на собесе иногда не можешь решить самую простую задачу, хотя без собеса решаешь задачи, которые в 10 раз сложнее.
@@abcdefghi1489 на ЕГЭ тоже стресс не маленький)
Это работает если нужно найти лишь одну пару чисел.
Но больше спасибо за объяснение. Очень легко воспринимается такая подача!)
Спасибо, очень интересно!
В втором решении тоже два цикла. Второй скрыт - это поиск в хешсете (скрытый
перебор по нему)
Чего??? Поиск в хешсете О(1)
@@Z3rgatul sets (аналог C++ std::unordered_map), Dictionary и Tuple (аналог std::map в C++) контейнеры для хранения списка ключей реализованы на базе бинарного дерева (сложность поиска log(n)). Хз. Почему во всех мануалах python написано O(1). Может кто объяснит?
@@sergeifomin3225 кто сказал что set в python это бинарное дерево? там hashtable
@@sergeifomin3225 | Нет, unordered_set и unordered_map это хэш-таблицы с O(1). Не дерево
Здорово, не занимаюсь программированием, никак не решаюсь начать, но настолько четкое объяснение, что понял даже я. Спасибо!
Спасибо! А программирование начать учить никогда не поздно, сейчас очень много моих друзей не из айти переходят в айти. Только время нужно выделить, я бы ориентировался хотя-бы на год, если довольно плотно заниматься.
Удачи!
@@sashalukin спасибо большое за совет и напутствие
Многое теряете, я когда по работе понял, что делаю много повторяющихся действий, решил автоматизировать процессы, я даже что такое IDE не знал. Уровень на доске меня пока восхищает, стремлюсь к тому, что бы сделать его банальным.
@@AVS11176 я вообще в банке работаю на данный момент, ну и как везде, 70% работы это эксель и какое-то статистическое ПО (типо R, у нас САС). То когда я залезал в VBA или в SAS все смотрели как на мага-чародея
А. Бал. Деть. Узнал много нового. Спасибо!
Я смог сам дойти до последнего решения в видео)
Спасибо автору за контент
Здравствуйте! Спасибо большое за разбор.
Задача интересная и довольно популярная. Но отдельный интерес вызывает именно математическое обоснование данного алгоритма. А именно: доказать, что решение найдется при движении именно левого поинтера, когда сумма меньше и правого, когда сумма больше.
Не сможете помочь разобрать? Обоснование порой спрашивают чаще, чем сам алгоритм. Спасибо!
массив упорядочен, поэтому. Если сумма меньше k мы сдвигаем левый указатель и теперь он указывает на большее число, а если больше чем k двигаем правый и он указывает на меньшее число.
@@bpht618 , здравствуйте. Да, я согласен, интуитивно и логически алгоритм полностью понятен. Но хочется именно математически обоснование/доказать в более менее лаконичной форме.
Возможно надо просто действовать от противного и на каком-то шаге N показать, что иной суммы нет, потому что иначе бы мы ее точно встретили на шаге К
Я бы доказывал через инвариант (условие, которое выполняется изначально и сохраняется после каждой итерации цикла).
Инвариант: все элементы массива с индексами < l, а также с индексами > r точно нам не подходят.
Изначально это условие выполняется, потому что элементов массива с индексами меньше 0 или больше nums.length-1 нет.
При каждой итерации мы считаем сумму элементов. Так как массив отсортирован, то по нашему инварианту arr[r] - максимальный по значению элемент среди всех тех, которые потенциально могут быть в ответе.
Если arr[l] + arr[r] < k, то arr[l] + arr[i
Но в Гуглах-Амазонах крайне редко спрашивают доказательства. Там все очень структурированно, т.е. есть четкие правила, по которым идут собеседования и правила, по которым они оцениваются. Грубо говоря, это решил/не решил задачу, придумал оптимальное/не оптимальное решение, написал код без багов/с багами, и.т.д. Но объяснить простыми словами, почему решение работает, конечно, нужно.
А в наших компаниях это любят, согласен. Меня несколько раз просили доказать какие-то штуки, самым популярным было, что добавление элемента в динамический массив работает в среднем за О(1).
www.quora.com/Do-I-need-to-study-mathematical-proofs-in-algorithms-for-a-software-engineer-interview-with-Facebook-Google
@@sashalukin спасибо! Да, Вы правы, такие вопросы на математические доказательства/обоснования мы получали именно в наших компаниях… интересно :) всего доброго, с нетерпением ждём новых выпусков! :)
Саша, привет! Большое спасибо за разборы задач. То, что ты делаешь - круто. Успехов тебе и каналу, продолжай. У меня вопрос: у тебя есть контактная почта или другие каналы связи? Хотелось бы написать: узнать и задать буквально пару вопросов про твой опыт переезда айтишника в Индонезию. Успехов!
сочувствую вам, если вы считаете, что ЭТО - круто...
Гениальное решение, спасибо)
шикарный разбор
Последнее решение даже не пришло в голову, пока не зашла речь про указатели, но чёрт возьми, оно такое простое и офигенное!
согласен
Здравствуйте! Спасибо за видео). Вопрос не совсем по теме: какая основная разница между массивом и коллекцией, которая позволяет "одновременно" перебирать все ее элементы?
Не совсем понятно что значит "одновременно" перебирать все ее элементы. Collection наследуется от Iterable т.е. все коллекции позволяют перебирать, если речь об этом. Могу предположить что речь идет о том что массивы фиксированной длины, а реализации интерфейса Collection динамической, т.е. увеличиваются по мере добавления элементов. Массив также используется под капотом некоторых реализаций интерфейса Collection например ArrayList и частично HashSet. Ну т.е. более простой базовый объект для более сложных структур данных. В контексте задачи наверное речь про то что поиск по HashSet за О1 а не за On как у массива отсюда и ускорение.
Да, меня заинтересовало то, что сложность использования коллекции - О(1), а не О(n). То есть коллекция способна перебирать элементы настолько быстро, что время, затраченное на перебор, считается постоянным?
@@enternickhere почитайте "как работает HashMap в джава". элементы там хранятся в массиве связанных списков или массиве бинарных деревьев. Индекс массива вычисляется(а не перебирается) в зависимости от содержимого элемента при его помещении. И также потом при его поиске и извлечении.
Почитал, понял)
отличное видео, спасибо)
Круто и очень понятно, спасибо
(Во втором примере) Разве проверка наличия элемента а массиве равна O(1)? Мне кажется, что больше на O(n) похоже, тогда алгоритм будет О(n^2)?
Тож заметил) set.contains написал и радуется)
В первом варианте нужно добавить проверку: если сумма двух чисел больше К, то вернуться в начало первого цикла, потому что дальнейшие суммы будут также больше К, т.к. массив отсортирован.
В варианте с бинарным поиском при делении на две части нужно использовать целочисленное деление на 2, потому что в какой-то момент программа будет пытаться найти элемент с не целым номером индекса, например, 6,5.
Делится тип Integer. Он при делении дает целочисленное значение без остатка. Пример: 13/2 = 6;
Java, в отличии от всяких питонов и js, строго типизированный язык и в нём исключено получить дробное значение при делении целых чисел, если явно это не указывать. При этом, результат деления всегда округляется до меньшего числа. То есть даже если провести операцию, к примеру, 59 / 10, то результат будет 5. Однако, если хотя бы одно из делимых чисел привести к дробному типу, вроде (float)59 / 10 или 59.0 / 10, то результат вычисления уже будет 5.9.
@@Rameronos не округляется до меньшего, а отбрасывается дробная часть - разницу хорошо видно если делить на 10 не 59, а минус 59
Зачем целочисленное деление, если есть битовый сдвиг? Или в джава он под запретом?
@@Rameronosпитон тоже строго типизирован, но динамически.
Спасибо за видео)
Можно попросить выпускать видео по чаще чем раз в год?)
Пока в России еще ютуб работает..
Попалось видео, я щас пока что ничего не понимаю, но мне очень интересно)
это разве не Two Sum с литкода?
Я конечно не работал ни в Амазоне, ни даже в эбэй, но из многолетней трудовой практики знаю, что никто, находясь в здравом уме, не будет платить большие деньги, только из за того, что ты задачки порешал)
Только из-за того, что задачки порешал, платить конечно не будут. Это условие обязательное, но не достаточное. А вот если задачки не порешал, то деньги ТОЧНО не будут платить.
@@realvall и тем не менее, данная задача не скажет ничего от слова совсем (т. е. 0%) по поводу уровня программиста. Соответственно, самый правильный способ - убрать эту задачу из собеседования и оставить олимпиадникам
@@sovaz1997
Ну тебе виднее)
@@sovaz1997эти задачи и не должны показывать "уровень программиста". на собеседованиях они для того, чтобы понять, есть у соискателя задатки логического мышления, необходимого в будущей работе, или на этапе выполнения простенькой задачки с ним уже можно закончить общение. а касательно того, что такие задачки нужно убрать из собеседования - я с вами и согласен, и нет, одновременно, как бы странно это не звучало. правильного ответа тут нет, зависит все от того, чья компания и кто определяет, как он будет отбирать сотрудников. если ваша, то, вероятно вы правы, и вам сотрудники, умеющие решать такие задачки, не нужны. если компания не ваша, то, скорее всего ее владельцам виднее, кто им нужен и какие задачки он должен уметь решать.
@@sovaz1997 если будете пробовать трудоустраиваться в yandex, там будет много таких и более сложных задач. Если пойдёте в дойче банк, то они тоже несколько задач подобных давали.
Спасибо, очень помогло!
Ой, кажется, я влюбилась)
Я далеко не разработчик (всего лишь МП), но было понятно и интересно)
Тоже заметила в начале про две пары, дающие правильный ответ)
Недавно подписался и вот
так ведь в set.contains еще один цикл есть. Причем его длина растёт. Так что в итоге проходов больше чем n.
Тоже не понимаю, это вроде как жадный алгоритм, у него сложность, в худшем случае, может быть и O(n*log_n), если не ошибаюсь. Но точно больше n
@@vladimir2208 n^2. Проходов будет столько же, сколько и в первом варианте. Разница только в том, что в первом второй цикл от i+1 до n, а во втором - от 0 до i-1.
Суммарно n запросов к хешсету работают за линейное время
Хотя и каждый запрос может работать дольше, чем за константу.
@@user-hg3wh1sm8k ну да, каждый запрос - это O(n). Да ещё и формирование таких запросов тоже O(n). Вот и получится O(n^2).
@@sibedir не каждый запрос это O(n)
Всё обращения к множеству суммарно работают за O(n)
Для доказательства этого советую лекции по хешированным структурам на ютубе, или просто почитать neerc
То есть, в написанной программе есть запросы к сету, работающие за линию суммарно, и остальные выче
Остальные вычисления - линейны, складываем (не умножаем! Каждый запрос не работает за линию!), получаем тоже линию
Шикарно! Здорово! Полезно! Лукас субскрайбович! 🤣👍
Прикольно, что сейчас в ЕГЭ задачи сложнее))
Годика 3 назад были задачи, что из списка чисел надо посчитать все пары, которые в сумме кратны заданному К. Вернуть все эти пары - это пара доп действий. Сейчас задаче ещё лютее)
@@kaspersky_ege у меня что-то похожее было, сдавала в 2017 году, решила на 4 балла 27-е в 2, что ли, цикла (без вложенного)
@@reisders с 2017 многое поменялось, мы теперь на компьютере экзамен пишем и программа реально должна работать на 1млн строк эффективно
ЕГЭ по информатике вообще можно в одном Экселе сделать
@@sed0k да конечно, особенно 24 задание и 15 удобно, 14 более менее, 1 и 13 -- один кайф, 10 -- обязательно в экселе, 6 -- ну естественно
к чему коммент? я сказал, что задача в 27 сложнее, пир чем эксель? почему? что за комментарий? я не понимаю.
я умер.
Во втором варианте все равно время работы O(n^2), так как поиск в хэшсете - тоже представляет из себя внутренний цикл еще и со сравнением входящего значения..., отличие лишь в том, что количество пар теперь образуется реверсивно на увеличение лесенки, а не на уменьшение как с двумя циклами, так еще и больше на одну пару становится: -3 и пусто, а уж потом 0 и -3, 1 и -3, 1 и 0. Явой не занимаюсь, могу лишь предположить, что просто поиск в хэшсете работает быстрее, чем функция for, но не забываем про время обращения к памяти , если работать с большим объемом + постоянное пополнение хэшсета - это тоже еще одно действие, на которое тратится время. Вообще плохо считать время выполнения по формуле, которая опирается только на количество данных)
>>"Во втором варианте все равно время работы O(n^2)"
Именно так, но видимо автор является очень "современным" программистом, т.е. о том, что внутри происходит особо не задумывается.
Логарифмическое время там должно быть на поиск. Пополнение за константу. Те сложность должна быть n + log(n)
Саша главное твоя подача! Красавчик
Как же круто он объясняет!!!
А разве hashset не использует цикл внутри себя для поиска элемента в массиве?
Нет, он высчитывает нужный индекс массива по ключу и просто возвращает данные по этому индексу
@@alex.lokhman Ага, пока коллизий нет, да там все "просто", а вот если есть...)
Та что уж там.. на миллион евро год
спасибо, интересно. Не запускай канал плз
Приятно, что моя первая мысль и была лучшим решением