Рубрика «структуры данных»

Мой опыт собеседования в Google [оффер на L5] - 1


Предупреждение: я не смогу привести в статье конкретные вопросы из-за подписанного соглашения о неразглашении (NDA).

Работая в лондонском офисе Facebook в команде Instagram*, я начал задумываться о возвращении в Индию. В ноябре 2022 года со мной связался рекрутер Google. Он сообщил об открытии в Бангалоре должности уровня L5 и спросил, интересно ли мне это.

Так как я уже раздумывал о переезде в Индию, то ранее собеседовался в Google, но мне предложили более низкую должность (L4), чем я хотел; потом я устроился в META* на уровень E5.

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

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

На этот раз в процессе подготовки возникла уникальная для меня сложность — счастливое пополнение в моей семье, дочка. За моё внимание боролись подгузники и кодинг, было очень сложно выделить время на сосредоточенную подготовку! У меня было примерно 25-30 дней на освоение и искусства ухода за ребёнком, и прохождения собеседования.Читать полностью »

Собственный строковый тип на Rust - 1


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

pub enum Expr<'src> {
  Int(u32)
  Ident(&'src str),
  // ...
}

Когда мы парсим идентификатор, то вместо копирования его названия в новую String мы заимствуем его из входной исходной строки. Это позволяет избежать дополнительных распределений, дополнительного копирования и экономит слово на представлении данных. Компиляторы могут быть очень требовательны к памяти, поэтому стоит выбирать краткое представление.
Читать полностью »

Выбор структур данных для самописного текстового редактора - 1


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

Ресурсы

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

  • Build Your Own Text Editor — наверно, самый фундаментальный пост о создании текстового редактора с нуля, который я видел. Это превосходный туториал на случай, если вы хотите начать писать собственный текстовый редактор. Стоит заметить, что в редакторе из этого туториала в качестве внутренней структуры для текста используется, по сути, вектор строк.
  • Text Editor: Data Structures — отличный обзор множества структур данных, которые можно использовать при реализации текстового редактора. (Спойлер: как минимум одна из них будет рассмотрена в моём посте)
  • Плейлист Ded (Text Editor) на YouTube — это потрясающая серия, в которой @tscoding фиксирует процесс создания с нуля текстового редактора. Эти видео стали для меня источником вдохновения.

Зачем?

Если в сети есть так много хороших ресурсов о создании собственного текстового редактора (не говоря уже о том, что уже существует множество феноменальных текстовых редакторов), то зачем я это пишу? На то есть несколько причин:

  1. Я хотел заняться проектом, непохожим ни на один свой прошлый.
  2. Я хотел создать инструмент, которым смогу пользоваться.
  3. Мне всегда хотелось глубже разобраться с созданием собственных структур данных.

Читать полностью »

6 Python декораторов, которые значительно упростят ваш код - 1

"Простое лучше сложного".

Лучшая функция Python, которая применяет эту философию из "дзен Python", - это декоратор.

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

Читать полностью »

Меня зовут Абай Баймуканов, я – разработчик-алгоритмист. Уже несколько лет увлекаюсь олимпиадными программированием, поэтому в этой статье хотел бы поделиться своим видением по этому поводу.

Читать полностью »

В данной статье для реализации алгоритма будут рассмотрены:

  1. Система хранения графа на основе List<>

  2. Сортировка рёбер графа по весу

  3. Система непересекающихся множеств


Алгоритм Краскала необходим для нахождения минимального остовного дерева графа.

О чём речь?

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

Читать полностью »

Что такое Big O нотация?

Обозначение Big O нотация (или просто Big O) — это способ оценки относительной производительности структуры данных или алгоритма, обычно по двум осям: времени и пространству.

Доминирующие операции

Способ, которым мы определяем Big O алгоритмов, заключается в том, чтобы посмотреть на худшую производительность в его доминирующих операциях.

Постоянное время - O(1)

func constantTime(_ n: Int) -> Int {
    let result = n * n
    return result
}

Читать полностью »

Довольно долгое время я воевал с красно-черным деревом (далее - кчд). Вся информация, которую я находил, была в духе "листья и корень дерева всегда черные, ПОТОМУ ЧТО", "топ 5 свойств красно-черного дерева" или "3 случая при балансировке и 12 случаев при удалении ноды". Такой расклад меня не устраивал.

Мне не хотелось заучивать свойства дерева, псевдокод и варианты балансировки, я хотел знать: почему. Каким образом цвета помогают при балансировке? Почему у красной ноды не может быть красного потомка? Почему глубину дерева измеряют "черной высотой"?

Ответы на эти вопросы я получил только тогда, когда мне дали ссылку на лекцию про два-три дерево,Читать полностью »

Про префиксное дерево (Trie) написано немало, в том числе и на Хабре. Вот пример, как оно может выглядеть:

Immutable Trie: найди то, не знаю что, но быстро, и не мусори - 1

И даже реализаций в коде, в том числе на JavaScript, для него существует немало — от «каноничной» by John Resig и разных оптимизированных версий до серии модулей в NPM.

Зачем же нам понадобилось использовать его для сервиса по сбору и анализу планов PostgreSQL, да еще и «велосипедить» какую-то новую реализацию?..
Читать полностью »

Пользуетесь ли вы структурами данных и алгоритмами в повседневной работе? Я обратил внимание на то, что всё больше и больше людей считает алгоритмы чем-то таким, чем, без особой связи с реальностью, технические компании, лишь по собственной прихоти, интересуются на собеседованиях. Многие жалуются на то, что задачи на алгоритмы — это нечто из области теории, имеющей слабое отношение к настоящей работе. Такой взгляд на вещи, определённо, распространился после того, как Макс Хауэлл, автор Homebrew, опубликовал твит о том, что произошло с ним на собеседовании в Google:

Google: 90% наших инженеров пользуются программой, которую вы написали (Homebrew), но вы не можете инвертировать бинарное дерево на доске, поэтому — прощайте.

Хотя и у меня никогда не возникало нужды в инверсии бинарного дерева, я сталкивался с примерами реального использования структур данных и алгоритмов в повседневной работе, когда трудился в Skype/Microsoft, Skyscanner и Uber. Сюда входило написание кода и принятие решений, основанное на особенностях структур данных и алгоритмов. Но соответствующие знания я, по большей части, использовал для того чтобы понять то, как созданы некие системы, и то, почему они созданы именно так. Знание соответствующих концепций упрощает понимание архитектуры и реализации систем, в которых эти концепции используются.

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

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


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js