Как справляться с проблемами в раунде кодирования
Введение
Это вторая статья из серии статей Подготовка к собеседованиям по программированию, которые я пишу, чтобы помочь студентам улучшить свои навыки прохождения собеседований по программированию. Ссылка на первую статью здесь.
Цель.Цель этой статьи — показать, как мы можем использовать методы, описанные в предыдущем блоге, для решения реальной проблемы кодирования.
Постановка задачи. Вот постановка задачи, которую я обычно задаю кандидатам:
Исходные данные: для заданной двумерной плоскости с N точками найдите уравнение прямой. с максимальным количеством точек на ней.
Пример. Пусть следующий набор точек лежит на плоскости следующим образом:
[{0, 0}, {0, 0}, {2, 2}, {3, 3}, {2, 1}].
Ожидаемый результат — строка y = x, поскольку точки [{0, 0}, {1, 1}, { 2, 2}, {3, 3}] лежат на нем. Кандидаты должны достичь следующего в течение 1 часа:
- Разработайте алгоритм для решения проблемы
- Напишите код для решения проблемы
- Напишите тест-кейсы для решения проблемы
Как кандидат, вот как вы можете пройти различные этапы:
Понимание проблемы. Прежде чем приступить к решению проблемы, необходимо ответить на следующие вопросы:
*Прояснение проблемы: Чтобы прояснить проблему, вот ряд вопросов, которые вы можете задать:
(i) Должны ли мы находить линию наилучшего соответствия (подумайте о линейной регрессии) или каждая точка лежит на линии точно ?
(ii) Нужно ли нам найти прямую или отрезок прямой?
(iii) Являются ли все точки целыми числами или они могут быть двойными/плавающими числами?
(iv) Что, если есть несколько строк с максимальным количеством точек на них?
* Понимание ввода/вывода:
(i) Каково максимальное количество точек во входных данных?
(ii) Могут ли во входных данных быть повторяющиеся точки? Должны ли эти точки считаться уникальными или неоднозначными?
(iii) Нужно ли нам выделять линию или максимальное количество точек на линии?
(iv) Каков результат в случае линия не может быть построена (например, ввод с нулевыми точками, 1 точкой или повторяющимися точками и т. д.).
Разработка алгоритма
*Выбор алгоритма перед кодированием. Учитывая проблему, лучше всего начать с подхода грубой силы. В методе грубой силы используемый алгоритм работает за O (N³). Алгоритм следующий:
Шаг 1. Выберите каждую пару точек и создайте из нее линию.
Шаг 2. Для каждой линии выберите все остальные точки, а затем проверьте, попадает ли точка на линию.
Шаг 3: Для каждой строки заведите счетчик.
Шаг 4: Выберите линию с максимальным количеством точек.
Обсудите это с интервьюером. После этого попробуйте улучшить решение. Некоторые идеи по улучшению алгоритма:
(i) Посмотрите, может ли интервьюер дать вам подсказку
(ii) Подумайте, в чем заключается неэффективность алгоритма. Если мы рассмотрим этот алгоритм, мы увидим, что для любой тройки (A, B, C) мы будем рассматривать каждую пару как линию, а также рассматривать другую точку, чтобы проверить, находится ли она на линии. Это не нужно. Учитывая тройку, мы должны иметь возможность рассмотреть каждую пару и сказать, коллинеарны они или нет. Это снижает эффективность алгоритма.
(iii) Проработайте примеры, чтобы увидеть, сможете ли вы придумать другой подход.
Одна интуиция для решения этой проблемы состоит в том, чтобы рассмотреть, что если вместо того, чтобы смотреть на точки, лежащие на каждой линии, можно было бы уменьшить проблему, чтобы найти линию, которая встречается максимальное количество раз, когда мы перечисляем множество всех линий. Это может снизить общую сложность проблемы. Напишем алгоритм:
Шаг 1. Выберите каждую пару точек и создайте из нее линию.
Шаг 2. Сохраните счетчик для каждой линии.
Шаг 3. Сохраните счетчик для каждой линии, указывающий, сколько раз это строка была видна.
Шаг 4: Выберите строку, которая встречается максимальное количество раз.
С помощью приведенного выше алгоритма мы видим, что общая сложность уменьшается до O (N²).
* Подумайте о входных данных: было бы неплохо подумать о том, будет ли вышеупомянутый алгоритм работать для выборки входных данных или нет. После этого было бы хорошо рассмотреть входные данные (с вертикальными линиями, горизонтальными линиями и т. д.). Если алгоритм может выдержать это, тогда продолжайте алгоритм
При написании кода:
*Дизайн структуры данных. При кодировании алгоритма нам необходимо учитывать следующие структуры данных:
(i) Класс для представления Point и Line.
(ii) HasTable для представления сопоставления каждой строки с количеством точек на ней.
* Дизайн интерфейса:Для решения вышеупомянутой проблемы будет хорошо рассмотреть следующие интерфейсы:
(i) Line GetMaxPointLine(vector‹Point› points );
(ii) Line GetLine(Point p1, Point p2);
(iii) HashTable: Int Get(Line), void Put (Линия); bool Contains(Line);
Эти интерфейсы можно записать до того, как вы начнете программировать. Кроме того, если в этих интерфейсах делаются какие-либо предположения, вызывайте их.
* Кодирование: выберите удобный для вас язык. Мы будем использовать C++.
Здесь — ссылка на код счастливого пути.
Здесь — ссылка на код счастливого пути + крайние случаи.
После написания кода:
*Продумывание тестовых сценариев. После того, как вы закончите работу с кодом, продумайте следующий набор тестовых сценариев:
(i) Тест пограничных случаев. Некоторые пограничные случаи могут возникать из-за различий во входных данных (пустой ввод, ввод с 1 точкой, 2 точки), распределения точек (уникальные, неуникальные точки), несколько строк с одинаковым количеством точек и т. д.
(ii) Тест интерфейса: проверка того, могут ли интерфейсы обрабатывать различные входные данные. Например. вертикальные линии, горизонтальные линии и т. д. Не рекомендуется предполагать, что интерфейсы всегда будут обрабатывать все сценарии.
(iii)Тест временной сложности:объяснение интервьюеру, как Не могли бы вы проверить, важна ли общая временная сложность входных данных O(N²).
Как вы можете получить помощь:
Мы также проводим бесплатные пробные собеседования, а здесь есть календарь, который вы можете использовать для планирования пробных собеседований (желательно на выходных).
Биография писателя:
Писатель, Рави Тандон, является архитектором программного обеспечения в ThoughtSpot и имеет более чем 6-летний опыт работы в отрасли по созданию крупномасштабных систем. Он работал в стартапах в Бангалоре (Flipkart, ThoughtSpot) и Кремниевой долине (ThoughtSpot). Он окончил ИИТ-Гувахати в 2012 году, факультет компьютерных наук со степенью бакалавр компьютерных наук. Затем он получил степень магистра компьютерных наук в Принстонском университете, США.
О ParShiksha:
ParShiksha – это небольшой шаг в предоставлении "Образования для всех" с использованием современных /современные технологии, методики обучения и социальное пробуждение масс. Если вам нравится наша работа, подписывайтесь на нас здесь:
WebSite, LinkedIn, YouTube, Facebook, Instagram.
Если эта статья показалась вам полезной, щелкните значок хлопка в ладоши ниже, чтобы другим было проще найти эту статью и использовать ее. Не стесняйтесь оставлять свои предложения/комментарии в разделах ниже.
