Основы O-оценки сложности для алгособесов📈

Постараюсь ввести вас в курс дела как аналитиков, потому что любое Leetcode-собеседование (а их становится больше) подразумевает если не совсем оптимальное решение, то что кандидат хотя бы понимает, как это измеряется🤵

➡️ Что это вообще такое?
Big-O («О большое») — это асимптотическая* оценка того, c какой скоростью растут время и/или память алгоритма при увеличении размера входных данных, если отбросить константы
* для подробностей нужно определение предела, не сегодня

Время в данном случае — это количество простейших операций (что-нибудь сложить, умножить, присвоить), память — количество переменных, которое приходится хранить (например, во вспомогательных массивах), размер входа — сколько данных нам дано. Например, даётся один массив чисел — его длину мы обозначаем за N. Может быть задача, где каждый элемент входного массива уже не просто число, а, например, строка длины не более M, и это тоже окажется важно...

➡️ Основные правила оценки сложности вашего кода
Учим, как аксиомы:
⚪️ Любые фиксированные присвоения переменных (например, инициализация какой-нибудь суммы или указателей-индексов) — это константная сложность O(1)
⚪️ Линейный проход по всем элементам массива — O(N)
⚪️ Сортировка — O(N log N), если встроенная и оптимальная, но иногда доходит до O(N^2) (это уже другая история)
⚪️ Вложенные циклы: сложности перемножаются. Если у вас 2 вложенных for i in arr, где arr — ваш входной массив длины N, то будет O(N^2), если 3 — то O(N^3), и так далее...

Если массива два, то будет O(N * M), пример:

for i in range(len(arr_1)): # arr_1 - массив длины N
    for j in range(len(arr_2)): # arr_2 - массив длины M
        ...

⚪️ У последовательных шагов сложности складываются, но более быстрорастущее слагаемое поглощает остальные. То есть, если у вас сначала один цикл обработки массива, а потом 2 вложенных, то в пределе не O(N^2) + O(N), а просто O(N^2).

Если циклы не вложенные по двум массивам, то мы оставляем O(N + M), потому что не можем сравнить N и M асимптотически.

➡️ Быстрый порядок величин «от лучше к хуже»:
O(1) < O(log N) < O(N) < O(N log N) < O(N²) < O(2^N) < O(N!)

До последних двух мы стараемся не доходить в задачах на собесах, это нереально много операций. Например, задача рандомной перестановки элементов массива не подразумевает, что вы сгенерируете все N! штук, сохраните их и выберете.

➡️ Библиотечные методы и структуры тоже учитываются
Они оптимизированы по мере возможности, но та же сортировка никогда не станет линейной😬 Продвинутый уровень — выучить, что оптимально для какой операции.

➡️ Пример фразы, которая растопит сердце интервьюера😎

Тут получается сложность O(N) за счёт линейного поиска по массиву, инициализация переменных была за O(1). Могу написать бинпоиск, будет оптимальнее — за O(log N)...

Особенно, если вы реально понимаете, почему так работает))

Буду ждать фидбек, стало ли понятнее👍 И пересылайте друзьям, которые собираются на стажировки и другие собесы!

#хардов_пост #найм_и_собесы
@analytess 👩

Про интровертных айтишников и нетворкинг😎

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

➡️ С одной стороны, есть люди, которым тяжеловато подойти к кому-то и заговорить. А может быть, и просто не особо хочется — бесплатный фуршет интереснее (0% осуждения, сама бываю на этом месте иногда). С другой стороны, нетворкинг может быть и чересчур нарочитым и активным, и это тоже что-то не то🚨

Например, я думаю, что напечатать и раздавать свои визитки — это действительно крутой способ запомниться, если вы предлагаете людям что-то конкретное. Но не просто подписаться на вас, потому что вы классный (но вас видят в первый раз, поэтому пруфов не будет😄). А если вы пока не знаете, что предложить, то можно начать с малого...

➡️ Есть такая книжка: «Никогда не ешьте в одиночку». Не стоит это высказывание понимать буквально, если обед для вас — это единственная возможность выдохнуть между встречами и побыть одному. Но тем не менее, я верю в то, что именно во время неформальных посиделок с коллегами можно узнать что-то интересное, что не говорится на встречах в зуме.

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

