Реши задачку с трансляции

algocode:
https://algocode.io/courses/algo-big-tech/problem/top-k-frequent-elements

leetcode:
https://leetcode.com/problems/top-k-frequent-elements/description/

Решить нужно за O(n) по времени и памяти

До 22:00 по МСК сегодня смотр твои решения и комментирую. Так что можешь смело присылать их в ЧАТИК под этим постом 🙂

Хорошего дня!

5 задач, на которых завалились 5000 кандидатов

С задачками Озона разобрались, так что…

С понедельника начинаем разбирать задачки Яндекса!

И — уже в компании ребят из сообщества:

• Встречаемся в Google Meet для удобства

• В 9:00 по МСК созваниваемся и обсуждаем идею задачи

• После разбора пишем код и делимся решениями

Присоединяйся, если хочешь уверенно чувствовать себя на собеседованиях!

https://algocode.io/algorithms

Задача - убийца джунов

Есть задачи, которые даже senior-а спокойно загоняют в тупик, да вообще всех загоняют в тупик...

Как раз эта задачка — одна из таких...

По условию: к нам приходит корень бинарного дерева, в каждом узле которого есть буква A-Z.

Нужно найти 2 вершины, которые содержат одинаковое множество букв без учёта повторений, и вернуть эти вершины.

----

От прошаренных кандидатов ждут, что они будут кодировать каждое поддерево в виде битовой маски.

Тут каждая буква представляет собой 1 бит:

A - 0...001
B - 0...010
C - 0...100

И если в поддереве есть, например, вершины A, A, C, то получим 0...101.

----

Дальше дело техники:

1) Обходим дерево и храним словарь, где ключ — битовое представление поддеревьев, а значение — сама вершина.

2) В каждой вершине проверяем, есть ли у нас в словаре уже эквивалентное поддерево, и если есть — возвращаем две вершины.

3) Если дошли до конца, то возвращаем два нулевых указателя.

----

Надеюсь, эта задачка обойдёт тебя стороной, ведь решить её за 40 минут непросто даже когда знаешь решение.

Ну и бахни 🌭 по-братски

Как же я нереально тупил на алго-задачах

Когда только начинал изучать алгосы, то, боже мой — как же они, сука, долго изучались

И я всё время пытался ускорить этот процесс

Вот что я пробовал:

- на протяжении нескольких месяцев решать по 2–4 задачки в день

- решать на релаксе одну задачку утром

- забить болт и не решать 😂

И тут нет плохих и хороших подходов, просто на разных этапах карьеры для меня работало что-то своё

До первого коммерческого опыта + Junior
тут я фигачил жёстко алго-задачи (2–4), ибо времени было много

Middle:
забил болт — да-да, я так перенасытился этими задачками, что мог уделять по алгоритмам в разговоре 95% времени с кем общался, и этого было достаточно как в работе, так и для собесов

Senior:
сейчас уже мне интересно порешать задачки для себя и для души

А ещё кайфую от рассказов, как вы прочитали пост/посмотрели ролик на ютубе и прошли собесы

Так что дерзай! Всё в твоих руках!

Еще одно успешное собеседование в Яндекс

Буквально пару дней назад еще один участник сообщества algocode.io

разбомбил секцию Яндекса

Расскажу про одну из задач, которая ему попалась:

Условие

Есть список чисел, и нужно найти монотонную последовательность максимальной длины (строго возрастающую или строго убывающую). В качестве ответа нужно вернуть индексы начала и конца последовательности

Это значит, что в

2 3 5 4 3 2 1 3
Ответ: 2, 6 (5 4 3 2 1)

А в

1 2 1 2 3 4
Ответ: 2, 5 (1 2 3 4)

В общем-то вся сложность только в том, что ЗАРАНЕЕ неизвестно, возрастает она или нет.

Вместо того чтобы городить кучу вложенных IF-ов, лучше в отдельной переменной всегда поддерживать текущую длину строго возрастающей последовательности,

а в отдельной переменной —

