coding interview university

Интервью по программированию Университет

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

Я учился по 8-12 часов в день в течение нескольких месяцев. Это моя история: Почему я 8 месяцев учился на очном отделении для собеседования в Google

Обратите внимание: вам не нужно будет учиться так много, как мне. Я потратил много времени на вещи, которые мне не нужно было знать. Дополнительная информация об этом ниже. Я помогу вам добраться туда, не теряя вашего драгоценного времени.

Перечисленные здесь пункты хорошо подготовят вас к техническому собеседованию практически в любой компании-разработчике программного обеспечения, включая гигантов: Amazon, Facebook, Google и Microsoft.

Удачи вам!

Переводы:

• Бахаса Индонезия

• болгарский

• испанский

• немецкий

• Японский (日本語)

• Маратхи

• Польский

• Португальский Бразилейро

• Русский

• Tiếng Việt - вьетнамский

• Урду – اردو

• Узбекский

• বাংলা - Бангла

• ខ្មែរ - Кхмерский

• 简体中文

• 繁體中文

Переводы в процессе:

• африкаанс

• арабский

• Французский

• греческий

• итальянский

• Корейский (한국어)

• малаялам

• Персидский - Фарси

• телугу

• тайский

• турецкий

• Украинская

• עברית

• हिन्दी

---

Станьте спонсором и поддержите Университет Coding Interview!

---

Что это такое?

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

Необходимый:

• Небольшой опыт программирования (переменные, циклы, методы/функции и т. д.).

• Терпение

• Время