В целом я бы начинала нетворкать следующим образом:
⭐️ позовите пообедать или за кофе коллегу, который вам интересен, даже если в команде нет такой традиции. Именно ланч или короткий кофе — это тот тип встречи, который возможен даже с занятым человеком, но при этом может положить начало чего-то бóльшего. Кстати, можно так поступать с бывшими коллегами (особенно, если офисы неподалёку))
⭐️ запишитесь на random coffee, если встретите такое предложение. Эти боты часто есть в айти-компаниях и разного рода чатах☕️ Обычно вам будут назначать одну пару в неделю, но фактически вряд ли вы всегда будете договариваться, так что это ненапряжная активность. А иногда бывает прямо мэтч🤝
⭐️ улыбайтесь, искренне интересуйтесь собеседником (задавайте вопросы в ответ и т.д.), поблагодарите за беседу и проговорите, если можете быть полезны чем-то в будущем👍

😘 Хочу вам признаться — я считаю себя интровертом, как и положено айтишнику (нет)😐 И это не мешает нетворкать, общаться в чатах, вести блог, просто после времени в компании мне требуется чуть больше тишины и отдыха в одиночестве🎧

➡️ А вам легко даётся нетворкинг? Были ли забавные кейсы?

#непопулярное_мнение
@analytess 👩

московский золотой час & вид из офиса Авито👍

к сожалению, не сегодня, но всё равно может вас замотивирует)

@analytess 👩

Меня прожарили по A/B по стандартам жёлтого банка🌟⚡️
(и нет, это не собеседование было. А пост — не рекламный)

Короче, мой знакомый Рома Филев (который против FOMO) прямо сейчас активно работает над форматом собеседований аналитиков и DS в Т-Банке, но все могут прикоснуться к их методам оценки — так я сходила на экзамен по A/B-тестам💊

Вы уже знаете, что A/B-тесты — чуть больная для меня тема.
Я ни на одной из своих big tech работ не погружалась в какие-то треш-кейсы, где всё пошло не так, потому что тест был неправильно спроектирован кем-то в jupyter notebook на коленке, который уже не воспроизводится, а продакт не шарит и требует остановить через 2 дня, и вот это вот всё😄

То есть это как бы слабое звено моего опыта, но я в последний год наконец-то стала уверена, что теорию выучила хорошо (потом обсудим, как). И поэтому мне было очень интересно мнение со стороны, основанное на чём-то сложнее, чем вопросы «что такое p-value» и «откуда берётся MDE».

За полтора часа мы с коллегой Ромы разобрали в телемосте три кейса по модели «найди, что тут пошло не так, и как сделать лучше». Успели поговорить достаточно подробно о нюансах выбора метрик, проектирования сложных экспериментов (например, с ML-моделью). Вскоре я получила фидбек с объяснениями, где конкретно я затупила, почему не 10😎

Я даже честно с вами поделюсь этими моментами:
➡️ не знала про одну популярную фишку для ускорения теста,
➡️ в кейсе с ML чутка зациклилась на технических штуках, тогда как ожидалось, что я выловлю бизнесовую проблему (кстати, это мэтчится с некоторыми моими провалами на собесах в прошлом)
➡️ можно глубже шарить за вариации CUPED и сетевые эффекты

Вывод: отлично, работаем дальше!👍
Я на своём примере по сути показываю, что не обязательно провести сотни тестов в компании без платформы, чтобы понять достаточно для найма. А так, всегда есть куда стремиться📈

#жизнь_в_бигтехах
@analytess 👩

Что внутри у GPT? Объяснение на 200 строк кода на питоне🐍

В последний, примерно, год часто чувствую в себе потребность по возможности успевать разбираться в современном машинном обучении чуть больше, чем на уровне «ну, LLM просто предсказывает наиболее вероятное слово» (хоть это и не так далеко от истины). Хотя бы для того, чтобы не быть совсем уж диванным аналитиком, когда высказываюсь скептически по поводу замены нас AI (мне иногда за такое предъявляют)😄

Признаюсь, во время учёбы я не очень любила ML и даже NLP, несмотря на мой некоторый интерес к лингвистике в целом. Закрывала базу на лабах, но не прочувствовала, что ли? Сейчас это кажется некоторым упущением, но так бывает, теперь читаю объяснения на стыке с научпопом и годные приношу вам🌟

И вот мне скинули прикольную статью на Хабре — точнее, перевод заметки из блога Андрея Карпаты (ориг на английском).
➡️ Проект microgpt — это буквально алгоритмические основы GPT без библиотек, на чистом Python. Всё остальное — уже вопрос эффективности и работы с большими наборами данных.

