Задача из Собеседования на 160,000 Евро в Год
ฝัง
- เผยแพร่เมื่อ 22 พ.ค. 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). Оказывается, лучшее решение не такое уж нетривиальное, как показалось на первый взгляд
Здравствуйте, давно увидел ваше видео в рекомендациях и жалею что не посмотрел ранее. Спасибо за контент👍
Очень круто обьясняешь! Только учусь программировать и из роликов понял много полезных методов, алгоритмов поиска значений! Очень благодарен!
Почитай Вирта: Структуры и Алгоритмы, целый мир откроешь
Рад, что появилось свежее видео. Интересная задача и подходы к ее решению, доступное объяснение👍💪
8:44 - тут лучше определить, что является входом и что является выходом нашей части, отвечающей за бинарный поиск и вынести наш бинарный поиск в отдельный компонент. Это как упростит чтение и понимание кода, так и сделает код более модульным. По сути тут происходит тоже самое что и в "HashSet"
Снимай пожалуйста ещё ролики. У тебя очень хорошо получается. Очень познавательно!!! Спасибо!!
С возвращением) спасибо за ролик)
Наконец то вы вернулисссссьььььььь
Классное видео. Автор все очень доступно и понятно объясняет.
Саше спасибо большое за труд и терпение к "диванным ворчунам" )))
Спасибо, так просто о сложном. Вы талант. Надо клон сделать и учителем в школу.
Очень круто, спасибо за видео!
Впервые столкнулся с вашим каналом. Смотрю на обложку, на название ролика и совсем не понимаю: а что тут сложного, это ведь решит даже ребёнок! Стал смотреть, а здесь оказалось программирование, тогда понятно стало. Забавно.
Ролик интересный, подача грамотная, успехов!
Супер!!! Спасибо огромное, за классное видео. 👍👍👍
очень интересный материал, спасибо =) хотелось бы больше подобных видео
Браво! Ваши видео просто замечательные! Продолжайте в том же духе! Хотелось бы узнать больше «инсайдерской» информации, как человеку, которому только предстоит работать :)
Ещё не работаешь в этой сфере?
Довольно простое задание, как мне показалось, наверное потому, что во многих заданиях, даже простых( на строки, например ) нужно идти с двух сторон.
Ураа,ждал твоих роликов давно)
Спасибо! Очень интересно. Подписался. Буду ждать новых видео
Решал такую на литкоде методом двух указателей left, right как раз. Спасибо за видео
Я даже не поленился и нашёл. Может кому-то интересно будет порешать такую задачу на leetcode. Задача с уровнем easy (на вход дан неотсортированный массив) "1. Two Sum". И ещё одна похожая задача уровня medium "167. Two Sum II - Input Array Is Sorted" (на вход дан отсортированный массив).
Я сначала не поняла решение с двумя указателями, а потом по коду как всё поняла. Очень интересно и хорошо рассказано, пасеба!
Спасибо за видео! Очень интересная задача 👍👍🔥🔥🔥🔥
очень интересное и понятное объяснение, топ. спасибо!
Просто очередной комментарий про то, что надо микрофон-петличку 😉 В целом огонь-пулемёт, продолжай обязательно у тебя отлично получается 💪 12к подписчиков за год на 4 видосах говорит о том, что ты всё делаешь правильно, материал актуальный! Подтяни качество, сделай выпуски регулярными и будет круто. Если это тебе надо конечно 😜
Я думаю, что Александр это делает для общего развития - творческий порыв. Поверь мне, с такими мозгами ему доход от ютуба так... на шоколадки.
Спасибо, круто!
Cпасибо за интересную задачу!
хочу ещё!)
Мужик,твой материал на таком легке заходит,учу js,до такого уровня ещё не дошел,но о чем ты рассказываешь понятно,и заходит лайтово, спасибо за труд !
Удачи тебе,юный подаван.
Интересно 👍
Палец и т.п. за этот видос!
По больше пожалуйста таких задача ! С разжевыванием и примером. Можно и не только на Алгоритмы.
Но и более простые на возвраты. На операции логики сравнения и т.п и т.д.
Вообще Очевидные цифры в особенности по условию - сразу бросаются в глаза.
Как пример из первого пункта: 8 + (-1)
Т.е крайние цифры к условию и цифры с отрицательным значением.
Опять же надо смотреть и на контекст условия..
Но учитывая последние примеры то как раз таки отрицательные цифры используются.
Ура, вернулся :)
Прекрасная подача. Так держать!
Спасибо. Доходчиво:) Подписка однозначно за годный контент:)
Оооочень круто!
Бинарный поиск требует проверки на размер массива, так как при маленьком размере у нас время процессора уходит на математические вычисления середины и проверки (просто пометка от ноунейма).
Спасибо за видео. Люблю искать возможности для оптимизации. Пока с такими задачами не сталкивался, но если столкнусь, то буду знать, как сделать код быстрым, да ещё и красивым.
Приятно слушать - классная подача
Круто и интересно, обязательно продолжай.
очень полезный алгоритм
Задача элементарная, двигаем окно и смотрим если сумма меньше, двигаем правую часть, если сумма больше двигаем левую часть.
На статистике данных по распределению чисел мин, Макс и n можно эмпирически вывести функцию которая весьма точно будет попадать в индекс массива, да ещё давать длинну окна.
Плюс для отриц и положит, будет два окна
9:49 - оно и есть. Только одно окно для любых элементов и любого результата суммы
А вот что делать если 3 слагаемых - пока непонятно.
@@kriguitar4753 воспользоваться решением примера именно из собеседования, чуть доработав, чтобы записываемый ответ слагался с оставшимися в окне элементами.
@@kriguitar4753 два указателя + хешсет
Отрицательные числа крайне редко в реальных задачах встречаются. Задачи эти теоретики диванные создают.
@@webblyy 2 указателя уже не нужны если есть хэш-сет
Спасибо большое, скоро приступлю к таким задачам)
Это было очень интересно!)
Я давно забросил программировать но первая мысль была от от 7 вычитать по одному и искать равные ! Последнее решение просто наикрасивейшее!!!
Можно так же идти с позиции I+1, чтобы не проверять уже пройденное число
последнее решение не работает
Круто!
Отлично объясняешь! Выпускай почаще видео)
Спасибо!
Очень интересно и полезно🎉
Очень круто, ждем еще интересных и реальных задачек)
Мне вот эта задача по математике понравилась. Бородатая и не совсем айтишная, но может будет интересно :)
Встречаются два приятеля - математика:
- Ну как дела, как живешь?
- Все хорошо, растут два сына дошкольника.
- Сколько им лет?
- Произведение их возрастов равно количеству голубей возле этой скамейки.
- Этой информации мне недостаточно.
- Старший похож на мать.
- Теперь я знаю ответ на твой вопрос.
Сколько лет сыновьям? (Ответ логичный и однозначный)
Саша Лукин, спасибо за твой труд! Крайне хорошо поясняешь. Уметь пояснять сложное простыми словами это очень важный и полезный навык. В будущем, мы, люди, все чаще и чаще будем коммуницировать.
Хотел бы тебя спросить вот о чем: Как ВИДЕТЬ более эффективный вариант чаще? Ведь до этого же надо додуматься! Вот ты привел разные решения, но ведь про них надо было сообразить . Как развивать соображалку то? ;)
Пока, развитие сооражалки в алгоритмах вижу такой: Ты смотришь как решают другие. В голове откладываются разные подходы. А потом методом брутфорса при решении той или иной задачи пишешь код. Либо ты видишь такую задачу, которая очень похожа на ту, которую ты уже видел ранее и применяешь то, что ты помнишь. Но все это цепляется на знание и на способность мозга вспомнить и увидеть схожие черты с ранее решенной задаче. Есть ли другие способы ?
Чтобы развивать навык решения задач, нужно решать задачи. Чтобы развивать навык решать задачи эффективно, нужно решать задачи эффективно.
Итого. Берёшь задачу, САМ решаешь её в лоб, то есть самым примитивным и очевидным способом. Пытаешься найти другие способы (да, сам). Сравниваешь полученные варианты, анализируешь их плюсы и минусы, ищешь слабые места, места, которые можно улучшить и т.д. и т.п. Смотришь, как другие люди решают другие задачи (да-да, именно другие) в поисках вдохновения. Смотришь, не появились ли ещё идеи, которые можно применить к своей задаче. Когда ты уже сдедал всё, что мог сделать сам, тогда и только тогда можно смотреть, как другие решают такие же задачи. Тогда будет развитие, а если просто смотреть на других, хоть и на лучших, ну хз... Сильно ли накачаешься, наблюдая за тем, как сильные силачи тягают железо? Вопрос риторический.
Можешь не благодарить 😌
@@Dimarious.Gбоюсь сравнение с силачами не уместно, когда мы смотрим на силача, мы смотрим на процесс, и не применяем никаких усилий, а когда мы смотрим решение задачи, то мы смотрим на решение, а не на процесс, и применяем усилия для понимания
@@Dimarious.Gа так думаю ты прав в остальном
спасибо, интересно и познавательно
Спасибо большое за информацию)
Классно все объяснил. Казалось бы просто решается, но как послушаешь, сколько есть вариантов, голова идет кругом. Да еще и на Джаве, красавчик!
Чего такого в яве то? возможно выбран как один из хорошо читаемых языков. напиши на питоне, уже не каждый поймет.
Вначале подумал и придумал вариант такой: берем первый и суммируем с последним. Если больше К, то берем предпоследний и тд. Ползем назад сравнивая с первым. Потом берем второй и опять сравниваем с последним, идя навстречу второму. О том, что последний можно не сбрасывать почему-то не додумался )
была такая задача в Яндексе))
спасибо за разбор, супер!
Спасибо большое!! Вы молодец!
лукас не глядя. давно ждал возвращения))
В втором решении тоже два цикла. Второй скрыт - это поиск в хешсете (скрытый
перебор по нему)
Чего??? Поиск в хешсете О(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). Не дерево
Интересно, спасибо за контент
Рад, что ты вернулся!
Контент топчик. Как раз изучаю алгоритмы и структуры данных, недавно узнал о 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х указателей
Спасибо, я только начал подступаться к программированию. Ничего еще не знаю, но все равно интересно.
Приятно слушать. Да ещё и Java)) спасибо
Любопытно, что некоторые задания из ЕГЭ сложнее, чем реальная задача с собеседования )
это же хорошо, подготовился к проф ЕГЭ, и можешь идти в гугл
Да, если не учитывать бэкграунд кандидата(опыт работы с платформами, модулями и тд), выпускник ЕГЭ подходит)
Задания из ЕГЭ по информатике?
На егэ ты в других условиях, на собесе иногда не можешь решить самую простую задачу, хотя без собеса решаешь задачи, которые в 10 раз сложнее.
@@abcdefghi1489 на ЕГЭ тоже стресс не маленький)
Я конечно не работал ни в Амазоне, ни даже в эбэй, но из многолетней трудовой практики знаю, что никто, находясь в здравом уме, не будет платить большие деньги, только из за того, что ты задачки порешал)
Только из-за того, что задачки порешал, платить конечно не будут. Это условие обязательное, но не достаточное. А вот если задачки не порешал, то деньги ТОЧНО не будут платить.
@@realvall и тем не менее, данная задача не скажет ничего от слова совсем (т. е. 0%) по поводу уровня программиста. Соответственно, самый правильный способ - убрать эту задачу из собеседования и оставить олимпиадникам
@@sovaz1997
Ну тебе виднее)
@@sovaz1997эти задачи и не должны показывать "уровень программиста". на собеседованиях они для того, чтобы понять, есть у соискателя задатки логического мышления, необходимого в будущей работе, или на этапе выполнения простенькой задачки с ним уже можно закончить общение. а касательно того, что такие задачки нужно убрать из собеседования - я с вами и согласен, и нет, одновременно, как бы странно это не звучало. правильного ответа тут нет, зависит все от того, чья компания и кто определяет, как он будет отбирать сотрудников. если ваша, то, вероятно вы правы, и вам сотрудники, умеющие решать такие задачки, не нужны. если компания не ваша, то, скорее всего ее владельцам виднее, кто им нужен и какие задачки он должен уметь решать.
@@sovaz1997 если будете пробовать трудоустраиваться в yandex, там будет много таких и более сложных задач. Если пойдёте в дойче банк, то они тоже несколько задач подобных давали.
Большое спасибо! Очень интересно )
Я бы сказал формализовать вообще всё.
Это работает если нужно найти лишь одну пару чисел.
Но больше спасибо за объяснение. Очень легко воспринимается такая подача!)
Здорово, не занимаюсь программированием, никак не решаюсь начать, но настолько четкое объяснение, что понял даже я. Спасибо!
Спасибо! А программирование начать учить никогда не поздно, сейчас очень много моих друзей не из айти переходят в айти. Только время нужно выделить, я бы ориентировался хотя-бы на год, если довольно плотно заниматься.
Удачи!
@@sashalukin спасибо большое за совет и напутствие
Многое теряете, я когда по работе понял, что делаю много повторяющихся действий, решил автоматизировать процессы, я даже что такое IDE не знал. Уровень на доске меня пока восхищает, стремлюсь к тому, что бы сделать его банальным.
@@AVS11176 я вообще в банке работаю на данный момент, ну и как везде, 70% работы это эксель и какое-то статистическое ПО (типо R, у нас САС). То когда я залезал в VBA или в SAS все смотрели как на мага-чародея
Последнее решение даже не пришло в голову, пока не зашла речь про указатели, но чёрт возьми, оно такое простое и офигенное!
согласен
Спасибо, очень интересно!
отличный контент и подача материала !! единственное упущение, мало роликов ((
Саша, привет! Большое спасибо за разборы задач. То, что ты делаешь - круто. Успехов тебе и каналу, продолжай. У меня вопрос: у тебя есть контактная почта или другие каналы связи? Хотелось бы написать: узнать и задать буквально пару вопросов про твой опыт переезда айтишника в Индонезию. Успехов!
сочувствую вам, если вы считаете, что ЭТО - круто...
Недавно подписался и вот
3:03 - i должно идти до i < nums.length - 1, так как следущий цикл начинается с j=i+1
шикарный разбор
Здравствуйте! Спасибо большое за разбор.
Задача интересная и довольно популярная. Но отдельный интерес вызывает именно математическое обоснование данного алгоритма. А именно: доказать, что решение найдется при движении именно левого поинтера, когда сумма меньше и правого, когда сумма больше.
Не сможете помочь разобрать? Обоснование порой спрашивают чаще, чем сам алгоритм. Спасибо!
массив упорядочен, поэтому. Если сумма меньше 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(n^2), так как поиск в хэшсете - тоже представляет из себя внутренний цикл еще и со сравнением входящего значения..., отличие лишь в том, что количество пар теперь образуется реверсивно на увеличение лесенки, а не на уменьшение как с двумя циклами, так еще и больше на одну пару становится: -3 и пусто, а уж потом 0 и -3, 1 и -3, 1 и 0. Явой не занимаюсь, могу лишь предположить, что просто поиск в хэшсете работает быстрее, чем функция for, но не забываем про время обращения к памяти , если работать с большим объемом + постоянное пополнение хэшсета - это тоже еще одно действие, на которое тратится время. Вообще плохо считать время выполнения по формуле, которая опирается только на количество данных)
>>"Во втором варианте все равно время работы O(n^2)"
Именно так, но видимо автор является очень "современным" программистом, т.е. о том, что внутри происходит особо не задумывается.
Логарифмическое время там должно быть на поиск. Пополнение за константу. Те сложность должна быть n + log(n)
отличное видео, спасибо)
Спасибо, очень помогло!
(Во втором примере) Разве проверка наличия элемента а массиве равна 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питон тоже строго типизирован, но динамически.
Ой, кажется, я влюбилась)
Я далеко не разработчик (всего лишь МП), но было понятно и интересно)
Тоже заметила в начале про две пары, дающие правильный ответ)
А. Бал. Деть. Узнал много нового. Спасибо!
Видимо действительно с программистами вообще напряг последнее время, раз такие задачи на собеседовании дают.
Согласен, мы примерно такую г*внину решали еще в нашем мухосранске. Обычный перебор чисел со сложением и сравнением. Зашел посмотреть, вдруг тут что-то гениальное, а тут какая-то фигня из методички по программированию
@@lsentinell Меня на собеседование на 440к рублей в месяц попросили вычислить координаты дрона, уже активно движущегося по заданной траектории, которая стабилизируется с использоваием фази логики с коэффициентом упреждения 0.4 относительно параллельной связки формации, изображающих некую геометрическую фигуру. Из доступных данных - координаты в текущий и следующий момент ведущего дрона из 2й формации, координаты предыдущей секунды "оператора" во 2й формации и текущая позиция на общем маршруте (геометрическая фигура задаётся в виде csv документе в виде уравнений) 2й формаци
Т.е. По факту дано всё, но ничего )00)) И даже источника сигнала нет, чтобы с помощью драйвера выяснить что там творит отдельно взятый дрон. Его нужно подстроить под параллельно движущуюся формацию. А проектным заданием, которым я сейчас занимаюсь - нужно научить дроны вовремя разлетаться, чтобы впускать в свой строй новую единицу, которая не сломает всю картину
И это на зп всего за 7 тысяч вечнозелёных ))
Собираю манатки, еду в амазон в гл офис )0))
Мне вот кажется, что если считать в тактах процессора, то не факт что самое быстрое решение будет самым быстрым.
Это кодеры, они математику не учат )))))
В тактах какого именно процессора, гражданин умник?
У тебя хватит пальцев перечислить процессоры и архитектуры, для которых результаты будут разными?
@@user-ng7zh9cl2f Что вы знаете об ассемблере?
Современные программисты, извините, это рукожопы, составляющие программы из кубиков --- кем-то написаных готовых функций. И вот он например, в своём алгоритме использует функцию перемещения в конец массива. А эта функция, вполне возможно, тупо переписывает данные из массива по одному в новый массив, и это нифига не быстрее.
@@user-ve2uo7wk6u Да, с большими массивами еще и кэшмиссы легко получить. Думаю, что на собесах имеет смысл рассказывать о плюсах-минусах каждого решения, начав с самого очевидного. А вообще да, сегодняшние программисты в основном кодеры.
Саша главное твоя подача! Красавчик
так ведь в 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
То есть, в написанной программе есть запросы к сету, работающие за линию суммарно, и остальные выче
Остальные вычисления - линейны, складываем (не умножаем! Каждый запрос не работает за линию!), получаем тоже линию
Во втором варианте, все же, оценка не совсем верная. 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)
Понравилось грамотная подача, четкая и чистая речь без эээ-каний, без слов-паразитов, без соплей. Так держать, удачи!
поиск индекса по значению (k-i)... но досмотрю до конца.
Досмотрел, остаюсь при своем для первой части задачи. Вторая часть интересней, бинарный поиск для ее решения подходит лучше. Спасибо!
А разве hashset не использует цикл внутри себя для поиска элемента в массиве?
Нет, он высчитывает нужный индекс массива по ключу и просто возвращает данные по этому индексу
@@alex.lokhman Ага, пока коллизий нет, да там все "просто", а вот если есть...)
Главный вопрос на собеседовании в икее: чей Крым?
Очень понравилось объяснение - доходчиво и наглядно!
Есть еще вариант: вычитать из требуемого числа последовательно один элемент массива и пробегаться по оставшемуся массиву в поисках такого же результата. Тоже не требует лишней памяти и также работает в O(n)
Это займет O(N^2) никак не O(N)
@@SayXaNow да, точно
Тогда вариант с вычитанием отпадает
Хорош! Спасибо