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

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

@sashalukin

2 жыл бұрын

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

@semchic888

2 жыл бұрын

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

@sashalukin

2 жыл бұрын

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

@FariusFriends

2 жыл бұрын

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

@user-qm7pl3ez4s

2 жыл бұрын

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

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

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

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

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

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

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

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

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

@user-sp5fv4kw2n

Жыл бұрын

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

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

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

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

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

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

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

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

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

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

@pontypilat_0338

Жыл бұрын

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

@Bartolph

Жыл бұрын

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

@carbonara_13

Жыл бұрын

изи, 55

@MiroSlave1

Жыл бұрын

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

@SmihoTvor_lite

Жыл бұрын

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

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

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

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

@COOKIEMONSTER90

Жыл бұрын

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

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

@nikolaifaist

Жыл бұрын

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

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

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

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

@alarmolord

Жыл бұрын

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

@user-yd2wm6gt5k

2 жыл бұрын

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

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

@ps-037

Жыл бұрын

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

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

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

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

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

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

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

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

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

@user-bx5ze4jw5p

2 жыл бұрын

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

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

@kriguitar4753

2 жыл бұрын

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

@WillsherT

2 жыл бұрын

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

@webblyy

2 жыл бұрын

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

@KKZ_5000_RUB

6 ай бұрын

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

@user-tk7nh1jw3y

5 ай бұрын

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

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

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

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

@user-kh9rp6tu2b

Жыл бұрын

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

@xelnagamex

Жыл бұрын

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

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

@sashalukin

2 жыл бұрын

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

@hacamadahimichiru6110

2 жыл бұрын

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

@kselnaag2482

2 жыл бұрын

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

@hacamadahimichiru6110

2 жыл бұрын

@@kselnaag2482 спасибо!

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

@user-qy7vv5yx3b

Жыл бұрын

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

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

Круто!

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

@Dimarious.G

Жыл бұрын

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

@byesedd

5 ай бұрын

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

@byesedd

5 ай бұрын

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

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

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

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

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

@sashalukin

2 жыл бұрын

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

@dimapimenov6807

2 жыл бұрын

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

@Boosty931

2 жыл бұрын

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

@dimapimenov6807

2 жыл бұрын

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

@dimapimenov6807

2 жыл бұрын

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

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

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

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

@sashalukin

2 жыл бұрын

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

@digimax1288

2 жыл бұрын

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

@AVS11176

2 жыл бұрын

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

@digimax1288

2 жыл бұрын

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

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

@vladislavbaranovskii4133

Жыл бұрын

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

@Grim_J0nes

Жыл бұрын

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

@dmitry7464

Жыл бұрын

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

@abcdefghi1489

Жыл бұрын

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

@Whitestarwhitestar

Жыл бұрын

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

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

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

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

@romanbykov5922

Жыл бұрын

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

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

@user-yf8jf3fo2x

2 жыл бұрын

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

@enternickhere

2 жыл бұрын

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

@user-yf8jf3fo2x

2 жыл бұрын

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

@enternickhere

2 жыл бұрын

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

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

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

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

@NikolayMishin

Жыл бұрын

согласен

это разве не Two Sum с литкода?

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

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

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

@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). Не дерево

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

@bpht618

2 жыл бұрын

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

@viacheslavmatveichev4039

2 жыл бұрын

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

@sashalukin

2 жыл бұрын

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

@sashalukin

2 жыл бұрын

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

@viacheslavmatveichev4039

2 жыл бұрын

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

Шикарно! Здорово! Полезно! Лукас субскрайбович! 🤣👍

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

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

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

@realvall

2 жыл бұрын

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

@sovaz1997

2 жыл бұрын

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

@anti_middle_ages

2 жыл бұрын

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

@realvall

2 жыл бұрын

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

@QuickCube

2 жыл бұрын

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

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

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

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

@user-fu7ox7ml2u

Жыл бұрын

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

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

@user-wn2vu9jb3x

2 жыл бұрын

Делится тип 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питон тоже строго типизирован, но динамически.

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

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

@griglog1309

2 жыл бұрын

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

@user-hg3wh1sm8k

2 жыл бұрын

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

@griglog1309

2 жыл бұрын

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

@user-hg3wh1sm8k

2 жыл бұрын

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

@user-hg3wh1sm8k

2 жыл бұрын

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

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

Хорош! Спасибо

Весьма интересно

Красиво. Я смог придумать решение похуже - O(2n) c двумя проходам по исходному массиву и одним оп массивом, но, формально, это, все равно, O(n) :) 1) проходим по исходному массиву a[] и вычисляем разницу d каждого элемента с 9. 2) кладем значение этого элемента в другой массив arr1[d] = a[i] 3) еще раз идем по массиву a[] и для каждого элемента пытаемся взять arr1[d] - если взялось,значит мы нашли результат. 4) в качестве доп оптимизации, можно сделать третий массив , где будут храниться значения d, чтобы не считать их во второй проход.

@z140140

9 ай бұрын

arr1 - это ассоциативный массив, т.е. хешсет. вся разница в том, что вы строите его целиком, а автор вероятно на лету проверяет

Прикольно, что сейчас в ЕГЭ задачи сложнее))

@kaspersky_ege

2 жыл бұрын

Годика 3 назад были задачи, что из списка чисел надо посчитать все пары, которые в сумме кратны заданному К. Вернуть все эти пары - это пара доп действий. Сейчас задаче ещё лютее)

@reisders

Жыл бұрын

@@kaspersky_ege у меня что-то похожее было, сдавала в 2017 году, решила на 4 балла 27-е в 2, что ли, цикла (без вложенного)

@kaspersky_ege

Жыл бұрын

@@reisders с 2017 многое поменялось, мы теперь на компьютере экзамен пишем и программа реально должна работать на 1млн строк эффективно

@sed0k

Жыл бұрын

ЕГЭ по информатике вообще можно в одном Экселе сделать

@kaspersky_ege

Жыл бұрын

@@sed0k да конечно, особенно 24 задание и 15 удобно, 14 более менее, 1 и 13 -- один кайф, 10 -- обязательно в экселе, 6 -- ну естественно к чему коммент? я сказал, что задача в 27 сложнее, пир чем эксель? почему? что за комментарий? я не понимаю. я умер.

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

Приятно, что моя первая мысль и была лучшим решением