Обратите внимание, что это учебный план по разработке программного обеспечения , а не по интерфейсной разработке или комплексной разработке. Есть действительно супер-дорожные карты и курсовые работы для этих карьерных путей в других местах (см. https://roadmap.sh/ для получения дополнительной информации).

На университетской программе по компьютерным наукам можно многому научиться, но знания только около 75% достаточно для собеседования, и именно об этом я и рассказываю здесь. Для полной программы самообучения по информатике ресурсы моего учебного плана были включены в дорожную карту компьютерных наук Камрана Ахмеда: https://roadmap.sh/computer-science.

---

Оглавление

План исследования

• Что это такое?

• Зачем его использовать?

• Как его использовать

• Не думай, что ты недостаточно умен

• Примечание о видеоресурсах

• Выберите язык программирования

• Книги по структурам данных и алгоритмам

• Книги для подготовки к собеседованию

• Не делай моих ошибок

• То, что вы не увидите покрытым

• Ежедневный план

• Практика вопросов по кодированию

• Проблемы с кодированием

Темы обучения

• Алгоритмическая сложность / Big-O / Асимптотический анализ

• Структуры данных

• Массивы

• Связанные списки

• Куча

• Очередь

• Хэш-таблица

• Больше знаний

• Бинарный поиск

• Побитовые операции

• Деревья

• Деревья – Введение

• Двоичные деревья поиска: BST

• Куча/Очередь приоритетов/Двоичная куча

• сбалансированные деревья поиска (общая концепция, а не детали)

• обходы: предварительный заказ, обратный порядок, обратный порядок, BFS, DFS

• Сортировка

• выбор

• вставка

• пирамидальная сортировка

• быстрая сортировка

• сортировка слиянием

• Графики

• направленный

• ненаправленный

• матрица смежности

• список смежности

• обходы: BFS, DFS

• Еще больше знаний

• Рекурсия

• Динамическое программирование

• Шаблоны проектирования

• Комбинаторика (n выбирает k) и вероятность

• NP, NP-полные и аппроксимационные алгоритмы

• Как компьютеры обрабатывают программу

• Тайники

• Процессы и потоки

• Тестирование

• Поиск строк и манипуляции

• Пытается

• Числа с плавающей запятой

• Юникод

• Порядок байтов

• сеть

• Окончательный обзор

Получение работы

• Обновите свое резюме

• Найти работу

• Процесс собеседования и общая подготовка к собеседованию

• Подумайте об этом, когда придет собеседование

• Есть вопросы к интервьюеру

• Как только вы получите работу

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

Дополнительные дополнительные темы и ресурсы

• Дополнительные книги

• Проектирование системы, масштабируемость, обработка данных (если у вас опыт работы от 4 лет)

• Дополнительное обучение

• Деревья АВЛ

• Распространение деревьев

• Красные/черные деревья

• 2-3 дерева поиска

• 2-3-4 дерева (или 2-4 дерева)

• N-арные (K-арные, M-арные) деревья

• B-деревья

• Составители

• Emacs и vi(m)

• Инструменты командной строки Unix

• Теория информации

• Четность и код Хэмминга

• Энтропия

• Криптография

• Сжатие

• Компьютерная безопасность

• Сбор мусора

• Параллельное программирование

• Системы обмена сообщениями, сериализации и массового обслуживания

• А*

• Быстрое преобразование Фурье

• Фильтр Блума

• Гиперлоглог

• Хэширование с учетом локальности

• Ван Эмде Боас Деревья

• Дополненные структуры данных

• Сбалансированные деревья поиска

• кД Деревья

• Пропустить списки

• Сетевые потоки

• Непересекающиеся множества и поиск объединений

• Математика для быстрой обработки

• Треп

• Линейное программирование

• Геометрия, Выпуклая оболочка

• Дискретная математика

• Дополнительная информация по некоторым предметам

• Видео серии

• Курсы информатики

• Статьи

---

Зачем его использовать?

Если вы хотите работать инженером-программистом в крупной компании, это то, что вам нужно знать.

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

Когда я начал этот проект, я не знал стека из кучи, ничего не знал о Big-O, ничего о деревьях или о том, как перемещаться по графу. Если бы мне пришлось написать алгоритм сортировки, могу сказать, что это было бы ужасно. Каждая структура данных, которую я когда-либо использовал, была встроена в язык, и я вообще не знал, как они работают внутри. Мне никогда не приходилось управлять памятью, если только запущенный мной процесс не выдавал ошибку «недостаточно памяти», и тогда мне приходилось искать обходной путь. В своей жизни я использовал несколько многомерных массивов и тысячи ассоциативных массивов, но никогда не создавал структуры данных с нуля.

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

⬆ наверх

Как его использовать

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

Я использую специальную версию уценки GitHub, включая списки задач для отслеживания прогресса.

• Подробнее об уценке с использованием GitHub

Если вы не хотите использовать git

На этой странице нажмите кнопку «Код» вверху, затем нажмите «Загрузить ZIP». Разархивируйте файл, и вы сможете работать с текстовыми файлами.

Если вы откроете редактор кода, который понимает уценку, вы увидите все в хорошем формате.

Если вам комфортно с git

Создайте новую ветку, чтобы вы могли проверять такие элементы, просто поставьте x в скобки: [x]

1. Создайте форк репозитория GitHub: https://github.com/jwasham/coding-interview-university нажав кнопку «Разветвить».

2. Клонируйте в свой локальный репозиторий:

    git clone https://github.com/<ВАШЕ_ИМЯ_ПОЛЬЗОВАТЕЛЯ_GITHUB>/coding-interview-university.gitcd coding-interview-university
   git удаленно добавить восходящий поток https://github.com/jwasham/coding-interview-university.git
   git удаленный set-url --push upstream DISABLE # чтобы вы не возвращали свой личный прогресс обратно в исходный репозиторий

3. Отметьте все поля значком X после внесения изменений:

    git commit -am "Отмеченный личный прогресс" git pull upstream main # обновляйте свою вилку с изменениями из исходного репозитория push # просто отправляйте ее в свою вилку

⬆ наверх

Не думай, что ты недостаточно умен

• Успешные инженеры-программисты умны, но многие из них не уверены в том, что они недостаточно умны.

• Следующие видео могут помочь вам преодолеть эту неуверенность:

• Миф о гениальном программисте

• Опасно идти в одиночку: борьба с невидимыми монстрами в сфере технологий

⬆ вернуться наверх

Примечание о видеоресурсах

Некоторые видео доступны только после регистрации на курсах Coursera или EdX. Это так называемые МООК. Иногда занятия не проводятся, поэтому вам приходится ждать пару месяцев, и у вас нет доступа.

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

⬆ вернуться наверх

Выберите язык программирования

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

Желательно, чтобы язык был одинаковым, чтобы вам нужно было владеть только одним.

Для этого плана обучения

Когда я составлял план обучения, большую его часть я использовал 2 языка: C и Python.

• C: Очень низкий уровень. Позволяет вам иметь дело с указателями и выделением/освобождением памяти, поэтому вы чувствуете структуры данных и алгоритмы в своих костях. В языках более высокого уровня, таких как Python или Java, они скрыты от вас. В повседневной работе это потрясающе, но когда вы изучаете, как строятся эти низкоуровневые структуры данных, приятно чувствовать себя ближе к металлу.

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

• Вам не нужно углубляться в книгу (или даже дочитывать ее). Просто доберитесь до того места, где вам удобно читать и писать на C.

• С есть везде. Вы увидите примеры в книгах, лекциях, видеороликах повсюду , пока учитесь.

• Язык программирования C, 2-е издание

• Python: современный и очень выразительный. Я выучил его, потому что он очень полезен и позволяет мне писать меньше кода на собеседовании.

Это мое предпочтение. Вы, конечно, делаете то, что вам нравится.

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

• упражнения

• Кодовые войны

• ХакерЗемля

• Темы масштабирования (Java, C++)

• Проблемы сообщества Programiz PRO)

