Кодирование проблемы с собеседованием

Сложный уровень

Середина

Спросил в

Amazon, Microsoft, Paytm

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

  • Обход матрицы по строкам (решение методом грубой силы)
  • Использование идеи бинарного поиска
  • Поэтапный подход с использованием одного сканирования (эффективное решение)

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

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

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

Учитывая логический 2D-массив, в котором сортируется каждая строка. Найдите строку с максимальным количеством единиц.

Input matrix
0 1 1 1
1 1 1 1 <- maximum number of 1s
0 0 1 1
0 0 0 0
Output: 1 (0-based indexing)

1. Подход грубой силы - обход матрицы по строкам

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

Простой метод - выполнить обход матрицы по строкам, подсчитать количество единиц в каждой строке и сравнить это количество с max. Наконец, верните индекс строки с максимумом единиц.

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

Мы просматриваем каждый индекс матрицы. Сложность времени = O (n * m)

Космическая сложность: O (1).

2. Использование идеи двоичного поиска

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

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

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

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

Сложность времени: O (nlogm), где n - количество строк, а m - количество столбцов в матрице. Двоичный поиск занимает время O (logm).

Космическая сложность: O (1)

3. Пошаговый подход с использованием единого сканирования

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

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

  1. Если текущая ячейка имеет значение 1, продолжайте движение влево, пока мы не найдем 0 и не обновим значения.
  2. Если текущая ячейка имеет значение 0, продолжайте движение вниз, пока не встретите 1.

Наконец, верните индекс строки с максимальным количеством единиц.

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

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

В коде есть два вложенных цикла, и временная сложность выглядит O (mn), но это неправильный анализ. Если мы внимательно наблюдаем, мы проходим каждую строку и столбец по крайней мере один раз, то есть внешний цикл проходит каждую строку, а внутренний цикл проходит каждый столбец. (Подумайте!)

  • Сложность времени = O (m + n)
  • Космическая сложность: O (1)

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

  • Каков худший и лучший сценарий проблемы?
  • Почему мы начинаем с правого верхнего угла? можем ли мы решить проблему с другой отправной точки?
  • Почему мы движемся в одной строке, если текущая ячейка имеет значение 1?

Матричные задачи для практики