How to забоать алгосы к ШАД за оставшееся время

Товарищи, вступительные ШАД совсем скоро, самое время начать готовиться!
Для начало сравним задачи вступительных 2023 и 2018 года.

Вот несколько задач которые встречались в 2023 году.
https://t.me/algoses/6
https://t.me/algoses/12
https://t.me/algoses/19

2018 год
https://t.me/algoses/69
https://t.me/algoses/9

Задачи сильно отличаются......
2018 год был аномальным по алгоритмам и сейчас такого уже не делают, так что расслабляемся и не тревожимся.
Лучше всего сфокусироваться на свежих задачах, это касается не только алгосов, но и всего другого. Тот же матанализ, если вы видели задания 2022 года и 2023, то согласитесь во многом общие темы.

И так какие же темы по алгоритмам попадались в прошлом году и какие скорее всего попадутся в этом ?
—Бинарный поиск, два указателя, префиксные суммы, жадные алгоритмы, бинарные деревья, графы.

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

Объясню логику почему на последним этапе именно такие задачи.
-Во первых это Яндекс и зачастую на собесах дают задачи со сложностью O(N).
-Во вторых собес длится 30 минут, давать задачи на сложные алгоритмы или сложную идею нет смысла, скорее всего будет задача где можно легко уйти не туда, не учесть подводные камни и наделать багов. Как раз таки темы на два указателя/жадные алгоритмы такие.


На вступительных экзаменах могут встречаться два типа задач: идеи‌ные и простые на реализацию.

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


—Теперь про подготовку:
Чтобы избежать ситуации, когда не удастся решить простую задачу на графах из-за недостаточного знания этой темы, я предлагаю вам ознакомиться с алгоритмами, перечисленными выше. Для этого можно решать простые задачи на соответствующие темы на платформе leetcode. Желательно до-конца марта это одолеть.

Начиная с апреля, мы переходим к решению более сложных задач.

-Для БП и двух указателей берите курс ИТМО (чтобы ссылка работала, нужно зарегаться), если вы прорешали все задачи на бп и два указателя, я уверен вы сможете решить любую задачу из ШАДа на эти темы.

-Префиксные суммы, жадные алгоритмы и бинарные деревья лучше всего решать на Leetcode, ваша цель дойти до уровня медиум.

-По графам не нужно знать супер сложные алгоритмы. Я вам рекомендую acmp, прорешать обязательно 1 часть, а второй части решить хотя-бы по 5 задач на алгоритм Флойда и Дейкстры.


Если вы все эти темы хорошо знаете или осталось еще свободное время для подготоки, я предлагаю вам порешать задачи на монотонный стек, СНМ, ДП.

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

Сегодня пост про статью моего любимого жанра - "если А, бери Б" 🌝

Встречайте - Battle of the Backbones. Ребята взялись найти лучший бекбоун для задачек Computer Vision. Искали для четырех задач - классификация, детекция, сегментация, image retrieval и определение out of distribustion. Подход прост - учили разные комбинация на разных датасетах, а потом смотрели, где метрики лучше.

Итого:

Топ средних по размеру бекбоунов:
- supervised ConvNeXt-Base
- supervised SwinV2-Base trained using ImageNet-21k
- CLIP ViT-Base

Топ маленьких бекбоунов:
- ConvNeXt-Tiny
- SwinV2-Tiny
- DINO ViT-Small

Более подробный топ по каждой задаче на картинке.

Веса брали из библиотечки timm, поэтому использовать их должно быть легко.

Пару интересных выводов от авторов:
- CNN часто опережает ванильный ViT (а неванильные заимствуют идеи у CNN - например, swin)
- при одинаковом количестве данных self-supervised претрейн (типа SimCLR, DINO) оказывается лучше

​​Распараллель меня, если сможешь
.
TaskFlow и динамический маппинг тасок в AirFlow. Эти две возможности
также открыли для меня коллеги. Стоит отметить, что программирование дагов для меня
неPythonic way - странный синтаксис, странная логика, как будто неPython внутри Python🤷‍♂️
.
Две вышеобозначенные возможности не добавляют питонячности, хотя и можно найти какие-то сходства с
функциональным программированием.
.
TaskFlow - набор удобных декораторов для создания дагов, тасок, как Python-функций. Теперь, вместо:

