Interview Cake — одно из лучших моих вложений в изучение алгоритмов и подготовку к техническим собеседованиям. У них есть обширный глоссарий необходимых алгоритмов, за которым следуют интересные вопросы, которые вы можете решить в их текстовом редакторе. Вы даже можете запустить свое решение в их тестах для отладки!
Одна из причин, по которой я потратился на InterviewCake, заключалась в том, что мне нужен был легкий доступ к решениям JavaScript. Cracking the Coding Interview написан на Java, поэтому приятно иметь возможность увидеть и попрактиковаться в языке, который вы будете использовать во время собеседования.
У них есть выбор из 14 языков, включая Python, C#, Go, JavaScript, Objective-C, PHP, Python и Ruby.
Вот вопрос из приведенной выше ссылки, который мы рассмотрим:
Ваша компания создала собственный календарь под названием HiCal. Вы хотите добавить функцию просмотра времени в течение дня, когда доступны все.
Для этого вам нужно знать, когда у какой-либо команды есть собрание. В HiCal собрание хранится в виде объектов ↴ с целочисленными свойствами startTime и endTime. Эти целые числа представляют количество 30-минутных блоков после 9:00.
Например:
{ startTime: 2, endTime: 3 } // meeting from 10:00 – 10:30 am
{ startTime: 6, endTime: 9 } // meeting from 12:00 – 1:30 pmЦель: Написать функцию mergeRanges(), которая принимает массив нескольких диапазонов времени встречи и возвращает массив сжатых диапазонов.
- *Мы не можем предполагать, что собрания проходят по порядку. Это важный ключ к эффективному решению проблемы.
Пограничные случаи:
[{ startTime: 3, endTime: 5}, { startTime: 4, endTime: 6}]- Встречи должны быть объединены, чтобы вернуть [{ startTime: 3, endTime: 6}]. Время начала первого собрания меньше времени начала второго собрания, а время окончания первого собрания меньше времени начала второго собрания.
2. Что если endTime первого совпадает с startTime второго? например.
[{ startTime: 4, endTime: 6}, { startTime: 6, endTime: 9}]
Затем мы должны рассмотреть, когда endTime первого собрания равно startTime второго собрания.
Собираем вместе:
Есть более простой способ увидеть шаблон для встреч, которые перекрываются. Если endTime первого больше или равно startTime второго, они должны быть объединены. Пока мы рассматриваем собрание с более ранним startTime как первая встреча, это сработает.
Мы могли бы настроить два цикла for для сравнения всех собраний, один с i = 0, а другой j = i + 1, но это дало бы нам время выполнения 0(n2).
В настоящее время наш массив встреч не отсортирован, но что, если бы он был отсортирован по времени начала? Затем мы могли бы просто перебрать наш отсортированный массив и проверить с помощью логики, которую мы уже подробно описали. Сортировка массива — logn, а проверка каждого элемента в отсортированном массиве — 0(n). n log n лучше, чем 0 (n2), так что это будет лучшим подходом.
Давайте работать над решением вместе:
Ознакомьтесь с моей сутью здесь для решения и пошагового руководства. Мои извинения за появление превью изображения.
function mergeRanges(meetings){
//We are calling #sort on meetingsCopy, which is an array of meeting objects. sort() will sort items in an array by default
//in ascending order. We are passing in an optional function that provides an alternative way to sort the array.
//For example, if a.startTime (5) - b.startTime(3), this would produce a positive number.
//If a positive number is returned, b will now come first, and a will be pushed forward.
//This pattern will ensure that the smaller numbers come first.
const sortedMeetings = meetingsCopy.sort((a, b) => {
return a.startTime - b.startTime;
});
// initialize merged meetings with the first meeting from sorted meetings We know the first index is the earlier startTime.
const mergedMeetings = [sortedMeetings[0]];
// Loop over the sorted meetings to find the right ones to merge. Access current meeting in loop with currentMeeting.
//As we loop, the i value will increase until it's one less than the length of the mergedMeetings, ie. the last meeting.
for (let i = 1; i < sortedMeetings.length; i++) {
const currentMeeting = sortedMeetings[i];
const lastMergedMeeting = mergedMeetings[mergedMeetings.length - 1];
if (currentMeeting.startTime <= lastMergedMeeting.endTime) {
// [{startTime: 3, endTime: 5}, //{startTime: 3, endTime: 4}]
//--> {startTime: 3, endTime: //5}
// To merge them, we also have to make sure we take the larger endTime. Unlike startTimes, endTimes are not sorted.
//Math.max() will return the assigned the higher value to the variable lastMergedMeeting.endTime
lastMergedMeeting.endTime = Math.max(lastMergedMeeting.endTime, currentMeeting.endTime);
} else {
// Add the current meeting since it doesn't overlap
mergedMeetings.push(currentMeeting);
}
}
return mergedMeetings;
}
