Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 73
Поиск по файлу: простой двоичный поиск
Когда работал в команде биллинга, у нас была задача загружать файл с мобильными номерами для последующей блокировки по бизнес-логике.
Во время загрузки по этому файлу нужно было выполнять поиск.В какой-то момент предложил коллеге использовать двоичный поиск вместо линейного.
А как можно во время загрузки выполнять двоичный поиск?
Согласен не очевидно написал и до конца раскрыл, но суть была такая:
- Какие то данные уже были в хранилище
- Надо было загрузить новые данные, которые могли пересекаться со старыми
- Для поиска пересечения данных и был использован binary search т.к мобильные номера можно было упорядочить.
Примерно сократилось с ~50 минут до 3 минут
Почему не использовали хэш таблицу?
Удалось накопать со старой работы этот script, итак:
в хранилище хранились данные в виде ranges, а не списком номеров.
То есть были диапазоны телефонов построчно где в одной колонки с 79... в другой по 792...
Использовать hash map в этом случае было бы эффективно.
Новые данные же были как раз списком номеров, и надо было находить вхождение этих номеров в этих ranges. После уже отфильтрованные данные, вставлять в другое место.
1000 задач и 2 года ради того чтобы изобрести сортировку вставками?
Пока не очень понял задачу, но если у вас есть список новых номеров в файле и список старых номеров, и надо найти пересечение, и оба списка сортированные, то самое быстрое и простое решение - выполнить операцию слияния, как в сортировке слиянием: Берете первые номера из двух списков, если они равны - вы нашли пересечение, перейдите к следующим номерам в обоих списках. Иначе сдвиньте указатель в том списке, где меньший из номеров. Это один цикл while и внутри сравнение двух номеров.
Если списки не сортированы, то возможно будет быстрее отсортировать меньший список и искать в нем бинпоиском. Или еще лучше, использовать хеш-таблицу.
Но, похоже вы там квадратичное решение соптимизировали, там что угодно быстрее будет.
У нас не было два списка номеров.
Упрощенно вот так:
List #1 (просто список номеров)
79293342323
79293342321
79293342320
List #2 (ranges)
[’79291000000’, ’79291000999’]
[‘79290000000’, ‘79290000099’]
Соответственно надо найти номер из списка #1 в ranges #2
Тоже делается сортировкой и слиянием, если отрезки не пересекаются. Если первый номер в списке 1 входит в отрезок в начале списка 2, вы нашли вхождение, выкидывайте номер. Если первый номер левее начала первого отрезка, тоже выкидывайте номер из списка 1 (этот номер не входит в отрезки). Если первый номер правее конца первого отрезка - выкидывайте отрезок. "Выкидывайте" тут - это сдвиг указателя/индекса в списке. Делайте циклом while, пока хотя бы один список не кончился.
Если отрезки пересекаются, то и бинпоиск по отрезкам сделать нельзя.
Еще, если отрезки всегда задаются префиксом (т.е. вида XXX0...0-XXX9...9), то можно все отрезки загрузить в структуру данных бор (trie) по префиксам. Надо только. Потом искомые номера в этом боре искать, если дошли до финальной вершины (в которой один из префиксов закончился) - номер входит в отрезок, если перехода по следующей цифре нет - номера в отрезках нет. Это будет даже быстрее сортировки.
Если отрезки пересекаются, то и бинпоиск по отрезкам сделать нельзя.
Почему? Вот у нас в списке 2 отсортированные по началу диапазона интервалы. Допустим они могут пересекаться, указатель на "список 1" у нас, понятно, как и раньше линейно идет, а вот указатель на "список 2" сдвигается если элемент из списка 1 вне текущего диапазона по указателю списка 2, причем проверяется это в цикле "пока". Нормально работать должно.
Наверное имеется ввиду, что загружали данные из больших файлов. Наверное искали в файле каждый раз вхождение. А потом автор догадался отсортировать файл перед чтением.
Это к вопросу о нужности знания алгоритмов. Конечно надо знать, вот только найти применение этим знаниям в повседневной жизни получается редко. Скорее приходится решать прикладные задачи завязанные на язык программирования и библиотеки.
Единственное, вызвал уважение подход автора к обучению. Научиться структурировано разбирать задачи дороже, чем знания алгоритмов имхо.
Во время загрузки как раз и не нужен никакой двоичный поиск: всё равно пои загрузке все элементы перебираются последовательно. Разве что загрузка выпоняется уже упорядоченными блоками, искать в этих блоках.
Интересный опыт, спасибо что поделились 👍
Цель была апнуться по карьере, вместо этого два года непонятно на что, в итоге цель поменялась
Однозначно провал, вместо того что бы идти к цели, автор "готовился" к интервью два года
Это как хотеть играть на пианино, но вместо того чтобы начать играть выбирать модель пианино и смотреть как оно в квартире встанет, такая форма прокрастинации, как и алгоритмы в данном случае. А задним числом ещё и оправдания
Не соглашусь, скорее это как хотеть играть на пианино, но вместо того, чтобы сразу учить концерт Рахманинова и писать свою симфонию, два года играть гаммы и "к Элизе". Для профессиональных писанистов это скорее норма.
И если уж продолжать аналогию, то цель была - попасть в оркестр пианистом, а теперь поменялась на "научиться играть на пианино" - я бы не назвал это провалом))
Я почти уверен, что при желании 1–2 часа в день найти можно.
А если не получается — значит, у вас просто другие приоритеты.
Где-то тут у меня появилось зерно сомнений.. Человек с женой, двумя детьми, работой и здоровым сном и при этом стабильно находящий 1-2 часа в день на то чтобы заниматься обучением и алгоритмами помимо бытовой рутины, занятий с детьми, здоровьем, не выпадающий из социума и успевающий вести ряд интернет ресурсов.. лично мне это кажется чем-то сказочным, и в лучшем случае напоминает ошибку выжившего
Да мне кажется тут сыграла моя дисциплина, могу правда каждый день сидеть и учиться в ущерб другим вещам.
Знаю множество примеров, где люди с детьми находят те же 2 часа на просмотры "рилсов", поиграть в компьютерные игры или футбол - они где то находят время на эти развлечения. В моем случае "развлечение" - это учеба.
в ущерб другим вещам.
это не попадает под категорию "найти"
я имел в виду в ущерб бесполезным вещам - по факту у всех 24 часа в сутках - где часть на сон, семью и работу. Если у вас что то остается - "хорошо" вам решать как это использовать - если не остается - то можно подумать где взять доп. время. Приведу пример, давно когда я работал в офисе - путь до работы в метро был 45 минут. За год я прочитал несколько десятков книг по профессии, пока ехал до офиса и обратно каждый день.
За год я прочитал несколько десятков книг по профессии, пока ехал до офиса и обратно каждый день.
Ну да, я так джаву выучил и работу нашёл, и собственно продолжаю учить
Все ещё противоречит исходному комментарию. Человек говорит что у человека с семьей работой и здоровым сном нет возможности вырвать 2 часа вот так просто, а вы говорите "ой, да рислы просто перестаньте смотреть"
по моему, очевидно, что человек имеет в виду, что он не смотрит лилсы 2 часа в день и "вырвать" в данном случае можно либо у семьи, либо у работы, либо у сна
и это я даже не затрагиваю вопрос того, что на отдых мозгу время тоже нужно обязательно, иначе последствия будут не слабее чем от вырывания времени из сна, работы или семьи
Не смогу к сожалению дать хороший совет как найти время каждому: по сути вопрос приоритетов. Не зная лично человека, я пока пытаюсь "угадать" как это можно организовать. Но будучи уже взрослым, я искренне понимаю что времени меньше свободного на свои занятия, поэтому поделился своим опытом и идеями как это можно осуществить.
По сути первая ваша задача это - придумайте алгоритм как я буду учиться 1 час в день чему нибудь. 🙂
Если хотите, давай - те разберем план дня и поштурмуем где найти время.
а дедлайны есть по работе?
Тоже не понимаю этого прикола с leetcode. 1-2 часа в день это не мало (особенно если есть какая-то работа). При этом реального результата, который можно "потрогать" нет.
То есть любой соискатель может "на уверенном" пройти собес, не тратя столько времени на алгоритмы
На мой взгляд уместна аналогия со сдачей экзаменов. Ты можешь понимать материал или вызубрить его. Часто "прохождение" литкода сводится ко второму. Отсюда и все вот эти чатики про хакинг интервью и шаринг задач с реальных собесов - на реальные навыки такое влияет опосредованно.
Хорошо, что у вас получилось выработать некую систему, которая в том числе помогает развивать смежные области, но столько времени на это убить я бы не решился)
Как у вас с прогрессом по изначальными целям поиска работы, удалось?
Читалось интересно сам увлекался leetcode, года 4 назад, но потом пришло понимание что это плохо поддаётся монетизации и быстро выветривается из головы если не использовать (так как у меня прикладные задачи то мне эти знания не пригодились нигде кроме собеса). Поэтому хотел задать несколько вопросов. Не считайте их токсичными, у меня схожий опыт в обучении (я работая паралельно на вечернем получал диплом MBA, 2 года и 2000 часов) и если на 1-2 вопрос я знал ответ ещё перед началом обучения, то на третий оторвав эти 2000 часов от себя и семьи и заработав в результате эрозию желудка не смог ответить себе до сих пор.
А как вы монетезировали или собираетесь монетизировать этот навык?
По объёму усилий вы закончили магистратуру, теже 2 года и 2000+ часов в дипломе, какие приимущества вам даёт дает ваш опыт решения задач по сравнению с магистратурой по AI или прикладной экономике?
Те жертвы которые вы ради этого приносоли в течении 2х лет стоили полученного результата?
2) я прямо сейчас учусь в магистратуре, скажем так, бОльшую часть знаний, что там дают можно было бы почерпнуть на курсере или на степике или где-либо-еще. Плюс, спустя дцать лет опыта и с наличием диплома специалиста за спиной, могу сказать, что сигнал/шум очень маленький, а некоторые вещи, которым там учат - откровенно вредны (по моему мнению). Радует, что таких вещей мало, не радует, что молодые люди на этом же потоке не имеют возможности распознать это.
Но лично мне нужна корочка в первую очередь, хотя я немного и жалею, что не было возможности выбрать лучший ВУЗ с лучшим значением сигнал/шум. И да, я надеюсь, что магистерский диплом мне в будущем поможет.
А ваша магистратура по вашей специальности, рядом с вашей специальностью или другое направление?
Спрашиваю по тому что обычно можно сильно разочароваться обучаясь в том месте где уже должен преподавать.
Я имея на момент поступления +15 лет стажа в embedded даже не рассматривал близкие специальности, очень интересно выглядело AI от ВШЭ(особенно в применении к embedded), но учитывая конечную цель одеть костюм и перестать писать код мне это не подходило. 😃
Изначально я хотел, из-за наличия работы с приличной нагрузкой+изучения иностранных языков (местный, испанский мой любимый, в универе понял, что надо бы подтянуть английский академический, хотя и сдал минимум на C1 в уважаемой организации), и личных проектов пойти на ту же прикладную информатику в экономике (или менеджменте), что когда-то сам окончил.
Тогда бы это была бы "easy катка", ведь моя основная задача -- получить диплом.
К сожалению, группа на Applied CS не набралась и мне предложили пойти в Data Analysis and Machine Learning. Тут да, есть интересные предметы и темы, но поскольку бэкграунд ака балакалавриат сильно разный у ребят, и ВУЗ не сильно крутой, то дают интересные темы ну очень скромно. Больше по принципу -- типа бывают такие и такие вещи, сейчас мы сделаем лабу уровня отличия банана от яблока, или там нахождения коэффициентов линейной регрессии (путем прямого подбора), ну а дальше кому интересно те пожалуйста сами. И вот сижу я такой грустный, и думаю, "а дальше кому интересно пожалуйста сами" действительно стояло 10 000 твердой валюты в год, или нет?
Спасибо за вопросы
1. Я не рассматривал алгоритмы как навык с обязательной прямой монетизацией. Если говорить прагматично, для себя я вижу несколько возможных сценариев:
поиск более сложной и, как следствие, более высокооплачиваемой инженерной работы
менторство и помощь другим разработчикам
блогинг и образовательный контент
Первый вариант в целом всегда возможен.
Второй - вполне реалистичен.
Третий - под вопросом: я не считаю себя особенно харизматичным, поэтому на него не делаю ставку.
При этом изначально у меня не было жесткой корыстной цели. Скорее это было инженерное любопытство и желание разбираться в более сложных задачах. А более сложные задачи, как правило, требуют более глубоких знаний. Свой рост я прогнозирую в первую очередь в сложности и качестве задач, с которыми работаю, а не напрямую в деньгах - хотя косвенная связь, конечно, есть.
2. Здесь я не могу дать полностью объективный ответ - у меня нет завершенной магистратуры по этим направлениям, поэтому любое сравнение будет частично нафантазированным.
Тем не менее, если говорить о формате самостоятельного обучения через алгоритмы, я бы выделил следующие моменты.
Плюсы:
не нужно подстраиваться под жесткий учебный график - это особенно важно, когда есть семья
высокая гибкость: можно самостоятельно решать, что изучать глубже, а что пропустить
возможность в любой момент остановиться или изменить фокус без "потери времени"
может быть практически нулевой финансовый порог входа
развитие навыка самостоятельного обучения и поиска информации - это отдельная ценность.
Минусы:
отсутствие конкурентной среды и живого социального взаимодействия
нет готовой, выверенной учебной программы - ее приходится собирать самому
нет диплома или формального подтверждения пройденного пути
нет преподавателей, которые направляют и корректируют - их нужно искать самостоятельно
высокий риск перекосов: можно слишком долго застрять в одной теме или, наоборот, поверхностно пройти много всего
требует сильной самодисциплины и умения критично оценивать собственный прогресс
По сути, это обмен структуры и внешнего контроля на гибкость и автономию. Кому-то такой формат подойдет, кому-то и нет.
3. Здесь я тоже не до конца объективен, потому что мне действительно нравится решать задачи. Если честно, не могу сказать, что все это время страдал.
При этом я согласен, что для "оптимального" уровня, вероятно, хватило бы и года - условно 500-600 задач, без попытки довести все до максимума.
Еще раз подчеркну о чем писал в статье: какими бы ни были цели, не стоит пренебрегать базовыми вещами — здоровьем, спортом, семьей и социальным взаимодействием(друзьями).
Спасибо за ответ.
Насколько я понимаю из 1000 задач, там от силы наберется по 3 полезных задачи на каждую категорию, а остальные это просто повторение того же самого материала с перламутровыми пуговицами.
Если вы составите свой топ 30, то возможно это будет полезнее чем абстрактные "Топ 100 залайканных задач" и "Top Interview 150". И объяснить базу по категории можно на примере Easy, а при разборе Medium и Hard уже сфокусироваться на разнице, без повторения основ.
Я уже делали такие видео: например 5 задач на двоичное дерево или 5 задач на Linked list для собеседований
Одни из самых популярных на мой взгляд. Больше задач решаются именно для интереса и разнообразия, потому что не интересно решать одни и те же 5 задач 🙂
Даже колесико устало. Должен сказать, работа по подготовке статьи впечатляет, без приувелечения хорошая работа и достаточно информации для тех, кто хотел бы пойти похожими стопами.
ИМХО, на таком объеме уже не стоит вопрос "надо ли оно", я жесткий приверженец "абсолютно нет" даже для простых задачек. Это во всех смыслах много часов и пожалуй результат не стоит того. Тот, кто никогда не решал задачки(например я) не оценит ваших трудов и вовсе подумает, что 3% сложных задач это "не Senior уровень".
развитие навыка самостоятельного обучения и поиска информации - это отдельная ценность.
Задачки, к сожалению, - плохой способ получать знания, не потому, что вы решили мало задач, или плохие задачи, а потому, что способность решать алгоритмы переводится около-нулевой рост глубины и широты знаний в разработке. Плюсы, которые вы привели в комментарии выше относятся практически ко всем методам самообучения ИТ, но не все они так сильно отбирают время и ограничивают разностороннее развитие
Я себя не могу заставить сесть за литкод по двум причинам:
после плотного рабочего дня голова с трудом соображает, ты и не отдыхаешь, и решается все через боль с огромными затратами по времени.
LLM плотно вошли в этот мир, как инструмент. Этот инструмент уже отлично решает алгоритмы, достаточно примерно понимать, где можно оптимизировать, натравить LLM - готово.
А утром не получается?
Пункт #2 интересный для обсуждения - готов дискутировать !
(потом что я AI приверженец)
У меня часто были случаи, когда LLM предлагал неработающие алгоритмы или говорил что он нашел ошибку и ее там не было и даже часто оценивал сложность неправильно (и потом по классике - да ты был прав!)думаю без знаний было бы тяжело найти эти проблемы.
Но в целом понимаю что точность и корректировка ошибок это скорее вопрос времени.
Но тут есть момент которые мне не дает покоя, а надо перестать учиться считать - если уже есть калькулятор?
алгоритмы сейчас не являются вашей целью.
Именно.
Правда, это понимание обошлось мне гораздо дешевле по деньгами и по времени, чем автору, но ему все равно спасибо за рефлексию и изложение опыта. Не каждый день видишь 2000 потраченных часов на определенную цель (несмотря на оправданные сомнения в точке приложения сил).
Исходя из статьи создаётся ощущение, что
У самурая нет цели, есть только путь (алгоритмы)
За N лет алгоритмы пригодились... Ну я так понял 3 раза. То же справедливо, если я выучу какой нибудь CI/CD и применю его раза 3 за карьеру (если конечно я не DevOps). Только на алгоритмы 2 года и гора мучений, а CI/CD это месяц - два и эффект будет такой же крутой, как с алгоритмами (например время деплоя ручками 30-50 минут, а CI/CD щелкнул, 1 минута и готово)
Ну и да, алгоритмы - вход в бигтех. Просто +1 к скиллу прохождения интервью
Надеюсь когда нибудь ИИ научится алгоритмы решать и все перейдут к проверке инженерного мышления (о чем сказано в статье) исключая при этом алгоритмические задачи.
Меня невероятно бесят алгоритмы тем, что задача вообще бессмысленная часто, ты никак не понимаешь что от тебя хотят и даже если поймёшь - сложно спроецировать "а где это можно ещё применить". Просто какой-то искусственный барьер на интервью
Илья, спасибо за статью с подробным описанием своего опыта и системы подготовки!
Будет круто увидеть продолжение статьи с рассказом о прикладных рабочих задачах, где глубокое понимание алгоритмов привело к ощутимым бизнес-эффектам в виде экономии времени разработчиков, снижении расходов на инфраструктуру, снижение числа ошибок, сокращение затрат времени сотрудников вне разработки.
Я не автор, но у меня есть статья как раз об этом: https://habr.com/ru/articles/962688/
Из овер 1000 задач всего 35 сложных. И миро доска ещё.
Поражаюсь вашей целеустремлённости и даже хвалю её, но всё таки кто-то должен вам сказать, что для развития скила, нужно повышать сложность. Пусть это буду я.
Но если цель была ежедневная разминка, то, да, отличная работа.
нужно повышать сложность
Проблема hard задач в том, что там шибко много думать нужно. Уметь находить хитрые закономерности. Включать смекалку. Порой требуют наличия весьма непривычных навыков (например всякие побитовые хитрости уровня глубокого понимания представления отрицательных чисел в памяти). И т.д.. Для большинства разработчиков такое уже сильно за гранью применимости в продуктовой разработке. Как хобби, как спорт — отличная тема. Как практически применимые навыки — очень спорно. Ибо решение многих hard задач сродне пробиванию стены головой. А ведь в это время можно было бы покататься на лыжах, почитать книгу, поиграть в игры, поняньчиться с детьми, выспаться и т.д.
У меня hard задача из непривычной мне области легко отнимает 5+ часов. Ну это как-то перебор для for fun. После решения же, я как правило, не чувствую что стал умнее. Скорее понял конкретный corner case конкретной задачи. Это несколько демотивирует.
Для примера изюминка hard задачи может заключаться в том чтобы придумать псевдо-вершину в графе, которой нет в ТЗ, но она разблокирует применимость какого-нибудь алгоритма поиска минимального остова. И вот пока допетришь до этого (если вообще удастся) можно все мозги вскипятить. Но в другой задаче уже не будет такого lifehack-а. Там будет своя изюминка.
Согласен лишь отчасти. Хард задачи учат видеть краевые случаи и комбинировать подходы, но их решение отнимает несоразмерно много времени. При лимите в 2 часа в день лучше решить 4 среднячка и закрепить паттерны, чем 3 дня биться над одной хард задачей
Ваши аргументы резонны. Я согласен, новичку такие упражнения не повредили бы. Но 500 раз делать задачку по сложности экваивалентную задачке на палиндромы? Пост же сениор с 9+ лет опытом разработки написал.
Мне попадалось довольно много medium задач, которые были сложнее ряда hard задач. Я часто тупо не понимал в чём была логика того, кто расставлял уровни. К примеру там есть задача Wiggle Sort (не помню точно название). Она medium. Я даже посмотрев решение мало что понял. В то время как были hard задачи уровня напиши небольшой парсер. 15 минут рутины и accepted. Видимо hard тупо за boilerplate.
да немного упомянул этот момент в статье, так часто и бывает. На Leetcode задачи делают обычные люди и уровень они ставят как считают.
Поэтому я знаю десятки medium задач, которые уровня hard и выше. Как альтернатива, попробовать Leetcode Difficulty Rating плагин. Это более точный рейтинг из leetcode context.
С недавнего времени leetcode сам начал это выводить для Premium пользователей.
Алгоритмы для ресёрчера - необходимая база, но тратить тысячи часов на изучение базовых вещей имхо крайне неэффективно. На практике в 99% случаев задача решается одним из стандартных методов уже реализованных в библиотеках и собственноручное написание низкоуровневых алгоритмов наподобие сортировок или обходов графов нужно крайне редко.
Почему-то возникла ассоциация с врачом который решил поставить тысячу капельниц и тысячу катетеров, чтобы повысить свою квалификацию.
А вам пригодились алгоритмы в реальной жизни?
Мне алгоритмы пригодились буквально 1 раз в начале моего карьерного пути, когда я был не то джуном и не то мидлом, в 2013 году. Я писал свой вариант поиска в ширину по графам, потому что библиотечная реализация не подходила. В то время алгоритмы не спрашивали ни в яндексе, ни в гугле(да, были и такие времена). Но вот сумел как-то без литкода разобраться, вспомнить университетскую программу по графам, да гугл помог. А уже потом появился тренд на собеседования по алгоритмам, тут уже хочешь не хочешь, но пришлось обогатить знания по ним. Я, конечно, не 2000, но часов 20-40 на теорию и практику потратил, в целом могу сказать, что на практике мне это пригодилось как "вложенный цикл - это O квадрат, так низя". Поскольку литкод я особо не нарешивал, то как результат имею 5-7 заваленных секций по алгоритмам(не в 0 конечно, но и не на 100% чисто), а также следующие из этого результата комментарии "фу, не программист, это база" на хабре :)
Heap пригодился когда писал свою версию React-а. Нужно было сортировать древо инвалидированных (= требует rerender-а) компонентов. Обычная сортировка отпадает, т.к. эта коллекция изменяется в процессе (инвалидация context provider-а инвалидирует всех consumer-ов).
Причём потребовалось комбинировать его с HashMap. После знакомства с LRU кешем решение пришло в голову моментально.
LRU cache использую обильно уже во 2-й компании подряд. Гениальная штука.
Всякие обходы графов и деревьев пригождались сотни раз.
Наиболее интересные варианты были когда нужно было избегать circular reference-ов.
Топологическая сортировка пригодилась когда игрался с паттерном Observable
Trie пригодился когда писал подсветку найденного в тексте.
Linked List использовал несколько раз в кастомной реализации rate limiter-ов.
Конечные автоматы во всяких парсерах, интерпретаторах и иже с ними.
То что удалось вспомнить за 5 минут
2000 часов это полноценный рабочий год фултайм. Если пересчитать это в деньги (упущенная выгода + стоимость ментора в 3-4 зарплаты сеньора), получается наверное самый дорогой курс повышения квалификации в истории, который пока не монетизировался через оффер
Надеюсь, оно окупится ментально, потому что финансово пока выглядит как хобби для очень обеспеченных инженеров)
Проходил алгоритмические секции Яндекса, Авито, Озона успешно - на это надо буквально пару недель (пройти какие-нибудь внятные курсы на виды алгоритмов, чтобы не тупить на каком-нибудь обходе в ширину). Для иностранного бигтеха - думаю, что сравнимо.
По выхлопу на единицу затраченного времени для роста как специалиста - тоже странное решение. Если есть столько времени - лучше пилить пет-проекты и/или проходить курсы (микросервисы, кафку, DDD, TDD, погрузится в постгрю - тысячи их на любой вкус).
Какой-то извращенный вариант прокрастинации.
По поводу Кнута. Его книга не является учебником для вкатывания в IT, её предмет состоит в доказательстве свойств алгоритмов. Она ориентирована больше на людей, которые сами изобретают вещи, сходные с описанными, нежели на прикладных программистов, использующих готовые алгоритмы. Поэтому он там очень аккуратно доказывает операционную семантику алгоритмов через точно определённый язык своей собственной виртуальной машины.
Уважение! Еще отмечу , что на мой взгляд, гораздо полезнее навык , умение что-то "поверхностно" доказать. Это гораздо сложнее , чем "научиться видеть паттерны путем нарешивания", сам пытаюсь, но идёт туго, так как тут всё-таки мат. Мышление надо развивать, а у мня его нету). Но суть в том , чтобы не видеть два указателя, к примеру , в задаче, где дана непрерывная подпоследовательность и надо характеристику какую-то посчитать, а уметь доказать оптимальность на отрезке при расширении, к примеру. Тогда паттерн придет не из-за того, что что-то похожее уже решал, а просто потому что он следует из оптимальности как бы
В телнграмме есть канал l33tcode, там русскоязычные решатели литкода делятся рекордами, приглашаем
Круто!
У тебя на LeetCode ссылка на LinkedIn с опечаткой в одной букве. y -> i
Спасибо за то, что поделились
Спасибо за подробный рассказ! Я, конечно, поражаюсь (ну и немного завидую) вашему упорству!
Вы пишете про динамическое программирование: "Прорыв произошёл не сразу и не за одну тему" - А это было сколько по времени? В смысле, месяц, год, неделя?
Ну и конечно, главный вопрос: почему не питон? :)
И чтоб два раза не вставать, хочу "защитить" мой любимый Heap - я не согласен, что его долго писать, он довольно простой, если в голове держать, какие элементы куда просеиваются. А если делать heapsort - там даже просеивания вверх не нужно, только просеивание вниз, и весь код умещается строчек в 15 на питоне! Для меня бинпоиск сложнее, чем heap, потому что там надо в голове держать, что вернуть, если элемент не найден, или есть несколько одинаковых элементов.
я не согласен, что его долго писать
У меня больше 100 строк вышло. Довольно дофига для собеса. Но, правда я думаю, он много где есть из коробки.
да, если его оформлять как отдельный переиспользуемый класс, то получается много кода. Но на интервью, вроде бы, обычно нормально относятся к сокращению кода. Я сейчас попробовал написать по памяти хип сорт, примерно так получилось:
def sieve_down(arr, i, n):
while True:
lt,rt,best = i*2+1, i*2+2, i
if lt < n and arr[lt] > arr[best]: best = lt
if rt < n and arr[rt] > arr[best]: best = rt
if best == i: break
arr[i], arr[best], i = arr[best], arr[i], best
def heapsort(arr):
for i in reversed(range(len(arr))):
sieve_down(arr, i, len(arr))
for i in reversed(range(len(arr))):
arr[0], arr[i] = arr[i], arr[0]
sieve_down(arr, 0, i)
На собесе, по крайней мере в фаангах, никогда не попросят написать кучу. Надо будет догадаться, что тут надо использовать кучу и правильно ее применить. А дальше можно использовать стандартную реализацию (например, priority_queue в C++). Более того, вы можете даже забыть какой там именно интерфейс, перепутать параметры или забыть, как методы называются. Если вы просто объясните, что есть вот такая структура данных, работает вот на таком принципе, вроде есть в стандартной библиотеке, но я не помню деталей, вам все зачтут и даже минусов не поставят скорее всего. Можно просто в комментариях написать, какой вы предполагаете у класса из библиотеки интерфейс и так его и использовать.
Более того, если вы начнете кучу на интервью писать, грамотный интервьювер вас остановит, чтобы вы не тратили на это время.
Это обратная сторона интервью без IDE. У вас нет автодополнения, но никто и не требует чтобы ваш код даже компилировался.
Я знаю. Просто lightin2 упомянул что мол структура простая и пишется слёту. Я бы поспорил. Я помнится долго её отлаживал. На собесе я бы сильно удивился, если бы меня заставили её писать. Это изврат.
Ну, может, и изврат)) мне просто интересны эти задачи с точки зрения ментальной нагрузки. Иногда это называют cyclomatic complexity, но я определяю как матожидание количества исправлений от первой версии до полностью рабочей.
Я иногда могу потратить пару часов на задачу LeetCode easy, пытаясь ее написать так, чтобы минимизировать количество потенциальных ошибок. С этой точки зрения heap для меня проще бинпоиска, у которого много пограничных случаев, которые надо в голове держать.
Это, кстати, и в работе помогает - развивает интуицию, как надо писать код, чтобы потом его мучительно не отлаживать ))
Python надо было учить, а JS мне показался не сложным и я его уже знал. Просто в планы не входило изучение еще одного языка.
Heap не так часто пишется в целом с нуля, и на интервью его почти никогда не просят написать. Но согласен что если написать много раз, то он безусловно уже начнет казаться простым в реализации. На интервью, heap используется как вспомогательная структура, и задачу не успеешь решить если рука не набита на реализацию кучи.
За 2000 часов можно было заработать на покупку квартиры или машины. Точно алгоритмы того стоили?
Соглашусь с автором, что знание алгоритмов и Computer Science позволяет лучше понимать, что происходит "под капотом" у языка программирования, какие типы данных для чего используются и как избежать распространенных ошибок с неверной оценкой сложности алгоритмов. Базовые вещи действительно неплохо бы понимать. Но тут главное не переусердствовать, и уже в реальной работе, там где это возможно, стараться обходиться готовыми решениями, без написания "велосипедов".
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как я решил больше 1000 задач на leetcode за 2 года и потратил на это 2000+ часов своей жизни