длину строго убывающей.

И все будет тип-топ!

Не нужно тут усложнять и пытаться сделать как можно меньше переменных.

По сути решаем 2 задачи:
1) Находим максимальную длину строго возрастающей
2) Находим максимальную длину строго убывающей

Потом просто выбираем максимальную и возвращаем как ответ.

ПРОФИТ!

Чтобы не тупить потом на собесе, обязательно прорешай задачку.

algocode:
https://algocode.io/courses/algo-big-tech/problem/search-monotonous-sequence

leetcode (очень похожа):
https://leetcode.com/problems/longest-strictly-increasing-or-strictly-decreasing-subarray/description/

На сколько нужно динамическое программирование?

В общем, ДП — это отдельный мир

Ты можешь вертеть деревья как не в себя, знать все обходы графов и как бог решать задачки на backtracking

НО

Это почти никак тебе не поможет в освоении ДП

Материала по тому, нужно ли ДП вообще, раз два и обчелся, поэтому рассказываю:

1. Если ты готовишься к олимпиадкам и в целом интересуешься спортивным программированием, то ОНО ТЕБЕ НУЖНО как воздух

Без этого сложновато будет затаскивать контесты, хоть и возможно

ОДНАКО

2. Если ты просто хочешь подготовиться к собесам, то тебе можно ничего не делать и ты в принципе не особо что-то потеряешь

Вероятность встретить ДП на собесе есть, но это будут простые задачки вроде:
• https://leetcode.com/problems/climbing-stairs/description/ (задачу дают в Озоне)

Но на сколько велика эта вероятность? Точно ли она мелкая?

На 50 задач компании приходится максимум 1–2 на ДП. И дают их в основном интервьюеры-олимпиадники, которые скучают по соревнованиям

Так что переживать особо не стоит

Советую это сэкономленное время потратить, например, на тему точек и отрезков (если никогда её не решали)

На ней достаточно часто сыпятся если раньше не видели и при этом тема встречается много где

Че для вас готовлю...

В общем, на ютубчике был разминочный ролик в новом формате

И

Я понял, что нужно разобрать какую-нить тему ОТ и ДО

Чтобы и в практике применялась

И широкое применение имела

И понтануться на собесе можно было

В общем, буду делать топовый гайд по сортировкам

Все книженции и гайды на ютубчике будут отдыхать и курить в сторонке

Тут только merge sort рискует 30 минут занять…

А у меня в планах еще минимум 7 сортировок есть :)

Я не понял, а где Bogosort???

Продолжаю ресерчить сортировки для ролика, и один из источников — это YouTube

Там неистово жаловались на автора, что он не разобрал Bogosort

Я такой ошибки не допущу 😄

Услышал я о ней вот буквально сегодня

Ну это, конечно, кто-то жестко угарнул

1) Проверяем, отсортирован ли массив
2) Если да — готово
3) Если нет — перемешиваем массив случайным образом и возвращаемся к шагу 1

import random

def is_sorted(arr):
    return all(arr[i] <= arr[i+1] for i in range(len(arr)-1))

def bogosort(arr):
    while not is_sorted(arr):
        random.shuffle(arr)
    return arr

print(bogosort([3, 2, 1]))

А ты слышал о ней раньше?

Сидим с Даней и обсуждаем ролики которые будем для вас готовить

Merge sort уже вымотал все мои нервы 😂

Из интересного - это оценивать не только пиковую память в сортировке, но и суммарную аллокацию

В общем, есть 2 оч похожие реализации где памяти суммарно выделяется O(n*log(n)) в первой и O(n) во второй

Хотя!

Обе имеют оценку O(n) по пиковой памяти

Вот тебе и Big O

Мерять в ней все не получится. Но прирост в производительности оч большой

Скоро уже перейду к описанию qsort

И в конце августа - начало сентября планирую выпустить для вас на YouTube уже готовый ролик со всеми сортировками

P.S. если я этого не сделаю, то проспорю 120 000 Дане :)