Для вашего собеседования по программированию

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

• С++

• Ява

• Питон

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

• JavaScript

• Руби

Вот статья, которую я написал о выборе языка для собеседования: «Выберите один язык для собеседования по программированию». Это оригинальная статья, на которой был основан мой пост: Выбор языка программирования для собеседований.

Вы должны очень хорошо владеть языком и быть хорошо осведомленным.

Подробнее о выборе:

• Выберите правильный язык для вашего собеседования по программированию

См. ресурсы по конкретным языкам здесь.

⬆ вернуться наверх

Книги по структурам данных и алгоритмам

Эта книга станет вашей основой для информатики.

Просто выберите один на том языке, который вам удобен. Вы будете много читать и кодировать.

С

• Алгоритмы на языке C, части 1–5 (пакет), 3-е издание

• Основы, структуры данных, сортировка, поиск и алгоритмы графов

Питон

• Структуры данных и алгоритмы в Python

• Гудрич, Тамассия, Гольдвассер

• Мне понравилась эта книга. Там было все и даже больше.

• Питонический код

• мой блестящий отчет о книге: https://startupnextdoor.com/book-report-data-structures-and-algorithms-in-python/

Ява

Ваш выбор:

• Гудрич, Тамассия, Гольдвассер

• Структуры данных и алгоритмы в Java

• Седжвик и Уэйн:

• Алгоритмы I

• Алгоритмы II

• Алгоритмы

• Бесплатный курс Coursera, охватывающий книгу (преподавают авторы!):

С++

Ваш выбор:

• Гудрич, Тамассия и Маунт

• Структуры данных и алгоритмы в C++, 2-е издание

• Седжвик и Уэйн

• Алгоритмы на C++, части 1–4: основы, структура данных, сортировка, поиск

• Алгоритмы в C++. Часть 5. Алгоритмы графов

⬆ вернуться наверх

Книги для подготовки к собеседованию

Вам не нужно покупать кучу всего этого. Честно говоря, «Cracking the Coding Interview», вероятно, достаточно, но я купил еще, чтобы попрактиковаться. Но я всегда делаю слишком много.

Я купил и то, и другое. Они дали мне много практики.

• Разоблачение собеседований по программированию: программирование на собеседовании, 4-е издание

• Ответы на C++ и Java

• Это хорошая разминка для собеседования по теме «Cracking the Coding Interview».

