1 Востаннє редагувалося FakiNyan (13.02.2022 21:12:37)

Тема: Пошук квартири, від котрої найкоротший шлях до потрібних будівель

Вітаю.
Дивився сьогодні інтерв'ю, подібне до тих, котрі проводять при спробі піти працювати в гугль. В самому інтерв'ю було незрозуміло, чи рішення взагалі працює, чи ні, і якщо працює, то чи є воно оптимальним по часу та використаній пам'яті, тому запитаю у вас, як ви б це завдання вирішили.

Нехай у нас є довжелезна вулиця, а на ній будинки, котрі розміщені вздовж вулиці. Відстань між сусідніми будинками однакова. По другий бік вулиці у нас розміщені магазини, школи, спортзали, бібліотеки та подібні будівлі.

У нас є список житлових будинків, та інформація про те, чи напроти цього будинку є якась з тих будівель.

[{
  магазин: нема,
  спортзал: нема,
  школа: нема
},
{
  магазин: нема,
  спортзал: нема,
  школа: є
},
{
  магазин: нема,
  спортзал: нема,
  школа: є
},
{
  магазин: нема,
  спортзал: є,
  школа: нема
},
{
  магазин: є,
  спортзал: нема,
  школа: нема
}]

Також у нас є список з необхідними будівлями, котрі цікавлять шукача квартири, наприклад

["спортзал", "магазин", "школа"] // може бути менше

Нам необхідно знайти такий житловий будинок, від котрого матимемо найменшу відстань до необхідних будівель (окремо до кожної будівлі).

У нашому випадку нам підходе будинок під індексом 3, бо напроти нього є спортзал, а школа та магазин знаходяться напроти двох сусідніх будинків.

2

Re: Пошук квартири, від котрої найкоротший шлях до потрібних будівель

Треба все ж таки мати якийсь критерій. Чи формулу. Що краще.
Магазин і школа на відстані 1, і спортзал на відстані 4.
Чи
Магазин, школа і спортзал на відстані 2.

3

Re: Пошук квартири, від котрої найкоротший шлях до потрібних будівель

Vo_Vik написав:

Треба все ж таки мати якийсь критерій. Чи формулу. Що краще.
Магазин і школа на відстані 1, і спортзал на відстані 4.
Чи
Магазин, школа і спортзал на відстані 2.

Мінімізуємо найдовшу відстань до необхідної будівлі, другий варіант кращий.

4

Re: Пошук квартири, від котрої найкоротший шлях до потрібних будівель

Гм, я аж завис над цим. Цікава задачка.

5

Re: Пошук квартири, від котрої найкоротший шлях до потрібних будівель

А якщо школи ніде нема, то повертати нуль, чи мінімальне по інших 2х?

6

Re: Пошук квартири, від котрої найкоротший шлях до потрібних будівель

Найменше що придумав на даний момент.
Створюємо ще один масив score.
І три точки коли останній раз зустрічали об'єкт. P0-P2
Ставим їхнє початкове значення в невизначене значення. І 3 змінні s0-s2 які показують найбличу відстань до об'єкту певного типу, ставимо початкове значення в n = довжина масиву даних.
Йдемо в масиву, якщо знаходимо якийсь об'єкт, то зберігаємо його положення в відповідній змінній. Ставимо відстань у відповідній s0-s2 = 0. І повертаємось половину шляху до поперднього об'єкту цього типу. Перерховуючи скоре. Поідеї максимальне О = 4n

7

Re: Пошук квартири, від котрої найкоротший шлях до потрібних будівель

Використана память n, плюс пару змінних.

8

Re: Пошук квартири, від котрої найкоротший шлях до потрібних будівель

Vo_Vik написав:

А якщо школи ніде нема, то повертати нуль, чи мінімальне по інших 2х?

якщо школи ніде нема, але вона треба, то ми не знайшли потрібної квартири

9

Re: Пошук квартири, від котрої найкоротший шлях до потрібних будівель

Vo_Vik написав:

Найменше що придумав на даний момент.
Створюємо ще один масив score.
І три точки коли останній раз зустрічали об'єкт. P0-P2
Ставим їхнє початкове значення в невизначене значення. І 3 змінні s0-s2 які показують найбличу відстань до об'єкту певного типу, ставимо початкове значення в n = довжина масиву даних.
Йдемо в масиву, якщо знаходимо якийсь об'єкт, то зберігаємо його положення в відповідній змінній. Ставимо відстань у відповідній s0-s2 = 0. І повертаємось половину шляху до поперднього об'єкту цього типу. Перерховуючи скоре. Поідеї максимальне О = 4n