def etl():
    pass

with Dag(...) as dag:
    etl = Python(task_id="etl", python_callable=etl, ...., da=dag)

Можно написать:

@dag(....)
def create_dag():

    @task
    def etl():
        pass

create_dag()

.
Красивый код получается, когда используются подходы в чистом виде: или классический или декораторы, когда классический стиль и TaskFlow смешиваются получается каша 🥣. TaskFlow даёт одно очевидное преимущество: TaskFlow сам заботиться о перемещении данных между input\output tasks, как если бы вы использовали обычные функции - это очень круто🤘 Пример ниже:

@task
def get_data_from_api() -> List[]:
    ...
    return data

api_data = get_data_from_api()

@task
def etl(data: List[]) -> None:
    # transfrom and save data
    ...

etl = etl(data=api_data)

.
Второй интересный паттерн: динамический маппинг тасок. Сегодня у тебя 1 хост, а завтра 7. Сегодня нужно 3 таски за разные дни, а завтра 8. Чтобы на зависеть от неизвестных входящих параметров следует брать на заметку динамический маппинг. Реализуется он довольно просто: у каждого оператора (таска) есть методы, например, partial, expand, что это нам дает:

1️⃣ Генерим несколько дат и выполняем etl за каждую

@task
def get_dates() -> List[str]:
    return ['2024-02-01', '2024-02-04', '2024-02-03']

@task
def etl(dated_at: str) -> None:
    # some code, which required from dated_at

dates = get_dates()

# метод expand - позволяет вызвать экземпляр таски для каждого элемента списка
etl = etl.expand(dated_at=dates)

2️⃣ На s3 N файлов, нужно однотипно все обработать или просто загрузить

@task
def find_s3_files() -> List[str]:
    return [{'filepath': 's3://file_0.parquet'},
     {'filepath': 's3://file_1.parquet'},
     {'filepath': 's3://file_2.parquet'}]

files = find_s3_files()

# используем partial для задания аргументов одинаковых для каждой таски
# выполняем загрузку каждого файла отдельной таской
load = ClickhouseOperator.partial(
        task_id="load",
        connection_id="conn_id",
        sql="""INSERT INTO stg.table SELECT * FROM s3('{{ params.filepath }})'""",
    ).expand(params=files)

.
Ранее такое приходилось реализовывать через циклы, а начиная с версии 2.3 у нас есть удобная возможность - используйте💪
.
Самое интересное, что маппить можно не только 1 -> N, но и Nin -> Nout, то есть рельтута одного маппинга подавать на вход другого и работать это будет именно так как ожидается: не сначала N первых тасок, а после N последующих. Таски свяжутся в последовательные кусочки: N1 -> N1, N2 -> N2 и тд 🔥

Набросал небольшой пример, как можно работать с API при помощи динамического маппинга - покрутите, экспериментируйте.

🔗 Links:
- TaskFlow
- Dynamic Task Mapping
- Create dynamic Airflow tasks (astronomer)

#airflow #taskflow #mapping

Инженерные грейды в Big Tech (ч1)

Меня часто спрашиваю про грейды в Big Tech компаниях. В MAANG и прочих Биг-Техах существует четка иерархия инженерных уровней, которая определяет ваш карьерный рост и компенсацию. Чем выше ваш грейд, тем больший масштаб импакта от вас ожидается, и тем шире должно быть ваше влияние на коллег вокруг, то есть требуется больше лидерских качеств.

В этом посте поговорим только про инженеров (SWE) и иcследователей (RS), которые, как правило, прокачиваются по одной и той же лестнице грейдов.

Система уровней в Meta и в Google считается христоматийной - она у них почти идентичная. Ее мы и рассмотрим.

E3, Junior: Начальный уровень - это джун, которого наняли без опыта после бакалавра или магистратуры. От джуна ожидается выполнять назначенные таски без большой помощи извне и не бояться задавать вопросы, если застрял. В Мете дают 2 года, чтобы запромоутиться с E3 до E4, иначе на выход.