• Не так уж сложно. Большинство проблем могут быть проще, чем то, что вы увидите в интервью (судя по тому, что я читал)

• Интервью «Cracking the Coding», 6-е издание

• ответы на Java

Если у вас есть много дополнительного времени:

Выберите один:

• Элементы интервью по программированию (версия C++)

• Элементы собеседований по программированию на Python

• Элементы интервью по программированию (Java-версия) — Сопутствующий проект — Заглушка метода и тестовые примеры для каждой проблемы в книге

⬆ вернуться наверх

Не делай моих ошибок

Этот список рос в течение многих месяцев, и да, он вышел из-под контроля.

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

1. Вы всего этого не запомните

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

Пожалуйста, прочтите, чтобы не допустить моих ошибок:

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

2. Используйте карточки

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

Сделайте свой собственный бесплатно:

• Репозиторий сайта Flashcards

Я НЕ РЕКОМЕНДУЮ использовать свои карточки. Их слишком много, и большинство из них — пустяки, которые вам не нужны.

Но если ты не хочешь меня слушать, то вот:

• Моя база флеш-карточек (1200 карточек):

• Моя база флеш карточек (предельная - 1800 карточек):

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

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

Альтернативой моему сайту с карточками является Anki, который мне неоднократно рекомендовали. Он использует систему повторения, чтобы помочь вам запомнить. Он удобен для пользователя, доступен на всех платформах и имеет систему облачной синхронизации. Он стоит 25 долларов на iOS, но на других платформах бесплатен.

Моя база данных карточек в формате Anki: https://ankiweb.net/shared/info/25173560 (спасибо @xiewenya).

Некоторые учащиеся упомянули проблемы форматирования с пробелами, которые можно исправить, выполнив следующие действия: откройте колоду, отредактируйте карту, щелкните карты, выберите переключатель «Стиль» и добавьте элемент «white-space: pre;». к классу карты.

3. Задавайте вопросы на собеседовании по программированию во время обучения

ЭТО ОЧЕНЬ ВАЖНО.

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

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

Как только вы изучите тему и почувствуете себя комфортно с ней, например, связанные списки :

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

2. Задайте 2 или 3 вопроса относительно связанных списков.

3. Переходите к следующей теме обучения.

4. Позже вернитесь и решите еще 2 или 3 задачи со связанным списком.

5. Делайте это с каждой новой темой, которую вы изучаете.

Продолжайте решать задачи пока изучаете все эти вещи, а не после.

Вас нанимают не за знания, а за то, как вы их применяете.

Для этого существует множество ресурсов, перечисленных ниже. Продолжать идти.

4. Фокус

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

⬆ вернуться наверх

То, что вы не увидите скрытым

Это распространенные технологии, но они не являются частью данного плана исследования:

• Javascript

• HTML, CSS и другие интерфейсные технологии

• SQL

⬆ вернуться наверх

Ежедневный план

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

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

Вы можете увидеть мой код здесь:

• С

• С++

• Питон

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

⬆ вернуться наверх

Практика вопросов по кодированию

Why is this here? I'm not ready to interview.

Тогда вернитесь и прочитайте это.

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

• Распознавание проблем и где нужны правильные структуры данных и алгоритмы

• Сбор требований к задаче

• Расскажите о проблеме так же, как на собеседовании.

• Программирование на доске или бумаге, а не на компьютере

• Придумываем временную и пространственную сложность для ваших решений (см. Big-O ниже).

• Тестирование ваших решений

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

Пишите код на доске или бумаге, а не на компьютере. Протестируйте с некоторыми примерами входных данных. Затем введите его и проверьте на компьютере.

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

Практика вопросов по кодированию заключается не в запоминании ответов на проблемы программирования.

⬆ вернуться наверх

Проблемы с кодированием

Не забудьте здесь свои книги для собеседований по ключевому кодированию.

Решение проблем:

• Как найти решение

• Как проанализировать постановку задачи Topcoder