Плохая новость для кого-то может быть разве что в том, что без градиентов (высшей математики) там всё равно не обошлось. А так получился весь базовый цикл обучения: выбор документа и токенизация -> проход модели по токенам -> вычисление функции потерь -> обратное распространение (через градиенты) -> обновление параметров 📈

«Настоящая» LLM вроде ChatGPT отличается, собственно, тем, что она Large. Вместо 32 тысяч коротких имён она обучается на триллионах токенов текста из интернета — всевозможных веб-страниц, книг, кода и всего такого. Также используются более оптимальные алгоритмы на последующих шагах, а количество параметров модели больше на порядки. Ну, и сервера...

А вот понимает ли даже самая большая модель что-нибудь на самом деле — пожалуй, останется вопросом философским🤨
➡️ Кстати, вы какую точку зрения выбрали для себя?

#хардов_пост #аналитика_и_жизнь
@analytess 👩

Мама, я в телевизоре
Обожаю коллабы с классными коллегами по блогерству💗

Разбор популярной задачи уровня Leetcode Medium из бигтехов😎

Я знаю 4 компании из tier 1-2, где её давали на собесах в разных вариациях, поэтому пост обещает быть полезным. Погнали🚀

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

Пусть дан массив пар с городами и их населением, например:
[['Kaliningrad', 488690], ['Sochi', 445149], ['Kolomna', 213701]]

Вывести случайный город с вероятностью, пропорциональной населению.

1️⃣ Интуиция: давайте положим в корзину 488690 бумажек с надписью «Калининград», 445149 — с надписью «Сочи», 213701 — с надписью «Коломна», и вытянем случайную из них.
Это ровно то, что требуется сделать по условию, и чисто технически мы действительно могли бы создать такой огромный список строк (но не set) с названиями городов, и выбирать случайную.

2️⃣ А надо ли тратить столько памяти (пожалейте деревья😬)?
Окей, давайте заметим, что можно сэмплить случайное число между 1 и суммой значений в словаре. Если выпало от 1 до 488690, то возвращаем Калининград, от 488691 до 488690 + 445149 — Сочи, от 488691 + 445150 до 488690 + 445149 + 213701 — Коломну. Мы избавились от вспомогательного массива, который мог бы оказаться большим.

3️⃣ Тем не менее, а если городов очень много, удобно ли работать с такими большими целыми? Давайте нормируем так, чтобы сумма всех жителей упомянутых городов равнялась 1.0 — это лучше соответствует определению вероятности в принципе, а работа с float достаточно точная на практике. Делим всё на 488690 + 445149 + 213701 и вызываем функцию для случайного числа на полуинтервале [0, 1) — в питоне это random.random().

Опишем алгоритмически: за один проход по массиву (O(N), где N — количество городов) мы формируем массив кумулятивных сумм вероятностей выпадения каждого города:

cur = 0.0
sums = []
total = sum([city[1] for city in cities])
for city in cities:
    sums.append(cur)
    cur += city[1] / total
assert cur == 1.0 # должно сойтись по построению

# print(sums)
# [0.0, 0.4258587935932516, 0.8137746832354428]

Далее вызываем рандомное действительное число и ищем слева направо первый элемент массива sums, который больше него. Тогда ответ — предыдущий город🌇

r = random.random()
for i in range(len(sums)):
    if r < sums[i]:
        return cities[i - 1][0]
return cities[-1][0]

Выхода за границу массива слева не будет из-за строгого <, а последний return отвечает за случай r == 1.0 (вообще такого не бывает, но чтобы точно собеседующий был доволен).

Это ещё один проход по массиву размера N (aka линейный поиск), то есть сложность алгоритма O(N) + O(N) = O(N).

4️⃣🌟 Высший пилотаж: доводим до оптимального решения📈
Выше я не просто так упомянула сложность каждого из шагов.

Вторая часть может быть оптимизирована до O(log N), если линейный поиск заменить на бинарный. Это можно сделать, так как выполнено основное требование — массив кумулятивных сумм вероятностей является отсортированным по построению.

Теперь заметим, что по сути первое действие достаточно сделать всего один раз, а не каждый раз при вызове функции выбора случайного города (вызывать её будут много раз, раз речь зашла о распределении). Тогда можно вместо функции написать класс, где эта часть будет вынесена в __init__, а основной метод sample() будет быстрее.