шось не дуже пойняв

10

Re: Пошук квартири, від котрої найкоротший шлях до потрібних будівель

Може трохи пізніше код напишу.

11

Re: Пошук квартири, від котрої найкоротший шлях до потрібних будівель

О і ще, чи може буте більше як одна будівля навпроти?

12

Re: Пошук квартири, від котрої найкоротший шлях до потрібних будівель

Vo_Vik написав:

О і ще, чи може буте більше як одна будівля навпроти?

Ну та, можуть бути хоч всі три разом

13

Re: Пошук квартири, від котрої найкоротший шлях до потрібних будівель

FakiNyan написав:
Vo_Vik написав:

Треба все ж таки мати якийсь критерій. Чи формулу. Що краще.
Магазин і школа на відстані 1, і спортзал на відстані 4.
Чи
Магазин, школа і спортзал на відстані 2.

Мінімізуємо найдовшу відстань до необхідної будівлі, другий варіант кращий.

Середнє арифметичне

14

Re: Пошук квартири, від котрої найкоротший шлях до потрібних будівель

Я вам тут поки шаблон зробив на js, шоб мона було бавитись і перевіряти то всьо
https://codesandbox.io/s/cocky-dubinsky-du6f6
зацініть назву посилання - cocky dubinsky, це воно автоматично так обралося

15

Re: Пошук квартири, від котрої найкоротший шлях до потрібних будівель

Написав той алгоритм, який запропонували в інтерв'ю на початку.
Код по посиланню зверху має бути, але я його ще під спойлер запихну.
Захочете своє писати, то клікайте там 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, бо із збільшенням кількості будинків необхідний час буде збільшуватися лінійно.
Хоча, там ще має значення кількість будівель, відстань до котрих ми шукаємо. Але кількість операцій так само буде лінійно зростати.

16

Re: Пошук квартири, від котрої найкоротший шлях до потрібних будівель

А чого ви тільки вліво вправо дивитесь, а не трохи далі?

17

Re: Пошук квартири, від котрої найкоротший шлях до потрібних будівель

Vo_Vik написав:

А чого ви тільки вліво вправо дивитесь, а не трохи далі?

Бо воно дивиться вліво і вправо для кожного будинку, і зберігає мінімальну відстань до будівель. Так шо коли ми йдемо зліва направо, то будинки зліва вже містять інфу про те, як далеко будівлі від них, а потім ми йдемо ще зправа наліво, і робимо те саме, і обираємо мінімальну відстань.

18

Re: Пошук квартири, від котрої найкоротший шлях до потрібних будівель

FakiNyan написав:

Я вам тут поки шаблон зробив на js, шоб мона було бавитись і перевіряти то всьо
https://codesandbox.io/s/cocky-dubinsky-du6f6
зацініть назву посилання - cocky dubinsky, це воно автоматично так обралося

це реакт чи що? як там взагалі зробити якийсь онклік івент
js використовувати для такого типу задач, це збоченство, бо js це явно не мінімальне використання потужностей і пам`яті, але потім якийсь ще фреймворк на основі js я вже не знаю як це назвати.

Подякували: leofun011

19

Re: Пошук квартири, від котрої найкоротший шлях до потрібних будівель

Vo_Vik написав:
FakiNyan написав:

Я вам тут поки шаблон зробив на js, шоб мона було бавитись і перевіряти то всьо
https://codesandbox.io/s/cocky-dubinsky-du6f6
зацініть назву посилання - cocky dubinsky, це воно автоматично так обралося

це реакт чи що? як там взагалі зробити якийсь онклік івент
js використовувати для такого типу задач, це збоченство, бо js це явно не мінімальне використання потужностей і пам`яті, але потім якийсь ще фреймворк на основі js я вже не знаю як це назвати.

Прихований текст

краще видаліть свого коментаря, бо в мене вже сусіди дивляться і сміються з вас

20

Re: Пошук квартири, від котрої найкоротший шлях до потрібних будівель

Ну кинь мені приклад найпростішого онкліка в тому сандбоксі.