Слишком много людей борются с этим. Это система, которую я рекомендую

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

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

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

Графики: лучшая перспектива

Когда я произношу слово «график», у вас в голове возникает одно из трех изображений.

  1. Если вы специалист по статистике, вы будете думать о диаграммах и графиках. Большинство ресурсов, ориентированных на кодирование, полностью игнорируют это. Это огромная ошибка
  2. Если вы знаток теории графов, вы вспомните карты с задачей коммивояжера. Это поможет вам визуализировать полезность различных (часто сложных) графических алгоритмов.
  3. Если вы тот редкий специалист по компьютерным наукам, у которого ограниченное знакомство с двумя другими, вы подумаете о чем-то, определяемом списком смежности. Это помогает при кодировании.

Естественно, то, о чем вы подумали в первую очередь, будет зависеть от вашего основного знакомства с графиками и от того, что они из себя представляют. И вот первая причина, по которой люди действительно борются с графиками: Все эти определения верны и полезны. К сожалению, большинство курсов/онлайн-ресурсов обычно придерживаются 2 и 3, говоря о графиках. Они полностью игнорируют 1. Почему 1 важен для целей кодирования?

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

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

Если карта более детализирована с различными типами ландшафтов, то отношение становится усилием, которое требуется для перемещения между местами (а не просто расстоянием). Видите, как мы связываем все 3 интерпретации графика в одном объяснении? Это именно то, что важно для ваших интервью по программированию/кодированию. Вы должны иметь возможность переключаться между этими тремя перспективами (на самом деле все остальные типы являются подмножеством типа 1, но это может быть очень абстрактно для людей, не разбирающихся в математике, таких как я). Обязательно перечитайте этот раздел, пока не уясните суть: Графики можно рассматривать с разных точек зрения. И каждая перспектива имеет что-то уникальное в реализации графиков.

Почему вы боролись с графиками

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

Добавьте ко всему этому тот факт, что люди неправильно обучают графикам. Вместо того, чтобы сосредоточиться на почему графики важны, люди тратили свои часы на множество как работают графики. Вот почему один из самых частых отзывов, которые я получаю от своих студентов, когда мы работаем над задачами, заключается не в том, что они находят кодирование или алгоритмы сложными, а просто в том, что они никак не могли понять, что им нужно использовать график в вопросе. Вспомните это утверждение. Они не борются с алгоритмами (случай 2) или кодированием (случай 3). Вместо этого их сбивает с толку использование графа (случай 1). Видите тенденцию? Так как мы можем сделать лучше?

Как на самом деле лучше ориентироваться в графике

Как упоминалось ранее, существует множество замечательных ресурсов, которые научат вас реализовывать детали и научат теории. Графики FCC для технических интервью — прекрасное видео. У них также есть 9-часовая теория графов, но я сомневаюсь, что большинству из вас интересны графы вне контекста интервью/кодирования. Что касается рентабельности инвестиций, видео предоставит вам необходимую информацию.

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

Ваша система обнаружения графиков

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

Я хочу, чтобы вы изменили свое представление о графике. Узлы, ребра и веса — все это правильные концепции, но они бесполезны. Нас волнует то, что они представляют. Графики представляют собой систему. Узлы — это Сущности/Граждане в этой системе. Ребра представляют отношения между гражданами. И веса этих ребер просто говорят нам, насколько сильны отношения. Как насчет невзвешенных графиков? Просто относитесь к ним как к взвешенным графам, где все веса ребер одинаковы. Это помогает при оценке правильного алгоритма обхода.

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

Стресс-тестирование нашего фреймворка

Чтобы проверить правильность этого подхода, мы возьмем только сложные вопросы от Leetcode, которые не делают очевидным, что мы должны использовать граф.

Проблема со словарем пришельцев

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

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

Отношения: нам нужен порядок букв. Учитывая букву, будет важно знать, что следует за ней (что хорошо работает, поскольку у нас есть отсортированный список).

Веса: между двумя парами букв нет разницы. Если в нашем инопланетном алфавите порядок s,v,g, то расстояние s&v== расстоянию b/w v&g.

