Поступашки С++

Поступашки открывают набор на курс по алгоритмам! Хочешь поступить в ШАД или магистратуру, затащить олимпиаду? Или просто мечтаешь стать крутым специалистом и тащить алгособесы, но не хватает фундамента и практики? Тогда тебе к нам! Курс заточен под практику, будут подробно разобраны ВСЕ идеи и подходы, используемые составителями. Более того, ты сможешь получить ВСЕ ДЕНЬГИ потраченные на курс обратно, если первым решишь все домашние задание 😎😎 Курс длится 6 недель, каждую неделю по 2 урока, огромное количество дополнительного контента, более 40 часов уроков с последующим доступом к записям и ДЗ с проверкой. На семинарах с каждым учеником общаются по очереди, полноценное общение как здесь. Ежедневная связь, пробные собесы, экзамены, персональные рекомендации, инсайды и домашнее задание с проверкой, код ревью и с разбором! Все будет еще круче, чем на всех прошлый курсах (отзывы тут). Все для того, чтобы получить топовый оффер уже летом или мы вернем потраченные деньги! Занятия стартуют 17 марта Программа и подробности. Цена 8000р за курс, при покупке на одного человека. При покупке с другом, или если покупали наши курсы ранее 7000р, а если приобретали наши прошлые курсы по алгоритмам, то цена 4500 р. (материал полностью обновлен и расширен). Для записи и вопросов: @menshe_treh

Столько правил

Рехнешься

Товарищи, продолжаем -- сегодня изучаем реализацию сортировки слиянием :

void merge_sort(
    std::bidirectional_iterator auto const head, 
    std::bidirectional_iterator auto const tail)
{
    auto const n = std::distance(head, tail);

    if (n < 2) {
        return;
    }

    if (n == 2) {
        auto const first = head;
        auto const second = std::next(head);

        if (*first > *second) {
            std::iter_swap(first, second);
            return;
        }
    }

    auto const middle = std::next(head, n / 2);

    merge_sort(head, middle);
    merge_sort(middle, tail);

    std::inplace_merge(head, middle, tail);
}

Сразу изучаем, действительно ли std::inplace_merge работает inplace и не выделяет память? 😎 Кто может сформулировать преимущества и недостатки сортировки слиянием относительно быстрой сортировки?

Как разработчику попасть на стажировку Наш курс по бэкенд разработке начинается уже завтра (можно еще записаться), поэтому мы попросили выпускника нашего прошлого потока, который попал на стажировку в Яндекс и уже перешел в штат, поделиться тем, что бы он советовал конкретно ботать. Далее сохранен оригинальный текст. Сейчас без алгоритмов вас никуда не возьмут - их надо знать хотя бы на макаковском уровне, про это мы говорить не будем. Рассмотрим другие навыки, которые нужно жестко заботать. Для начала нужно разобраться в языке, на который идете (хотя бывают и исключения, когда в вакансии разрешают переходить на другие языки). Разбираться нужо на уровне нормально+/хорошо, ведь придется читать много чужого кода и быть готовым к популярным паттернам или почему делается так, а не иначе. Тут алгоритм один - найти какой-нибудь нормальный курс и найти задачи к нему. Дать ссылки на все учебные материалы по всем языкам дать не могу по понятным причинам, но рассмотрю подробно C++. Если смотреть базу - то тут подойдет любой курс на условном степике, например, от дяди Густокашина. Хорошо посмотреть какой-нибудь уже продвинутый курс от МФТИ от Ильи Мещерина или ФКН’а от Дани Кутенина. Полезно прорешать задачи, которые, благо, находятся в открытом доступе - их мне хватило в своё время. И конечно советую балдежный курс Поступашек. Также, попрактикуйтесь в написании упрощенных версий стандартных контейнеров, умных указателей (std::shared_ptr, std::unique_ptr, std::vector, std::unordered_map…) - бывает такое, что у собеседующего нет желания придумывать какие-то задачи и он уже пальцем в STL тыкает и говорит - “А реализуйте то, а реализуйте это” :) После изучения языка, если идете в бекенд разработчику, то полезно понимать работу сетей – почитайте сначала про модель OSI, что происходит, когда человек делает запрос в браузер и обязательно изучите HTTP, REST – по этим темам есть очень много статей на хабре. Прочитайте про JSON и попробуйте реализовать какой-нибудь примитивный HTTP сервис по типу записной книжки. Также, полезно будет посмотреть пару лекций по распределенным системам. Часто спрашивают что-то про многопоточку - посмотрите пару первых уроков от Романа Липовского. Тут обычно задают вопросы по типу какие примитивы синхронизации знаете, и что каждый из них делае (ну то есть нужно просто базовое понимание). Бывает, могут спросить и SQL – тут нужно изучить синтаксис (он не шибко богатый), почитать про индексы, и порешать пару задачек. Полезно будет изучить пару инструментов промышленной разработки - Docker, git, shell чтобы комфортно себя ощущать на работе, не факт, что их спросят, но пользуются ими очень часто. Вот пару полезных лекций по этой теме.