Видео с вопросами для собеседования по программированию:

• IDserve (88 видео)

• Тушар Рой (5 плейлистов)

• Супер для пошаговых решений проблем

• Ник Уайт — LeetCode Solutions (187 видео)

• Хорошие объяснения решения и кода.

• Вы можете посмотреть несколько за короткое время

• FisherCoder - Решения LeetCode

Площадки для испытаний/практик:

• ЛитКод

• Мой любимый сайт по проблемам кодирования. Это стоит денег на подписку на 1-2 месяца, которые вы, вероятно, будете готовить.

• См. видео Ника Уайта и FisherCoder выше для ознакомления с кодом.

• ХакерРанк

• ТопКодер

• Кодфорс

• Кодильность

• Гики для гиков

• АлгоЭксперт

• Созданный инженерами Google, это также отличный ресурс для оттачивания своих навыков.

• Проект Эйлера

• очень ориентирован на математику и не совсем подходит для собеседований по программированию

⬆ вернуться наверх

Давайте начнем

Ладно, хватит разговоров, давайте учиться!

Но не забывайте решать задачи по кодированию, описанные выше, пока учитесь!

Алгоритмическая сложность / Big-O / Асимптотический анализ

• Здесь нечего реализовывать, вы просто смотрите видео и делаете заметки! Ура!

• Здесь много видео. Просто смотрите достаточно, пока не поймете это. Вы всегда можете вернуться и просмотреть.

• Не волнуйтесь, если вы не понимаете всей математики, стоящей за этим.

• Вам просто нужно понять, как выразить сложность алгоритма в терминах Big-O.

• Harvard CS50 — Асимптотическая запись (видео)

• Big O Notations (общее краткое руководство) (видео)

• Big O Notation (а также Omega и Theta) — лучшее математическое объяснение (видео)

• Скиена (видео)

• Калифорнийский университет в Беркли Big O (видео)

• Амортизированный анализ (видео)

• TopCoder (включает рекуррентные соотношения и основную теорему):

• Вычислительная сложность: раздел 1

• Вычислительная сложность: раздел 2

• Шпаргалка

• [Обзор] Анализ алгоритмов (плейлист) за 18 минут (видео)

Ну, этого достаточно.

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

⬆ наверх

Структуры данных

• Массивы

• непрерывны в памяти, поэтому близость повышает производительность

• необходимое пространство = (емкость массива >= n) * размер элемента, но даже если 2n, все равно O(n)

• O(1) для добавления/удаления в конце (амортизируется при выделении большего пространства), индексации или обновления

• O(n) для вставки/удаления в другом месте

• Практикуйтесь в кодировании с использованием массивов и указателей, а также в математических вычислениях с указателями для перехода к индексу вместо использования индексации.

• Новый массив необработанных данных с выделенной памятью.

• size() - количество элементов

• емкость() — количество элементов, которые он может хранить

• is_empty()

• at(index) — возвращает элемент по заданному индексу, уничтожается, если индекс выходит за пределы

• толчок (пункт)

• Insert(index, item) — вставляет элемент по индексу, сдвигает значение этого индекса и конечные элементы вправо

• prepend(item) — можно использовать вставку выше по индексу 0

• pop() — удалить с конца, вернуть значение

• delete(index) — удалить элемент по индексу, сдвигая все конечные элементы влево

• Remove(item) — ищет значение и удаляет содержащий его индекс (даже если он находится в нескольких местах)

• find(item) — ищет значение и возвращает первый индекс с этим значением, -1, если не найден

• resize(new_capacity) // частная функция

• может выделить массив int под капотом, но не использовать его функции

• начните с 16 или, если стартовое число больше, используйте степень 2 — 16, 32, 64, 128

• когда вы достигнете емкости, измените размер в два раза

• при выталкивании предмета, если его размер составляет 1/4 емкости, измените размер до половины

• Массивы CS50 Гарвардского университета

• Массивы (видео)

