@@sashalukin я конечно не программист, но почему нельзя например из непосредственно результата "К" начать вычитать числа и сравнивать их с предложенными?
Надо в собеседовании ввести задание, чтоб и пытуемый посчитал пальцы на правой руке, затем на левой, а затем назвал общее количество пальцев на обеих руках.
Топ-видос! Посмотрел и сохранил в один из своих плейлистов еще в феврале, но вернулся и разобрался в последнем варианте решения только сейчас, когда твердо решил апнуть скилл в решении задачек (наткнулся на эту задачу на leetcode). Оказывается, лучшее решение не такое уж нетривиальное, как показалось на первый взгляд
еще улучшу ваш алгоритм! Совершенно бесплатно. в реальных проектах таких смешных массивов не бывает, а вот данных, состоящих из миллиарда элементов - очень частый случай. В первую очередь можно дропнуть львиную долю данных, установив "зум" на числа, потенциально допустимые. если границы массива i и n, искомое число k, то i >= -1*(n-k), n
Задача элементарная, двигаем окно и смотрим если сумма меньше, двигаем правую часть, если сумма больше двигаем левую часть. На статистике данных по распределению чисел мин, Макс и n можно эмпирически вывести функцию которая весьма точно будет попадать в индекс массива, да ещё давать длинну окна. Плюс для отриц и положит, будет два окна
@@gitarnoob воспользоваться решением примера именно из собеседования, чуть доработав, чтобы записываемый ответ слагался с оставшимися в окне элементами.
Ну, на php это можно решить ещё и таким простым и изящным способом, смысл которого очень прост. Нам известен результат k и дан некоторый массив array. Чтобы найти 2 числа наименьшим числом попыток, можно запустить 2 цикла for один в другом и проверять во втором цикле только числа справа от индекса первого. А можно как у меня - запустить всего один цикл и попытаться воссоздать второе число математическим образом, вычитая из результата первое число. Далее остаётся только проверить, существует ли такое число в массиве. И если да - результат нас устраивает $array = [-3, 0, 1, 3, 4]; $k = 5; for ($i = 0; $i < count($array); $i++) { $j = ($k - $array[$i]); if (in_array($j, $array) { var_dump([$i, $j]); } }
Впервые столкнулся с вашим каналом. Смотрю на обложку, на название ролика и совсем не понимаю: а что тут сложного, это ведь решит даже ребёнок! Стал смотреть, а здесь оказалось программирование, тогда понятно стало. Забавно. Ролик интересный, подача грамотная, успехов!
for i in [.......... ]: if k - i in [...........] answer = [i] answer.append(k - i) brake else: answer = [ ] print(answer) Сильно не вникал в задачу, поэтому возможно понадобится типизация данных. Главное схема решения Аналогично через index или метод pop Мое уважение автору, забывшему уточнить, что его оптимальное решение работает только на отсортированном списке
Спасибо! Мне кажется, не лишним будет упомянуть, что сортировка это в среднем еще плюс O(n log n) по времени к оценке сложности, если изначально массив не отсортирован.
Ага, и часто эту задачу дают в виде неотсортированного массива, где нужно найти 3 числа, в сумме дающих k. В таком случае просто в начале сортируем массив, потом пишем цикл прохода по массиву (это будет первое число из 3), а второе и третье каждый раз пытаемся найти методом двух указателей как в видео. Тогда время будет O(n^2) и O(n log n) от сортировки не влияет на итоговую сложность.
Нет, в таком случае алгоритм работать не будет Пример: [0, 3, 2], к=3 Тогда начальная пара (0, 2) в сумме даст меньше, чем надо, и следующая пара для рассмотрения будет (3, 2)
Контент топчик. Как раз изучаю алгоритмы и структуры данных, недавно узнал о 2-х указателях. Теперь бы еще научиться все это видеть в конкретных задачах.
Спасибо :) С опытом придет, если до этого решил 10 задач на два указателя, то и в 11 увидишь. Если хочешь потренить, то вот сайт, на нем все к собесам готовятся: leetcode.com/problemset/all/?topicSlugs=two-pointers Решай easy задачи, и если не можешь придумать решение (а так в начале всегда будет), то смотри в комментах (секция Discuss). Удачи!
@@hacamadahimichiru6110 Сам сейчас прохожу направление CS от Принстона на Курсере (от профессора Седжвика). Еще хвалят курс CS50 от Гарварда, но сам не пробовал. Все бесплатно и в интернете. Гуглите.
8:44 - тут лучше определить, что является входом и что является выходом нашей части, отвечающей за бинарный поиск и вынести наш бинарный поиск в отдельный компонент. Это как упростит чтение и понимание кода, так и сделает код более модульным. По сути тут происходит тоже самое что и в "HashSet"
Бинарный поиск требует проверки на размер массива, так как при маленьком размере у нас время процессора уходит на математические вычисления середины и проверки (просто пометка от ноунейма). Спасибо за видео. Люблю искать возможности для оптимизации. Пока с такими задачами не сталкивался, но если столкнусь, то буду знать, как сделать код быстрым, да ещё и красивым.
@@Paravarka В хорошо распределенных хеш таблицах. Если распределилась плохо, то может быть и O(n), если реализация тупая и O(log n) если реализация похитрее.
Просто очередной комментарий про то, что надо микрофон-петличку 😉 В целом огонь-пулемёт, продолжай обязательно у тебя отлично получается 💪 12к подписчиков за год на 4 видосах говорит о том, что ты всё делаешь правильно, материал актуальный! Подтяни качество, сделай выпуски регулярными и будет круто. Если это тебе надо конечно 😜
Спасибо! А программирование начать учить никогда не поздно, сейчас очень много моих друзей не из айти переходят в айти. Только время нужно выделить, я бы ориентировался хотя-бы на год, если довольно плотно заниматься. Удачи!
Многое теряете, я когда по работе понял, что делаю много повторяющихся действий, решил автоматизировать процессы, я даже что такое IDE не знал. Уровень на доске меня пока восхищает, стремлюсь к тому, что бы сделать его банальным.
@@AVS11176 я вообще в банке работаю на данный момент, ну и как везде, 70% работы это эксель и какое-то статистическое ПО (типо R, у нас САС). То когда я залезал в VBA или в SAS все смотрели как на мага-чародея
@@Z3rgatul sets (аналог C++ std::unordered_map), Dictionary и Tuple (аналог std::map в C++) контейнеры для хранения списка ключей реализованы на базе бинарного дерева (сложность поиска log(n)). Хз. Почему во всех мануалах python написано O(1). Может кто объяснит?
В первом варианте нужно добавить проверку: если сумма двух чисел больше К, то вернуться в начало первого цикла, потому что дальнейшие суммы будут также больше К, т.к. массив отсортирован. В варианте с бинарным поиском при делении на две части нужно использовать целочисленное деление на 2, потому что в какой-то момент программа будет пытаться найти элемент с не целым номером индекса, например, 6,5.
Java, в отличии от всяких питонов и js, строго типизированный язык и в нём исключено получить дробное значение при делении целых чисел, если явно это не указывать. При этом, результат деления всегда округляется до меньшего числа. То есть даже если провести операцию, к примеру, 59 / 10, то результат будет 5. Однако, если хотя бы одно из делимых чисел привести к дробному типу, вроде (float)59 / 10 или 59.0 / 10, то результат вычисления уже будет 5.9.
Саша Лукин, спасибо за твой труд! Крайне хорошо поясняешь. Уметь пояснять сложное простыми словами это очень важный и полезный навык. В будущем, мы, люди, все чаще и чаще будем коммуницировать. Хотел бы тебя спросить вот о чем: Как ВИДЕТЬ более эффективный вариант чаще? Ведь до этого же надо додуматься! Вот ты привел разные решения, но ведь про них надо было сообразить . Как развивать соображалку то? ;) Пока, развитие сооражалки в алгоритмах вижу такой: Ты смотришь как решают другие. В голове откладываются разные подходы. А потом методом брутфорса при решении той или иной задачи пишешь код. Либо ты видишь такую задачу, которая очень похожа на ту, которую ты уже видел ранее и применяешь то, что ты помнишь. Но все это цепляется на знание и на способность мозга вспомнить и увидеть схожие черты с ранее решенной задаче. Есть ли другие способы ?
Чтобы развивать навык решения задач, нужно решать задачи. Чтобы развивать навык решать задачи эффективно, нужно решать задачи эффективно. Итого. Берёшь задачу, САМ решаешь её в лоб, то есть самым примитивным и очевидным способом. Пытаешься найти другие способы (да, сам). Сравниваешь полученные варианты, анализируешь их плюсы и минусы, ищешь слабые места, места, которые можно улучшить и т.д. и т.п. Смотришь, как другие люди решают другие задачи (да-да, именно другие) в поисках вдохновения. Смотришь, не появились ли ещё идеи, которые можно применить к своей задаче. Когда ты уже сдедал всё, что мог сделать сам, тогда и только тогда можно смотреть, как другие решают такие же задачи. Тогда будет развитие, а если просто смотреть на других, хоть и на лучших, ну хз... Сильно ли накачаешься, наблюдая за тем, как сильные силачи тягают железо? Вопрос риторический. Можешь не благодарить 😌
@@Dimarious.Gбоюсь сравнение с силачами не уместно, когда мы смотрим на силача, мы смотрим на процесс, и не применяем никаких усилий, а когда мы смотрим решение задачи, то мы смотрим на решение, а не на процесс, и применяем усилия для понимания
Мне вот эта задача по математике понравилась. Бородатая и не совсем айтишная, но может будет интересно :) Встречаются два приятеля - математика: - Ну как дела, как живешь? - Все хорошо, растут два сына дошкольника. - Сколько им лет? - Произведение их возрастов равно количеству голубей возле этой скамейки. - Этой информации мне недостаточно. - Старший похож на мать. - Теперь я знаю ответ на твой вопрос. Сколько лет сыновьям? (Ответ логичный и однозначный)
поиск индекса по значению (k-i)... но досмотрю до конца. Досмотрел, остаюсь при своем для первой части задачи. Вторая часть интересней, бинарный поиск для ее решения подходит лучше. Спасибо!
Во втором варианте все равно время работы O(n^2), так как поиск в хэшсете - тоже представляет из себя внутренний цикл еще и со сравнением входящего значения..., отличие лишь в том, что количество пар теперь образуется реверсивно на увеличение лесенки, а не на уменьшение как с двумя циклами, так еще и больше на одну пару становится: -3 и пусто, а уж потом 0 и -3, 1 и -3, 1 и 0. Явой не занимаюсь, могу лишь предположить, что просто поиск в хэшсете работает быстрее, чем функция for, но не забываем про время обращения к памяти , если работать с большим объемом + постоянное пополнение хэшсета - это тоже еще одно действие, на которое тратится время. Вообще плохо считать время выполнения по формуле, которая опирается только на количество данных)
>>"Во втором варианте все равно время работы O(n^2)" Именно так, но видимо автор является очень "современным" программистом, т.е. о том, что внутри происходит особо не задумывается.
Браво! Ваши видео просто замечательные! Продолжайте в том же духе! Хотелось бы узнать больше «инсайдерской» информации, как человеку, которому только предстоит работать :)
@@hapcuji n^2. Проходов будет столько же, сколько и в первом варианте. Разница только в том, что в первом второй цикл от i+1 до n, а во втором - от 0 до i-1.
@@sibedir не каждый запрос это O(n) Всё обращения к множеству суммарно работают за O(n) Для доказательства этого советую лекции по хешированным структурам на ютубе, или просто почитать neerc То есть, в написанной программе есть запросы к сету, работающие за линию суммарно, и остальные выче Остальные вычисления - линейны, складываем (не умножаем! Каждый запрос не работает за линию!), получаем тоже линию
Очень понравилось объяснение - доходчиво и наглядно! Есть еще вариант: вычитать из требуемого числа последовательно один элемент массива и пробегаться по оставшемуся массиву в поисках такого же результата. Тоже не требует лишней памяти и также работает в O(n)
Здравствуйте! Спасибо большое за разбор. Задача интересная и довольно популярная. Но отдельный интерес вызывает именно математическое обоснование данного алгоритма. А именно: доказать, что решение найдется при движении именно левого поинтера, когда сумма меньше и правого, когда сумма больше. Не сможете помочь разобрать? Обоснование порой спрашивают чаще, чем сам алгоритм. Спасибо!
массив упорядочен, поэтому. Если сумма меньше 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 спасибо! Да, Вы правы, такие вопросы на математические доказательства/обоснования мы получали именно в наших компаниях… интересно :) всего доброго, с нетерпением ждём новых выпусков! :)
А вот адгоритм О(logn) - Находим серпдину массива - берем сумму чисел слева и справа от середины - если сумма = искосому числу, то адгоритм завершён - если сумма > искомого числа, то берем левую половину - если меньше то правую - с выбранной половиной проделывем предвдущие шаэто должно работать так, как сумма двух крайних элементов больше, чем сумма любых двух элементов слева и меньше, чем сумма лббых других двух элементов справа Хотя может быть будут проблемы когда ожни и те же элементы идут подряд. К примеру: [....., 7,7,7....] Тогда гаркшается учловие выше и сумма любых двух элементов левого (правого), множества ре обязана быть строго меньше(больше) суммы крайних
@@КотМорзе Что вы знаете об ассемблере? Современные программисты, извините, это рукожопы, составляющие программы из кубиков --- кем-то написаных готовых функций. И вот он например, в своём алгоритме использует функцию перемещения в конец массива. А эта функция, вполне возможно, тупо переписывает данные из массива по одному в новый массив, и это нифига не быстрее.
@@СтрогийЛёх Да, с большими массивами еще и кэшмиссы легко получить. Думаю, что на собесах имеет смысл рассказывать о плюсах-минусах каждого решения, начав с самого очевидного. А вообще да, сегодняшние программисты в основном кодеры.
Годика 3 назад были задачи, что из списка чисел надо посчитать все пары, которые в сумме кратны заданному К. Вернуть все эти пары - это пара доп действий. Сейчас задаче ещё лютее)
@@sed0k да конечно, особенно 24 задание и 15 удобно, 14 более менее, 1 и 13 -- один кайф, 10 -- обязательно в экселе, 6 -- ну естественно к чему коммент? я сказал, что задача в 27 сложнее, пир чем эксель? почему? что за комментарий? я не понимаю. я умер.
Вначале подумал и придумал вариант такой: берем первый и суммируем с последним. Если больше К, то берем предпоследний и тд. Ползем назад сравнивая с первым. Потом берем второй и опять сравниваем с последним, идя навстречу второму. О том, что последний можно не сбрасывать почему-то не додумался )
Спасибо, за материал. Небольшой комментарий: если k известно, находим число ближайшее к k число в массиве (поскольку массив отсортирован это легко сделать либо методом дихотомии либо с помощью встроенных функций). После того как нашли число ближайшее k, назовем его X, мы знаем какое число нужно искать дальше, X+Y=k, Y = k-X. Проверяем на наличие Y в массиве. Если его нет, тогда ищем X от текущей позиции в массиве влево и вправо. Снова проверяем на наличие Y = k-X. Идт. Плюс мы еще можем отсечь хвосты массива, поскольку мы в поиске если Y = k-X < min(array) or k-X > max(array) then break. Интуитивно это мне дает в среднем логарифмическое время вычисления, потому что мы изначально нашли хорошее приближение. В худшем случае, n. Удачи!
Ваш алгоритм ничем не отличается от перебора всех пар, только с дополнительными шагами. Проверить на наличие Y в массиве - это уже сложность n-1 (пройтись по всем значениям массива кроме Х). В худшем случае надо будет перебрать все значения массива. Это дает n*(n-1). Еще найти найти ближайшее к К число. Метод дихотомии (он же бинарный поиск, 3е решение в данном видео) - log(n). Итого сложность вашего алгоритма log(n)+n*(n-1). Пример: [1,2,3,4,5,6,7,8] k=16 P.S. время работы алгоритма - это максимальное время работы алгоритма для любого датасета.
Во втором варианте, все же, оценка не совсем верная. O() -оценка в ХУДШЕМ случае, а не в среднем. В ХУДШЕМ случае (если хеш-функция - хреновая), сложность будет O(n log n). Другое дело, что для int хэш известен. И в конкретном случае с int - все будет верно - O(n), но стоит заменить тип (самое простое обобщение), как все станет совсем не очевидно
Суммарно n запросов к хеш таблице будут иметь сложность O(n) И худший случая - линия, кажется, а не логарифм. Однако оценку на среднее время выполнение операции в O(1) можно доказать.
@@griglog но ведь оценка вида умножить худший случай на количество вызовов будет слишком грубой. Амортизированная оценка дает линейное время работы, как и у всех хешированных структур.
@@griglog а какой худший случай времени работы одной операции, линия или логарифм, пока что не понял. Кажется, что использование хеш таблицы обычно дает линию в худшем случае, но могу ошибаться. В любом случае, суммарное время работы будет всегда линейным, а я ответил на комментарий, где автор оценивает асимптотику как O(nlogn)
Интересно 👍 Палец и т.п. за этот видос! По больше пожалуйста таких задача ! С разжевыванием и примером. Можно и не только на Алгоритмы. Но и более простые на возвраты. На операции логики сравнения и т.п и т.д. Вообще Очевидные цифры в особенности по условию - сразу бросаются в глаза. Как пример из первого пункта: 8 + (-1) Т.е крайние цифры к условию и цифры с отрицательным значением. Опять же надо смотреть и на контекст условия.. Но учитывая последние примеры то как раз таки отрицательные цифры используются.
Саша, привет! Большое спасибо за разборы задач. То, что ты делаешь - круто. Успехов тебе и каналу, продолжай. У меня вопрос: у тебя есть контактная почта или другие каналы связи? Хотелось бы написать: узнать и задать буквально пару вопросов про твой опыт переезда айтишника в Индонезию. Успехов!
даже two sum с литкода другая немного, как будто она даже сложнее там массив не отсортированный и решается задача через хэшмапу и еще там индексы нужно вернуть, а не сами числа
Компания, которая ищет разработчика, спрашивая на собеседовании такие задачи, и получит разработчика, который умеет решать такие задачи. Проще говоря, если их бизнес не построен на таких алгоритмах, они не знают, кого ищут
Знают они прекрасно кого ищут, просто крупные компании могут позволить себе заградительный ценз из алгоритмических задач на одном из этапов многоступенчатого собеса (подойдет ли человек для повседневной рутины на позицию X обычно решают этапы обычного технического интервью по стеку + этап по системному дизайну). У них там такой поток соискателей, что нужна лакмусовая бумажка на упертых, способных часами дриллить задачки с LeetCode, чтобы иметь хоть какой-то шанс пройти whiteboard-собеседование.
маня . иди сервисы пилить . а то селект с базы долго отрабатывает . тока не вздумай тесты писать "этаже дорохоооо". а если серьезно . дружище вот это наша работа(алгоритмы) а не в точности знать каким методом вызвать балансировку авл дерева . а уменее её написать.
@@richagreen9937 и как, пригодились тебе в работе деревья? Мне за 10 лет работы реально пригождается регулярно только знание многопоточки, индексов в БД (что основные их реализации - это B-tree со всеми вытекающими) и простейших вещей из курса по анализу алгоритмов, чтобы приблизительно оценить, что джун воткнул для задачки код квадратичной сложности, хотя можно в линейку в один проход. Ну да, у меня были в вузе алгоритмы на графах, сортировки, основные структуры данных (несколько видов деревьев, хэштаблицы, кольцевые списки), были отрешаны куча задач на это в свое время, но за ненадобностью я все эти алгоритмы позабыл уже давно. Помню только названия и для чего применяется. Этого хватает, чтобы в случае чего, понять, что в задаче подойдёт какая-нибудь топологическая сортировка, гуглануть её код и скопипастить в проект. А мое начальство вообще не алгоритмы интересуют, а системный дизайн, так как от хорошего сильного программиста требуется понимание, когда нужны очереди, балансировщики и шардирование, а когда нет.
Серега, ты несколько не прав! Это всего лишь гипотеза, что если чел разбирается в алгоритмах, то он только их и умеет решать. Гипотеза ничем не подтвежденная. Я работаю в ИТ чуть больше чем {floor(log10(factorial(36)))+1 - 27} лет и заметил вот что: 1. Бывают случаи, когда математик или олимпиадник, становятся крайне хреновыми программистами, т.к. любят заумничать. Но из этой выборки чаще всего попадаются люди, которые настолько хорошо видят код, что могут обрезать его скорость до таких малых единиц, что диву даешься и это без отладчика.Ты только подумал и решил, применить где-то тип set() , а чел вдруг говорит "Ну, так тут можно дальше sqrt(n) не считать" а ты только репу чешь с чего это он взял? 2. Также бывают и другие случаи, когда из программистов , которые самоучки или в универе учились на инженеров программеров выходят толковые ребята и их очень много. Однако при собеседовании ты видя, что перед тобою программист, а не программист который изучал математику или любит алгоритмы и у тебя нет понимания какой чел перед тобою. Он может быть с одинаковой вероятностью как хорошим продуктовым программером, а также с такой же вероятностью и хреновым. То что он прошел собес и ты ему дал работу , у тебя нет уверенности. Практика во многих компаниях , в том числе и в России, показывает то, что у программиста, который любил, любит и продолжает любить математику и алгоритмы лучше код! Прям вот в разы! Различным best practice как писать код по-чище, по понятнее, т.е. ремесловое это все нарабатывается. А вот научить человека думать и думать крайне хорошо это ой как не просто и лучшего способа чем алгоритмы и математика нету! Мы, люди, крайне сложные создания и то как работает наш мозг нам , можно сказать, не известно! То что мы знаем про мозг, это крайне малая часть от того что нужно было бы знать. К примеру, почему детям в школе чаще заставляют писать руками, а не пользоваться компами? Да потому что моторика крайне серьезно штырит мозг и вынуждает его работать еще лучше! Попробуй при решении своий рабочих программерских задач чаще рисовать.Задачки свои чаще пиши на бумагу, т.е. вынуждай руку писать и уверяю тебя, через полгода твой мозг будет еще лучше работать!!! Также и с математикой и алгоритмами, они настолько трогают мозг, что человек становится очень хорошим технарем. Хер его знает как это все работает, но оно именно так и работает! Не упрямься, а просто попробуй, к примеру, в свою повседневную жизнь добавить ежедневное решение задачек на LeetCode. Уверяю тебя ты от этого получишь только и только пользу: 1. Ты можешь дать ссылку на leet code в своем резюме, это отлично будет выделять тебя среди других кандидатов 2. Это отлично взбодрит мозг и настроит на рабочий режим перед основными рабочими задачами. Это как зарядку сделать, потом позавтракать, потом чуть отдохнуть и пойти на первую тренировку по лыжам. С мозгами также. Им утром надо дать пинка 3. Это позволит тебе видеть типовые решения при написании продуктового кода и видеть более эффективные подходы в программировании. Это как в лыжах, ты сначала не понимаешь, как же черт побери встать на эту долбанную лыжу, удержать свое равновесие и как можно дольше на ней прокатиться. Но спустя время, тело привыкает, мышцы как крупные так и мелкие развиваются и ты катишь на лыже очень долго и правильно. В программировании также. Не надо просто решать задачу, надо стремиться решать быстро, качественно и эффективно. Тогда твой роботодатель тебя будет ценить. Кстати, попробуй походи по собеседованиям с двумя резюме указывая что ты любишь алгоритмы и в другом просто без упоминания про алгоритмы. Результа тебя удивит
Вариант с HashSet тоже может отнести к сложности O (n log n), так как сложность поиска в нем O(1) лишь только ожидаемая и в худшем варианте будет О (log n). Вкупе с прожорливостью по памяти этот вариант вообще самый худший.
@@ВалерийБерезовский-я6р HashSet считается алгоритмически условным О(1). Этот момент на собесе я бы тоже проговаривал. Ну и алгоритмически он даже если будет выдавать О(1), то на практике он вполне может оказаться самым долгим. Там пара вопросов: какая реализация HashSet и какой хэш функцией мы пользуемся. Для чисел хэш считать не нужно, но вот к реализации вопросы остаются. Если там бакеты + списки, то результат будет в худшем случае О(n).
3:34 двойной цикл сделан неправильно Первая ошибка в первом цикле, нужно было сделать так for (int i = 0; i < nums.length - 1; i++) а лучше как то так for (int i = 0, endI = nums.length - 1; i < endI; i++) В твоём варианте при последней итерации будет i=4 и j=4 что приведет к сравнение одно и того же числа которое последнее в массиве. Вторая ошибка в условии где если в массиве если например цифра 2 а k=4 то твоя функция вернет массив [2, 2] Нужно было добавить проверку i!=j и получилось бы так if (i!=j && nums[i]+nums[j]==k) Ты не прошёл собеседование уже
Красиво. Я смог придумать решение похуже - O(2n) c двумя проходам по исходному массиву и одним оп массивом, но, формально, это, все равно, O(n) :) 1) проходим по исходному массиву a[] и вычисляем разницу d каждого элемента с 9. 2) кладем значение этого элемента в другой массив arr1[d] = a[i] 3) еще раз идем по массиву a[] и для каждого элемента пытаемся взять arr1[d] - если взялось,значит мы нашли результат. 4) в качестве доп оптимизации, можно сделать третий массив , где будут храниться значения d, чтобы не считать их во второй проход.
Если цель задания - выдать ответ, то все эти рассуждения не имеют смысла, т.к. занимают времени на порядок-два больше, чём само решение, к-рое видно сразу невооружённым глазом.
Так задача-то найти для любого массива пару дающую в сумме число k для всех возможных массивов и для всех k. А не просто для конкретного примера это сделать
А теперь представьте, что вы - компания Google с петабайт данными, и у вас в массиве миллиард элементов. Тогда ваше "очевидное" решение будет занимать сотни лет обработки.
Здравствуйте! Спасибо за видео). Вопрос не совсем по теме: какая основная разница между массивом и коллекцией, которая позволяет "одновременно" перебирать все ее элементы?
Не совсем понятно что значит "одновременно" перебирать все ее элементы. Collection наследуется от Iterable т.е. все коллекции позволяют перебирать, если речь об этом. Могу предположить что речь идет о том что массивы фиксированной длины, а реализации интерфейса Collection динамической, т.е. увеличиваются по мере добавления элементов. Массив также используется под капотом некоторых реализаций интерфейса Collection например ArrayList и частично HashSet. Ну т.е. более простой базовый объект для более сложных структур данных. В контексте задачи наверное речь про то что поиск по HashSet за О1 а не за On как у массива отсюда и ускорение.
Да, меня заинтересовало то, что сложность использования коллекции - О(1), а не О(n). То есть коллекция способна перебирать элементы настолько быстро, что время, затраченное на перебор, считается постоянным?
@@enternickhere почитайте "как работает HashMap в джава". элементы там хранятся в массиве связанных списков или массиве бинарных деревьев. Индекс массива вычисляется(а не перебирается) в зависимости от содержимого элемента при его помещении. И также потом при его поиске и извлечении.
"Встречный линейный поиск", названный оптимальным в данном ролике, со сложностью O(n) вовсе не является лучшим по скорости для больших массивов. Он будет лучшим только для массивов размером не более 16 элементов. Для значительно бОльших массивов лучшим будет алгоритм "встречного бинарного поиска". Его средняя сложность O(log2(n)*log2(n/2)), или что то же самое O(log2(n)^2 - log2(n)). Сравним на примере массива с 1000000 элементов. Для "встречного линейного" алгоритма, среднее время будет O(500000). Для "встречного бинарного" ~ O(20*19) = O(380). // На какую зарплату меня примут в Амазон? :)
А можешь накидать псевдокод или ссылку на реализацию, а то простое if (sum < value) left = (left + right) / 2; if (sum > value) right = (left + right) / 2; вместо if (sum < value) left++; if (sum > value) right--; явно не прокатывает
Бинарный код... он разный бывает. я своего рода бинарник на железной дороге использую для записи отсутствия стыковых болтов в журнале ограничений: 1 - есть болт, 0 - нет болта. Видео смотрю с удовольствием.
Не очень согласен со вторым и третьим решение. Во втором решение, как мне кажется, производительносить не вырастит так как нам нужно каждый раз проходить по set-у и искать в нем числа, а это не единичная сложность. А третий вариант требует отсортировочного списка.
Ну якобы, хеш таблица ищет за О(1). на практике это конечно не совсем так, так как О(1) - это хорошо распределенная хэш таблица, а если она плохо распределенная, то O(n) (или O(log n) если реализация хэш таблицы хитрая)
на python решается эта задача проще def twoSum( nums: list, k): index = 0 while index < len(nums) - 1 iskomoe = k - nums[ index ] if iskomoe in nums: return [ nums[ index ], iskomoe ] else: index = index + 1 return [ 0 ]
Вот-вот. Это наглядно можно заметить на потреблении ресурсов. А, ну и нужно больше пакетов богу пакетов (мы ж не будем писать свой велосипед возведения в квадрат допустим, мы возьмём его и стороннего open source пакета), чтобы например чат жрал 1гб памяти как discord тот же. Привет electron 😂 Как-то искал под Андроид приложение в маркете для перевода из разных ед (метрич/империч). Одно приложение нашёл 200кб, остальные 12мб+ 😂
![[#2024MAMA] ROSÉ (로제), Bruno Mars - APT. | Mnet 241122 방송](http://i.ytimg.com/vi/dgGqD28J6aQ/mqdefault.jpg)
Создал Telegram канал, в котором рассказываю о жизни в Лондоне, работе в Google и подготовке к собеседованиям. Подписывайтесь: t.me/saschalukin
-1 и 8 тоже дадут 7 :)
Хехе, точно, не заметил :)
@@sashalukin а я увидел, но так как профан, подумал что не все условия увидел)))
Так, закреплю коммент, чтобы все увидели) В начале в первом примере тоже два ответа и тоже можно вернуть любой из них.
Круто, что заметили :)
ток хотел написать
@@sashalukin я конечно не программист, но почему нельзя например из непосредственно результата "К" начать вычитать числа и сравнивать их с предложенными?
Надо в собеседовании ввести задание, чтоб и пытуемый посчитал пальцы на правой руке, затем на левой, а затем назвал общее количество пальцев на обеих руках.
Ппфф легко же. 5 на левой, 5 на правой, значит общее количество 25
@@pontypilat_0338 разве не 30?
изи, 55
@@carbonara_13 ты меня опередил
@@carbonara_13 а разве не жолтый?
Очень рад, что вы вернулись.
Наконец то вы вернулисссссьььььььь
Топ-видос! Посмотрел и сохранил в один из своих плейлистов еще в феврале, но вернулся и разобрался в последнем варианте решения только сейчас, когда твердо решил апнуть скилл в решении задачек (наткнулся на эту задачу на leetcode). Оказывается, лучшее решение не такое уж нетривиальное, как показалось на первый взгляд
Очень круто обьясняешь! Только учусь программировать и из роликов понял много полезных методов, алгоритмов поиска значений! Очень благодарен!
Почитай Вирта: Структуры и Алгоритмы, целый мир откроешь
еще улучшу ваш алгоритм! Совершенно бесплатно. в реальных проектах таких смешных массивов не бывает, а вот данных, состоящих из миллиарда элементов - очень частый случай. В первую очередь можно дропнуть львиную долю данных, установив "зум" на числа, потенциально допустимые. если границы массива i и n, искомое число k, то i >= -1*(n-k), n
Автор, мамкин кодер, опыт минимален, самомнение максимально.
Задача элементарная, двигаем окно и смотрим если сумма меньше, двигаем правую часть, если сумма больше двигаем левую часть.
На статистике данных по распределению чисел мин, Макс и n можно эмпирически вывести функцию которая весьма точно будет попадать в индекс массива, да ещё давать длинну окна.
Плюс для отриц и положит, будет два окна
9:49 - оно и есть. Только одно окно для любых элементов и любого результата суммы
А вот что делать если 3 слагаемых - пока непонятно.
@@gitarnoob воспользоваться решением примера именно из собеседования, чуть доработав, чтобы записываемый ответ слагался с оставшимися в окне элементами.
@@gitarnoob два указателя + хешсет
Отрицательные числа крайне редко в реальных задачах встречаются. Задачи эти теоретики диванные создают.
@@webblyy 2 указателя уже не нужны если есть хэш-сет
Ну, на php это можно решить ещё и таким простым и изящным способом, смысл которого очень прост. Нам известен результат k и дан некоторый массив array. Чтобы найти 2 числа наименьшим числом попыток, можно запустить 2 цикла for один в другом и проверять во втором цикле только числа справа от индекса первого. А можно как у меня - запустить всего один цикл и попытаться воссоздать второе число математическим образом, вычитая из результата первое число. Далее остаётся только проверить, существует ли такое число в массиве. И если да - результат нас устраивает
$array = [-3, 0, 1, 3, 4];
$k = 5;
for ($i = 0; $i < count($array); $i++) {
$j = ($k - $array[$i]);
if (in_array($j, $array) {
var_dump([$i, $j]);
}
}
Довольно простое задание, как мне показалось, наверное потому, что во многих заданиях, даже простых( на строки, например ) нужно идти с двух сторон.
Впервые столкнулся с вашим каналом. Смотрю на обложку, на название ролика и совсем не понимаю: а что тут сложного, это ведь решит даже ребёнок! Стал смотреть, а здесь оказалось программирование, тогда понятно стало. Забавно.
Ролик интересный, подача грамотная, успехов!
Хорошее объяснение и понятный код, спасибо. Ждём ещё, удачи в развитии!
Комментарий в поддержку канала. Автор, ты молодец, спасибо за труд!
лукас не глядя. давно ждал возвращения))
Спасибо! Очень интересно. Подписался. Буду ждать новых видео
как здорово, что Саша вернулся на канал! спасибо и ждем новые видео!
for i in [.......... ]:
if k - i in [...........]
answer = [i]
answer.append(k - i)
brake
else:
answer = [ ]
print(answer)
Сильно не вникал в задачу, поэтому возможно понадобится типизация данных. Главное схема решения
Аналогично через index или метод pop
Мое уважение автору, забывшему уточнить, что его оптимальное решение работает только на отсортированном списке
Спасибо! Мне кажется, не лишним будет упомянуть, что сортировка это в среднем еще плюс 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 на ЕГЭ тоже стресс не маленький)
Здравствуйте, давно увидел ваше видео в рекомендациях и жалею что не посмотрел ранее. Спасибо за контент👍
Я сначала не поняла решение с двумя указателями, а потом по коду как всё поняла. Очень интересно и хорошо рассказано, пасеба!
3:03 - i должно идти до i < nums.length - 1, так как следущий цикл начинается с j=i+1
Контент топчик. Как раз изучаю алгоритмы и структуры данных, недавно узнал о 2-х указателях. Теперь бы еще научиться все это видеть в конкретных задачах.
Спасибо :)
С опытом придет, если до этого решил 10 задач на два указателя, то и в 11 увидишь.
Если хочешь потренить, то вот сайт, на нем все к собесам готовятся:
leetcode.com/problemset/all/?topicSlugs=two-pointers
Решай easy задачи, и если не можешь придумать решение (а так в начале всегда будет), то смотри в комментах (секция Discuss). Удачи!
Подскажите, пожалуйста, по алгоритмам годные источники. И по структурные данным, если можно
@@hacamadahimichiru6110 Сам сейчас прохожу направление CS от Принстона на Курсере (от профессора Седжвика). Еще хвалят курс CS50 от Гарварда, но сам не пробовал. Все бесплатно и в интернете. Гуглите.
@@kselnaag2482 спасибо!
Снимай пожалуйста ещё ролики. У тебя очень хорошо получается. Очень познавательно!!! Спасибо!!
Я давно забросил программировать но первая мысль была от от 7 вычитать по одному и искать равные ! Последнее решение просто наикрасивейшее!!!
Можно так же идти с позиции I+1, чтобы не проверять уже пройденное число
последнее решение не работает
Ураа,ждал твоих роликов давно)
Спасибо, так просто о сложном. Вы талант. Надо клон сделать и учителем в школу.
Спасибо!
Очень интересно и полезно🎉
8:44 - тут лучше определить, что является входом и что является выходом нашей части, отвечающей за бинарный поиск и вынести наш бинарный поиск в отдельный компонент. Это как упростит чтение и понимание кода, так и сделает код более модульным. По сути тут происходит тоже самое что и в "HashSet"
Спасибо большое, скоро приступлю к таким задачам)
Классное видео. Автор все очень доступно и понятно объясняет.
Саше спасибо большое за труд и терпение к "диванным ворчунам" )))
Спасибо за видео! Очень интересная задача 👍👍🔥🔥🔥🔥
Бинарный поиск требует проверки на размер массива, так как при маленьком размере у нас время процессора уходит на математические вычисления середины и проверки (просто пометка от ноунейма).
Спасибо за видео. Люблю искать возможности для оптимизации. Пока с такими задачами не сталкивался, но если столкнусь, то буду знать, как сделать код быстрым, да ещё и красивым.
Круто и интересно, обязательно продолжай.
В решении с Set сложность set.contains в худшем случае O(log n), соответственно сложность решения O(n * log n)
Хэш сет имеет сложность на проверку вхождения в О(1)
Как и любая хэш таблица
Но что меня удивило, так это то, что мы вдруг отсортировали массив за просто так
@@Paravarka нет, у хэш таблицы худший случай O(N) (когда все айтемы попали в один бакет). Set в java использует TreeMap - у него O(log n)
@@Paravarka В хорошо распределенных хеш таблицах. Если распределилась плохо, то может быть и O(n), если реализация тупая и O(log n) если реализация похитрее.
Cпасибо за интересную задачу!
хочу ещё!)
Просто очередной комментарий про то, что надо микрофон-петличку 😉 В целом огонь-пулемёт, продолжай обязательно у тебя отлично получается 💪 12к подписчиков за год на 4 видосах говорит о том, что ты всё делаешь правильно, материал актуальный! Подтяни качество, сделай выпуски регулярными и будет круто. Если это тебе надо конечно 😜
Я думаю, что Александр это делает для общего развития - творческий порыв. Поверь мне, с такими мозгами ему доход от ютуба так... на шоколадки.
Приятно слушать. Да ещё и Java)) спасибо
Здорово, не занимаюсь программированием, никак не решаюсь начать, но настолько четкое объяснение, что понял даже я. Спасибо!
Спасибо! А программирование начать учить никогда не поздно, сейчас очень много моих друзей не из айти переходят в айти. Только время нужно выделить, я бы ориентировался хотя-бы на год, если довольно плотно заниматься.
Удачи!
@@sashalukin спасибо большое за совет и напутствие
Многое теряете, я когда по работе понял, что делаю много повторяющихся действий, решил автоматизировать процессы, я даже что такое IDE не знал. Уровень на доске меня пока восхищает, стремлюсь к тому, что бы сделать его банальным.
@@AVS11176 я вообще в банке работаю на данный момент, ну и как везде, 70% работы это эксель и какое-то статистическое ПО (типо R, у нас САС). То когда я залезал в VBA или в SAS все смотрели как на мага-чародея
спасибо, интересно и познавательно
В втором решении тоже два цикла. Второй скрыт - это поиск в хешсете (скрытый
перебор по нему)
Чего??? Поиск в хешсете О(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, потому что в какой-то момент программа будет пытаться найти элемент с не целым номером индекса, например, 6,5.
Делится тип Integer. Он при делении дает целочисленное значение без остатка. Пример: 13/2 = 6;
Java, в отличии от всяких питонов и js, строго типизированный язык и в нём исключено получить дробное значение при делении целых чисел, если явно это не указывать. При этом, результат деления всегда округляется до меньшего числа. То есть даже если провести операцию, к примеру, 59 / 10, то результат будет 5. Однако, если хотя бы одно из делимых чисел привести к дробному типу, вроде (float)59 / 10 или 59.0 / 10, то результат вычисления уже будет 5.9.
@@Rameronos не округляется до меньшего, а отбрасывается дробная часть - разницу хорошо видно если делить на 10 не 59, а минус 59
Зачем целочисленное деление, если есть битовый сдвиг? Или в джава он под запретом?
@@Rameronosпитон тоже строго типизирован, но динамически.
3:32 ошибка в алгоритме. в таких переборах первый цикл должен проходить массив до предпоследнего элемента: for(int i = 0; i < nums.length-1; i++)
Саша Лукин, спасибо за твой труд! Крайне хорошо поясняешь. Уметь пояснять сложное простыми словами это очень важный и полезный навык. В будущем, мы, люди, все чаще и чаще будем коммуницировать.
Хотел бы тебя спросить вот о чем: Как ВИДЕТЬ более эффективный вариант чаще? Ведь до этого же надо додуматься! Вот ты привел разные решения, но ведь про них надо было сообразить . Как развивать соображалку то? ;)
Пока, развитие сооражалки в алгоритмах вижу такой: Ты смотришь как решают другие. В голове откладываются разные подходы. А потом методом брутфорса при решении той или иной задачи пишешь код. Либо ты видишь такую задачу, которая очень похожа на ту, которую ты уже видел ранее и применяешь то, что ты помнишь. Но все это цепляется на знание и на способность мозга вспомнить и увидеть схожие черты с ранее решенной задаче. Есть ли другие способы ?
Чтобы развивать навык решения задач, нужно решать задачи. Чтобы развивать навык решать задачи эффективно, нужно решать задачи эффективно.
Итого. Берёшь задачу, САМ решаешь её в лоб, то есть самым примитивным и очевидным способом. Пытаешься найти другие способы (да, сам). Сравниваешь полученные варианты, анализируешь их плюсы и минусы, ищешь слабые места, места, которые можно улучшить и т.д. и т.п. Смотришь, как другие люди решают другие задачи (да-да, именно другие) в поисках вдохновения. Смотришь, не появились ли ещё идеи, которые можно применить к своей задаче. Когда ты уже сдедал всё, что мог сделать сам, тогда и только тогда можно смотреть, как другие решают такие же задачи. Тогда будет развитие, а если просто смотреть на других, хоть и на лучших, ну хз... Сильно ли накачаешься, наблюдая за тем, как сильные силачи тягают железо? Вопрос риторический.
Можешь не благодарить 😌
@@Dimarious.Gбоюсь сравнение с силачами не уместно, когда мы смотрим на силача, мы смотрим на процесс, и не применяем никаких усилий, а когда мы смотрим решение задачи, то мы смотрим на решение, а не на процесс, и применяем усилия для понимания
@@Dimarious.Gа так думаю ты прав в остальном
А. Бал. Деть. Узнал много нового. Спасибо!
Очень круто, ждем еще интересных и реальных задачек)
Мне вот эта задача по математике понравилась. Бородатая и не совсем айтишная, но может будет интересно :)
Встречаются два приятеля - математика:
- Ну как дела, как живешь?
- Все хорошо, растут два сына дошкольника.
- Сколько им лет?
- Произведение их возрастов равно количеству голубей возле этой скамейки.
- Этой информации мне недостаточно.
- Старший похож на мать.
- Теперь я знаю ответ на твой вопрос.
Сколько лет сыновьям? (Ответ логичный и однозначный)
поиск индекса по значению (k-i)... но досмотрю до конца.
Досмотрел, остаюсь при своем для первой части задачи. Вторая часть интересней, бинарный поиск для ее решения подходит лучше. Спасибо!
Во втором варианте все равно время работы O(n^2), так как поиск в хэшсете - тоже представляет из себя внутренний цикл еще и со сравнением входящего значения..., отличие лишь в том, что количество пар теперь образуется реверсивно на увеличение лесенки, а не на уменьшение как с двумя циклами, так еще и больше на одну пару становится: -3 и пусто, а уж потом 0 и -3, 1 и -3, 1 и 0. Явой не занимаюсь, могу лишь предположить, что просто поиск в хэшсете работает быстрее, чем функция for, но не забываем про время обращения к памяти , если работать с большим объемом + постоянное пополнение хэшсета - это тоже еще одно действие, на которое тратится время. Вообще плохо считать время выполнения по формуле, которая опирается только на количество данных)
>>"Во втором варианте все равно время работы O(n^2)"
Именно так, но видимо автор является очень "современным" программистом, т.е. о том, что внутри происходит особо не задумывается.
Логарифмическое время там должно быть на поиск. Пополнение за константу. Те сложность должна быть n + log(n)
Большое спасибо! Очень интересно )
Я бы сказал формализовать вообще всё.
Браво! Ваши видео просто замечательные! Продолжайте в том же духе! Хотелось бы узнать больше «инсайдерской» информации, как человеку, которому только предстоит работать :)
Ещё не работаешь в этой сфере?
Попалось видео, я щас пока что ничего не понимаю, но мне очень интересно)
так ведь в set.contains еще один цикл есть. Причем его длина растёт. Так что в итоге проходов больше чем n.
Тоже не понимаю, это вроде как жадный алгоритм, у него сложность, в худшем случае, может быть и O(n*log_n), если не ошибаюсь. Но точно больше n
@@hapcuji n^2. Проходов будет столько же, сколько и в первом варианте. Разница только в том, что в первом второй цикл от i+1 до n, а во втором - от 0 до i-1.
Суммарно n запросов к хешсету работают за линейное время
Хотя и каждый запрос может работать дольше, чем за константу.
@@ВалерийБерезовский-я6р ну да, каждый запрос - это O(n). Да ещё и формирование таких запросов тоже O(n). Вот и получится O(n^2).
@@sibedir не каждый запрос это O(n)
Всё обращения к множеству суммарно работают за O(n)
Для доказательства этого советую лекции по хешированным структурам на ютубе, или просто почитать neerc
То есть, в написанной программе есть запросы к сету, работающие за линию суммарно, и остальные выче
Остальные вычисления - линейны, складываем (не умножаем! Каждый запрос не работает за линию!), получаем тоже линию
Очень понравилось объяснение - доходчиво и наглядно!
Есть еще вариант: вычитать из требуемого числа последовательно один элемент массива и пробегаться по оставшемуся массиву в поисках такого же результата. Тоже не требует лишней памяти и также работает в O(n)
Это займет O(N^2) никак не O(N)
@@SayXaNow да, точно
Тогда вариант с вычитанием отпадает
Здравствуйте! Спасибо большое за разбор.
Задача интересная и довольно популярная. Но отдельный интерес вызывает именно математическое обоснование данного алгоритма. А именно: доказать, что решение найдется при движении именно левого поинтера, когда сумма меньше и правого, когда сумма больше.
Не сможете помочь разобрать? Обоснование порой спрашивают чаще, чем сам алгоритм. Спасибо!
массив упорядочен, поэтому. Если сумма меньше 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 спасибо! Да, Вы правы, такие вопросы на математические доказательства/обоснования мы получали именно в наших компаниях… интересно :) всего доброго, с нетерпением ждём новых выпусков! :)
Шикарно! Здорово! Полезно! Лукас субскрайбович! 🤣👍
Последнее решение даже не пришло в голову, пока не зашла речь про указатели, но чёрт возьми, оно такое простое и офигенное!
согласен
А вот адгоритм О(logn)
- Находим серпдину массива
- берем сумму чисел слева и справа от середины
- если сумма = искосому числу, то адгоритм завершён
- если сумма > искомого числа, то берем левую половину
- если меньше то правую
- с выбранной половиной проделывем предвдущие шаэто должно работать так, как сумма двух крайних элементов больше, чем сумма любых двух элементов слева и меньше, чем сумма лббых других двух элементов справа
Хотя может быть будут проблемы когда ожни и те же элементы идут подряд. К примеру: [....., 7,7,7....]
Тогда гаркшается учловие выше и сумма любых двух элементов левого (правого), множества ре обязана быть строго меньше(больше) суммы крайних
Недавно подписался и вот
Интересно, спасибо за контент
Мне вот кажется, что если считать в тактах процессора, то не факт что самое быстрое решение будет самым быстрым.
Это кодеры, они математику не учат )))))
В тактах какого именно процессора, гражданин умник?
У тебя хватит пальцев перечислить процессоры и архитектуры, для которых результаты будут разными?
@@КотМорзе Что вы знаете об ассемблере?
Современные программисты, извините, это рукожопы, составляющие программы из кубиков --- кем-то написаных готовых функций. И вот он например, в своём алгоритме использует функцию перемещения в конец массива. А эта функция, вполне возможно, тупо переписывает данные из массива по одному в новый массив, и это нифига не быстрее.
@@СтрогийЛёх Да, с большими массивами еще и кэшмиссы легко получить. Думаю, что на собесах имеет смысл рассказывать о плюсах-минусах каждого решения, начав с самого очевидного. А вообще да, сегодняшние программисты в основном кодеры.
Спасибо большое за информацию)
Прикольно, что сейчас в ЕГЭ задачи сложнее))
Годика 3 назад были задачи, что из списка чисел надо посчитать все пары, которые в сумме кратны заданному К. Вернуть все эти пары - это пара доп действий. Сейчас задаче ещё лютее)
@@kaspersky_ege у меня что-то похожее было, сдавала в 2017 году, решила на 4 балла 27-е в 2, что ли, цикла (без вложенного)
@@reisders с 2017 многое поменялось, мы теперь на компьютере экзамен пишем и программа реально должна работать на 1млн строк эффективно
ЕГЭ по информатике вообще можно в одном Экселе сделать
@@sed0k да конечно, особенно 24 задание и 15 удобно, 14 более менее, 1 и 13 -- один кайф, 10 -- обязательно в экселе, 6 -- ну естественно
к чему коммент? я сказал, что задача в 27 сложнее, пир чем эксель? почему? что за комментарий? я не понимаю.
я умер.
Спасибо, я только начал подступаться к программированию. Ничего еще не знаю, но все равно интересно.
Вначале подумал и придумал вариант такой: берем первый и суммируем с последним. Если больше К, то берем предпоследний и тд. Ползем назад сравнивая с первым. Потом берем второй и опять сравниваем с последним, идя навстречу второму. О том, что последний можно не сбрасывать почему-то не додумался )
Спасибо, за материал. Небольшой комментарий: если k известно, находим число ближайшее к k число в массиве (поскольку массив отсортирован это легко сделать либо методом дихотомии либо с помощью встроенных функций). После того как нашли число ближайшее k, назовем его X, мы знаем какое число нужно искать дальше, X+Y=k, Y = k-X. Проверяем на наличие Y в массиве. Если его нет, тогда ищем X от текущей позиции в массиве влево и вправо. Снова проверяем на наличие Y = k-X. Идт. Плюс мы еще можем отсечь хвосты массива, поскольку мы в поиске если Y = k-X < min(array) or k-X > max(array) then break. Интуитивно это мне дает в среднем логарифмическое время вычисления, потому что мы изначально нашли хорошее приближение. В худшем случае, n. Удачи!
Ваш алгоритм ничем не отличается от перебора всех пар, только с дополнительными шагами. Проверить на наличие Y в массиве - это уже сложность n-1 (пройтись по всем значениям массива кроме Х). В худшем случае надо будет перебрать все значения массива. Это дает n*(n-1). Еще найти найти ближайшее к К число. Метод дихотомии (он же бинарный поиск, 3е решение в данном видео) - log(n). Итого сложность вашего алгоритма log(n)+n*(n-1).
Пример: [1,2,3,4,5,6,7,8] k=16
P.S. время работы алгоритма - это максимальное время работы алгоритма для любого датасета.
Во втором варианте, все же, оценка не совсем верная. O() -оценка в ХУДШЕМ случае, а не в среднем. В ХУДШЕМ случае (если хеш-функция - хреновая), сложность будет O(n log n). Другое дело, что для int хэш известен. И в конкретном случае с int - все будет верно - O(n), но стоит заменить тип (самое простое обобщение), как все станет совсем не очевидно
Тип не имеет значения, коллизии будут всегда. С int'ами тоже вполне можно упереться в nlogn.
Суммарно n запросов к хеш таблице будут иметь сложность O(n)
И худший случая - линия, кажется, а не логарифм. Однако оценку на среднее время выполнение операции в O(1) можно доказать.
@@ВалерийБерезовский-я6р Ты не понял, сложность обращения к хэш-таблице в джаве - O(log(n)) в худшем случае
@@griglog но ведь оценка вида умножить худший случай на количество вызовов будет слишком грубой. Амортизированная оценка дает линейное время работы, как и у всех хешированных структур.
@@griglog а какой худший случай времени работы одной операции, линия или логарифм, пока что не понял. Кажется, что использование хеш таблицы обычно дает линию в худшем случае, но могу ошибаться.
В любом случае, суммарное время работы будет всегда линейным, а я ответил на комментарий, где автор оценивает асимптотику как O(nlogn)
Рад, что ты вернулся!
А разве hashset не использует цикл внутри себя для поиска элемента в массиве?
Нет, он высчитывает нужный индекс массива по ключу и просто возвращает данные по этому индексу
@@alex.lokhman Ага, пока коллизий нет, да там все "просто", а вот если есть...)
Прекрасная подача. Так держать!
(Во втором примере) Разве проверка наличия элемента а массиве равна O(1)? Мне кажется, что больше на O(n) похоже, тогда алгоритм будет О(n^2)?
Тож заметил) set.contains написал и радуется)
Разберитесь сначала что такое HashSet. Это не массив.
очень интересный материал, спасибо =) хотелось бы больше подобных видео
Интересно 👍
Палец и т.п. за этот видос!
По больше пожалуйста таких задача ! С разжевыванием и примером. Можно и не только на Алгоритмы.
Но и более простые на возвраты. На операции логики сравнения и т.п и т.д.
Вообще Очевидные цифры в особенности по условию - сразу бросаются в глаза.
Как пример из первого пункта: 8 + (-1)
Т.е крайние цифры к условию и цифры с отрицательным значением.
Опять же надо смотреть и на контекст условия..
Но учитывая последние примеры то как раз таки отрицательные цифры используются.
Приятно слушать - классная подача
Саша, привет! Большое спасибо за разборы задач. То, что ты делаешь - круто. Успехов тебе и каналу, продолжай. У меня вопрос: у тебя есть контактная почта или другие каналы связи? Хотелось бы написать: узнать и задать буквально пару вопросов про твой опыт переезда айтишника в Индонезию. Успехов!
сочувствую вам, если вы считаете, что ЭТО - круто...
Саша главное твоя подача! Красавчик
это разве не Two Sum с литкода?
даже two sum с литкода другая немного, как будто она даже сложнее
там массив не отсортированный и решается задача через хэшмапу
и еще там индексы нужно вернуть, а не сами числа
Спасибо большое!! Вы молодец!
Компания, которая ищет разработчика, спрашивая на собеседовании такие задачи, и получит разработчика, который умеет решать такие задачи.
Проще говоря, если их бизнес не построен на таких алгоритмах, они не знают, кого ищут
Знают они прекрасно кого ищут, просто крупные компании могут позволить себе заградительный ценз из алгоритмических задач на одном из этапов многоступенчатого собеса (подойдет ли человек для повседневной рутины на позицию X обычно решают этапы обычного технического интервью по стеку + этап по системному дизайну). У них там такой поток соискателей, что нужна лакмусовая бумажка на упертых, способных часами дриллить задачки с LeetCode, чтобы иметь хоть какой-то шанс пройти whiteboard-собеседование.
@@НикитаГлухов-п5ю на позицию Х - конечно подойдёт. А на нормальную позицию люди смотрят навыки, необходимые для позиции
маня . иди сервисы пилить . а то селект с базы долго отрабатывает . тока не вздумай тесты писать "этаже дорохоооо". а если серьезно . дружище вот это наша работа(алгоритмы) а не в точности знать каким методом вызвать балансировку авл дерева . а уменее её написать.
@@richagreen9937 и как, пригодились тебе в работе деревья? Мне за 10 лет работы реально пригождается регулярно только знание многопоточки, индексов в БД (что основные их реализации - это B-tree со всеми вытекающими) и простейших вещей из курса по анализу алгоритмов, чтобы приблизительно оценить, что джун воткнул для задачки код квадратичной сложности, хотя можно в линейку в один проход. Ну да, у меня были в вузе алгоритмы на графах, сортировки, основные структуры данных (несколько видов деревьев, хэштаблицы, кольцевые списки), были отрешаны куча задач на это в свое время, но за ненадобностью я все эти алгоритмы позабыл уже давно. Помню только названия и для чего применяется. Этого хватает, чтобы в случае чего, понять, что в задаче подойдёт какая-нибудь топологическая сортировка, гуглануть её код и скопипастить в проект. А мое начальство вообще не алгоритмы интересуют, а системный дизайн, так как от хорошего сильного программиста требуется понимание, когда нужны очереди, балансировщики и шардирование, а когда нет.
Серега, ты несколько не прав! Это всего лишь гипотеза, что если чел разбирается в алгоритмах, то он только их и умеет решать. Гипотеза ничем не подтвежденная.
Я работаю в ИТ чуть больше чем {floor(log10(factorial(36)))+1 - 27} лет и заметил вот что:
1. Бывают случаи, когда математик или олимпиадник, становятся крайне хреновыми программистами, т.к. любят заумничать. Но из этой выборки чаще всего попадаются люди, которые настолько хорошо видят код, что могут обрезать его скорость до таких малых единиц, что диву даешься и это без отладчика.Ты только подумал и решил, применить где-то тип set() , а чел вдруг говорит "Ну, так тут можно дальше sqrt(n) не считать" а ты только репу чешь с чего это он взял?
2. Также бывают и другие случаи, когда из программистов , которые самоучки или в универе учились на инженеров программеров выходят толковые ребята и их очень много. Однако при собеседовании ты видя, что перед тобою программист, а не программист который изучал математику или любит алгоритмы и у тебя нет понимания какой чел перед тобою. Он может быть с одинаковой вероятностью как хорошим продуктовым программером, а также с такой же вероятностью и хреновым. То что он прошел собес и ты ему дал работу , у тебя нет уверенности.
Практика во многих компаниях , в том числе и в России, показывает то, что у программиста, который любил, любит и продолжает любить математику и алгоритмы лучше код! Прям вот в разы! Различным best practice как писать код по-чище, по понятнее, т.е. ремесловое это все нарабатывается. А вот научить человека думать и думать крайне хорошо это ой как не просто и лучшего способа чем алгоритмы и математика нету!
Мы, люди, крайне сложные создания и то как работает наш мозг нам , можно сказать, не известно! То что мы знаем про мозг, это крайне малая часть от того что нужно было бы знать. К примеру, почему детям в школе чаще заставляют писать руками, а не пользоваться компами? Да потому что моторика крайне серьезно штырит мозг и вынуждает его работать еще лучше! Попробуй при решении своий рабочих программерских задач чаще рисовать.Задачки свои чаще пиши на бумагу, т.е. вынуждай руку писать и уверяю тебя, через полгода твой мозг будет еще лучше работать!!! Также и с математикой и алгоритмами, они настолько трогают мозг, что человек становится очень хорошим технарем. Хер его знает как это все работает, но оно именно так и работает!
Не упрямься, а просто попробуй, к примеру, в свою повседневную жизнь добавить ежедневное решение задачек на LeetCode. Уверяю тебя ты от этого получишь только и только пользу:
1. Ты можешь дать ссылку на leet code в своем резюме, это отлично будет выделять тебя среди других кандидатов
2. Это отлично взбодрит мозг и настроит на рабочий режим перед основными рабочими задачами. Это как зарядку сделать, потом позавтракать, потом чуть отдохнуть и пойти на первую тренировку по лыжам. С мозгами также. Им утром надо дать пинка
3. Это позволит тебе видеть типовые решения при написании продуктового кода и видеть более эффективные подходы в программировании. Это как в лыжах, ты сначала не понимаешь, как же черт побери встать на эту долбанную лыжу, удержать свое равновесие и как можно дольше на ней прокатиться. Но спустя время, тело привыкает, мышцы как крупные так и мелкие развиваются и ты катишь на лыже очень долго и правильно. В программировании также.
Не надо просто решать задачу, надо стремиться решать быстро, качественно и эффективно. Тогда твой роботодатель тебя будет ценить. Кстати, попробуй походи по собеседованиям с двумя резюме указывая что ты любишь алгоритмы и в другом просто без упоминания про алгоритмы. Результа тебя удивит
Мужик,твой материал на таком легке заходит,учу js,до такого уровня ещё не дошел,но о чем ты рассказываешь понятно,и заходит лайтово, спасибо за труд !
Удачи тебе,юный подаван.
Вариант с HashSet тоже может отнести к сложности O (n log n), так как сложность поиска в нем O(1) лишь только ожидаемая и в худшем варианте будет О (log n). Вкупе с прожорливостью по памяти этот вариант вообще самый худший.
А почему худший случай - логарифм?
Кажется, худший случай - это линия. Однако среднее время работы О(1).
@@ВалерийБерезовский-я6р HashSet считается алгоритмически условным О(1). Этот момент на собесе я бы тоже проговаривал. Ну и алгоритмически он даже если будет выдавать О(1), то на практике он вполне может оказаться самым долгим. Там пара вопросов: какая реализация HashSet и какой хэш функцией мы пользуемся. Для чисел хэш считать не нужно, но вот к реализации вопросы остаются. Если там бакеты + списки, то результат будет в худшем случае О(n).
У Вас талант объяснять понятно!
3:34 двойной цикл сделан неправильно
Первая ошибка в первом цикле, нужно было сделать так
for (int i = 0; i < nums.length - 1; i++)
а лучше как то так
for (int i = 0, endI = nums.length - 1; i < endI; i++)
В твоём варианте при последней итерации будет i=4 и j=4 что приведет к сравнение одно и того же числа которое последнее в массиве.
Вторая ошибка в условии где если в массиве если например цифра 2 а k=4 то твоя функция вернет массив [2, 2]
Нужно было добавить проверку i!=j и получилось бы так
if (i!=j && nums[i]+nums[j]==k)
Ты не прошёл собеседование уже
Эм.... Во втором цикле и так +1 к переменной j => i всегда меньше j на 1. Советую разглядеть первый пример получше
Красиво.
Я смог придумать решение похуже - O(2n) c двумя проходам по исходному массиву и одним оп массивом, но, формально, это, все равно, O(n) :)
1) проходим по исходному массиву a[] и вычисляем разницу d каждого элемента с 9.
2) кладем значение этого элемента в другой массив arr1[d] = a[i]
3) еще раз идем по массиву a[] и для каждого элемента пытаемся взять arr1[d] - если взялось,значит мы нашли результат.
4) в качестве доп оптимизации, можно сделать третий массив , где будут храниться значения d, чтобы не считать их во второй проход.
arr1 - это ассоциативный массив, т.е. хешсет. вся разница в том, что вы строите его целиком, а автор вероятно на лету проверяет
была такая задача в Яндексе))
спасибо за разбор, супер!
Если цель задания - выдать ответ, то все эти рассуждения не имеют смысла, т.к. занимают времени на порядок-два больше, чём само решение, к-рое видно сразу невооружённым глазом.
Так задача-то найти для любого массива пару дающую в сумме число k для всех возможных массивов и для всех k. А не просто для конкретного примера это сделать
А теперь представьте, что вы - компания Google с петабайт данными, и у вас в массиве миллиард элементов. Тогда ваше "очевидное" решение будет занимать сотни лет обработки.
Здравствуйте! Спасибо за видео). Вопрос не совсем по теме: какая основная разница между массивом и коллекцией, которая позволяет "одновременно" перебирать все ее элементы?
Не совсем понятно что значит "одновременно" перебирать все ее элементы. Collection наследуется от Iterable т.е. все коллекции позволяют перебирать, если речь об этом. Могу предположить что речь идет о том что массивы фиксированной длины, а реализации интерфейса Collection динамической, т.е. увеличиваются по мере добавления элементов. Массив также используется под капотом некоторых реализаций интерфейса Collection например ArrayList и частично HashSet. Ну т.е. более простой базовый объект для более сложных структур данных. В контексте задачи наверное речь про то что поиск по HashSet за О1 а не за On как у массива отсюда и ускорение.
Да, меня заинтересовало то, что сложность использования коллекции - О(1), а не О(n). То есть коллекция способна перебирать элементы настолько быстро, что время, затраченное на перебор, считается постоянным?
@@enternickhere почитайте "как работает HashMap в джава". элементы там хранятся в массиве связанных списков или массиве бинарных деревьев. Индекс массива вычисляется(а не перебирается) в зависимости от содержимого элемента при его помещении. И также потом при его поиске и извлечении.
Почитал, понял)
Приятно, что моя первая мысль и была лучшим решением
Та что уж там.. на миллион евро год
Спасибо. Доходчиво:) Подписка однозначно за годный контент:)
"Встречный линейный поиск", названный оптимальным в данном ролике, со сложностью O(n) вовсе не является лучшим по скорости для больших массивов. Он будет лучшим только для массивов размером не более 16 элементов. Для значительно бОльших массивов лучшим будет алгоритм "встречного бинарного поиска". Его средняя сложность O(log2(n)*log2(n/2)), или что то же самое O(log2(n)^2 - log2(n)). Сравним на примере массива с 1000000 элементов. Для "встречного линейного" алгоритма, среднее время будет O(500000). Для "встречного бинарного" ~ O(20*19) = O(380).
// На какую зарплату меня примут в Амазон? :)
Верно замечено. Ибо следующий вопрос, а если в массиве 10ки тыс. значений напрашивается сам собой...
20тыс рублей :)
Как оценили что именно с 16 элементов?
@@dimkin33 "Не помню, пьяный был" (с) КоллегаПоРаботе
Наверно просто пересёк фунции O(x) и O(log(x)^2)
А можешь накидать псевдокод или ссылку на реализацию, а то простое
if (sum < value) left = (left + right) / 2;
if (sum > value) right = (left + right) / 2;
вместо
if (sum < value) left++;
if (sum > value) right--;
явно не прокатывает
Бинарный код... он разный бывает.
я своего рода бинарник на железной дороге использую для записи отсутствия стыковых болтов в журнале ограничений: 1 - есть болт, 0 - нет болта.
Видео смотрю с удовольствием.
Не очень согласен со вторым и третьим решение. Во втором решение, как мне кажется, производительносить не вырастит так как нам нужно каждый раз проходить по set-у и искать в нем числа, а это не единичная сложность. А третий вариант требует отсортировочного списка.
В условиях задачи - отсортированный список (тайминг 0:55-0:57). Жаль, что это забыли упомянуть в заголовке.
Поддреживаю вопрос. Разве метод contains выполняется за 1 шаг? Внутренний цикл в метод спрятали и всё.
@@iwaneboshin3702 спасибо
Тогда третий способ имеет смысл
@@cotara92 поиск по хеш мапу выполняется за log(n) ну и по факту это решение под капотом одинаковое со следующим, с бинарным поиском
Ну якобы, хеш таблица ищет за О(1).
на практике это конечно не совсем так, так как О(1) - это хорошо распределенная хэш таблица, а если она плохо распределенная, то O(n) (или O(log n) если реализация хэш таблицы хитрая)
на python решается эта задача проще
def twoSum( nums: list, k):
index = 0
while index < len(nums) - 1
iskomoe = k - nums[ index ]
if iskomoe in nums:
return [ nums[ index ], iskomoe ]
else:
index = index + 1
return [ 0 ]
Самое интересное, что в реальных задачах очень мало программистов ищут оптимальный алгоритм, да же те, кто прошёл собеседование.)))
Вот-вот. Это наглядно можно заметить на потреблении ресурсов. А, ну и нужно больше пакетов богу пакетов (мы ж не будем писать свой велосипед возведения в квадрат допустим, мы возьмём его и стороннего open source пакета), чтобы например чат жрал 1гб памяти как discord тот же. Привет electron 😂
Как-то искал под Андроид приложение в маркете для перевода из разных ед (метрич/империч).
Одно приложение нашёл 200кб, остальные 12мб+ 😂
@@MrJloa Да, всё так.
Всё зависит от размера массива. Если там 100 элементов, то конечно какая разница. А если миллиард, то у вас программа повиснет с плохим решением.
@@thisismycoolnickname да не бывает миллиардов, в память не воезит))
@@deniangler большие компании как-раз работают с гиганискими массивами данных, и работают они быстро благодаря таким алгоритмам.
Круто и очень понятно, спасибо
Главный вопрос на собеседовании в икее: чей Крым?
Правильный ответ: "У меня плохо с географией, я не знаю". Полит. нейтрально!