Задача из Собеседования на 160,000 Евро в Год
HTML-код
- Опубликовано: 18 июн 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 я конечно не программист, но почему нельзя например из непосредственно результата "К" начать вычитать числа и сравнивать их с предложенными?
Очень рад, что вы вернулись.
Комментарий в поддержку канала. Автор, ты молодец, спасибо за труд!
очень интересный материал, спасибо =) хотелось бы больше подобных видео
как здорово, что Саша вернулся на канал! спасибо и ждем новые видео!
Хорошее объяснение и понятный код, спасибо. Ждём ещё, удачи в развитии!
Здравствуйте, давно увидел ваше видео в рекомендациях и жалею что не посмотрел ранее. Спасибо за контент👍
Супер!!! Спасибо огромное, за классное видео. 👍👍👍
Очень круто обьясняешь! Только учусь программировать и из роликов понял много полезных методов, алгоритмов поиска значений! Очень благодарен!
Почитай Вирта: Структуры и Алгоритмы, целый мир откроешь
Рад, что появилось свежее видео. Интересная задача и подходы к ее решению, доступное объяснение👍💪
Топ-видос! Посмотрел и сохранил в один из своих плейлистов еще в феврале, но вернулся и разобрался в последнем варианте решения только сейчас, когда твердо решил апнуть скилл в решении задачек (наткнулся на эту задачу на leetcode). Оказывается, лучшее решение не такое уж нетривиальное, как показалось на первый взгляд
Надо в собеседовании ввести задание, чтоб и пытуемый посчитал пальцы на правой руке, затем на левой, а затем назвал общее количество пальцев на обеих руках.
Ппфф легко же. 5 на левой, 5 на правой, значит общее количество 25
@@pontypilat_0338 разве не 30?
изи, 55
@@carbonara_13 ты меня опередил
@@carbonara_13 а разве не жолтый?
Очень круто, спасибо за видео!
С возвращением) спасибо за ролик)
Снимай пожалуйста ещё ролики. У тебя очень хорошо получается. Очень познавательно!!! Спасибо!!
Классное видео. Автор все очень доступно и понятно объясняет.
Саше спасибо большое за труд и терпение к "диванным ворчунам" )))
Наконец то вы вернулисссссьььььььь
Спасибо, так просто о сложном. Вы талант. Надо клон сделать и учителем в школу.
Спасибо! Очень интересно. Подписался. Буду ждать новых видео
Cпасибо за интересную задачу!
хочу ещё!)
Решал такую на литкоде методом двух указателей left, right как раз. Спасибо за видео
Я даже не поленился и нашёл. Может кому-то интересно будет порешать такую задачу на leetcode. Задача с уровнем easy (на вход дан неотсортированный массив) "1. Two Sum". И ещё одна похожая задача уровня medium "167. Two Sum II - Input Array Is Sorted" (на вход дан отсортированный массив).
Очень круто, ждем еще интересных и реальных задачек)
Мне вот эта задача по математике понравилась. Бородатая и не совсем айтишная, но может будет интересно :)
Встречаются два приятеля - математика:
- Ну как дела, как живешь?
- Все хорошо, растут два сына дошкольника.
- Сколько им лет?
- Произведение их возрастов равно количеству голубей возле этой скамейки.
- Этой информации мне недостаточно.
- Старший похож на мать.
- Теперь я знаю ответ на твой вопрос.
Сколько лет сыновьям? (Ответ логичный и однозначный)
Отлично объясняешь! Выпускай почаще видео)
Спасибо. Доходчиво:) Подписка однозначно за годный контент:)
Браво! Ваши видео просто замечательные! Продолжайте в том же духе! Хотелось бы узнать больше «инсайдерской» информации, как человеку, которому только предстоит работать :)
Ещё не работаешь в этой сфере?
Я сначала не поняла решение с двумя указателями, а потом по коду как всё поняла. Очень интересно и хорошо рассказано, пасеба!
Спасибо за видео! Очень интересная задача 👍👍🔥🔥🔥🔥
Прекрасная подача. Так держать!
8:44 - тут лучше определить, что является входом и что является выходом нашей части, отвечающей за бинарный поиск и вынести наш бинарный поиск в отдельный компонент. Это как упростит чтение и понимание кода, так и сделает код более модульным. По сути тут происходит тоже самое что и в "HashSet"
Ура, вернулся :)
очень интересное и понятное объяснение, топ. спасибо!
Круто и интересно, обязательно продолжай.
Впервые столкнулся с вашим каналом. Смотрю на обложку, на название ролика и совсем не понимаю: а что тут сложного, это ведь решит даже ребёнок! Стал смотреть, а здесь оказалось программирование, тогда понятно стало. Забавно.
Ролик интересный, подача грамотная, успехов!
Довольно простое задание, как мне показалось, наверное потому, что во многих заданиях, даже простых( на строки, например ) нужно идти с двух сторон.
Ураа,ждал твоих роликов давно)
Спасибо большое, скоро приступлю к таким задачам)
Спасибо, круто!
Бинарный поиск требует проверки на размер массива, так как при маленьком размере у нас время процессора уходит на математические вычисления середины и проверки (просто пометка от ноунейма).
Спасибо за видео. Люблю искать возможности для оптимизации. Пока с такими задачами не сталкивался, но если столкнусь, то буду знать, как сделать код быстрым, да ещё и красивым.
Приятно слушать - классная подача
Это было очень интересно!)
Оооочень круто!
лукас не глядя. давно ждал возвращения))
Мужик,твой материал на таком легке заходит,учу js,до такого уровня ещё не дошел,но о чем ты рассказываешь понятно,и заходит лайтово, спасибо за труд !
Удачи тебе,юный подаван.
Рад, что ты вернулся!
Задача элементарная, двигаем окно и смотрим если сумма меньше, двигаем правую часть, если сумма больше двигаем левую часть.
На статистике данных по распределению чисел мин, Макс и n можно эмпирически вывести функцию которая весьма точно будет попадать в индекс массива, да ещё давать длинну окна.
Плюс для отриц и положит, будет два окна
9:49 - оно и есть. Только одно окно для любых элементов и любого результата суммы
А вот что делать если 3 слагаемых - пока непонятно.
@@kriguitar4753 воспользоваться решением примера именно из собеседования, чуть доработав, чтобы записываемый ответ слагался с оставшимися в окне элементами.
@@kriguitar4753 два указателя + хешсет
Отрицательные числа крайне редко в реальных задачах встречаются. Задачи эти теоретики диванные создают.
@@webblyy 2 указателя уже не нужны если есть хэш-сет
Классно все объяснил. Казалось бы просто решается, но как послушаешь, сколько есть вариантов, голова идет кругом. Да еще и на Джаве, красавчик!
Чего такого в яве то? возможно выбран как один из хорошо читаемых языков. напиши на питоне, уже не каждый поймет.
Спасибо!
Очень интересно и полезно🎉
Приятно слушать. Да ещё и Java)) спасибо
Я давно забросил программировать но первая мысль была от от 7 вычитать по одному и искать равные ! Последнее решение просто наикрасивейшее!!!
Можно так же идти с позиции I+1, чтобы не проверять уже пройденное число
последнее решение не работает
очень полезный алгоритм
была такая задача в Яндексе))
спасибо за разбор, супер!
Спасибо, я только начал подступаться к программированию. Ничего еще не знаю, но все равно интересно.
Контент топчик. Как раз изучаю алгоритмы и структуры данных, недавно узнал о 2-х указателях. Теперь бы еще научиться все это видеть в конкретных задачах.
Спасибо :)
С опытом придет, если до этого решил 10 задач на два указателя, то и в 11 увидишь.
Если хочешь потренить, то вот сайт, на нем все к собесам готовятся:
leetcode.com/problemset/all/?topicSlugs=two-pointers
Решай easy задачи, и если не можешь придумать решение (а так в начале всегда будет), то смотри в комментах (секция Discuss). Удачи!
Подскажите, пожалуйста, по алгоритмам годные источники. И по структурные данным, если можно
@@hacamadahimichiru6110 Сам сейчас прохожу направление CS от Принстона на Курсере (от профессора Седжвика). Еще хвалят курс CS50 от Гарварда, но сам не пробовал. Все бесплатно и в интернете. Гуглите.
@@kselnaag2482 спасибо!
Саша Лукин, спасибо за твой труд! Крайне хорошо поясняешь. Уметь пояснять сложное простыми словами это очень важный и полезный навык. В будущем, мы, люди, все чаще и чаще будем коммуницировать.
Хотел бы тебя спросить вот о чем: Как ВИДЕТЬ более эффективный вариант чаще? Ведь до этого же надо додуматься! Вот ты привел разные решения, но ведь про них надо было сообразить . Как развивать соображалку то? ;)
Пока, развитие сооражалки в алгоритмах вижу такой: Ты смотришь как решают другие. В голове откладываются разные подходы. А потом методом брутфорса при решении той или иной задачи пишешь код. Либо ты видишь такую задачу, которая очень похожа на ту, которую ты уже видел ранее и применяешь то, что ты помнишь. Но все это цепляется на знание и на способность мозга вспомнить и увидеть схожие черты с ранее решенной задаче. Есть ли другие способы ?
Чтобы развивать навык решения задач, нужно решать задачи. Чтобы развивать навык решать задачи эффективно, нужно решать задачи эффективно.
Итого. Берёшь задачу, САМ решаешь её в лоб, то есть самым примитивным и очевидным способом. Пытаешься найти другие способы (да, сам). Сравниваешь полученные варианты, анализируешь их плюсы и минусы, ищешь слабые места, места, которые можно улучшить и т.д. и т.п. Смотришь, как другие люди решают другие задачи (да-да, именно другие) в поисках вдохновения. Смотришь, не появились ли ещё идеи, которые можно применить к своей задаче. Когда ты уже сдедал всё, что мог сделать сам, тогда и только тогда можно смотреть, как другие решают такие же задачи. Тогда будет развитие, а если просто смотреть на других, хоть и на лучших, ну хз... Сильно ли накачаешься, наблюдая за тем, как сильные силачи тягают железо? Вопрос риторический.
Можешь не благодарить 😌
@@Dimarious.Gбоюсь сравнение с силачами не уместно, когда мы смотрим на силача, мы смотрим на процесс, и не применяем никаких усилий, а когда мы смотрим решение задачи, то мы смотрим на решение, а не на процесс, и применяем усилия для понимания
@@Dimarious.Gа так думаю ты прав в остальном
Спасибо большое!! Вы молодец!
спасибо, интересно и познавательно
Просто очередной комментарий про то, что надо микрофон-петличку 😉 В целом огонь-пулемёт, продолжай обязательно у тебя отлично получается 💪 12к подписчиков за год на 4 видосах говорит о том, что ты всё делаешь правильно, материал актуальный! Подтяни качество, сделай выпуски регулярными и будет круто. Если это тебе надо конечно 😜
Я думаю, что Александр это делает для общего развития - творческий порыв. Поверь мне, с такими мозгами ему доход от ютуба так... на шоколадки.
Интересно 👍
Палец и т.п. за этот видос!
По больше пожалуйста таких задача ! С разжевыванием и примером. Можно и не только на Алгоритмы.
Но и более простые на возвраты. На операции логики сравнения и т.п и т.д.
Вообще Очевидные цифры в особенности по условию - сразу бросаются в глаза.
Как пример из первого пункта: 8 + (-1)
Т.е крайние цифры к условию и цифры с отрицательным значением.
Опять же надо смотреть и на контекст условия..
Но учитывая последние примеры то как раз таки отрицательные цифры используются.
Большое спасибо! Очень интересно )
Я бы сказал формализовать вообще всё.
Интересно, спасибо за контент
Круто!
Спасибо! Мне кажется, не лишним будет упомянуть, что сортировка это в среднем еще плюс O(n log n) по времени к оценке сложности, если изначально массив не отсортирован.
Ага, и часто эту задачу дают в виде неотсортированного массива, где нужно найти 3 числа, в сумме дающих k.
В таком случае просто в начале сортируем массив, потом пишем цикл прохода по массиву (это будет первое число из 3), а второе и третье каждый раз пытаемся найти методом двух указателей как в видео.
Тогда время будет O(n^2) и O(n log n) от сортировки не влияет на итоговую сложность.
Нет, в таком случае алгоритм работать не будет
Пример: [0, 3, 2], к=3
Тогда начальная пара (0, 2) в сумме даст меньше, чем надо, и следующая пара для рассмотрения будет (3, 2)
@@dimapimenov6807 у тебя не сортирован массив. После сортировки все будет ок.
Ну так и вопрос был про несортированный массив и алгоритм на нем
Если я вообще правильно понял вопрос... Я решил что вопрос про метод 2х указателей
Спасибо большое за информацию)
Это работает если нужно найти лишь одну пару чисел.
Но больше спасибо за объяснение. Очень легко воспринимается такая подача!)
Здорово, не занимаюсь программированием, никак не решаюсь начать, но настолько четкое объяснение, что понял даже я. Спасибо!
Спасибо! А программирование начать учить никогда не поздно, сейчас очень много моих друзей не из айти переходят в айти. Только время нужно выделить, я бы ориентировался хотя-бы на год, если довольно плотно заниматься.
Удачи!
@@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 спасибо! Да, Вы правы, такие вопросы на математические доказательства/обоснования мы получали именно в наших компаниях… интересно :) всего доброго, с нетерпением ждём новых выпусков! :)
В втором решении тоже два цикла. Второй скрыт - это поиск в хешсете (скрытый
перебор по нему)
Чего??? Поиск в хешсете О(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). Не дерево
Круто и очень понятно, спасибо
Я смог сам дойти до последнего решения в видео)
Спасибо автору за контент
Последнее решение даже не пришло в голову, пока не зашла речь про указатели, но чёрт возьми, оно такое простое и офигенное!
согласен
Любопытно, что некоторые задания из ЕГЭ сложнее, чем реальная задача с собеседования )
это же хорошо, подготовился к проф ЕГЭ, и можешь идти в гугл
Да, если не учитывать бэкграунд кандидата(опыт работы с платформами, модулями и тд), выпускник ЕГЭ подходит)
Задания из ЕГЭ по информатике?
На егэ ты в других условиях, на собесе иногда не можешь решить самую простую задачу, хотя без собеса решаешь задачи, которые в 10 раз сложнее.
@@abcdefghi1489 на ЕГЭ тоже стресс не маленький)
Гениальное решение, спасибо)
Понравилось грамотная подача, четкая и чистая речь без эээ-каний, без слов-паразитов, без соплей. Так держать, удачи!
Саша, привет! Большое спасибо за разборы задач. То, что ты делаешь - круто. Успехов тебе и каналу, продолжай. У меня вопрос: у тебя есть контактная почта или другие каналы связи? Хотелось бы написать: узнать и задать буквально пару вопросов про твой опыт переезда айтишника в Индонезию. Успехов!
сочувствую вам, если вы считаете, что ЭТО - круто...
Я конечно не работал ни в Амазоне, ни даже в эбэй, но из многолетней трудовой практики знаю, что никто, находясь в здравом уме, не будет платить большие деньги, только из за того, что ты задачки порешал)
Только из-за того, что задачки порешал, платить конечно не будут. Это условие обязательное, но не достаточное. А вот если задачки не порешал, то деньги ТОЧНО не будут платить.
@@realvall и тем не менее, данная задача не скажет ничего от слова совсем (т. е. 0%) по поводу уровня программиста. Соответственно, самый правильный способ - убрать эту задачу из собеседования и оставить олимпиадникам
@@sovaz1997
Ну тебе виднее)
@@sovaz1997эти задачи и не должны показывать "уровень программиста". на собеседованиях они для того, чтобы понять, есть у соискателя задатки логического мышления, необходимого в будущей работе, или на этапе выполнения простенькой задачки с ним уже можно закончить общение. а касательно того, что такие задачки нужно убрать из собеседования - я с вами и согласен, и нет, одновременно, как бы странно это не звучало. правильного ответа тут нет, зависит все от того, чья компания и кто определяет, как он будет отбирать сотрудников. если ваша, то, вероятно вы правы, и вам сотрудники, умеющие решать такие задачки, не нужны. если компания не ваша, то, скорее всего ее владельцам виднее, кто им нужен и какие задачки он должен уметь решать.
@@sovaz1997 если будете пробовать трудоустраиваться в yandex, там будет много таких и более сложных задач. Если пойдёте в дойче банк, то они тоже несколько задач подобных давали.
отличное видео, спасибо)
отличный контент и подача материала !! единственное упущение, мало роликов ((
В первом варианте нужно добавить проверку: если сумма двух чисел больше К, то вернуться в начало первого цикла, потому что дальнейшие суммы будут также больше К, т.к. массив отсортирован.
В варианте с бинарным поиском при делении на две части нужно использовать целочисленное деление на 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питон тоже строго типизирован, но динамически.
Недавно подписался и вот
Ой, кажется, я влюбилась)
Я далеко не разработчик (всего лишь МП), но было понятно и интересно)
Тоже заметила в начале про две пары, дающие правильный ответ)
Как же круто он объясняет!!!
Здравствуйте! Спасибо за видео). Вопрос не совсем по теме: какая основная разница между массивом и коллекцией, которая позволяет "одновременно" перебирать все ее элементы?
Не совсем понятно что значит "одновременно" перебирать все ее элементы. Collection наследуется от Iterable т.е. все коллекции позволяют перебирать, если речь об этом. Могу предположить что речь идет о том что массивы фиксированной длины, а реализации интерфейса Collection динамической, т.е. увеличиваются по мере добавления элементов. Массив также используется под капотом некоторых реализаций интерфейса Collection например ArrayList и частично HashSet. Ну т.е. более простой базовый объект для более сложных структур данных. В контексте задачи наверное речь про то что поиск по HashSet за О1 а не за On как у массива отсюда и ускорение.
Да, меня заинтересовало то, что сложность использования коллекции - О(1), а не О(n). То есть коллекция способна перебирать элементы настолько быстро, что время, затраченное на перебор, считается постоянным?
@@enternickhere почитайте "как работает HashMap в джава". элементы там хранятся в массиве связанных списков или массиве бинарных деревьев. Индекс массива вычисляется(а не перебирается) в зависимости от содержимого элемента при его помещении. И также потом при его поиске и извлечении.
Почитал, понял)
(Во втором примере) Разве проверка наличия элемента а массиве равна O(1)? Мне кажется, что больше на O(n) похоже, тогда алгоритм будет О(n^2)?
Тож заметил) set.contains написал и радуется)
Приятно, что моя первая мысль и была лучшим решением
шикарный разбор
это разве не Two Sum с литкода?
Во втором варианте, все же, оценка не совсем верная. O() -оценка в ХУДШЕМ случае, а не в среднем. В ХУДШЕМ случае (если хеш-функция - хреновая), сложность будет O(n log n). Другое дело, что для int хэш известен. И в конкретном случае с int - все будет верно - O(n), но стоит заменить тип (самое простое обобщение), как все станет совсем не очевидно
Тип не имеет значения, коллизии будут всегда. С int'ами тоже вполне можно упереться в nlogn.
Суммарно n запросов к хеш таблице будут иметь сложность O(n)
И худший случая - линия, кажется, а не логарифм. Однако оценку на среднее время выполнение операции в O(1) можно доказать.
@@user-hg3wh1sm8k Ты не понял, сложность обращения к хэш-таблице в джаве - O(log(n)) в худшем случае
@@griglog1309 но ведь оценка вида умножить худший случай на количество вызовов будет слишком грубой. Амортизированная оценка дает линейное время работы, как и у всех хешированных структур.
@@griglog1309 а какой худший случай времени работы одной операции, линия или логарифм, пока что не понял. Кажется, что использование хеш таблицы обычно дает линию в худшем случае, но могу ошибаться.
В любом случае, суммарное время работы будет всегда линейным, а я ответил на комментарий, где автор оценивает асимптотику как O(nlogn)
Шикарно! Здорово! Полезно! Лукас субскрайбович! 🤣👍
Спасибо, очень помогло!
Во втором варианте все равно время работы O(n^2), так как поиск в хэшсете - тоже представляет из себя внутренний цикл еще и со сравнением входящего значения..., отличие лишь в том, что количество пар теперь образуется реверсивно на увеличение лесенки, а не на уменьшение как с двумя циклами, так еще и больше на одну пару становится: -3 и пусто, а уж потом 0 и -3, 1 и -3, 1 и 0. Явой не занимаюсь, могу лишь предположить, что просто поиск в хэшсете работает быстрее, чем функция for, но не забываем про время обращения к памяти , если работать с большим объемом + постоянное пополнение хэшсета - это тоже еще одно действие, на которое тратится время. Вообще плохо считать время выполнения по формуле, которая опирается только на количество данных)
>>"Во втором варианте все равно время работы O(n^2)"
Именно так, но видимо автор является очень "современным" программистом, т.е. о том, что внутри происходит особо не задумывается.
Логарифмическое время там должно быть на поиск. Пополнение за константу. Те сложность должна быть n + log(n)
Видимо действительно с программистами вообще напряг последнее время, раз такие задачи на собеседовании дают.
Согласен, мы примерно такую г*внину решали еще в нашем мухосранске. Обычный перебор чисел со сложением и сравнением. Зашел посмотреть, вдруг тут что-то гениальное, а тут какая-то фигня из методички по программированию
@@lsentinell Меня на собеседование на 440к рублей в месяц попросили вычислить координаты дрона, уже активно движущегося по заданной траектории, которая стабилизируется с использоваием фази логики с коэффициентом упреждения 0.4 относительно параллельной связки формации, изображающих некую геометрическую фигуру. Из доступных данных - координаты в текущий и следующий момент ведущего дрона из 2й формации, координаты предыдущей секунды "оператора" во 2й формации и текущая позиция на общем маршруте (геометрическая фигура задаётся в виде csv документе в виде уравнений) 2й формаци
Т.е. По факту дано всё, но ничего )00)) И даже источника сигнала нет, чтобы с помощью драйвера выяснить что там творит отдельно взятый дрон. Его нужно подстроить под параллельно движущуюся формацию. А проектным заданием, которым я сейчас занимаюсь - нужно научить дроны вовремя разлетаться, чтобы впускать в свой строй новую единицу, которая не сломает всю картину
И это на зп всего за 7 тысяч вечнозелёных ))
Собираю манатки, еду в амазон в гл офис )0))
Саша главное твоя подача! Красавчик
Привет. Я семь лет назад перешёл на электронику, но посмотрел по приколу и Очень понравилось, понятно получаеться!
Если цель задания - выдать ответ, то все эти рассуждения не имеют смысла, т.к. занимают времени на порядок-два больше, чём само решение, к-рое видно сразу невооружённым глазом.
Так задача-то найти для любого массива пару дающую в сумме число k для всех возможных массивов и для всех k. А не просто для конкретного примера это сделать
А теперь представьте, что вы - компания Google с петабайт данными, и у вас в массиве миллиард элементов. Тогда ваше "очевидное" решение будет занимать сотни лет обработки.
Прикольно, что сейчас в ЕГЭ задачи сложнее))
Годика 3 назад были задачи, что из списка чисел надо посчитать все пары, которые в сумме кратны заданному К. Вернуть все эти пары - это пара доп действий. Сейчас задаче ещё лютее)
@@kaspersky_ege у меня что-то похожее было, сдавала в 2017 году, решила на 4 балла 27-е в 2, что ли, цикла (без вложенного)
@@reisders с 2017 многое поменялось, мы теперь на компьютере экзамен пишем и программа реально должна работать на 1млн строк эффективно
ЕГЭ по информатике вообще можно в одном Экселе сделать
@@sed0k да конечно, особенно 24 задание и 15 удобно, 14 более менее, 1 и 13 -- один кайф, 10 -- обязательно в экселе, 6 -- ну естественно
к чему коммент? я сказал, что задача в 27 сложнее, пир чем эксель? почему? что за комментарий? я не понимаю.
я умер.
Попалось видео, я щас пока что ничего не понимаю, но мне очень интересно)