E4, Middle: Средний уровень, на который хайрят после 1-5 лет опыта либо свежих выпускников с PhD. Мидл берет на себя отдельные фичи в проекте (много тасок) и выполняет их с минимальным руководством извне. На этом уровне ставят жесткие рамки в 3 года, чтобы стать E5.

E5, Senior: Это независимая боевая единица в компании, эксперт в своей сфере. Синьор владеет целыми фичами или системами и успешно завершает свои проекты. Это терминальный уровень в том смысле, что на этом уровне можно оставаться до пенсии. Промоушен на E6 никто обещать не может, так как прыжок с E5 на E6 на порядок сложнее чем с E4 на E5.

Про E6+ расскажу в следующем посте.

#bigtechlevels #карьера

@ai_newz

Инженерные грейды в Big Tech (ч2)

Все инженеры глобально делятся на две категории: просто инженеры (E3-E5) и Стафф+ (E6+) инженеры. Тут под инженерами я также имею в виду и сайнтистов - их глобально не отделяют и грейды у них такие же.

Когда в компании говорят про "leadership" роли, то обычно подразумевают именно Стафф+. Количество E6+ инженеров и сайнтистов в компаниях всего примерно 10%-15% .

E6, Staff: С этого уровня начинается новая игра. Стафф обладает исключительным техническим мастерством, имплементирует самые сложные фичи, решает задачи, которые мало кто может решить. Кроме того от него ожидаются еще и серьезные коммуникативные и лидерские качества. Он сам предлагает новые проекты и лидит их, ставит цели своей команде и влияет на другие команды.

E7, Senior Staff: Тут ожидают все тоже самое, что и на E6, но с еще большим импактом и ценностью для организации. Синьор стафф драйвит идеи от появления до реализации, попутно правильно расставляя приоритеты, понимая стратегию и тренды на масштабе всей компании.

E8, Principal Engineer/RS: Ты признанный эксперт в одной или нескольких областях как внутри компании так и за ее пределами. Твои проекты и идеи имеют влияние на всю компанию, а также на людей из твоей сферы в индустрии. В случае с наукой — ты исключительный эксперт, статьи которого узнают на конференциях. Как пример — Kaiming He, автор ResNet, который был где-то на E8-E9, пока не ушел из Меты в MIT.

Сложность перехода на каждый следующий уровень после Синьора (E5) растет экспоненциально, и количество людей на каждом следующем уровне убывает тоже по экспоненте.

Начиная с E6 появляются архетипы инженеров, например "фиксер", "архитектор", "тех лид", "Coding Machine" и другие. Про это поговорим позже. Но если вам любопытно, то подробнее про E6+ можно почитать на staffeng.com, там собраны истории людей на E6+ из разных крупных компаний.

#bigtechlevels #карьера

@ai_newz

System Design
Learn how to design systems at scale and prepare for system design interviews

What is system design?
System design is the process of defining the architecture, interfaces, and data for a system that satisfies specific requirements. System design meets the needs of your business or organization through coherent and efficient systems. It requires a systematic approach to building and engineering systems. A good system design requires us to think about everything, from infrastructure all the way down to the data and how it's stored.

Table of contents

- Getting Started
What is system design?
- Chapter I
IP, OSI Model, TCP and UDP, Domain Name System (DNS), Load Balancing, Clustering, Caching, Content Delivery Network (CDN), Proxy, Availability, Scalability, Storage
- Chapter II
Databases and DBMS, SQL databases, NoSQL databases, SQL vs NoSQL databases, Database Replication, Indexes, Normalization and Denormalization, ACID and BASE consistency models, CAP theorem, PACELC Theorem, Transactions, Distributed Transactions, Sharding, Consistent Hashing, Database Federation
- Chapter III
N-tier architecture, Message Brokers, Message Queues, Publish-Subscribe, Enterprise Service Bus (ESB), Monoliths and Microservices, Event-Driven Architecture (EDA), Event Sourcing, Command and Query Responsibility Segregation (CQRS), API Gateway, REST, GraphQL, gRPC, Long polling, WebSockets, Server-Sent Events (SSE)
- Chapter IV
Geohashing and Quadtrees, Circuit breaker, Rate Limiting, Service Discovery, SLA, SLO, SLI, Disaster recovery, Virtual Machines (VMs) and Containers, OAuth 2.0 and OpenID Connect (OIDC), Single Sign-On (SSO), SSL, TLS, mTLS
- Chapter V
System Design Interviews, URL Shortener, WhatsApp, Twitter, Netflix, Uber
- Appendix
Next Steps, References

