Если вы предпочитаете следить за моим видео на YouTube, вы можете посмотреть его здесь:
Структуры данных используются для хранения информации в нашем коде. Мы используем разные структуры данных, чтобы мы могли добавлять, получать доступ и удалять данные наиболее эффективными и применимыми способами решения наших проблем. Во время собеседований выбор правильной структуры данных может позволить вам уменьшить временную сложность вашего решения, что очень ценится компаниями. Я знаю, что не могу оптимизировать некоторые вопросы на собеседовании только потому, что использовал неправильную структуру данных. Поэтому сегодня мы рассмотрим структуры данных, которые необходимо знать для собеседований по кодированию.
Если этот пост полезен, подумайте о том, чтобы подписаться на мой канал YouTube или подписаться на меня в среде, чтобы получить больше подобного контента! Если вы ищете хороший ресурс для изучения этих структур данных, я рекомендую взять копию Cracking the Coding Interview, в которой все это и более подробно рассматриваются! Также, если вы еще этого не сделали, ознакомьтесь с моей последней статьей о Алгоритмах, которые необходимо знать для собеседований!
Отказ от ответственности: этот пост создан на основе моего опыта поиска стажировок и должностей начального уровня (новых выпускников). В любой момент, если я заявляю, что вам нужно знать структуру данных, это означает, что вы должны понимать причины ее использования, временную сложность вставки, поиска и удаления элементов, компромиссы между ними и другими, а также знать, как реализовать это на языке. на ваш выбор. Если я упоминаю Big-O в любом месте статьи, я имею в виду промышленное использование этого термина (в академических кругах он эквивалентен Big-Theta). Кроме того, ссылка на Cracking the Coding Interview on Amazon является партнерской ссылкой, и я получу комиссию, если вы купите что-либо на Amazon по моей ссылке. Теперь, когда у нас это есть, давайте перейдем к списку!
1. Массив
Массивы - это базовая структура данных, которая обычно встроена в большинство языков. Они важны по двум основным причинам. Во-первых, массивы часто являются параметрами ваших вопросов по кодированию на собеседовании. Таким образом, их четкое понимание обеспечит вам успех на собеседовании. Во-вторых, вы можете реализовать большинство других структур данных с помощью массива, поэтому вы не сможете понять, сколько других структур данных реализовано, не имея фундаментального понимания массивов.
2. Связанный список
Связанные списки похожи на массивы в том, что они распространены в интервью и могут использоваться для реализации некоторых других структур данных. Для этого я настоятельно рекомендую понять, как это реализовать, а также добавить методы для добавления, поиска и удаления значений из списка. У меня были интервью, в которых меня просили создать связанный список с нуля, поэтому я знаю, что он может появиться в ваших интервью!
3. Стек и очередь
Стек и очереди - это противоположные структуры данных. Каждый из них может быть реализован с помощью массива, но чаще всего реализуется с помощью связанного списка. Стек представляет собой структуру данных Last In, First Out (LIFO), что означает, что последний элемент, который вы вставляете, выходит первым. Думайте об этом, как будто вы строите башню из лего. Вы строите башню из отдельных блоков, и когда вы хотите ее снести, вы снимаете блоки сверху, пока не удалите их все.
С другой стороны, очередь представляет собой структуру данных «первым пришел - первым ушел» (FIFO), что означает, что первый элемент, который вы вставляете, выходит первым. Вы можете думать об этом как о очереди в продуктовом магазине, где первый человек в очереди - это первый человек, который подходит к кассе. Знание этих различий позволяет вам выбрать, какой из них использовать на собеседовании.
4. Хеш-таблица
Хеш-таблицы реализованы с помощью массива и хеш-функции. Хеш-функция принимает элемент, который вы хотите поместить в хеш-таблицу, и выдает индекс в массиве, чтобы поместить этот элемент. Самое замечательное в хэш-таблицах заключается в том, что они амортизируют временную сложность (не знаете, что это значит? У меня есть определение ниже!) - O (1) для вставки, поиска и удаления. Таким образом, вы можете подумать, что мы нашли идеальную структуру данных, но у использования хеш-таблицы есть некоторые недостатки.
Во-первых, в них отсутствует какая-либо структура или организация, поэтому, если вы хотите сделать что-то вроде сортировки элементов или узнать порядок, в котором они были вставлены, хеш-таблицы этого не предлагают. Во-вторых, вам нужен массив большего размера, чем количество элементов в хеш-таблице. Это связано с тем, что если вы поместите новый элемент через свою хеш-функцию, и она выдаст индекс в вашем массиве, где у вас уже есть другой элемент, вы получите коллизию. Столкновения могут уменьшить вашу временную сложность, поэтому мы стремимся минимизировать количество столкновений, имея массив большего размера, чем количество элементов в таблице. Это означает, что если вы ограничены в пространстве, хеш-таблица может быть не лучшим вариантом.
Сложность с амортизированным временем заключается в том, что в большинстве случаев мы достигаем определенной временной сложности, но в редких случаях нам приходится выполнять более дорогостоящую операцию. К счастью, эта операция выполняется так редко, что наша средняя временная сложность ниже. Итак, для хэш-таблиц мы говорим, что это амортизированная временная сложность O (1), потому что мы знаем, что хеш-коллизии очень редки и в большинстве случаев нам потребуется O (1) времени для выполнения всех трех операций.
5. Деревья и графики
Деревья и графы построены на идее наличия узлов со значениями, а каждый узел имеет ссылки на соседние узлы. Я рекомендую начать с понимания деревьев с ознакомления с двоичными деревьями поиска, n-арными деревьями и попытками. С деревьями двоичного поиска или BST знайте самобалансирующийся BST. Некоторые общие включают деревья AVL и красно-черные деревья. Освоив деревья, воспользуйтесь этими знаниями и узнайте больше о графах, потому что они очень часто встречаются в более сложных вопросах собеседования.
Надеюсь, этот рассказ был для вас информативным! Пожалуйста, поделитесь им с другом, который, по вашему мнению, тоже может извлечь из этого пользу! Если вам понравился пост / видео, не стесняйтесь оставить аплодисменты / лайк и подписаться / подписаться на мой канал и аккаунт YouTube, чтобы получать больше подобного контента. Кроме того, подписывайтесь на меня в Twitter, чтобы получать обновления о том, когда я публикую новый контент. Если у вас есть другие предложения, не стесняйтесь делиться ими в комментариях, чтобы читатели могли извлечь максимум из этой истории! Кроме того, если вы еще этого не сделали, не забудьте взять копию Cracking the Coding Interview, потому что это действительно один из лучших ресурсов для изучения структур данных, алгоритмов и многого другого, чтобы подготовиться к собеседованию по кодированию!