• UC Berkeley CS61B — Линейные и многомерные массивы (видео) (Начало просмотра с 15 мин 32 с)

• Динамические массивы (видео)

• Зубчатые массивы (видео)

• О массивах:

• Реализуйте вектор (изменяемый массив с автоматическим изменением размера):

• Время

• Космос

• Связанные списки

• Описание (видео)

• Нет необходимости реализовывать

• size() — возвращает количество элементов данных в списке

• пустой() — bool возвращает true, если пусто

• value_at(index) — возвращает значение n-го элемента (начиная с 0 для первого)

• push_front(value) — добавляет элемент в начало списка.

• pop_front() — удалить передний элемент и вернуть его значение

• push_back(value) — добавляет элемент в конец

• pop_back() — удаляет конечный элемент и возвращает его значение

• front() — получить значение переднего элемента

• back() — получить значение конечного элемента

• Insert(index, value) — вставить значение по индексу, чтобы на текущий элемент по этому индексу указывал новый элемент по индексу.

• стереть(индекс) — удаляет узел по заданному индексу

• value_n_from_end(n) — возвращает значение узла на n-й позиции от конца списка

• verse() — переворачивает список

• Remove_value(value) — удаляет первый элемент в списке с этим значением.

• Указатели на указатели

• Основные связанные списки против массивов (видео)

• В реальном мире связанные списки против массивов (видео)

• Связанные списки CS50 Гарвардского университета — это развивает интуицию.

• Односвязные списки (видео)

• CS 61B — Связанные списки 1 (видео)

• CS 61B — Связанные списки 2 (видео)

• [Обзор] Связанные списки за 4 минуты (видео)

• Описание:

• Код C (видео) — не все видео, только части о структуре Node и распределении памяти.

• Связанный список против массивов:

• Почему следует избегать связанных списков (видео)

• Попался: вам нужны знания указателя на указатель: (когда вы передаете указатель функции, которая может изменить адрес, на который указывает этот указатель) Эта страница предназначена только для того, чтобы получить представление о ptr to ptr. Я не рекомендую этот стиль обхода списка. Читабельность и ремонтопригодность страдают из-за хитрости.

• Реализуйте (я сделал с указателем хвоста и без):

• Двусвязный список

• Куча

• Стеки (видео)

• [Обзор] Складывается за 3 минуты (видео)

• Не буду реализовывать. Реализация с использованием массива тривиальна.

• Очередь

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

• постановка в очередь: O(1) (амортизированный связанный список и массив [зондирование])

• удаление из очереди: O(1) (связный список и массив)

• пусто: O(1) (связанный список и массив)

• enqueue(value) — добавляет элемент в конце доступного хранилища.

• dequeue() — возвращает значение и удаляет последний добавленный элемент

• пустой()

• полный()

• enqueue(value) — добавляет значение в хвостовую позицию

• dequeue() — возвращает значение и удаляет последний добавленный элемент (спереди)

• пустой()

• Очередь (видео)

• Круговой буфер/FIFO

• [Обзор] Очереди за 3 минуты (видео)

• Реализуйте с использованием связанного списка с указателем хвоста:

• Реализуйте, используя массив фиксированного размера:

• Расходы:

• Хэш-таблица

• hash(k, m) — m — размер хеш-таблицы

• add(key, value) — если ключ уже существует, обновить значение

• существует (ключ)

• получить (ключ)

• удалить (ключ)

• Основные хеш-таблицы (видео)

• Структуры данных (видео)

• Проблема с телефонной книгой (видео)

• распределенные хэш-таблицы:

• Мгновенная загрузка и оптимизация хранилища в Dropbox (видео)

• Распределенные хэш-таблицы (видео)

• Хеширование с цепочкой (видео)

• Стол «Двойной», Карп-Рабин (видео)

• Открытая адресация, криптографическое хеширование (видео)

• PyCon 2010: Могучий словарь (видео)

• PyCon 2017: словарь еще сильнее (видео)

• (Дополнительно) Рандомизация: универсальное и идеальное хеширование (видео)