Links:
- Direct link to the site with the course
- Direct link to the repository for the course
- Content Guide link
- Topic Guide link

Navigational hashtags: #armknowledgesharing #armcourses
General hashtags: #systemdesign

@data_science_weekly

#dl #nlp

Балалайка, березка, Matryoshka.

Выпустили концептуальный гайд по эмбам матрехи на hf. Красивые картиносы матрех и схемы, концепты теории и примеры на sentence-transformers.

Ну че тут рассказывать? Все просто берем embs и вдоль dim нарезаем по нарастающей, сводим саб эмбы и эмбы в конвеере metric learning на нужной датке в NLI, STS или qa задачках. Хочешь сводишь все на одном и том же, хочешь каждому эмбу из нарезки сообщаешь свою таску.

В чем польза?
1. Меньше индекс - на поверхности.
2. Возможность строить быстрые каскадные пайпы ранжирования. Преранк, например, на full index с маленьким эмбом (так быстрее), далее сложные примеры на more big эмбах, итоговый реранк в топ1 на жирнючем.

Код в блоге присутствует. Поэтому дерзайте.

🐈 CatBoost - супер удобный градиентный бустинг

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

Про то, как работает градиентный бустинг можно почитать, например, в статье с обзором ансамблей машинного обучения или в хендбуке от Яндекса. Одна из самых лучших библиотек для градиентного бустинга над деревьями решений – CatBoost. С этой библиотекой побеждают в соревнованиях на kaggle, она используется для решения задач классификации в крупных компаниях

Её преимущества:
– Встроенная обработка категориальных данных (их не нужно предобрабатывать, просто выставить гиперпараметры)
– Уменьшенный риск переобучения
– Высокая скорость работы и эффективность на больших объемах данных
– Встроенная обработка пропущенных значений
– Классная визуализация

Чтобы разобраться с этой библиотекой, стоит:
– Почитать официальную документацию
– [ENG] Посмотреть тетрадку с обзором катбуста
– Почитать статью про катбуст
🦖[ENG] Посмотреть видео от StatQuest (часть 1 и часть 2)
🌶 Посмотреть видео от Computer Science Club

Ставьте огоньки 🔥 под этим постом, и пишите в комментариях, про что написать ещё)

Пацаны из Майкрософта выпустили самую обсуждаемую статью месяца The Era of 1-bit LLMs:All Large Language Models are in 1.58 Bits
Пока остальные кряхтели и пытались отквантовать числа до 4 бит с большими потерями или до 8 бит с небольшими, челы из МС зашли с ноги: любой вес будем представлять как трит - 1.58 бита {-1; 0; 1} и покажем как это сделать не теряя перформанса! It matches the full-precision (i.e., FP16 or BF16) Transformer LLM with the same model size and training tokens in terms of both perplexity and end-task performance

Так же пишут: More profoundly, the 1.58-bit LLM defines a new scaling law and recipe for training new generations of LLMs that are both high-performance and cost-effective. Шортим Нвидию? Теперь вместо умножения - просто складываем (ведь умножение на 1, 0 или -1 это просто плюс, минус или пропуск). The new computation paradigm of BitNet b1.58 calls for actions to design new hardware optimized for 1-bit LLMs.

Что делают? Повторяют BitNet, то есть трансформер где nn.Linear заменен на BitLinear (ниже будет пост с описанием). It is trained from scratch, with 1.58-bit weights and 8-bit activations
Чтобы веса держать в диапазоне -1, 0, 1 - накидывают absmean quantization function (про нее тоже в посте ниже)

И это все
Результаты в посте ниже

Дальнейшее чтиво
https://t.me/hn_best_comments/21227
#ArticleReview

Кому удобнее на русском - есть перевод:
https://habr.com/ru/companies/ruvds/articles/793698/