Итак, товарищи, сегодня рассмотрим быструю сортировку:

void quick_sort(std::bidirectional_iterator auto const head,  std::bidirectional_iterator auto const tail)
{
    if (head == tail) {
        return;
    }

    auto const pivot = std::prev(tail);
    auto const middle = std::partition(head, tail, [pivot](auto const& value) { return value < *pivot; });
    std::iter_swap(middle, pivot);

    quick_sort(head, middle);
    quick_sort(std::next(middle), tail);
}

Кто из вас сможет объяснить в комментариях, почему 1) может быть выгодно в качестве опорного элемента (pivot) брать последний? 2) в худшем случае у нас O(n^2), что это за худший случай?

Товарищи, а сегодня небольшая подготовка к интервью! Если вы прошли первоначальный скрининг, то на очном этапе вам могут устроить "проверку на вшивость" -- спросить что-то про временнУю и пространственную сложность алгоритмов сортировки, а также предложить реализовать известный алгоритм или его часть -- к примеру, лично мне однажды выпало написать реализацию алгоритма std::partition (который используется внутри быстрой сортировки). Сегодня начнем с того, что для оценки временной сложности рассматривают лучший, средний и худший случай. Оценки для временной сложности алгоритмов сортировки смотрим в таблице, знать нужно приблизительно верхнюю половину. Знакомимся с информацией, товарищи, а дальше будем реализовывать наиболее актуальные для интервью сортировки!

Мечтаешь стать крутым разработчиком, но не хватает фундамента? Хочешь овладеть знаниями и навыками для работы в крупной компании как Яндекс, ВК, Сбер или Тинькофф? Тогда тебе к нам! На курсах вся теория будет разобраны на конкретных задачах и кейсах, с которыми сталкиваются на работе и на собесах. А после прохождения курса тебя ждёт пробный собес с консультацией и такие пет проекты как реализация библиотек, HTTP KV хранилища с репликацией через RPC, которые пойдут в портфолио! Более того, ты сможешь получить ВСЕ ДЕНЬГИ потраченные на курс обратно, если первым решишь все домашние задание 😎😎 На курсе тебя ждёт 6 недель семинаров, лекций, материала и ДЗ с проверкой, ежедневная связь с куратором, личные рекомендации и инсайды. Все для того, чтобы получить топовый оффер уже летом или мы вернем потраченные деньги! Программа и подробности. Цена 6000р за один курс, при покупке на одного человека. При покупке с другом, или если покупали курсы ранее 5000р. Только 09.02 по промокоду "const everything!" скидка -20% (скидки не суммируются). Для записи: @menshe_treh

How to заботать С++ Начать изучение -- тут обойдемся без сюрпризов -- разумно с прочтения парочки хороших книг. Следует выбирать книги посвежее, которые охватывают как минимум стандарт С++11. Могу порекомендовать эту и эту. Выбирайте книги с большим количеством примеров кода, желательно маленьких работающих программ, и по мере прочтения книги обязательно самостоятельно компилируйте, изменяйте и запускайте эти примеры, а также придумывайте свои. Могу предложить эту и эту. Ускорить изучение вам может помочь напарник-единомышленник, который тоже горит желанием изучить как можно скорее мощный язык программирования! В нашем чате всегда можно обсудить примеры и непонятные моменты, что нелинейно ускорит процесс изучения и сделать его интереснее. Изучив базовый синтаксис языка, следует перейти к практике. Попробуйте самостоятельно написать какую-нибудь небольшую утилиту -- например, сделать собственную реализацию утилиты find (можно воспроизвести только часть функциональности). Это хороший способ оценить свои силы, а также познакомиться со сторонними библиотеками, ведь вам точно понадобится что-то наподобие Boost::program_options и, возможно, CTRE (для обработки регулярных выражений). Наконец, вы скорее всего придете к тому уровню, когда дальше можно будет учиться, читая чужой программный код. В сети много хороших и разных open source проектов, поэтому все сводится к тому, что нужно выбрать именно хорошие (с точки зрения качества кода и практик проектирования). Я бы порекомендовал на начальном этапе ориентироваться на библиотеку Boost, а дальше с опытом и практикой у вас выработается хороший вкус. Следующий шаг уже боевой опыт -- подавайтесь на стажировки, джуниор вакансии, ищите ментора, в общем, пробуйте свои силы в работе. А сократить путь вы можете на нашем курсе по бэкенду, где получите все необходимые метериалы, практику, личные рекомендации, инсайды и внимание от наших опытных наставников и, главное, найдете верных товарищей — все то, что нужно для карьеры!