• (Дополнительно) Идеальное хеширование (видео)

• [Обзор] Хеш-таблицы за 4 минуты (видео)

• Видео:

• Онлайн-курсы:

• Реализуйте массив с использованием линейного зондирования

⬆ наверх

Больше знаний

• Бинарный поиск

• двоичный поиск (по отсортированному массиву целых чисел)

• двоичный поиск с использованием рекурсии

• Бинарный поиск (видео)

• Бинарный поиск (видео)

• деталь

• план

• [Обзор] Бинарный поиск за 4 минуты (видео)

• Осуществлять:

• Побитовые операции

• Абсолютное целое число

• Менять

• 4 способа посчитать биты в байте (видео)

• Подсчет битов

• Как посчитать количество установленных битов в 32-битном целом числе

• Двоичный код: плюсы и минусы (почему мы используем дополнение до двух) (видео)

• 1с дополнение

• 2s Дополнение

• слова

• Хорошее введение: битовые манипуляции (видео)

• Учебник по программированию на C 2-10: Побитовые операторы (видео)

• Битовые манипуляции

• Побитовая операция

• Битхаки

• Бит-Твиддлер

• Интерактивный Bit Twiddler

• Бит-хаки (видео)

• Практика операций

• вы должны знать многие степени двойки от (2^1 до 2^16 и 2^32)

• Шпаргалка по битам

• Получите действительно хорошее представление о манипулировании битами с помощью: &, |, ^, ~, >>, <<

• Дополнение 2 и 1

• Подсчитать установленные биты

• Значения обмена:

• Абсолютное значение:

⬆ наверх

Деревья

• Деревья – Введение

• БФС отмечает:

• ДФС отмечает:

• порядок уровня (BFS, с использованием очереди)

• временная сложность: O(n)

• пространственная сложность: лучшее: O(1), худшее: O(n/2)=O(n)

• временная сложность: O(n)

• пространственная сложность: лучшее: O(log n) – ср. высота дерева наихудшая: O(n)

• в порядке (DFS: слева, самостоятельно, справа)

• постзаказ (DFS: слева, справа, самостоятельно)

• предзаказ (DFS: самостоятельно, влево, вправо)

• Знакомство с деревьями (видео)

• Обход дерева (видео)

• BFS (поиск в ширину) и DFS (поиск в глубину) (видео)

• [Обзор] Поиск в ширину за 4 минуты (видео)

• [Обзор] Поиск в глубину за 4 минуты (видео)

• [Обзор] Обход дерева (плейлист) за 11 минут (видео)

• Двоичные деревья поиска: BST

• вставить // вставляем значение в дерево

• get_node_count // получаем количество сохраненных значений

• print_values ​​// печатает значения в дереве от минимального до максимального

• удалить_дерево

• is_in_tree // возвращает true, если заданное значение существует в дереве

• get_height // возвращает высоту в узлах (высота одного узла равна 1)

• get_min // возвращает минимальное значение, хранящееся в дереве

• get_max // возвращает максимальное значение, хранящееся в дереве

• is_binary_search_tree

• удалить_значение

• get_successor // возвращает следующее по величине значение в дереве после заданного значения, -1, если его нет

• Бинарное дерево поиска – реализация на C/C++ (видео)

• Реализация BST — распределение памяти в стеке и куче (видео)

• Найдите минимальный и максимальный элемент в бинарном дереве поиска (видео)

• Найдите высоту бинарного дерева (видео)

• Обход двоичного дерева — стратегии в ширину и в глубину (видео)

• Бинарное дерево: обход порядка уровней (видео)

• Обход двоичного дерева: Preorder, Inorder, Postorder (видео)

• Проверьте, является ли бинарное дерево бинарным деревом поиска или нет (видео)

• Удаление узла из двоичного дерева поиска (видео)

• Преемник порядка в бинарном дереве поиска (видео)

• Обзор дерева двоичного поиска (видео)

• Введение (видео)

• Массачусетский технологический институт (видео)

