Написав той алгоритм, який запропонували в інтерв'ю на початку.
Код по посиланню зверху має бути, але я його ще під спойлер запихну.
Захочете своє писати, то клікайте там Fork
▼Прихований текст
const будинки = [
{
магазин: false,
спортзал: false,
школа: false
},
{
магазин: false,
спортзал: false,
школа: true
},
{
магазин: false,
спортзал: false,
школа: true
},
{
магазин: false,
спортзал: true,
школа: false
},
{
магазин: true,
спортзал: false,
школа: false
}
];
const будівлі = ["школа", "магазин", "спортзал"];
const відстані = будинки.map((будинок) =>
Object.entries(будинок).reduce((acc, [поле, значення]) => {
return {
...acc,
[поле]: значення ? 0 : Number.POSITIVE_INFINITY
};
}, {})
);
for (let idx = 1; idx < будинки.length; idx++) {
const будинок = будинки[idx];
Object.keys(будинок).forEach((поле) => {
const значення = відстані[idx][поле];
if (значення !== 0) {
відстані[idx][поле] = Math.min(відстані[idx - 1][поле] + 1, значення);
}
});
}
for (let idx = будинки.length - 2; idx >= 0; idx--) {
const будинок = будинки[idx];
if (!будинок) continue;
Object.keys(будинок).forEach((поле) => {
const значення = відстані[idx][поле];
if (значення !== 0) {
відстані[idx][поле] = Math.min(відстані[idx + 1][поле] + 1, значення);
}
});
}
function обрахуватиМаксимальнуВідстань(будинок) {
return Math.max(...Object.values(будинок));
}
let потрібнийБудинок = 0;
let попередняМаксВідстань = обрахуватиМаксимальнуВідстань(відстані[0]);
console.log(відстані, попередняМаксВідстань);
відстані.forEach((відстань, idx) => {
const максВідстань = обрахуватиМаксимальнуВідстань(відстань);
if (максВідстань < попередняМаксВідстань) {
потрібнийБудинок = idx;
попередняМаксВідстань = максВідстань;
}
});
console.log({ потрібнийБудинок, попередняМаксВідстань });
Ідея така.
1. Створюємо ще один масив, який міститиме об'єкт такої структури
{ школа: <відстань до школи>, магазин: <відстань до магазину...> і т.д. }
Індекс об'єкту дорівнюватиме індексу будинку, таким чином у нас буде інфа про те, яка відстань від конкретного будинку до необхідних будівель.
2. Ініціалізуємо ті відстані дуже великим числом, якщо напроти будинку немає необхідної будівлі.
3. Проходимо по масиву відстаней, від другого будинку в списку і до останнього, і перевірямо:
3.1 якщо напроти будинку немає необхідної будівлі (відстань !== 0), то встановлюємо цю відстань значення, котре є меншим між тим, що зараз стоїть, і відповідним значенням попереднього будинку + 1.
// на цьому етапі у нас є інформація про те, яка відстань від будинку до необхідних будівель у нас є, якщо ми будемо шукати необхідні будівлі зліва (якщо ми йдемо по вулиці зліва направо, перевіряючи будинки і решту інфи). Але перший будинок не буде перевірений, бо ми починали з другого.
3.2 Тепер робимо те саме, але починаючи з передостаннього будинку, і йдемо до першого. При цьому перевіряємо будинки зправа (якщо ми йдемо по вулиці зправа наліво).
4. На цьому етапі у нас є інфа про відстані до необхідних будівель для кожного будинку.
5. Тепер обраховуємо максимальну відстань до будівель для кожного будинку, а потім знаходимо мінімальне значення серед них.
Результатом роботи того алгоритму є такий масив з інфою про відстані
[
{
"магазин": 4,
"спортзал": 3,
"школа": 1
},
{
"магазин": 3,
"спортзал": 2,
"школа": 0
},
{
"магазин": 2,
"спортзал": 1,
"школа": 0
},
{
"магазин": 1,
"спортзал": 0,
"школа": 1
},
{
"магазин": 0,
"спортзал": 1,
"школа": 2
}
]
А індекс найкращого будинку - 3. Тобто,
магазин: 1
спортзал: 0
школа: 1
Бо максимальна відстань до будівель в нього 1.
Це ми пройшли один раз по масиву, другий раз, потім порахували максимальну відстань для кожного будинку, одночасно знаходячи мінімельне значення серед тих відстаней. Виходе N, бо із збільшенням кількості будинків необхідний час буде збільшуватися лінійно.
Хоча, там ще має значення кількість будівель, відстань до котрих ми шукаємо. Але кількість операцій так само буде лінійно зростати.