Техники устранения коллизий в разных языках программирования

Разница между кодером и инженером — в понимании "базы". Для кодера многое в работе компьютера — магия. Какие-то гномы крутят колесики в комьютере и наш код чудесным образом выполняется. В этом канале мы не приветствуем этот путь.

Computer Sience — это масштабная и глубокая наука. Она объясняет нам как работают привычные инструменты. Чем шире и глубже кругозор, тем лучше и крепче знания для решения рабочих задач. Даже вчера, созваниваясь со своим менти, он рассказал, что изучив работу управления памятью в Rust'е он лучше стал понимать как работает память в Swift'е.

Вдохновившись этим я решил собрать разные подходы решения одних проблем из разных языков. Начнем с решения коллизий:

Для нас хэштаблицы это магическое место, куда можно складывать элементы и брать оттуда за единицу времени. Есть некая хэш функция, которая вычисляет номер ячейки, но бывает так, что для нескольких разных объектов хэш функция вернет одно и тоже число. Если у вас 100 попугаев и 80 клеток, значит в какой-то клетке будет несколько попугаев. Это и называется коллизия.

🔗 Separate chaining

В данном подходе используется вместо одной ячейки используется двухсвязанный список. Соотвественно когда добавляется элемент, высчитывается номер ячейки, находится соответствующий список и добавляется в конец объект. Такой подход используется во многих языках программирования, в том числе в Java, Go, C++.

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

Посчитает ассимптотику по времени.
🟣Поиск элемента: в среднем O(1), в худшем случае O(N)
🟣Добавление элемента: в среднем O(1), в худшем случае O(N)
🟣Удаление элемента: в среднем O(1), в худшем случае O(N)

В Java есть оптимизация, если список разрастается и становится больше определенного количество элементов, то список превращается в сбалансированное двоичное дерево. Соотвественно сложность уменьшается до O(log N)

📂 Open addressing

Второй подход называется открытая адресация. Подход предполагает, что количество элементов для вставки не больше, чем количество ячеек в таблице. Если при вставке элемента оказывается, что ячейка уже занята, то смотрим на ячейку +1, если свободна то вставляем туда, иначе проверяем +2, +3 и так далее. Есть мини оптимизации, позволяющие не линейно прыгать по ячейкам в поисках свободного слота, а квадратично.

Стоит отметить, что удаление здесь это просто флажок (tombstone), означающий что ячейка свободна. Такой хак позволяет продолжать прыгать по ячейкам при поиске элемента, чтобы не остановиться раньше времени.

Сложность по времени.
🔘Поиск элемента: в среднем O(1), в худшем случае O(N)
🔘Добавление элемента: в среднем O(1), в худшем случае O(N)
🔘Удаление элемента: в среднем O(1), в худшем случае O(N)

Такой подход тоже находит свою реализация в языках программирования, таких как Python, Ruby, Rust.

💎 Большая статья про хэштаблицы

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

Я вычитал все платные статьи в медиуме, все хабр статьи, книги, доку и исходники, чтобы сделать эту статью. В ней мы разберемся:
🟣Что такое хэштаблицы
🟣Какие проблемы решает
🟣Что такое колизии и к чему приводит
🟣Как Swift решает проблему коллизий
🟣Создаем хештаблицу с нуля
🟣Разбор исходников
🟣Задачи для закрепления

Эта инфа точно пригодится вам в работе и на собеседованиях.

💎 Получить доступ можно на бусти и в телеграмм.

⚠️ Сегодня последний день скидок ⚠️

Большая подборка вопросов и задач на хештаблицы

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

В подборке:
🟣Какие структуры данных в Swift используют хештаблицы
🟣Как Swift помогает решить проблему коллизий: Hashable, Equatable, hasher, hashValue
🟣Решение задач в реальной практике и на собесах
🟣Как сделать кастомную хештаблицу

💎 Получить доступ можно на бусти и в телеграмм.

Сосредоточьтесь не на задаче, а на проблеме, стоящей за задачей

Мы продолжаем копать в сторону Software Engineer'инга.

Bruno Rocha из Spotify поднял популярную тему постановки задач. Как найти виноватого между инженером и продактом?

