Middle+

In een prototype van een advertentienetwerk werkt de verkoop van advertentieruimtes als volgt: kopers geven vooraf hun prijs op, en voor elke advertentieruimte antwoorden ze of ze deze willen kopen of niet. Het is nodig om een functie te implementeren die, voordat een advertentieruimte wordt verkocht, de acceptatie of weigering van de kopers met de hoogste biedingen afwacht, en vervolgens de advertentieruimte verkoopt aan de koper met de hoogste bieding onder degenen die hebben geaccepteerd. Het antwoord van de functie moet zo snel mogelijk worden teruggegeven. Het moet de index van de koper retourneren. Voorbeelden: Kopers bieden prijzen 1, 5, 10 De koper met bod 10 heeft geweigerd De koper met bod 1 heeft geaccepteerd // We wachten nog, omdat de koper met bod 5 nog kan antwoorden De koper met bod 5 heeft geaccepteerd // We kiezen de koper met bod 5 ------------ Kopers bieden prijzen 1, 5, 10 De koper met bod 10 heeft geweigerd De koper met bod 5 heeft geaccepteerd // We wachten niet meer op de koper met bod 1 - hij wordt zeker niet gekozen ------------ Kopers bieden prijzen 1, 2 De koper met bod 1 heeft geweigerd De koper met bod 2 heeft geweigerd // We kiezen geen koper interface 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

Antwoord van 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;
}

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

Vorige Volgende