• Си/С++:

• Осуществлять:

• Куча/Очередь приоритетов/Двоичная куча

• вставлять

• sift_up — необходим для вставки

• get_max — возвращает максимальный элемент, не удаляя его

• get_size() — возвращает количество сохраненных элементов

• is_empty() — возвращает true, если куча не содержит элементов

• extract_max — возвращает максимальный элемент, удаляя его

• sift_down — необходим для Extract_max

• Remove(x) — удаляет элемент с индексом x

• heapify — создать кучу из массива элементов, необходимую для heap_sort

• heap_sort() — взять несортированный массив и превратить его в отсортированный массив на месте, используя максимальную или минимальную кучу

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

• Куча

• Введение (видео)

• Двоичные деревья (видео)

• Замечание по высоте дерева (видео)

• Основные операции (видео)

• Полные бинарные деревья (видео)

• Псевдокод (видео)

• Сортировка пирамидой — переходы к началу (видео)

• Кучная сортировка (видео)

• Построение кучи (видео)

• MIT 6.006 Введение в алгоритмы: двоичные кучи

• CS 61B Лекция 24: Приоритетные очереди (видео)

• Линейное время BuildHeap (максимальная куча)

• [Обзор] Куча (плейлист) за 13 минут (видео)

• Реализуйте максимальную кучу:

⬆ вернуться наверх

Сортировка

• Примечания:

• Я бы не рекомендовал сортировать связанный список, но сортировку слиянием можно выполнить.

• Сортировка слиянием для связанного списка

• Стабильность алгоритма сортировки

• Стабильность алгоритмов сортировки

• Стабильность алгоритмов сортировки

• Алгоритмы сортировки — стабильность

• нет пузырьковой сортировки - это ужасно - O(n^2), за исключением случаев, когда n <= 16

• Реализуйте сортировку и узнайте лучший случай/худший случай, среднюю сложность каждого:

• Стабильность алгоритмов сортировки («Стабильна ли быстрая сортировка?»)

• Какие алгоритмы можно использовать в связанных списках? Какой на массивах? Какой из обоих?

• Для пирамидальной сортировки см. структуру данных кучи выше. Сортировка кучей — это здорово, но не стабильно

• Седжвик - Mergesort (5 видео)

• 1. Сортировка слиянием

• 2. Сортировка слиянием снизу вверх

• 3. Сортировка сложности

• 4. Компараторы

• 5. Стабильность

• Седжвик - Быстрая сортировка (4 видео)

• 1. Быстрая сортировка

• 2. Выбор

• 3. Дублирующиеся ключи

• 4. Системные сортировки

• Калифорнийский университет в Беркли:

• CS 61B Лекция 29: Сортировка I (видео)

• CS 61B Лекция 30: Сортировка II (видео)

• CS 61B Лекция 32: Сортировка III (видео)

• CS 61B Лекция 33: Сортировка V (видео)

• CS 61B 21 апреля 2014 г.: Поразрядная сортировка (видео)

• Пузырьковая сортировка (видео)

• Анализ пузырьковой сортировки (видео)

• Сортировка вставками, сортировка слиянием (видео)

• Сортировка вставками (видео)

• Сортировка слиянием (видео)

• Быстрая сортировка (видео)

• Сортировка выбором (видео)

• Код сортировки слиянием:

• Использование выходного массива (C)

• Использование выходного массива (Python)

• На месте (C++)

• Код быстрой сортировки:

• Реализация (С)

• Реализация (С)

• Реализация (Python)

• [Обзор] Сортировка (плейлист) за 18 минут

• Быстрая сортировка за 4 минуты (видео)

• Сортировка кучей за 4 минуты (видео)

• Сортировка слиянием за 3 минуты (видео)

• Сортировка пузырьком за 2 минуты (видео)

• Сортировка выбором за 3 минуты (видео)

• Сортировка вставками за 2 минуты (видео)

• Осуществлять:

• Сортировка слиянием: O(n log n) среднее и худшее