Основной код интервью для карт и словарей

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

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

Терминология

Терминология вокруг карты смешанный.

Python и C# предпочитают использовать «словарь». Там словарь представляет собой конкретную карту 1:1, где ключ сопоставляется с одним значением. PHP использует термин «ассоциативные массивы». C++ использует «map», а также имеет «unordered_map». В Java «HashMap» является обычной реализацией их интерфейса «Map».

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

Ссылка

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

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

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

Создайте карту: Используйте наиболее распространенный или общий для языка. Для статически типизированного языка вам необходимо указать тип ключа и значения.
Добавьте элемент с ключом и значением: Основной способ получить пару ключ-значение на карте.
Проверить, существует ли элемент по ключу: Проверка существования — основная причина, по которой мы используем карту.
Получить элемент по ключу: Это сильно различается между языками, и окружающий код обычно меняется.
Получить длину карты: Синтаксис отличается практически во всех языках.
Языковая идиома для «проверить и получить предмет» с карты: Эта комбинация распространена, и во многих языках есть особый способ объединения двух шагов.

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

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

Мы можем захотеть сделать что-то для всех элементов карты. Это может использовать механизм цикла языка, или они могут быть специальными функциями for-each на самой карте.

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

Мы не всегда хотим работать с полной картой или можем захотеть изолировать определенные элементы.

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

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

Создайте мультикарту: Если ваш язык не поддерживает его, узнайте, как использовать массив внутри карты нормалей.
Добавить элемент по ключу: Если ключ уже существует, вы получите два значения, связанные с одним и тем же ключом.
Повторите элементы, соответствующие ключу: Для одного ключа может быть несколько значений.
Удалить элемент, соответствующий ключу: Удалите один элемент, соответствующий ключу, но оставив дополнительные значения. Это может привести к удалению первого или последнего значения или потребовать дополнительного сопоставления значения.
Замените все элементы, соответствующие ключу: Убедитесь, что на мультикарте больше не осталось предметов с ключом.

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

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

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

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