А отдавать деньги неохота...

Лучше для вас 120 000 в монтаж вложу

Монтаж про то, как на изи залететь в Яндекс, уже на подходе

По большей части мемный, но и полезные задачки есть

И я там говорю, что в Яндексе самые красивые рекрутеры

И БУКВАЛЬНО СЕГОДНЯ

Мне пишет рекрутер :)

Ля, ну я не знаю, чем они их заманивают, но рекрутерам Яндекса я всегда отвечаю

Как решать алго-задачу с первой попытки?

Прикинь: заходишь на собес, 10 минут — и первая алго-задачка отлетает в нокаут, ещё через 15 минут вторая готова

Оставшееся время спокойно болтаешь с интервьюером за жизнь 🙂

Примерно так проходят 90% моих собесов по алгосам

Для этого я всего лишь решил в районе 1000+ алго-задач (олимпиадные + LeetCode)

НО БЛЯ…

Лучше бы я этого не делал 😂

В общем, хочу рассказать, что самое важное, чтобы научиться щёлкать алго-задачи быстрее, чем гопник щёлкает семки

🤙 ТОП-1 ФАКТОР: насмотренность

Каждый раз, когда мне удавалось закрыть алго-собес за 30–40 минут, это были понятные мне задачи

Понятные — значит, я читаю условие и сразу знаю, как решать. Причём не одно решение, а сразу вижу оптимальное и ещё 2–3 варианта, которые можно обсудить

И это не обязательно были задачи, которые я прям решал. Просто я видел кучу разных задач и перепробовал столько подходов, что становится легко

А как её прокачать?

И нужно ли так много задач решать как ты? (нет)

---------

Когда ты решаешь много задач, твой мозг автоматически пытается объединять их в смысловые группы

Другими словами, мозг экономит ресурсы и хранит меньше инфы

Такие группы принято называть паттернами

Мозг — это очень умная нейронка, поэтому, даже не осознавая, ты вырабатываешь чуйку: просто подкидываешь ему периодически задачки и их решения

Минус только один: процесс долгий

А, нет, обманул: минусов дофига. Например, если перестанешь закидывать новые алго-задачи в мозг, он начнёт СТИРАТЬ НЕЙРОНЫ

И вернуть форму будет сложно — придётся заново его прокачивать

И что, теперь всю жизнь задачи решать?

---------

В идеале — да

НО!

Есть способ строить более мощные нейроны, которые время ломает не так быстро

Тут тебе поможет осознанность

Да-да, если ты не просто решаешь задачки, а:

- решаешь их по одному паттерну

- стараешься сокращать число паттернов до минимума (делая правила универсальными и простыми)

- пишешь код каждого паттерна в едином стиле, чтобы они были похожи

---------

То внезапно объём информации сокращается, и мозгу проще выстраивать нейросвязи

Более того, так как паттернов мало, ты регулярно их повторяешь и закрепляешь ещё сильнее

Именно такие паттерны и такой майндсет я выстраиваю для ребят в нашем сообществе algocode.io

За счёт них получается серьёзный буст в продуктивности и экономии времени

👍 Бахни лойс, если зашло. Тогда продолжу эту тему

И

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

Даже 50 верно решенных задач уже могут принести оффер в тот же Яндекс

Это было кайфно)

Пару часов назад закончился стрим, где с ребятами из сообщества algocode.io обсуждали, как получить жирный оффер в Авито

Хочу поделиться с вами основными идеями, которые помогут выйти на новый уровень офферов (в том числе и в Авито)

Пожалуй, это больше актуально для middle+ при переходе в senior

НО

Сам факт того, что так можно делать, точно будет полезен!

------------

Во-первых, про особенности компании:

1) Авито — до мозга костей продуктовая компания, а значит, не избежать вопросов:

Важнее бизнес или клиенты?

А почему? Аргументируй!

2) Авито — BigTech, в котором куча стандартов, и к каждому грейду есть свои требования

https://github.com/avito-tech/playbook/blob/master/developer-profile.md