Многие неопытные или начинающие инженеры наивно думают, что каждая их задача должна быть идеально описана менеджером, тимлидом, старшим коллегой. А его роль только сделать так, как ему сказали.
Очевидно, что такие разработчики первые кандидаты на сокращения или на замену ИИ. Это критическая ошибка, которая никогда не позволит вырости до самостоятельного спеца высокого уровня.

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

Хороший инженер должен быть не просто кодером, но и консультантом, который подсветит неэффективные решения.

Новые форматы собесов System Design. Что не так с текущими собесами в снг?

Мы часто обсуждаем собесы в бигтехи и не только в чате. Спрашиваем у разрабов гугла, эпл, наших снг компаний. Сейчас жертвой стали популярные форматы system design'а и архитектуры на снг пространстве. В прошлом году их много кто ввел, отказываясь от теории и других задач, которые легко хакаются с чатгпт. Например, т-банк и альфа, вк, озон. Но в этом посте мы разберем почему текущий формат систем дизайна также легко хакается.

Сейчас многие процессы собесов выглядят так:
- созвон с рекрутером
- опциональный скрининг
- дают задачу на лайфкодинг, рефакторинг и проектирование
- финал

Прошел почти год и можно сказать об эффективности этого подхода. На мой взгляд (спойлер следующих интервью: не только на мой) в этой формуле много проблем:

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

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

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

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

🟣задач должно быть больше. У некоторых компаний всего 3-4 задачи в базе, которые легко опять же сливаются всякими паровозиками и разбираются рейдами буквально за пару недель. Добавьте в базу 10-15 задач

🟣минимализация повторов. В каждой задаче должно быть по 2-3 варианта для вариативности. Так сложнее зазубрить. Яндекс и FAANG'и также делает с алгоритмами. Вроде задача из литкода, но немного изменена. Это очень эффективная защита.

Мое же мнение такое: систем дизайн должен даваться также как раньше — только кандидатам на высокие грейды. Многие ушли от такой практики, потому что затянет процесс найма с поиском слотов для эксперта и отпугнет на дополнительные этапы. Но как я всегда говорю, что чем больше я смотрю на FAANG процессы, тем лучше понимаю их степень зрелости. Они просто не контрятся по эффективности и экономности.

Сливы им не страшны, где в базе лежит 1000 задач, которые рандомно даются. Если задача была замечена слитой, то ее резко заменяют. Не нужно много сил и энергии тратить на поддержку шаблонов, обучения инженеров и поиск специальных экспертов. Задачи а-ля литкод выполняют задачу найма лучше всего. Я уверен, что потихоньку мы тоже придем к таким собесам.

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

Подборка ред флагов от рекрутеров фаанга и не только

Продолжаем копаться в карьерных вопросах и искать инфу для повышения шансов для трудоустройства. В этом треде люди делятся неочевидными вещами, которые снизят ваши шансы получить оффер.

🔴Спам вопросами
🔴Непрофессиональные фото или странные эмейлы
🔴Спам резюме в разные компании не читая требования вакансии в слепой надежде "проскочить"
🔴постоянная смена ожидаемой зп
🔴Постоянно говорить "мы сделали", вместо "я сделал"
🔴Слишком много смен работы, которые не приводят к росту грейда.

Кстати, скоро для подписчиков бусти выйдет крутой материал на 2 часа с руководителем Яндекса. Все о собесах, красных флагах, резюме, алгоритмах, развитии, софтах и хардах. Один из полезнейших выпусков.

Ссылки:
- Recruiters: what are some non-obvious candidate red flags
- Candidate Red Flags: What Recruiters Should Watch Out For
- Ред-флаги в резюме ИТ-специалистов: топ ошибок глазами рекрутеров

💎 Продвинутый System Design: Logger

Логирование — одна из важных суперспособностей программиста. Более 50% задач у программиста — поиск багов и других дефектов.

Я люблю давать эту задачу, а также слышал ее дают на архитектурных секциях ВК, Яндекса и других. Это правда очень хорошая задача оценить глубину и ширину знаний кандидата.

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

В этой статье я к своему запроектированному решению также:
🟣дал код
🟣разобрал основные сущности
🟣дал комментарии
🟣Ожидаемые ответы на джуна, мидла, сеньора.

Такие статьи дают лучшую усваемость материала


💎 Получить доступ можно на бусти и в телеграмм.