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

Постановка проблемы:

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

Перед написанием кода мне нужно было кое-что сделать.

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

СОВЕТ №1. Всегда уточняйте двусмысленность формулировки проблемы.

Вот несколько вопросов, которые я задал для борьбы с двусмысленностью:

В: Почему имя продавца важно в контексте вопроса?

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

В: Что возвращает addProduct?

A: Он ничего не возвращает.

В: Что возвращает listProducts?

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

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

СОВЕТ №2. Спросите, можно ли использовать любой язык по вашему выбору. СПОЙЛЕР: Это почти всегда нормально.

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

В моем случае интервьюер был более чем счастлив, если я решил вопрос на python3.

СОВЕТ № 3. Всегда спрашивайте, для чего вы оптимизируете решение (например, для памяти, времени выполнения и т. д.).

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

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

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

СОВЕТ №4. Измените вставленный код на свой язык и добавьте документацию, отражающую вашу цель.

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

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

Теперь я собирался опустить голову и сосредоточиться на решении проблемы в полном молчании. Верно? НЕПРАВИЛЬНЫЙ!

СОВЕТ №5. Думайте вслух. Внимательно слушайте подсказки. Используйте блокнот.

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

Прежде всего, вы можете услышать, как вы объясняете свою логику. Так что, если в нем есть какие-то явные ошибки, вы сможете исправить себя еще до того, как начнете.

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

Это, в свою очередь, означает, что на протяжении всего процесса важно уделять пристальное внимание интервьюеру. В большинстве случаев есть намеренная причина того, что интервьюер скажет (или не скажет).

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

СОВЕТ №6. Попробуйте найти работающее, хотя и наивное решение.

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

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

БОНУСНЫЙ СОВЕТ № 6.5. Выбирайте имена переменных для максимальной удобочитаемости.

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

Во всяком случае, вот как выглядело мое решение v1:

На данный момент я был довольно доволен своим решением. У моего кода была хорошо оптимизированная сложность выполнения O (1) для list_products, которую я хотел. Моя другая функция, add_product (), имела время выполнения O (N). Я мог бы жить с этим. Но как я мог быть уверен?

СОВЕТ № 7. Выполните несколько тестовых примеров.

Тестовые примеры вселяют уверенность в ваш код. Просмотрите хотя бы один стандартный тестовый пример, обеспечивающий максимальное покрытие кода. Если у вас есть время, рассмотрите несколько крайних случаев.

В моем случае я прошел через состояния self.product_price_map_per_seller и self.avg_price_per_product, выполняя следующие вызовы функций:

Мой интервьюер кивнул, когда я объяснил свой код, и наконец нарушил его молчание, когда я закончил.

Выглядит хорошо. Но как вы думаете, можно ли оптимизировать среду выполнения для add_product ()?

СОВЕТ № 8. Прислушайтесь к отзывам, которые дает вам интервьюер. Если возможно, используйте подсказки, чтобы улучшить свое решение.

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

  • Строка №20 - Повышение цены для продавца по продукту было O (1). Я думаю, это нормально.
  • Строка №22 - Создание списка цен для каждого продукта было O (N). Ага! потенциальное узкое место.
  • Строка №23 - Суммирование списка было O (N). Еще одно узкое место!

Мне нужно было каким-то образом рассчитать среднее значение цен, не посещая каждую цену продукта. Как я мог это сделать? Думаю, я смогу сохранить скользящее среднее. Но это работает только в том случае, если я гарантированно увижу только новые значения. Моя программа предназначена для обновления старых цен (если продавец определенного продукта вызывает add_product () с ценой, отличной от исходной).

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

Интервьюер казался довольным ходом моих мыслей. Итак, я пошел дальше и сделал именно это.

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

TL; DR: вот советы в красивом списке:

  • Всегда уточняйте двусмысленность формулировки проблемы.
  • Спросите, можно ли использовать любой язык по вашему выбору. СПОЙЛЕР: Это почти всегда нормально.
  • Всегда спрашивайте, для чего вы оптимизируете решение (например, память, время выполнения и т. д.).
  • Измените зарезервированный код на свой язык и добавьте документацию, отражающую вашу цель.
  • Думайте вслух. Внимательно слушайте подсказки. Используйте блокнот.
  • Попробуйте рабочее, хотя и наивное, решение.
  • Выбирайте имена переменных для максимальной удобочитаемости.
  • Выполните несколько тестовых примеров.
  • Прислушайтесь к отзывам, которые дает вам интервьюер. Если возможно, используйте подсказки, чтобы улучшить свое решение.

Надеюсь, это помогло. Если у вас есть отзывы или полезные советы, которые я пропустил, не стесняйтесь оставлять заметки!