И для каждого грейда свои требования в:

- Agile Mindset
- Инженерная культура
- Экспертность
- Ответственность за результат
- Коммуникация

И ещё 2 :)

3) Fit-собес в Авито (финал) — сложнее, чем техническая секция, и именно там определяется твой грейд

Благодаря таким вопросам:

- Какую самую сложную техническую задачу решал?

- А как вообще решаешь daily-задачки?

...

------------

В общем, без подготовки может быть тяжко на финале

Поэтому с ребятами разобрали:

- Как рассказывать про свой опыт с примерами

- Какие есть способы выделиться среди кандидатов +2 примерчика

- Что ценят в Авито и как это монетизировать

В общем, прошлись основательно

Аж 2 часа получилось 😂

------------

Очень советую глянуть:

- Playbook:
https://github.com/avito-tech/playbook/blob/master/developer-profile.md

- Манифест:
https://manifesto.avito.com/

Там много полезного

В общем, ресерч компании и ее документов топовая тема

Ведь высокий грейд - это всегда про доверие. И если вы приходите готовыми, то компания готова доверить вам и высокий грейд и ЗП

------------

Фух, ну всё, я погнал пилить дальше qsort — вот анимации делаю для вас :)

Ролик про сортировки будет бомбезным, так что с тебя 🌭

Получи год+ премиума на algocode.io бесплатно

Будет актуально для тех, кто имеет хорошую экспертизу в Go и кайфует от решения задач (в формате собесов)

Что от нас:

📌 С кайфом накинем тебе год+ премиума

📌Актуальные задачки прямо с собесов

📌 Сильная команда — проведём ревью с пристрастием к твоим решениям и дадим точки роста

📌 Менторинг (по карьере/технике)

P.S. если ты в МСК, можем сгонять в кальянную/рестик — просто вживую посидеть, поболтать

Что с тебя:

🎯 Кайфовать от написания кода на Go

🎯 Иметь успешный опыт прохождения собесов

🎯 Опыт в Go (1 год+)

Что нужно будет делать:

- По сути решать задачки с собесов

Если интересно — пиши мне в ЛС: @fatinmaks (будет круто, если сразу резюмешку скинешь в первом сообщении)

P.S. ищем не одного человека, а нескольких (сейчас у нас 3 человека в команде — все работают на Go с суммарным опытом от 4 лет)

Если сработаемся, то без проблем поможем устроится в компанию, которая тебе интересна + дадим рефералку.

P.S. если сомневаешься - пиши просто в ЛС, а там разберемся :)

А можно ли подключать библиотеку XYZ на алго-собесе?

Бывает так, что видишь решение, но берёт сомнение — говорить ли вслух...

Например, видишь решение через кучу (heap)

Но не помнишь, как она работает внутри...

Да и реализовать не помнишь, как с нуля...

Да и даже библиотеку не помнишь, в которой она подключается...

Что делать?

Во-первых, взять смузи на КОКОСОВОМ МОЛОКЕ и расслабиться

-------------

Я провёл суммарно 100+ собесов и как интервьюер прекрасно понимаю, когда человек забыл библиотеку, но понимает, что ему нужно

Так что тут ничего страшного

Просто можешь загуглить и подключить

-------------

НО ТЕБЕ МОГУТ ОТКАЗАТЬ

Тут есть несколько причин:

1) Задача решается оптимально вообще другим способом

2) Задача подразумевает, что ты сам реализуешь

3) Интервьюер оторвался от земли — тут бог ему судья, а тебе советую погуглить просто

-------------

Что если "Задача решается оптимально вообще другим способом"

Тут обычно прозвучит: "а давай попробуем без кучи", "а может нам и не нужна эта библиотека" и т. д.

Лучше довериться интервьюеру, как штурману в самолёте —
он уже видит маршрут сверху и знает, куда вывести разговор

-------------

Что если "Задача подразумевает, что ты сам реализуешь"

Ну ты просто попал в 1% вероятности, и вот почему:

