кодирование задачи собеседования

Уровень сложности

Середина

Запрошено

Amazon, Adobe

Обсуждены три решения

  1. Включение и исключение каждого элемента
  2. Исправьте элементы и повторите для создания комбинации номеров K
  3. Рекурсивный поиск с возвратом - подход DFS

Основные выводы после прочтения этого блога

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

Давайте разберемся в проблеме

Даны два числа n и K, и вы должны найти все возможные комбинации чисел K от 1 до n.

Пример

Решение 1. Включение и исключение всех элементов

Идея алгоритма

Мы используем идею, аналогичную задаче о сумме подмножества, для создания возможных комбинаций K чисел из n чисел - мы выбираем каждое число от 1 до n и повторяем его для двух возможных случаев:

(i) Выбранное число является частью решения или входит в набор

(ii) Выбранный номер не является частью решения или не включен в набор

Предположим, у нас есть n = 4 и K = 2, т.е. данный диапазон: [1,2,3,4]. Следующая древовидная диаграмма объясняет создание всех комбинаций размера 2.

  • Мы идем налево, если мы включаем число, и идем направо, если мы не включаем число.
  • На каждом уровне мы включаем или исключаем по одному числу за раз.
  • У нас есть комбинация размера 2 на каждом листовом узле.

Чтобы реализовать это, мы используем временный массив temp [], чтобы сохранять все выходные данные один за другим. Когда количество элементов в temp [] становится равным K (размеру комбинации), мы печатаем его. Все, что нам нужно сделать, это рассмотреть оба случая и рекурсивно создать все возможные комбинации. Основная идея этого подхода исходит из идентичности паскаля, то есть: C (n, K) = C (n-1, K) + C (n-1, K-1) (Подумайте!)

Код алгоритма C ++

Анализ алгоритмов

Здесь для каждого элемента есть две возможности, т.е. будет ли элемент выбран или нет. Это создает два случая для каждого элемента, и мы собираемся выполнить итерацию для всех n элементов. Итак, общая временная сложность будет O (2 ^ n). (Подумайте!)

Сложность пространства = O (K * C (n, K))

Возможные вопросы интервьюера

  • Почему сложность пространства O (K * C (n, K))?
  • Как обрабатывать дубликаты в приведенном выше решении?
  • Как мы можем улучшить временную сложность?

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

Идея алгоритма

Идея состоит в том, чтобы сгенерировать дерево комбинаций, в котором мы фиксируем каждое число от 1 до n и рекурсивно строим комбинацию из K чисел. Предположим, у нас есть n = 5 и K = 3, т.е. данный диапазон: [1,2,3,4, 5].

  • Сначала мы исправляем номер 1 и рекурсивно генерируем всю уникальную комбинацию размера 3, начиная с номера 1, то есть {1,2,3}, {1,2,4}, {1,2,5}, {1,3,4 }, {1,4,5}.
  • Затем мы сначала исправляем номер 2 и рекурсивно генерируем всю уникальную комбинацию размера 3, начиная с номера 2, то есть {2,3,4}, {2,3,5} и {2,4,5}.
  • Затем мы сначала фиксируем номер 3 и рекурсивно генерируем всю уникальную комбинацию размера 3, начиная с номера 3, то есть {3,4, 5}.
  • Не может быть уникальной комбинации размера 3, начинающейся с 4 и 5. (Подумайте!)

Для реализации этого

  • Мы используем временный массив temp [], чтобы сохранять все выходные данные один за другим.
  • Мы начинаем с первого индекса в temp [] и один за другим фиксируем элементы в этом индексе и повторяемся для остальных индексов.
  • Когда количество элементов в temp [] становится равным K (размеру комбинации), рекурсия останавливается, и мы печатаем temp [].

Код алгоритма C ++

Анализ алгоритмов

Цикл в алгоритме будет выполняться C (n, K) раз, поскольку это возможное количество комбинаций, и на каждой итерации элементы могут быть выбраны в диапазоне (nK), поскольку K элементов уже выбраны, и мы просто заменяем элементы, которые уже заняты. Таким образом, общая временная сложность будет O (C (n, K) * (n-K)).

Сложность пространства = O (K * C (n, K)) (поскольку у нас есть всего C (n, K) возможных ответов, каждый из которых имеет размер K)

Возможные вопросы интервьюера

  • Объясните происхождение пространственно-временной сложности?
  • Почему мы проверяем условие end-i + 1 ≥ k - ind внутри цикла?
  • Нарисуйте дерево рекурсии для приведенного выше кода.
  • Можем ли мы использовать эту идею для решения других подобных проблем?
  • есть ли другой способ реализовать вышеуказанное решение?
  • Какие модификации в алгоритме при дублировании номеров?
  • можем ли мы еще больше улучшить временную сложность?

3. Рекурсивный поиск с возвратом - подход DFS

Идея алгоритма

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

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

Код алгоритма C ++

Анализ алгоритмов

Цикл for может выполняться максимум n раз с каждым возвратом с максимальной итерацией NcK раз. то есть: общая временная сложность будет O (N * C (n, K)).

Сложность пространства = O (k * C (n, K)) (поскольку у нас есть всего C (n, K) возможных ответов, каждый из которых имеет размер k)

Возможные вопросы интервьюера

  • Объясните пространственную и временную сложность?
  • Изучить лучший, средний и наихудший сценарий?
  • Сколько крайних случаев необходимо обработать?
  • какие модификации в алгоритме в случае повторяющихся номеров?

Задачи для практики - подход с возвратом / DFS

Наслаждайтесь обучением, наслаждайтесь алгоритмами!