Это в целом хорошая практика — выносить предвычисления из основного метода, так как за много вызовов sample() один целый проход по массиву амортизируется («размазывается» по всем вызовам).

➡️ Итоговый код приложу в комментарии! Как вам такой формат?

И голосуйте: 🤓 — если переслал другу, который ищет работу, 👩 — слишком сложно, до свидания, 🦄 — наконец-то понятно, спасибо

#найм_и_собесы #хардов_пост
@analytess 👩

Что спрашивают на собесах на 400+ тысяч на руки🤵💸

Недавно я получила очень, не побоюсь этого слова, жирный оффер в красный ритейл с юга России. Случилось это, как обычно бывает, стихийно — сидели в кафешке с другими ребятами-авторами аналитических каналов, и заговорили, кто кого куда может пореферить. Ритейл этот сейчас на слуху как HR-бренд — хоть пока и не в топе бигтехов, но явно развивается📈

Вакансия была сразу чётко на грейд Senior, подразумевала высшее профильное образование, плюсом было бы понимание ML и продвинутых концепций вроде A/B без A/B. При первом созвоне рекрутер сразу рассказала, что на самом деле подобных вакансий несколько в разные команды, и можно пообщаться последовательно, чтобы понять, куда я лучше подойду👍

➡️ Этап 1. Техническое собеседование SQL + Python⚡️
В этой компании пайплайн собесов не унифицирован, поэтому в некоторых командах просят что-то более практическое в Jupyter Notebook и/или разрешают гуглить. У меня же был классический лайвкодинг на чистом листе с CTE и оконками в первой части и алгосами Easy/Medium во второй.

Попалась задача на два указателя — моя нелюбимая концепция в алгосах, мне немного подсказывали, но засчитали.
За 10 минут до конца собеседующий спросил, хочу ли я ещё задачу на питон (это странно, то есть она уже не влияла на исход? или вопрос с подвохом?), там попалась более приятная, и я реабилитировалась (в том числе в своих же глазах😄)

➡️ Этап 2. Проверяем знание базы чутб по глубже📝
Здесь у меня не сохранился полный список вопросов, помню, что было не очень сложно, мне понравилось. Много маленьких задач и кейсов — а-ля интерпретация задачки про светофор, парадокс Симпсона, что-то про кубики, кейсы, где A/B плохо работает, и что можно с этим делать (достаточно было знать методы A/B без A/B по базовым концепциям, ну а читала я про них много). В какой-то момент собеседующий задумался, что бы еще такого спросить, и мы даже затронули классическое NLP😐

За эту секцию я получила резко положительный фидбек ещё в моменте лично от собеседующего — думаю, она во многом повлияла на итог этой авантюры. Спасибо моему кругозору😎

➡️ Этап 3. Финалы и раздумья со всех сторон☯️
Тут повторилась тенденция, которую я стала видеть в 80% случаев и часто о ней говорю — теперь финал это полноценный собес, зачастую с кейсами, не просто вайб-чек и оргвопросы вроде «а будет ли у вас удалёнка и сколько вкусов сырков».

Пофиналилась с одними ребятами сначала, но там было как будто бы чисто измерение качества ML-моделей, любопытно, но не то, что я бы хотела. Попросила ещё команду, пообщалась с прикольным хэдом, который просил рассуждать «не как математик, а бизнесово», но оценил мой бэкграунд и назначил знакомство с продактами, которым я тоже понравилась👀

Дальше был перерыв где-то на неделю, во время которого вроде как обсуждали, как оптимально заюзать мои навыки и тех.кругозор🌟 Я тоже не особо торопилась, как вы понимаете.

В итоге мне сделали оффер, который ооочень приятен финансово, даже если бы что-то случилось с премиями (обещали кварталки 20%). Что я решила делать с этим предложением и почему — расскажу через пару дней😏 А пока сохраняйте, распространяйте, намекайте реакциями, если интересно⚡️

➡️ Мораль: хорошие вилки всё ещё есть на рынке, но есть и требования взамен — у меня создалось чёткое ощущение, что это не какой-то базовый оклад, который предлагают всем🥲
😘 Кстати, весь процесс от контакта с HR до оффера занял полтора месяца, но там ещё был НГ. Норм или стрём?

➡️ Что думаете? Собеситесь? Как вам ситуация на рынке?
😏 — всё очень плохо, 🤓 — всё не очень плохо, 👩 — какие такие собесы?

#найм_и_собесы #карьерный_путь #жизнь_в_бигтехах
@analytess 👩