Яндекс, Авито, Озон да и в целом BigTech отказываются от реализации структур данных и больше стараются проверить, КАК ТЫ ИМИ ПОЛЬЗУЕШЬСЯ

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

Но чаще всего кандидаты просто решают не тем способом, поэтому им нужна либа

-------------

Частый вопрос: "Реализовывать ли мне самому сортировку?"

Реализовать сортировку нужно только если это count sort или в задаче написано "Реализуй сортировку"

В ДРУГИХ СЛУЧАЯХ НЕ МУДРИ! Просто используй встроенную сортировку

-------------

Итог

- чаще всего либы не нужны, а нужен другой вариант решения
- если либа нужна, то тебе дадут погуглить и найти её
- для сортировок (кроме count sort) можно использовать встроенную либу

Ну и хот-дог бахни, по-братски, если зашло 🌭

И тут интервьюер такой: «О, такого я ещё не слышал, прикольно» 🤔

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

Расскажу про пару таких моментов

1) Предаллокация

Я пишу на Go, и там можно заранее выделить память под элементы в хеш-таблице.

Если просят реализовать кеш (а это очень частый кейс), то круто сразу зааллоцировать, скажем, 32, 64 или 128 элементов.

Да, константа «с потолка».
Но зато это помогает избежать переаллокаций и ускоряет работу программы.

На первый взгляд — фигня.

Но когда ты невзначай вкидываешь фразу:

«Кстати, можем подумать о предаллокации памяти под интенсивную запись/удаления» — интервьюер оживляется, потому что это редкость.

Пару раз даже начинал активнее помогать :)

2) Арена памяти

Тут уже привет из C++.

Извините, GC-шники, но память нужно уважать 😎

Вместо того, чтобы бесконечно плодить аллокации — можно использовать арену: заранее выделенный блок, из которого раздаём память.

P.S. про него подробнее расскажу в ролике про сортировки - скоро планирую выпустить на YouTube

Будем там merge sort за счет арены памяти оптимизировать

Да, да, даже Python c его GC будет такое полезно

---

Мораль простая: не игнорь базовые оптимизации.

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

А это запоминается и дает тебе конкурентное преимущество!

Ну и бахни 🌭

Что реально спрашивают в Яндексе

В общем, недавно мне сказали, что сильно не хватает отзывов на сообщество algocode.io и его кейсы.

Делюсь кейсами, где ребята писали, КАКИЕ ЗАДАЧИ ИМ ДАВАЛИ.

Просто приходили в личку или чат, а я их собрал.

В общем, получились и отзывы, и полезный контент.

Кейс 1

Собесился вчера, решил две задачи, интервьюер похвалил.

Первая: массив и число — найти кол-во подмассивов, сумма элементов которых меньше этого числа, и кол-во нулей — не больше 1.

Вторая — на окно.

Кстати, курс очень помог, я как раз окна повторял перед собесом — помогло очень.

Кейс 2

На собесе попалась задача на возрастающую последовательность (https://algocode.io/courses/algo-big-tech/problem/longest-continuous-increasing-subsequence) , но с изюминкой: нужно найти строго возрастающую или строго убывающую и вернуть индексы, а не длину массива.

Спустя 5 минут затупа на том, как объединить 2 задачи, просто прошёлся по массиву дважды, а индекс вернул как (текущий - maxLength).

Огромное спасибо алгокоду за бинжвотчинг задач перед собесом)

Лучший материал для подготовки, который мне попадался!

Кейс 3

Сходил на собес на ML-инженера в Яндекс, на первом этапе была лёгкая алгоритмическая, что-то типа этой — https://algocode.io/courses/algo-big-tech/problem/intersection-of-sorted-arrays, но надо вернуть не пересечение, а то, что есть в первом, но нет во втором.

UPD: вот эта — 1 в 1 https://algocode.io/courses/algo-big-tech/problem/find-one-sided-difference

----

В общем, курс по алго-собесу в Яндекс удался