Middle+

Reklamos tinklo prototipe, reklamos vietų pardavimas organizuotas taip: pirkėjai iš anksto nurodo savo kainą, ir kiekvienam reklamos vietai atsako, ar jie pasiruošę ją įsigyti ar ne. Reikia įgyvendinti funkciją, kuri prieš parduodant reklamos vietą, lauks sutikimo arba atsisakymo iš pirkėjų su aukščiausia pasiūlymo kaina, ir tada parduos reklamos vietą pirkėjui su aukščiausia pasiūlymo kaina iš tų, kurie sutiko. Funkcijos atsakymas turi būti kuo greitesnis. Reikia grąžinti pirkėjo indeksą. Pavyzdžiai: Pirkėjai siūlo kainas 1, 5, 10 Pirkėjas su pasiūlymu 10 atsakė atsisakymu Pirkėjas su pasiūlymu 1 atsakė sutikimu // Dar laukiame, nes gali atsakyti pirkėjas su kaina 5 Pirkėjas su pasiūlymu 5 atsakė sutikimu // Pasirenkame pirkėją su pasiūlymu 5 ------------ Pirkėjai siūlo kainas 1, 5, 10 Pirkėjas su pasiūlymu 10 atsakė atsisakymu Pirkėjas su pasiūlymu 5 atsakė sutikimu // Ne laukiame atsakymo iš pirkėjo su pasiūlymu 1 - jo tikrai nepasirinksime ------------ Pirkėjai siūlo kainas 1, 2 Pirkėjas su pasiūlymu 1 atsakė atsisakymu Pirkėjas su pasiūlymu 2 atsakė atsisakymu // Nė vienas pirkėjas nepasirenkamas type Buyer = { price: number, accepts: () => Promise<boolean>, } async function bestBuyer(buyers) { const sorted = buyers.map((buyer, index) => ({buyer, index})) .sort((a, b) => a.buyer.price - b.buyer.price); const promise = sorted.map(({buyer}) => buyer.accepts()); for (let i = 0; i < sorted.length; i++) { const accepted = await promise[i]; if (accepted) { return sorted[i].index; } } if (await buyers[0].accepts()) { return 0; } return -1; }

sobes.tech AI

Atsakymas iš AI

Ваша задача — как можно быстрее определить покупателя с максимальной ценой, который согласился купить рекламное место. При этом ответы покупателей приходят асинхронно и могут быть в любом порядке.

Основная идея решения:

Отсортировать покупателей по цене по убыванию — от самого дорогого к дешевому.
Запустить параллельно все промисы accepts().
Обрабатывать ответы в порядке убывания цены, чтобы как только самый дорогой покупатель согласится, сразу вернуть его индекс.
Если самый дорогой отказался, ждать ответа следующего по цене и так далее.

Это позволит не ждать всех ответов, а вернуть результат как можно раньше.

Пример реализации:

async function bestBuyer(buyers) {
  // Сортируем по убыванию цены
  const sorted = buyers
    .map((buyer, index) => ({ buyer, index }))
    .sort((a, b) => b.buyer.price - a.buyer.price);

  // Запускаем все промисы параллельно
  const acceptPromises = sorted.map(({ buyer }) => buyer.accepts());

  for (let i = 0; i < sorted.length; i++) {
    const accepted = await acceptPromises[i];
    if (accepted) {
      // Возвращаем индекс покупателя с самой высокой ценой, который согласился
      return sorted[i].index;
    }
  }

  // Если никто не согласился
  return -1;
}

Таким образом, мы не ждём ответы покупателей с меньшей ценой, если уже получили согласие от более дорогого покупателя. Это ускоряет получение результата.

Ankstesnis Kitas