Вопрос, заданный на собеседовании в Stripe

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

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

Проведя время в нескольких разных странах, я создал крепкую сеть друзей, которые работали в сфере программного обеспечения в Лондоне, Сан-Франциско, Чикаго, Сингапуре, Берлине и Мюнхене.

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

Вопрос

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

Например, [0, 1] и [1, 2] не являются перекрывающимися интервалами, в то время как [0, 2] и [1, 2] являются. Вот пример:

  • Ввод: [0, 3], [9, 12], [3, 8], [8, 10]
  • Ответ: 1

В этом случае, если [8, 10] будет удален, между остальными не будет перекрытия. Вот еще один пример:

  • Ввод: [0,5], [1, 2], [3, 5]
  • Ответ: 1

В этом случае, если [0, 5] будет удален, между остальными не будет перекрытия.

Решение

Дайте себе время, чтобы найти ответ для практики. Если вам не удалось или вам нужно было проверить свой ответ, вот решение на JavaScript:

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

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

Вы можете попробовать это, скопировав функцию в консоль своего браузера, а затем предоставив ей ввод, например:

removeOverlappingIntervals([[0,1], [1,2], [2, 5], [3, 5]]);

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