На техническом собеседовании проблемы с белой доской могут застать вас врасплох. Иногда бывает сложно последовать решению, которое вы придумываете в уме, и достичь финиша, особенно если кто-то пытается направить вас сделать это по-другому.
Находясь под давлением, если мы не можем придумать лучший ответ, по крайней мере, мы можем придумать рабочий Решение.
Возьмем эту давнюю проблему слияния наборов диапазонов:
Комбинируйте [1..5, 10..15, 35..40] с [5..20, 38..48]
Первая загадка здесь заключается в том, являются ли концы ваших диапазонов включающими или исключающими. Простой способ решить эту проблему - определить диапазоны в соответствии с началом и длиной, а не началом и концом. Конец диапазона - это расплывчатое понятие (потенциально включающее или исключающее), но длина очевидна.
Теперь, когда у нас есть способ точно выразить наши данные, приступим к работе.
Таким образом, входные данные представляют собой массив объектов диапазона, где объект диапазона может обозначаться буквально:
{
start: 35,
length: 5
}
Мы можем описать нашу функцию следующим образом:
function mergeRanges(arr, arr2) {
let result = [];
// compute something
return result;
}
Мы знаем как данность, что в каждом из исходных массивов ничего не перекрывается. Но мы знаем, что объединенный результат может иметь размер от 1 элемента до суммы всех исходных элементов.
Поскольку любой элемент может перекрываться с любым другим элементом, я думаю, будет справедливо просмотреть каждый элемент один за другим, чтобы проверить, не перекрываются ли они с чем-то другим, и пройтись по каждому массиву, чтобы наши индексы были выровнены.
1..5 10..15 35...40 5..........20 38.......48
Но увы, я забегаю вперед. Идея обхода обоих массивов в теории кажется простой, но реализация может оказаться сложной очень быстрой.
Итак, давайте перейдем к решению грубой силы. Просто попробуйте смешать каждый элемент с каждым другим элементом и повторяйте, пока ничего не столкнется. Мы будем использовать вложенные циклы, очень похожие на реализацию пузырьковой сортировки.
function mergeRanges(arr1, arr2) {
let result = arr1.concat(arr2);
let goAgain = true;
while (goAgain) {
goAgain = false;
for (let i = 0; i < result.length — 1; i++) {
for (let j = i + 1; j < result.length; j++) {
if (overlaps(result[i], result[j])) {
result[i] = merge(result[i], result[j]);
result.splice(j, 1);
j--; // since the element at j got trashed, walk backwards
goAgain = true;
}
}
}
}
return result;
}
Заметили, что я сделал несколько новых функций "на лету": перекрытия и слияние? Давайте заполним их. Теперь, что такое перекрытие? Перекрытие означает, что крайний левый ИЛИ крайний правый элемент одного диапазона присутствует в другом диапазоне.
[....] [....] [....] [..........] [....] [....] [..........] [....]
Сначала я создам вспомогательную функцию, чтобы получить эксклюзивный результат. Я знаю, что сказал, что длина была более интуитивной, и это так, но это избавляет нас от работы.
const getEnd = a => {
return a.start + a.length;
}
Теперь функция перекрытия:
const overlaps = (a, b) => {
let leftAinB = a.start >= b.start && a.start < getEnd(b);
let rightAinB = getEnd(a) > b.start && getEnd(a) <= getEnd(b);
return leftAinB || rightAinB;
}
И, наконец, функция слияния:
const merge = (a, b) => {
// assume a and b overlap
let start = Math.min(a.start, b.start);
let length = Math.max(getEnd(a), getEnd(b)) — start;
return { start, length };
}
Теперь предположим, что это решение работает и в нем нет ошибок. Насколько это быстро? Поскольку у нас есть концентрические циклы, и алгоритм может запускаться повторно каждый раз, когда элементы объединяются, время выполнения будет O (n³), где n представляет средний размер каждого из массивов. Это достойное решение для небольшого набора данных, но я думаю, что мы можем добиться большего. Можем ли мы создать решение O (m + n)?
function mergeRanges(arr1, arr2) {
let index1 = 0;
let index2 = 0;
let result = [];
while (index1 < arr1.length && index2 < arr2.length) {
// case 1: range 1 comes before range 2 and does not overlap
if (getEnd(arr1[index1]) < arr2[index2]) {
result.push(arr1[index1]);
index1++;
}
// case 2: range 2 comes before range 1 and does not overlap
if (getEnd(arr2[index2]) < arr1[index1]) {
result.push(arr2[index2]);
index2++;
}
// case 3: they overlap
result.push(merge(arr1[index1], arr2[index2]));
index1++;
index2++;
// Wait a minute, I’m going to have to run through the list
// of results again to see if they merge.
// Ugh, I think it’s time to pull my hair out. All of it.
}
return result;
}
К сожалению, мой мозг превратился в тушеное мясо. Кайф от кофеина, который помог мне перебором, больше не работает. Я нервничаю. Мне стыдно. Я думаю про себя: Я просто тупой?
Если бы у меня было больше практики. Если бы я только лучше справлялся с такими проблемами. Я уже могу представить, что инженер, интервьюирующий меня, смотрит на меня сверху вниз, потому что знает ответ. Он умнее меня? Запомнил ли он решение? Я полный неудачник? Должен ли я просто продираться, как идиот, полностью осознавая, что я идиот без шансов на улучшение? Когда я попрошу о помощи, они поймут, что я волшебный единорог, и побалуют меня волшебной пылью? Думаю, займусь другой профессией.
Серьезно, эти мысли приходят мне в голову. Давление здесь реально, ребята. Что делать? Думаю, я собираюсь обсудить это, готовясь к худшему, но надеясь на лучшее.
Потому что реальность такова: в благоприятной среде окружающие нас люди будут нам помогать. В неблагоприятной среде они этого не сделают. Если кто-то не желает помочь вам в наиболее уязвимом состоянии, то ваше сияние им не светит. Это не потому, что у вас нет свечения, а потому, что их темнота его отталкивает.
Да, пройди через звонок, но нет, не чувствуй себя менее человеком из-за того, что тебя избили и избили. Спросите любого эксперта, и он скажет, что настойчивость окупается. Возможно, вы станете самым скромным, но в самом скромном человеке проявятся ваши истинные сильные стороны.
А пока используйте решение грубой силы. Как видите, это был довольно окольный путь решения этой проблемы, но для этого потребовалась только одна развилка, а не 10. Оптимизированное решение, безусловно, в моих силах, но для этого потребуется третья чашка кофе, и спасибо, но я действительно мог бы воспользоваться своим прекрасным отдыхом сегодня вечером.
Столкнувшись с невозможным компромиссом, выберите легкий выход. Когда вы сами себе босс, будьте амбициозны, но пока вы работаете на кого-то другого, просто делайте дела. Вы естественным образом поплывете в место, где вас ценят за волшебного единорога, внутри которого вы действительно находитесь, и там будет множество умных людей, которые окатят вас ведрами с волшебной пылью.
Так что идите туда, будь собой, и приберегите совершенство для повседневного ухода за собой.