Здесь мы получаем четкое указание на жизнеспособность графа. И решение на самом деле включает графики. Чтобы оставаться в курсе решения этой проблемы, убедитесь, что у вас есть премиум-подписка. По этой ссылке можно получить 20% на целый год

2 СБ Проблема

Имея формулу 2-CNF, найдите способ присвоить значения истинности, чтобы удовлетворить ее, или вернуть False, если это невозможно.

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

Сущности: разные литералы.

Отношения: последствия между литералами.

Веса. Опять же, степени влияния нет. Все последствия одинаково «тяжёлые». Таким образом, граф имеет одинаковый вес во всех ребрах (невзвешенных).

Словесная лестница

Последовательность преобразования слова beginWord в слово endWord с использованием словаря wordList — это последовательность слов beginWord -> s1 -> s2 -> ... -> sk, такая, что:

  • Каждая соседняя пара слов отличается на одну букву.
  • Каждый si для 1 <= i <= k находится в wordList. Обратите внимание, что beginWord не обязательно должно быть в wordList.
  • sk == endWord

Имея два слова, beginWord и endWord, и словарь wordList, вернуть количество слов в кратчайшей последовательности преобразования из beginWord в endWordили0, если такой последовательности не существует.

Например. учитывая begin=cat и end=bag, мы можем пойти [cat→bat→bag]. Мы хотим вернуть это.

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

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

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

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

Практика определения графика

Это навык. И навыки нужно развивать. Вот как я рекомендую это делать. Начните с простых задач. Начните определять компоненты проблем с графом, а также то, как вы настроите решение (не сосредотачивайтесь на кодировании для этого). Как только вы справитесь с 1 за 2–3 минуты, вы можете перейти к следующему уровню. На сложные задачи можно потратить до 5 минут.

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

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

Очевидно, вам нужно будет сочетать эту систему с реальными техническими знаниями и способностями к кодированию. Мой ежедневный информационный бюллетень Простые интервью по программированию охватывает темы проектирования алгоритмов, математики, последних событий в области технологий, разработки программного обеспечения и многого другого, чтобы помочь вам стать лучшим разработчиком. В настоящее время у меня действует скидка 20% на ЦЕЛЫЙ ГОД, так что не забудьте проверить это.

Я создал Coding Interviews Made Simple, используя новые методы, полученные в результате обучения нескольких людей в ведущих технологических компаниях. Информационный бюллетень предназначен для того, чтобы помочь вам добиться успеха, избавив вас от часов, потраченных впустую на работу с Leetcode. Вы можете прочитать FAQ и узнать больше здесь

Чтобы помочь мне лучше писать статьи и понять вас, заполните этот опрос (анонимно). Это займет максимум 3 минуты и позволит мне улучшить качество моей работы.

Не стесняйтесь обращаться, если у вас есть какие-либо интересные работы/проекты/идеи для меня. Всегда рад вас выслушать.

Для денежной поддержки моей работы следуют мои Venmo и Paypal. Любая сумма приветствуется и очень помогает. Пожертвования открывают эксклюзивный контент, такой как анализ бумаги, специальный код, консультации и специальные тренировки:

Венмо: https://account.venmo.com/u/FNU-Devansh

Paypal: paypal.me/ISeeThings

Свяжитесь со мной

Воспользуйтесь ссылками ниже, чтобы ознакомиться с другим моим контентом, узнать больше о репетиторстве или просто поздороваться. Кроме того, ознакомьтесь с бесплатной реферальной ссылкой Robinhood. Мы оба получаем свободный сток (денег вкладывать не надо), и никакого риска для вас нет. Таким образом, если вы не используете его, вы просто потеряете бесплатные деньги.

Ознакомьтесь с другими моими статьями на Medium. : https://rb.gy/zn1aiu

Мой Ютуб: https://rb.gy/88iwdd

Свяжитесь со мной в LinkedIn. Подключаемся: https://rb.gy/m5ok2y

Мой Инстаграм: https://rb.gy/gmvuy9

Мой Твиттер: https://twitter.com/Machine01776819

Если вы готовитесь к программированию/техническим интервью: https://codinginterviewsmadesimple.substack.com/

Получите бесплатный сток на Robinhood: https://join.robinhood.com/fnud75